一种基于核心节点扩展的社区挖掘算法

doi:10.6040/j.issn.1671-9352.1.2015.121

山东大学学报（理学版） ›› 2016, Vol. 51 ›› Issue (1): 106-114.doi: 10.6040/j.issn.1671-9352.1.2015.121

一种基于核心节点扩展的社区挖掘算法

刘井莲^1,2,王大玲^1,3,赵卫绩²,冯时^1,3,张一飞^1,3

1. 东北大学信息科学与工程学院, 辽宁沈阳 110819;2. 绥化学院信息工程学院, 黑龙江绥化 152061;3.东北大学医学影像计算教育部重点实验室, 辽宁沈阳 110819

收稿日期:2015-08-10 出版日期:2016-01-16 发布日期:2016-11-29
作者简介:刘井莲(1980— ),女,博士研究生,讲师,研究方向为社会网络分析与社会媒体挖掘. E-mail:datamining@163.com
基金资助:
国家自然科学基金资助项目(61370074、61402091)

A community mining algorithm based on core nodes expansion

LIU Jing-lian^1,2, WANG Da-ling^1,3, ZHAO Wei-ji², FENG Shi^1,3, ZHANG Yi-fei^1,3

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

摘要/Abstract

摘要： 在充分考虑网络中节点间的连接关系和节点的影响力的基础上,提出一种基于核心节点扩展的社区挖掘算法。算法分为三个阶段:首先,网络中的前k个核心节点逐层向外扩展,直至覆盖网络中大部分节点,各核心节点与其多层邻居节点组成候选初始社区;然后,对候选初始社区进行重叠处理,计算候选初始社区两两之间的重叠度,将重叠度高于阈值的两个社区中相对小的社区删掉,形成初始社区;最后,计算初始社区间的重叠节点和不在初始社区中的节点到各个初始社区的连接度,将连接度最大的节点加入相应社区,不断迭代,直到网络中所有节点都划入到相应社区内,形成最终社区结构。试验结果说明了本文方法的有效性和灵活性,相比GN算法和FN算法,能够实现准确的网络划分;相比Hub算法和TopLeaders算法,由于对候选初始社区间进行了重叠处理,对预置的社区数量k在一定范围内不敏感。

关键词: 社区结构, 核心节点, 连接度

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

中图分类号:

TP399

刘井莲,王大玲,赵卫绩,冯时,张一飞. 一种基于核心节点扩展的社区挖掘算法[J]. 山东大学学报（理学版）, 2016, 51(1): 106-114.

LIU Jing-lian, WANG Da-ling, ZHAO Wei-ji, FENG Shi, ZHANG Yi-fei. A community mining algorithm based on core nodes expansion[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(1): 106-114.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于核心节点扩展的社区挖掘算法

A community mining algorithm based on core nodes expansion

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

多维度评价

本文评价

推荐阅读 0