计算机科学 ›› 2016, Vol. 43 ›› Issue (3): 33-37.doi: 10.11896/j.issn.1002-137X.2016.03.006
刘井莲,王大玲,赵卫绩,冯时,张一飞
LIU Jing-lian, WANG Da-ling, ZHAO Wei-ji, FENG Shi and ZHANG Yi-fei
摘要: 针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。
[1] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826 [2] Gan W Y,He N,Li D Y,et al.Community Discovery Method in Networks Based on Topological Potential[J].Journal of Software,2009,20(8):2241-2254(in Chinese) 淦文燕,赫南,李德毅,等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8):2241-2254 [3] Shen H W,Cheng X Q,Chen H Q,et al.Information bottleneck based community detection in networks[J].Chinese Journal of Computer,2008,31(4):677-686(in Chinese) 沈华伟,程学旗,陈海强,等.基于信息瓶颈的社区发现[J].计算机学报,2008,31(4):677-686 [4] Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,9(6):066133-1-066133-5 [5] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818 [6] Shen H W,Cheng X Q,Cai K,et al.Detect overlapping and hie-rarchical community structure in networks[J].Physica A,2009,388(8):1706-1712 [7] Evans T S.Clique graphs and overlapping communities[J].Journal of Statistical Mechanics Theory and Experiment,2010,2010(3):257-265 [8] Lancichinetti A,Fortunato S,Kertesz J.Detecting the overlapping and Hierarchical community structure in complex networks[J].New Journal of Physics,2008,11(15):19-44 [9] Evans T S,Lambiotte R.Line graphs,link partitions and overlapping communities[J].Physics Review E,2009,80(1):145-148 [10] Costa L F.Hub-based Community Finding.[2015-06-15].http://wenku.baidu.com/view/ca8a35e981c758f5f61f6767.html [11] Khorasgani R R,Chen J,Zaane O R.Top Leaders CommunityDetection Approach in Information Networks[C]∥ Proceedings of the 4th Workshop on Social Network Mining and Analysis.Washington DC,USA,2013 [12] Wang L,Lou T,Tang J,et al.Detecting Community Kernels in Large Social Networks[C]∥The 11th IEEE International Conference on Data Mining.Vancouver,BC,Canada,2011:784-793 [13] Coscia M,Rossetti G,Giannotti F,et al.DEMON:a local-firstdiscovery method for overlapping communities[C]∥The 18th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.Beijing,China,2012:615-623 [14] Zhang T,Wu B.A Method for Local Community Detection by Finding Core Nodes[C]∥International Conference on Advances in Social Networks Analysis and Mining.Istanbul,Turkey,2012:1171-1176 [15] Pan L,Dai C,Wang C J,et al.Overlapping Community Detection via Leader-Based Local Expansion in Social Networs[C]∥IEEE 24th International Conference on Tools with Artificial Intelligence.Athens,Greece,2012:397-404 [16] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473 [17] Nooy W D,Mrvar A,Batagelj V.Informal communication within a sawmill strike.[2015-06-15].http://vlado.fmf.uni-lj.si/pub/networks/data/esna/strike.htm [18] Zhang Z H,Miao D Q,Qian J.Detecting Overlapping Communities with Heuristic Expansion Method Based on Rough Neighborhood[J].Chinese Journal of Computers,2013,36(10):2078-2086(in Chinese) 张泽华,苗夺谦,钱进.邻域粗糙化的启发式重叠社区扩张方法[J].计算机学报,2013,36(10):2078-2086 [19] Newman M E J,Girvan M.Finding and evaluating communitystructure in networks[J].Physical Review E,2004,69(2):026113 |
No related articles found! |
|