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

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

CLC Number:

TP391

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.

Figures/Tables 2

种子选择方法	时间复杂度	种子选择方法	时间复杂度
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})$

社区扩展方法	时间复杂度	社区扩展方法	时间复杂度
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})$

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Research status of community detection based on local expansion

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 58

Related Articles 15

Metrics

Recommended 0

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network [J]. Journal on Communications, 2022, 43(8): 151-163.
[3]	Tao PENG, Wentao ZHONG, Guojun WANG, Entao LUO, Jinbo XIONG, Yining LIU, Wang Hao. Privacy-preserving precise profile matching in mobile social network [J]. Journal on Communications, 2022, 43(11): 90-103.
[4]	Zhen LIU,Na’na WANG,Xiaodong WANG,Yongqi SUN. Spectral clustering and embedding-enhanced POI recommendation in location-based social network [J]. Journal on Communications, 2020, 41(3): 197-206.
[5]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[6]	Jing CHEN,Ziyi QI. Research on social network influence maximization algorithm based on time sequential relationship [J]. Journal on Communications, 2020, 41(10): 211-221.
[7]	Junlei BI,Zhiyuan LI. Time-variant interest community based query message routing algorithm in opportunity social network [J]. Journal on Communications, 2019, 40(9): 86-94.
[8]	Fenghua LI,Zhe SUN,Ben NIU,Jin CAO,Hui LI. Privacy-preserving photo sharing framework cross different social network [J]. Journal on Communications, 2019, 40(7): 1-13.
[9]	Haiping HUANG,Kai WANG,Xiong TANG,Dongjun ZHANG. Differential privacy protection scheme based on edge betweenness model [J]. Journal on Communications, 2019, 40(5): 88-97.
[10]	Xiaomeng WANG, Binxing FANG, Hongli ZHANG, Xing WANG. TSL:predicting popularity of Facebook content based on tie strength [J]. Journal on Communications, 2019, 40(10): 1-9.
[11]	Guanghui YAN, Meng ZHANG, Hao LUO, Shikui LI, Ting LIU. Identifying vital nodes algorithm in social networks fusing higher-order information [J]. Journal on Communications, 2019, 40(10): 109-118.
[12]	Yu FU, Yihan YU, Xiaoping WU. Differential privacy protection technology and its application in big data environment [J]. Journal on Communications, 2019, 40(10): 157-168.
[13]	Lu DENG,Yan JIA,Binxing FANG,Bin ZHOU,Tao ZHANG,Xin LIU. Performance analysis of topic detection algorithms in distributed environment [J]. Journal on Communications, 2018, 39(8): 176-184.
[14]	Yong ZENG,Lingjie ZHOU,Zhongyuan JIANG,Zhihong LIU,Jianfeng MA. Security analysis of weighted network anonymity based on singular value decomposition [J]. Journal on Communications, 2018, 39(5): 23-33.
[15]	Weihao LI,Sheng DING,Jiajie MENG,Hui LI. Spatio-temporal aware privacy-preserving scheme in LBS [J]. Journal on Communications, 2018, 39(5): 134-142.