|
|
- 2015
采用模糊层次聚类的社会网络重叠社区检测算法
|
Abstract:
为了能够发现社会网络中的重叠社区以及解决重叠社区之间关系的模糊性和层次性,提出了一种基于模糊层次聚类的重叠社区检测算法(CDHC)。算法中引入了距离加权因子来计算社区间的相似度,通过模糊层次聚类来合并相似度高的社区;针对合并生成的原始社区计算社区中节点的隶属度,再将隶属度小于阈值的节点从社区中移除,从而形成最终的网络重叠社区结构。该算法不仅可以发现重叠的社区结构,还可以处理孤立节点。在Lancichinetti基准网络和真实网络上将CDHC算法与具有代表性的重叠社区发现算法CMP和LFM进行了比较, 结果表明:影响社区检测精度的主要因素是社区间的混合程度, 而网络规模和网络中社区的规模的影响并不显著;CDHC算法在小社区网络上的社区检测精度优于LFM, 在大社区网络上的社区检测精度优于CMP。CDHC算法在保持社区检测质量的同时,还具有较好的稳定性,是一种有效的社会网络重叠社区检测算法。
A detection algorithm for overlapping communities based on fuzzy hierarchical clustering, CDHC, is proposed to detect the overlapping communities and to solve the fuzzy and hierarchical relationships among communities in social networks. The algorithm first utilizes the distance weighting factors to calculate the similarity among communities, and the communities with similarity larger than a given threshold are then merged together. The membership grade of each node for the merged community is computed and nodes with membership grades less than a given threshold are removed from the community to form a structure of the final overlapping community. The algorithm can not only detect the overlapping communities, but also detect the isolated nodes. The effectiveness of the proposed algorithm is tested through comparing it with two existing overlapping community detection algorithms, CMP and LFM, on the Lancichinetti synthetic network and real network datasets. Results show that the size of network and size of communities have little effect on accuracy of detecting communities, and the main factor to affect the accuracy is the mixed degree among communities. The detection accuracy of the CDHC on social networks with small communities is higher than that of LFM, and it is better than CMP on networks with large communities. The CDHC algorithm improves the detection accuracy while its stability is good. Therefore, it can be concluded that the CDHC is an effective overlapping community detection algorithm for social networks
| [1] | ［2］TYLER J R, WILKINSON D M, HUBERMAN B A. Email as spectroscopy: automated discovery of community structure within organizations［C］∥Proceedings of First International Conference on Communities and Technologies. Dordrecht, Holland: Kluwer, 2003:81？？96. |
| [2] | ［12］EVANS T S, LAMBIOTTE R. Line graphs, link partitions and overlapping communities ［J］. Physics Review: E, 2009, 80(1): 016105. |
| [3] | ［13］AHM Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks ［J］. Nature, 2010, 466(7303): 761？？764. |
| [4] | ［14］朱牧,孟凡荣,周勇. 基于链接密度聚类的重叠社区发现算法 ［J］. 计算机研究与发展, 2013, 50(12): 2520？？2530. |
| [5] | ［11］PALLA G, DERENYI I, FARKAS I, et al. Uncovering the overlapping community structures of complex networks in nature and society ［J］. Nature, 2005, 435(7043): 814？？818. |
| [6] | ［15］LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks ［J］.New Journal of Physics, 2009, 11(3): 033015. |
| [7] | ［16］索勃,李战怀,陈群,等. 基于信息流动分析的动态社区发现方法 ［J］. 软件学报, 2014, 26(3): 547？？559. |
| [8] | SUO Bo, LI Zhanhuai, CHEN Qun, et al. Dynamic community detection based on information flow analysis ［J］. Journal of Software, 2014, 26(3): 547？？559. |
| [9] | ［17］LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms ［J］. Physics Review: E, 2008, 78(4): 046110. |
| [10] | ［18］NICASIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities ［EB／OL］. (2009？？03？？16)［2013？？12？？13］. http:∥iopscience.iop.org/1742？？5468/2009/03/p03024. |
| [11] | ［1］GIRVAN M, NEWMAN M E J. Community structure in social and biological networks ［J］. Proceedings of National Academy of Science, 2002, 9(12): 7821？？7826. |
| [12] | ［3］RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communities in networks ［J］. Proceedings of National Academy of Science, 2004, 101(9):2658？？2663. |
| [13] | ［4］NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks ［J］. Physical Review: E, 2004, 69(2): 026113. |
| [14] | ［5］NEWMAN M E J. Modularity and community structure in networks ［J］. Proceedings of National Academy of Science, 2006,103(23): 8577？？8582. |
| [15] | ［6］LEE J, GROSS S P, LEE J. Modularity optimization by conformational space annealing ［J］. Physical Review: E, 2012, 85(5):056702. |
| [16] | ［7］SHANG Ronghua, BAI Jing, JIAO Licheng, et al. Community detection based on modularity and an improved genetic algorithm ［J］. Physica: AStatistical Mechanics and Its Applications, 2013, 392(5):1215？？1231. |
| [17] | ［8］RAGHAVAN U N, ALBERT R, KUMARA S. Near linear？？time algorithm to detect community structures in large？？scale networks ［J］,Physical Review: E, 2007, 76(3): 036106. |
| [18] | ［9］SUBELJ L, BAJEC M. Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction ［J］. Physical Review: E, 2011, 83(3):036103. |
| [19] | ［10］邓小龙,王柏,吴斌,等. 基于信息熵的复杂网络社团划分建模和验证 ［J］. 计算机研究与发展, 2012, 49(4): 725？？734. |
| [20] | DENG Xiaolong, WANG Bai, WU Bin, et al. Modularity modeling and evaluation in community detecting of complex network based on information entropy ［J］. Journal of Computer Research and Development, 2012, 9(4): 725？？734. |
| [21] | ZHU Mu, MENG Fanrong, ZHOU Yong. Density？？based link clustering algorithm for overlapping community detection ［J］. Journal of Computer Research and Development, 2013, 50(12): 2520？？2530. |
