Computer Science ›› 2016, Vol. 43 ›› Issue (3): 33-37.doi: 10.11896/j.issn.1002-137X.2016.03.006

Previous Articles     Next Articles

Algorithm for Discovering Network Community with Centrality and Overlap

LIU Jing-lian, WANG Da-ling, ZHAO Wei-ji, FENG Shi and ZHANG Yi-fei   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Many social networks have central nodes and overlap nodes in more than one initial community,so a two-stage algorithm for discovering network community with centrality and overlap was proposed in this paper.In the first stage,initial communities are found.First,the top-k maximum degree nodes are chosen as candidate central nodes and the central nodes with their own neighbor nodes form separate candidate initial communities,and then the overlap degree of the candidate initial communities is computed one by one with generated initial communities.If all the overlap degrees are less than a given threshold,a new initial community is formed.In the second stage,the community division is adjusted.A concept of deviate degree is defined,and the corresponding nodes are merged to a closely linked community with maximum deviate degree.Finally community division is formed.Experimental results show that it can not only reveal the tightly-knit network communities in network with centrality,but also deal with problems of overlap initial communities effectively.Compared with existing algorithms,the algorithm in this paper is not sensitive to the prior number of candidate initial communities k,and has a high accuracy and flexibility.

Key words: Social network,Community discovery,Degree centrality,Overlap degree,Deviate degree

[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,Zaane 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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!