摘要
社区发现作为复杂社交网络中一个重要的研究方向.针对目前基于种子节点的算法在种子选取与扩展等方面的不足,提出了一种基于影响力与种子扩展的重叠社区发现算法(Influence Seeds Extension Overlapping Community Detection,简称i-SEOCD算法).首先,利用节点影响力策略找出具有紧密结构的种子社区.其次,从这些种子社区出发,计算社区邻居集节点与社区的相似度,并取出相似度超过设定阈值的节点.然后,采用优化自适应函数的策略来扩展社区.最后,对网络中的自由节点进行社区隶属划分,进而实现了整个网络的重叠社区结构挖掘.在真实社交网络和人工生成网络上实验表明,i-SEOCD算法能够准确、快速地发现复杂网络中的重叠社区结构.
Community detection is a significant research direction in the research of social networks. To improve the quality of seeds selection and expansion,we propose an influence seeds extension overlapping community detection( iSEOCD) algorithm for overlapping community detection. First,i-SEOCD uses a node influence strategy to find the seed communities with tight structures. Second,on the basis of the seed communities,we calculate the similarity among communities and their neighbor nodes. The nodes whose similarity is greater than a predefined threshold are selected. Third, the strategy of optimizing a self-adaptive function is adopted to expand the communities. Finally, the free nodes in the network are assigned to their corresponding communities in order to find out all the overlapping community structures. Experiments on the real and artificial networks show that i-SEOCD is capable of discovering overlapping communities in complex social networks efficiently.
引文
[1]Newman M E. The structure of scientific collaboration netw orks[J]. Proceedings of the National Academy of Sciences of the United States of America,2001,98(2):404
[2] Fortunato S. Community detection in graphs[J]. Physics Reports,2012,486(3):75-174.
[3]Radicchi F,Castellano C,Cecconi F,et al. Defining and identifying communities in netw orks[J]. Proceedings of theNational Academy of Sciences of the United States of America,2003,101(9):2658.
[4] Girvan M,Newman M E. Community structure in social and biological netw orks[J]. Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[5]Luxburg,Ulrike. A tutorial on spectral clustering[J]. Statistics&Computing,2007,17(4):395-416.
[6]Palla G,Derényi I,Farkas I,et al. Uncovering the overlapping community structure of complex netw orks in nature and society[J]. Nature,2005,435(7043):814.
[7] Kim Y,Jeong H. Map equation for link communities[J].Physical Review E,2011,84(2):026110.
[8] Xie J,Szymanski B K. Towards linear time overlapping community detection in social netw orks[A]. Pacific-Asia Conference on Know ledge Discovery and Data M ining[C]. Springer,Berlin,Heidelberg,2012. 25-36.
[9]Lancichinetti A,Fortunato S,Kertész J. Detecting the overlapping and hierarchical community structure in complex netw orks[J]. New Journal of Physics, 2009, 11(3):033015.
[10] Coscia M,Rossetti G,Giannotti F,et al. Demon:a localfirst discovery method for overlapping communities[A].Proceedings of the 18th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining[C].ACM,2012. 615-623.
[11]Su Y,Wang B,Zhang X. A seed-expanding method based on random w alks for community detection in netw orks w ith ambiguous community structures[J]. Scientific Reports,2017,7:41830.
[12] Chen Q,Wu T T,Fang M. Detecting local community structures in complex netw orks based on local degree central nodes[J]. Physica A:Statistical M echanics and Its Applications,2013,392(3):529-537.
[13]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.
[14]Cravino N,Figueira. Community detection by local influence[A]. Advances in Information Systems and Technologies[M]. Springer,Berlin,Heidelberg,2013. 193-200.
[15] Wang X,Liu G,Li J. Overlapping community detection based on structural centrality in complex netw orks[J].IEEE Access,2017,5:25258-25269.
[16]Jaccard P. Etude de la distribution florale dans une portion des Alpes et du Jura[J]. Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.
[17]Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research,1977,33(4):452-473.
[18] Lusseau D,Schneider K,Boisseau O J,et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[19]Newman M E J,Girvan M. Finding and evaluating community structure in netw orks[J]. Physical review E,2004,69(2):026113.
[20]Gleiser P M,Danon L. Community structure in jazz[J].Advances in Complex Systems,2003,6(04):565-573.
[21] Leskovec J,Kleinberg J,Faloutsos C. Graph evolution:densification and shrinking diameters[J]. ACM Transactions on Know ledge Discovery from Data(TKDD),2007,1(1):2.
[22] Lancichinetti A,Fortunato S,Radicchi F. Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[23]Shen H,Cheng X,Cai K,et al. Detect overlapping and hierarchical community structure in netw orks[J]. Physica A:Statistical M echanics and Its Applications,2009,388(8):1706-1712.
[24]Danon L,Diaz-Guilera A,Duch J,et al. Comparing community structure identification[J]. Journal of Statistical Mechanics:Theory and Experiment,2005,2005(09):P09008.
