《计算机应用研究》|Application Research of Computers

基于连边距离矩阵的重叠社区发现

Overlapping community detecting based on link distance matrix

免费全文下载 (已被下载 次)  
获取PDF全文
作者 张建国,黄瑞阳,李鹏,何赞园,邵文超,常振超
机构 国家数字交换系统工程技术研究中心,郑州 450002
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2017)09-2748-05
DOI 10.3969/j.issn.1001-3695.2017.09.041
摘要 现有重叠社团发现算法大多直接从相邻连边的相似性出发,不能有效利用网络的多层连边信息,基于此提出了一种基于连边距离矩阵的重叠社区发现算法LDM。首先结合连边—节点—连边随机游走模型,以实现多级连边信息的有效利用;借助模糊聚类方法,处理连边距离矩阵以获取连边社区;最后根据扩展模块度调整和优化重叠社区结构。在人工网络和真实网络上的实验结果表明,所提算法能够有效提高重叠社区发现算法的准确度。
关键词 复杂网络;重叠社团发现;连边距离;随机游走
基金项目 国家“973”计划资助项目(2012CB315901,2012CB315905)
国家自然科学基金创新群体项目(61521003)
本文URL http://www.arocmag.com/article/01-2017-09-041.html
英文标题 Overlapping community detecting based on link distance matrix
作者英文名 Zhang Jianguo, Huang Ruiyang, Li Peng, He Zanyuan, Shao Wenchao, Chang Zhenchao
机构英文名 NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,Zhengzhou450002,China
英文摘要 Most overlapping community detecting algorithms ignored the similarity of non-adjacent edges, which reduced the accuracy of overlapping community detection. This paper proposed an overlapping community detecting algorithm based on link distance matrix(LDM). Firstly, based on the link-node-link random walk model and superposed random walk index, this paper proposed a method to calculate the similarity of the non-adjacent edges in the network, which improved the utility of edge information. Then it used the fuzzy clustering methods to deal with link distance matrix to obtain the edge community structure. Finally it adjusted and optimized the overlapping community structure of the network according to the extension module degree function. Compared with existing algorithms in LFR artificial networks and real networks, the experiment results show that the LDM algorithm can effectively improve the accuracy of overlapping community detection algorithm.
英文关键词 complex network; overlapping community detecting; link distance; random walk
参考文献 查看稿件参考文献
  [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] Newman M E J. The structure and function of complex networks[J] . SIAM Review, 2003, 45(2):167-256.
[3] Aggarwal C C. An introduction to social Network Data Analytics[M] //Social Network Data Analytics. Berlin:Springer, 2011:1-15.
[4] Fortunato S. Community detection in graphs[J] . Physics Reports, 2009, 486(3-5):75-174.
[5] Newman M E J. Modularity and community structure in networks[J] . Proceedings of the National Academy of Sciences of the USA, 2006, 103(23):8577-8582.
[6] Yang J, Leskovec J. Community-affiliation graph model for overlapping network community detection[C] //Proc of the 12th International Conference on Data Mining. [S. l. ] :IEEE Press, 2012:1170-1175.
[7] Wang Wenjun, Liu Dong, Liu Xiao, et al. Fuzzy overlapping community detection based on local random walk and multidimensional scaling[J] . Physica A:Statistical Mechanics and its Applications, 2013, 392(24):6578-6586.
[8] He Dongxiao, Liu Dayou, Zhang Weixiong, et al. Discovering link communities in complex networks by exploiting link dynamics[J] . Journal of Statistical Mechanics:Theory and Experiment, 2012, 2012(10):P10015.
[9] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks[J] . Nature, 2010, 466(7307):761-764.
[10] Huang Lan, Wang Guishen, Wang Yan, et al. Link clustering with extended link similarity and EQ evaluation division[J] . PLoS ONE, 2013, 8(6):e66005.
[11] Shi Chuan, Cai Yanan, Fu Di, et al. A link clustering based overlapping community detection algorithm[J] . Data & Knowledge Engineering, 2013, 87(9):394-404.
[12] Dickinson B, Valyou B, Hu W. A genetic algorithm for identifying overlapping communities in social networks using an optimized search space[J] . Social Networking, 2013, 2(4):193-201.
[13] 王琦, 温志平. 一种基于多维遗传算法的重叠社区发现方法[J] . 计算机应用研究, 2016, 33(12):3543-3546.
[14] Lim S, Ryu S, Kwon S, et al. LinkSCAN*:overlapping community detection using the link-space transformation[C] //Proc of the 30th International Conference on Data Engineering. [S. l. ] :IEEE Press, 2014:292-303.
[15] Shen Huawei, Cheng Xueqi, Cai Kai, et al. Detect overlapping and hierarchical community structure in networks[J] . Physica A:Statistical Mechanics and Its Applications, 2009, 388(8):1706-1712.
[16] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J] . New Journal of Physics, 2009, 11(3):033015.
[17] Chen Duanbing, Shang Mingsheng, Lv Zehua, et al. Detecting overlapping communities of weighted networks via a local algorithm[J] . Physica A:Statistical Mechanics and Its Applications, 2010, 389(19):4177- 4187.
[18] Dunn J C. A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters[J] . Journal of Cybernetics, 1973, 3(3):32-57.
[19] Bezdek J C. Pattern recognition with fuzzy objective function algorithms[M] . Nonwell:Kluwer Academic Publishers, 1981.
[20] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J] . Physical Review E, 2008, 78(4):046110.
[21] Zachary W W. An information flow model for conflict and fission in small groups[J] . Journal of Anthropological Research, 1977, 33(4):452-473.
[22] Lusseau D. The emergent properties of a dolphin social network[J] . Proceedings of the Royal Society of London B:Biological Sciences, 2003, 270(S2):S186-S188.
[23] Knuth D E. The Stanford graphBase:a platform for combinatorial computing[M] . Reading:Addison-Wesley Professional, 1993.
收稿日期 2016/6/28
修回日期 2016/8/22
页码 2748-2752
中图分类号 TP393.02
文献标志码 A