南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 751–.

• • 上一篇    下一篇

一种基于加权共同邻居相似度的局部社区发现算法

赵卫绩1,2,张凤斌1*,刘井莲2   

  • 出版日期:2018-04-30
  • 作者简介:1.哈尔滨理工大学计算机科学与技术学院,哈尔滨,150080;2.绥化学院信息工程学院,绥化,152061
  • 基金资助:
    基金项目:国家自然科学基金(61172168),绥化学院基本科研业务费(2017-XKYYWF-016) 收稿日期:2018-05-20 *通讯联系人,E-mail:zhangfb@hrbust.edu.cn

A novel local community detection algorithm based on common neighbors similarity measurement with weighted neighbor nodes

Zhao Weiji1,2,Zhang Fengbin1*,Liu Jinglian2   

  • Online:2018-04-30
  • About author:1.School of Computer Science and Technology,Harbin University of Science and Technology,Harbin,150080,China; 2.School of Information Engineering,Suihua University,Suihua,152061,China

摘要: 传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模. 挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义. 目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法. 针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法. 首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验. 实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.

Abstract: Community structure is a common property in many networks. Traditional community detection algorithms aim at discovering all communities in a network and the running time of these algorithms usually depends on the size of the entire network. For big networks,it is difficult to discover their global community structure due to the high time complexity. Local community detection surges as a kind of methods which start with a given node that is already known to be in the target community,and the goal is to uncover the remaining nodes in the community. This kind of algorithms usually starts from a given node and gradually expands outward without requiring global network structure. The running time of these local communities detection algorithms depends on the size of the community rather than that of the entire network. Thus local community detection has important application significance in big network analysis tasks. So far the research of local community detection has drawn a lot of attention and many algorithms have been proposed. Most of the existing local community detection algorithms require users to specify the parameter values manually and have low accuracy. For solving this problem,a new local community detection algorithm is proposed in this paper. Firstly,we propose a new common neighbors based similarity measurement with weighted neighbor nodes,which is employed to calculate the similarity between two nodes in a network. Secondly,based on this similarity measurement,a new local community quality metric is given. We discover a local community of the given node by iteratively adding a node from shell node set to the target community which has the largest embedded degree with the current local community,while ensuring the gain of the current local community quality metric is not negative. Extensive experimental results on both synthetic and real-world network datasets show that the proposed algorithm is highly effective at local community detection compared with Clauset,LWP and GMAC algorithms.

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!