JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (1): 106-114.doi: 10.6040/j.issn.1671-9352.1.2015.121

Previous Articles     Next Articles

A community mining algorithm based on core nodes expansion

LIU Jing-lian1,2, WANG Da-ling1,3, ZHAO Wei-ji2, FENG Shi1,3, ZHANG Yi-fei1,3   

  1. 1. School of Information Science and Engineering, Northeastern University, Shenyang 110819, Liaoning, China;
    2. Information Engineering College, Suihua University, Suihua 152061, Heilongjiang, China;
    3. Key Laboratory of Medical Image Computing of Ministry of Education, Northeastern University, Shenyang 110819, Liaoning, China
  • Received:2015-08-10 Online:2016-01-16 Published:2016-11-29

PDF (PC)

1208

Abstract: Based on the connections between the nodes in a network and the influence of each node, a community mining algorithm based on expansion of core nodes was proposed in this paper. The algorithm was divided into three stages. Firstly, the top-k core nodes were expanded to their neighbors until most nodes were covered in the network, that the core nodes and its neighbors formed candidate initial communities. Secondly, candidate initial communities were overlap processed, the overlap degree of each candidate initial communities pair was calculated, and the small candidate initial community was deleted if the overlap degree is greater than a given threshold. The left communities formed the initial communities. Finally, the connection degree for the overlap nodes between the initial communities and the nodes outside the communities to each candidate initial communitiy was calculated, and the node with maximum connection degree was added to the corresponding initial community. These operations were repeated until all nodes were assigned to the respective community. Experiment results showed the effectiveness and flexibility of the proposed algorithm in this paper. Compared with the GN and FN algorithm, our algorithm could divide the network accurately. Due to the overlap operation of the candidate initial communities, our algorithm was not sensitive within a certain range compared with Hub and TopLeaders algorithms.

Key words: core nodes, community structure, connection degree

CLC Number: 

  • TP399
[1] 金弟. 复杂网络社区挖掘中若干关键问题研究[D]. 长春:吉林大学计算机科学与技术学院, 2012. JIN Di. Research on community Mining in complex network[D].Changchun: College of Computer Science and Technology,Jinlin University, 2012.
[2] 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.
[3] TYLER J R, WILKINSON D M, HUBERMAN B A. E-mail as spectroscopy: automated discovery of community structure within organizations[J]. Springer Netherlands, 2003, 21(2):81-96.
[4] RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9):2658-2663.
[5] 金弟, 刘杰, 贾正雪, 等. 基于k最近邻网络的数据聚类算法[J]. 模式识别与人工智能, 2010, 23(4):546-551. JIN Di, LIU Jie, JIA Zhengxue, et al. k nearest neighbor network based data clustering algorithm[J].Pattern Recognition and Artificial Intelligence, 2010, 23(4):546-551.
[6] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133-1-066133-5.
[7] SHANG R H, BAI J, JIAO L C, et al. Community detection based on modularity and an improved genetic algorithm[J]. Physical A, 2013, 392(5):1215-1231.
[8] 刘大有, 金弟, 何东晓, 等. 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013,50(10):2140-2153. LIU Dayou, JIN Di, HE Dongxiao, et al. Community mining in complex network[J]. Journal of Computer Research and Development, 2013, 50(10):2140-2153.
[9] FORTUNATO S, BARTHELEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.
[10] PARETO V. Manual of political economy[M]. New York: A. M. Kelly,1971.
[11] 丁连红,时鹏. 网络社区发现[M]. 北京:化学工业出版社,2008: 46. DING Lianhong, SHI Peng. Network community detection[M].Beijing: Chemical Industry Press, 2008: 46.
[12] KHORASGANI R R, CHEN J Y, ZAÏANE O R. Top leaders community detection approach in information networks[C] //Proceedings of 4th SNA-KDD Workshop on Social Network Mining and Analysis.Washington, D.C.:ACM, 2010:1-9.
[13] ZHANG T, WU B. A method for local community detection by finding core nodes[C] //Proceedings of International Conference on Advances in Social Networks Analysis and Mining(ASONAM). Istanbul, Turkey: IEEE, 2012:1171-1176.
[14] PAN L, DAI C, WANG C J, et al. Overlapping community detection via leader-based local expansion in social Nnetworks[C] //Proceedings of IEEE 24th International Conference on Tools with Artificial Intelligence(ICTAI12). Washington D.C., USA: IEEE, 2012:397-404.
[15] 汪小帆,李翔,陈关荣. 网络科学导论[M]. 北京:高等教育出版社,2012:159. WANG Xiaofan, LI Xiang, CHEN Guanrong. Network science:an induction[M]. Beijing: Higher Education Press, 2012:159.
[16] 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.
[17] 张泽华, 苗夺谦, 钱进. 邻域粗糙化的启发式重叠社区扩张方法[J]. 计算机学报, 2013, 36(10):2078-2086. ZHANG Zehua, MIAO Duoqian, QIAN Jin. Detecting overlapping communities with heuristic expansion method based on rough neighborhood[J]. Chinese Journal of Computers, 2013, 36(10):2078-2086.
[18] 马兴福, 王红. 一种新的重叠社区发现算法[J]. 计算机应用研究, 2012, 29(3): 844-846. MA Xingfu, WANG Hong. New algorithm for detecting overlapping communities[J].Application Research of Computers, 2012, 29(3):844-846.
[19] 沈华伟, 程学旗, 陈海强, 等. 基于信息瓶颈的社区发现[J]. 计算机学报, 2008, 31(4): 677-686. SHEN Huawei, CHENG Xueqi, CHEN Haiqiang, et al. Information bottleneck based community detection in networks[J]. Chinese Journal of Computer, 2008, 31(4):677-686.
[20] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[21] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations——Can geographic isolation explain this unique trait?[J]. Behavioral Ecology and Sociobiology, 2003, 54(4):396-405.
[22] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.
[23] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2):026113.
[24] HE D X, LIU D Y, ZHANG W X, et al. Discovering link communities in complex networks by exploiting link dynamics[J]. Journal of Statistical Mechanics Theory and Experiment, 2012, 10(2013):P10015-1-P10015-18.
[25] 朱牧, 孟凡荣, 周勇. 基于链接密度聚类的重叠社区发现算法[J]. 计算机研究与发展, 2013, 50(15):2520-2530. ZHU Mu, MENG Fanrong, ZHOU Yong. Density-based link clustering algorithm for overlapping community detection[J].Journal of Computer Research and Development, 2013, 50(15): 2520-2530.
[26] DANON L, DÍAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics, 2005, 9(9):P09008-1-P09008-10.
[1] SUI Yun-xian, LIU Yong. Mining algorithm of E-burt structural hole based on two-step neighbor [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 59-68.
[2] HONG Pi-zheng, LIU Shi-rong, YU Hao-long, HAO Jian. Effects of simulated nitrogen deposition on soil microbial biomass and community structure in a young plantation of Castanopsis hystrix [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(5): 18-28.
[3] LIU Qi, GE Lian-sheng, QIN Feng-lin. Modeling of community structure based on P2P streaming systems [J]. J4, 2012, 47(5): 84-88.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd