基于局部扩展的社区发现研究现状

doi:10.11959/j.issn.1000-436x.2019013

摘要/Abstract

摘要：

社区发现能有效挖掘网络的特性以及隐藏的信息。局部扩展是社区发现常用的一种方法，该方法大体上可以分为种子的选择和局部扩展两部分。因此，为了分析现有方法的优劣以及适用场合，对种子的选择、局部扩展以及评价指标等方法进行概括、比较和分析，总结了基于局部扩展的社区发现的应用以及研究难点。最后，对基于局部扩展的社区发现的研究方向进行了展望。

关键词: 社会网络, 社区发现, 种子选取, 局部扩展

Abstract:

Community detection can effectively mine the characteristics of the network as well as the hidden information.Local expansion is a commonly used method of community detection,and it can be divided into two steps:the selection of seeds and the local expansion.Therefore,in order to analyze the advantages and disadvantages of the existing methods and their application,these methods about the selection of seeds,local expansion and evaluation were summarized,compared and analyzed.Then,the application and the research difficulties of community detection based on local extension were summarized.Finally,the research directions of community detection based on local expansion were given.

Key words: social network, community detection, selection of seeds, local expansion

中图分类号:

TP391

史艳翠,王嫄,赵青,张贤坤. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019, 40(1): 149-162.

Yancui SHI,Yuan WANG,Qing ZHAO,Xiankun ZHANG. Research status of community detection based on local expansion[J]. Journal on Communications, 2019, 40(1): 149-162.

图/表 2

表1

种子选择方法的时间复杂度的对比"

种子选择方法	时间复杂度	种子选择方法	时间复杂度
LFM ^[5]	O(K)	LMMC ^[2]	$O (N_{n U} N_{U})$
LTE ^[6]	O(K)	LMC ^[21]	$O (N_{n U} N_{U})$
IS ^[7]	O(K)	LCC ^[22]	$O (N_{U}^{2} + K l o g (N_{U}))$
RaRe ^[7]	$O (\frac{N_{U}^{2}}{t} \log N_{U})$	RWA ^[23]	$O (N_{n U} N_{U} + N_{n U} K)$
仿团集^[11]	$O (N_{U} ⌈ \log N_{U} ⌉)$	LCD-NJ ^[24]	$O (N_{n k U})$
LA ^[12]	$O (N_{U} l o g N_{U} + K N_{n U})$	IN-LCD ^[25]	$O (N_{n k U} l o g N_{n k U})$
OClu-detect ^[13]	$O (N_{U} l o g N_{U})$	Graclus centers ^[16]	$O (⌈ \log K ⌉ (N_{v c} + N_{ε c}))$
WM ^[14]	$O (N_{U}^{2})$	GCE ^[26]	$O (3^{N_{U} / 3})$
SLEM ^[15]	$O (K N_{U})$	派系^[27]	$O (3^{N_{U} / 3})$
spread hubs ^[16]	$O (N_{v c})$	k-回路^[31]	$O ((N_{U} + N_{E}) (K + 1))$
OCDW ^[17]	$O (N_{U} + K N_{C U})$	ITEM ^[4]	$O (N_{n U} N_{E} + p T K)$
TRACED ^[18]	$O (N_{E})$	ARISEN ^[32]	$O ((R + 2) T)$
LMD ^[19]	$O (N_{n U} N_{U})$	NewLCD ^[33]	$O (N_{n U} K)$
LP1 ^[20]	$O (N_{n U} N_{U})$	核心区域 ^[34]	$O (N_{U} l o g N_{U} + K k_{C} N_{n U})$

表1

表2

局部扩展方法的时间复杂度对比"

社区扩展方法	时间复杂度	社区扩展方法	时间复杂度
OClu-detect ^[13]	O(K N_nU)	LCDA ^[19]	O(N_UN_nU)
LFM in ^[5]	$O (K N_{C U}^{2} + N_{U}_{} N_{n U})$	HMSC ^[14]	$O (K \frac{2^{b} \log (N_{E})}{β} + N_{U}^{2} + K K_{Z} \log N_{U})$
贪心扩展种子算法 ^[34]	$O (K N_{C U}^{2} + N_{U}_{} N_{n U})$	LA ^[12]	O(K N_E)
GCE ^[26]	O(N_UN_nU)	LCE ^[22]	$O (K N_{C U}^{2} + N_{U}_{} N_{n U})$
OCDW ^[17]	O(K N_E)	RWA ^[23]	O(K log N_U)
LCD-NJ ^[24]	O(K N_lE)	PPKC ^[8]	O(N_U log N_CU)
IN-LCD ^[25]	O(K N_lE)	NISE ^[16]	$O (\sum_{i}^{K} links (C_{i}, U_{C}))$
改进的GCE ^[11]	O(N_UN_nU)	TRACED ^[18]	$O (K N_{C U}^{2} + N_{U}_{} N_{n U})$
CLFMw ^[28]	O(K N_E)	RaRe ^[7]	O(K N_E)
LTE ^[6]	O(N_UN_nU)	IS ^[7]	O(K N_U log N_U)
CM算法 ^[31]	O(K N_E)	IS²[12]	O(K N_nU log N_nU)
改进的CM算法 ^[27]	O(K N_E)	ITEM ^[4]	O(m p N_nE)
NewLCD ^[33]	O(N_UN_nU)	SLEM ^[15]	$O (K N_{C U}^{2} + N_{U}_{} N_{n U})$

表2

参考文献 58

[1]	李建华, 汪晓锋, 吴鹏 . 基于局部优化的社区发现方法研究现状[J]. 中国科学院院刊, 2015,30(002): 238-247.
	LI J H , WANG X F , WU P . Research status of community discovery methods based on local optimization[J]. Bulletin of Chinese Academy of Sciences, 2015,30(002): 238-247.
[2]	YIN H , BENSON A R , LESKOVEC J ,et al. Local higher-order graph clustering[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 555-564.
[3]	ZENG J P , YU H F . A study of graph partitioning schemes for parallel graph community detection[J]. Parallel Computing, 2016,58(C): 131-139.
[4]	SHANG C X , FENG S Z , ZHAO Z Y ,et al. Efficiently detecting overlapping communities using seeding and semi-supervised learning[J]. International Journal of Machine Learning and Cybernetics, 2017,8(2): 455-468.
[5]	LANCICHINETTI A , FORTUNATO S , KERTESZ J . Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009,11(3): 1-20.
[6]	HUANG J B , SUN H L , LIU Y G ,et al. Towards online multiresolution community detection in large-scale networks[J]. Plos One, 2011,6(8): 1-11.
[7]	BAUMES J , GOLDBERG M , KRISHNAMOORTHY M ,et al. Finding communities by clustering a graph into overlapping subgraphs[C]// IADIS International Conference on Applied Computing. 2005: 97-104.
[8]	NATHAN E , ZAKRZEWSKA A , RIEDY J ,et al. Local community detection in dynamic graphs using personalized centrality[J]. Algorithms, 2017,10(3): 1-26.
[9]	JEUB L G S , MAHONEY M W , MUCHA P J ,et al. A local perspective on community structure in multilayer networks[J]. Network Science, 2017,5(2): 144-163.
[10]	BAE S H , HALPERIN D , WEST J ,et al. Scalable and efficient flow-based community detection for large-scale graph analysis[J]. ACM Transactions on Knowledge Discovery from Data, 2017,11(3): 1-29.
[11]	龙渊 . 基于局部扩充的重叠社区发现算法研究和改进[D]. 重庆:重庆大学, 2016.
	LONG Y . Study and improvement of overlapping community discovery based on local expansion[D]. Chongqing:Chongqing University, 2016
[12]	BAUMES J , GOLDBERG M , MAGDON-ISMAIL M . Efficient identification of overlapping communities[C]// International Conference on Intelligence and Security Informatics. 2005: 27-36.
[13]	国琳, 左万利, 彭涛 . 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016,44(3): 587-594.
	GUO L , ZUO W L , PENG T . Overlapping community detection and dynamic group evolution analysis based on the degree of membership in social network[J]. ACTA Electronica Sinica, 2016,44(3): 587-594.
[14]	YANG J X , ZHANG X D . Finding overlapping communities using seed set[J]. Physica A Statistical Mechanics ＆ Its Applications, 2017,467: 96-106.
[15]	陈俊宇, 周刚, 南煜 ,等. 一种半监督的局部扩展式重叠社区发现方法[J]. 计算机研究与发展, 2016,53(6): 1376-1388.
	CHEN J Y , ZHOU G , NAN Y ,et al. Semi-supervised local expansion method for overlapping community detection[J]. Journal of Computer Research and Development, 2016,53(6): 1376-1388.
[16]	WHANG J J , GLEICH D F , DHILLON I S . Overlapping community detection using neighborhood-inflated seed expansion[J]. IEEE Transactions on Knowledge and Data Engineering, 2016,28(5): 1272-1284.
[17]	杨贵, 郑文萍, 王文剑 ,等. 一种加权稠密子图社区发现算法[J]. 软件学报, 2017,28(11): 3103-3114.
	YANG G , ZHENG W P , WANG W J ,et al. Community detection algorithm based on weighted dense subgraphs[J]. Journal of Software, 2017,28(11): 3103-3114.
[18]	CAO J P , WANG S Z , WANG H . Detecting communities on topic of transportation with sparse crowd annotations[J]. IEEE Transactions on Intelligent Transportation Systems, 2017,18(4): 1017-1022.
[19]	CHEN Q , WU T T , FANG M . Detecting local community structures in complex networks based on local;degree central nodes[J]. Physica A Statistical Mechanics ＆ Its Applications, 2013,392(3): 529-537.
[20]	DESHPANDE P , RAVINDRAN B . MCEIL:An improved scoring function for overlapping community detection using seed expansion methods[C]// IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2017: 652-659.
[21]	GLEICH D F , SESHADHRI C . Vertex neighborhoods,low conductance cuts,and good seeds for local community methods[C]// 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 2012: 597-605.
[22]	WANG X F , LIU G S , LI J H ,et al. Locating structural centers:a density-based clustering method for community detection[J]. Plos One, 2017,12(1): 1-23.
[23]	SU Y S , WANG B J , ZHANG X Y . A seed-expanding method based on random walks for community detection in networks with ambiguous community structures[J]. Scientific Reports, 2017,7: 1-10.
[24]	汪涛, 刘阳, 席耀一 . 一种基于核心节点跳转的局部社区发现算法[J]. 上海交通大学学报, 2015,49(12): 1809-1816.
	WANG T , LIU Y , XI Y Y . Detection of local community structure of complex networks based on core nodes jumping[J]. Journal of Shanghai Jiaotong University, 2015,49(12): 1809-1816.
[25]	常振超, 陈鸿昶, 黄瑞阳 ,等. 采用影响力节点集扩展的局部社团检测[J]. 西安交通大学学报, 2016,50(4): 41-47.
	CHANG Z C , CHEN H C , HUANG R Y ,et al. A local community detection method using expansion of influential nodes set[J]. Journal of Xian Jiaotong University, 2016,50(4): 41-47.
[26]	LEE C , REID F , MCDAID A ,et al. Detecting highly overlapping community structure by greedy clique expansion[C]// 4th International Workshop on Social Network Mining and Analysis (SNA-KDD). 2010.
[27]	SHANG M S , CHEN D B , ZHOU T . Detecting overlapping communities based on community cores in complex networks[J]. Chinese Physics Letters, 2010,27(5): 1-4.
[28]	李婕, 王兴伟, 郭静 ,等. 面向移动通信网络的局部扩张群组构造方法[J]. 东北大学学报(自然科学版), 2017,38(12): 1691-1695.
	LI J , WANG X W , GUO J ,et al. Clique percolation based local fitness method for user clustering in telecommunication network[J]. Journal of Northeastern University, 2017,38(12): 1691-1695.
[29]	KUMAR P , GUPTA S , BHASKER B . An upper approximation based community detection algorithm for complex networks[J]. Decision Support Systems, 2017,96: 103-118.
[30]	BECKER E , ROBISSON B , CHAPPLE C E ,et al. Multifunctional proteins revealed by overlapping clustering in protein interaction network[J]. Bioinformatics, 2011,28(1): 84-90.
[31]	肖觅, 孟祥武, 史艳翠 . 一种基于移动用户行为的回路融合社区发现算法[J]. 电子与信息学报, 2012,34(10): 2369-2374.
	XIAO M , MENG X W , SHI Y C . A circuits merging community discovery algorithm based on mobile user behaviors[J]. Journal of Electronics ＆ Information Technology, 2012,34(10): 2369-2374.
[32]	WILDER B , IMMORLICA N , RICE E ,et al. Influence maximization with an unknown network by exploiting community structure[C]// The 3rd International Workshop on Social Influence Analysis. 2017: 2-7.
[33]	ZHOU Y , SUN G B , XING Y ,et al. Local community detection algorithm based on minimal cluster[J]. Applied Computational Intelligence and Soft Computing, 2016,2016(2): 1-11.
[34]	张忠正 . 基于核心区域扩展的重叠社区发现算法研究[D]. 北京:北京理工大学, 2016.
	ZHANG Z Z . Overlapping community detection based on core region expansion[D]. Beijing:Beijing Institute of Technology, 2016
[35]	黄立威, 李彩萍, 张海粟 ,等. 一种基于因子图模型的半监督社区发现方法[J]. 自动化学报, 2016,42(10): 1520-1531.
	HUANG L W , LI C P , ZHANG H L ,et al. A semi-supervised community detection method based on factor graph model[J]. ACTA Automatica Sinica, 2016,42(10): 1520-1531.
[36]	徐建民, 李腾飞, 吴树芳 . 一种基于用户交互行为的微博社区发现方法[J]. 河北大学学报 (自然科学版), 2016,36(2): 189-196.
	XU J M , LI T F , WU S F . A micro-blogging community discovery method based on user’s interactions[J]. Journal of Heibei University (Natural Science Edition), 2016,36(2): 189-196.
[37]	NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks[J]. Physical review E, 2004,69(2): 1-16.
[38]	陈晶, 万云 . 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017,38(2): 25-33.
	CHEN J , WAN Y . Research on label propagation algorithm based on modularity maximization in the social network[J]. Journal on Communications, 2017,38(2): 25-33.
[39]	邓琨, 李文平, 余法红 ,等. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017,38(2): 53-66.
	DENG K , LI W P , YU F H ,et al. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on Communications, 2017,38(2): 25-33.
[40]	陈羽中, 施松, 朱伟平 ,等. 一种基于邻域跟随关系的增量社区发现算法[J]. 计算机学报, 2017,40(3): 570-583.
	CHEN Y Z , SHI S , ZHU W P ,et al. An incremental community discovery algorithm based on neighborhood following relationship[J]. Chinese Journal of Computers, 2017,40(3): 570-583.
[41]	LIAKOS P , NTOULAS A , DELIS A . Scalable link community detection:a local dispersion-aware approach[C]// 2016 IEEE International Conference on Big Data (Big Data). 2016: 716-725.
[42]	LI L , FAN K , ZHANG Z ,et al. Community detection algorithm based on local expansion k-means[J]. Neural Network World, 2016,26(6): 589-605.
[43]	WEN X Y , CHEN W N , LIN Y ,et al. A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J]. IEEE Transactions on Evolutionary Computation, 2017,21(3): 363-377.
[44]	郭弘毅, 刘功申, 苏波 ,等. 融合社区结构和兴趣聚类的协同过滤推荐算法[J]. 计算机研究与发展, 2016,53(8): 1664-1672.
	GUO H Y , LIU G S , SU B ,et al. Collaborative filtering recommendation algorithm combining community structure and interest clusters[J]. Journal of Computer Research and Development, 2016,53(8): 1664-1672.
[45]	刘宇, 吴斌, 曾雪琳 ,等. 一种基于社交网络社区的组推荐框架[J]. 电子与信息学报, 2016,38(9): 2150-2157.
	LIU Y , WU B , ZENG X L ,et al. A group recommendation framework based on social network community[J]. Journal of Electronics ＆ Information Technology, 2016,38(9): 2150-2157.
[46]	BOUCHARD M , WESTLAKE B G . Community detection in online criminal networks and its implications for research co-offending (forthcoming)[M]. Analysis of Criminal Networks. Montreal: The University Press, 2017.
[47]	丁晟春, 王楠, 吴靓婵媛 . 基于关键词共现和社区发现的微博热点主题识别研究[J]. 现代情报, 2018,38(3): 10-18.
	DING S C , WANG N , WU J C Y . Hot topic detection of Weibo based on keyword co-occurrence and community discovery[J]. Journal of Modern Information, 2018,38(3): 10-18.
[48]	HOSHI M , TACHIMORI Y . Evaluation of community detection of the networks derived from clinical information and its application to patient classification[J]. Japan Journal of Medical Informatics, 2014,34(1): 3-15.
[49]	MALL R , ULLAH E , KUNJI K ,et al. An adaptive refinement for community detection methods for disease module identification in biological networks using novel metric based on connectivity,conductance ＆ modularity[C]// IEEE International Conference on Bioinformatics and Biomedicine. 2017: 2282-2284.
[50]	HARENBERG S , SEAY R G , RANSHOUS S ,et al. Memory-efficient query-driven community detection with application to complex disease associations[J]. SDM, 2016,15(1): 65-79.
[51]	GARCIA J O , ASHOURVAN A , MULDOON S F ,et al. Applications of community detection techniques to brain graphs:algorithmic considerations and implications for neural function[J]. Proceedings of the IEEE, 2018,106(5): 846-867.
[52]	吴哲 . 基于局部社区发现的微信朋友圈信息流广告推荐算法研究[D]. 浙江:浙江工商大学, 2016.
	WU Z . Local method for WeChat friendship flow advertisement recommendation algorithm[D]. Zhejiang:Zhejiang Gongshang University, 2016.
[53]	胡旭 . 基于微博平台企业舆情影响力最大化研究[D]. 天津：天津大学, 2017.
	HU X . Influence maximization of enterprise public opinion based on Weibo platform[D]. Tianjin:Tianjin University, 2017.
[54]	李国良, 楚娅萍, 冯建华 ,等. 多社交网络的影响力最大化分析[J]. 计算机学报, 2016,39(4): 643-656.
	LI G L , CHU Y P , FENG J H ,et al. Influence maximization on multiple social networks[J]. Chinese Journal of Computers, 2016,39(4): 643-656.
[55]	马茜, 马军 . 在影响力最大化问题中寻找种子节点的替补节点[J]. 计算机学报, 2017,40(3): 674-686.
	MA Q , MA J . Discovering the substitute for the seeds in influence maximization problem[J]. Chinese Journal of Computers, 2017,40(3): 674-686.
[56]	TONG G M , WU W L , TANG S J ,et al. Adaptive influence maximization in dynamic social networks[J]. IEEE/ACM Transactions on Networking, 2017,25(1): 112-125.
[57]	INTERDONATO R , TAGARELLI A . Personalized recommendation of Points-of-Interest based on multilayer local community detection[C]// International Conference on Social Informatics. 2017: 552-571.
[58]	史艳翠, 杨巨成, 陈亚瑞 ,等. 基于移动数据的用户间影响力计算方法[J]. 华中科技大学学报(自然科学版), 2017,45(7): 110-114.
	SHI Y C , YANG J C , CHEN Y R ,et al. Calculation method of influence between users based on mobile data[J]. Journal of Huazhong University of Science ＆ Technology (Natural Science Edition), 2017,45(7): 110-114.