南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 751.
赵卫绩1,2,张凤斌1*,刘井莲2
Zhao Weiji1,2,Zhang Fengbin1*,Liu Jinglian2
摘要: 传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模. 挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义. 目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法. 针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法. 首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验. 实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.
[1] 刘 阳,季新生,刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法. 电子与信息学报,2014,36(12):2809-2815.(Liu Y,Ji X S,Liu C Y. Detecting local community structure based on the identification of boundary nodes in complex networks. Journal of Electronic & Information Technology,2014,36(12):2809-2815.) [2] Girvan M,Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826. [3] Tyler J R,Wilkinson D M,Huberman B A. E-Mail as spectroscopy:Automated discovery of community structure within organizations. The Information Society,2005,21(2):143-153. [4] Newman M E J. Modularity and community structure in networks. Proceedings of the National Academy of Science of the United States of America,2006,103(23):8577-8582. [5] Shang R H,Bai J,Jiao L C,et al. Community detection based on modularity and an improved genetic algorithm. Physica A:Statistical Mechanics and its Applications,2013,392(5):1215-1231. [6] Barber M J,Clark J W. Detecting network communities by propagating labels under constrains. Physical Review E,2009,80(2):026129. [7] Liu X,Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A:Statistical Mechanics and its Applications,2010,389(7):1493-1500. [8] Fortunato S. Community detection in graphs. Physics Reports,2010,486(3-5):75-174. [9] Bagrow J P,Bollt E M. Local method for detecting communities. Physical Review E,2015,72(4 Pt 2):04618. [10] Clauset A. Finding local community structure in networks. Physical Review E,2005,72(2):026132. [11] Luo F,Wang J Z,Promislow E. Exploring local community structures in large networks. Web Intelligence and Agent Systems,2008,6(4):387-400. [12] Chen Q,Wu T T,Fang M. Detecting local community structures in complex networks based on local degree central nodes. Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537. [13] Li Y X,He K,Bindel D,et al. Uncovering the small community structure in large networks:A local spectral approach ∥ Gangemi A,Leonardi S,Panconesi A. The 24th International Conference on World Wide Web. Florence,Italy:ACM,2015:658-668. [14] Ma L H,Huang H,He Q M,et al. GMAC:A seed-insensitive approach to local community detection ∥ Bellatreche L,Mohania M K. Proceedings of the 15th International Conference on Data Warehousing and Knowledge Discovery. Springer Berlin Heidelberg,2013:297-308. [15] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research,1977,33(4):452-473. [16] Lancichinetti A,Fortunato S,Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E,2008,78(4):046110. |
No related articles found! |
|