基于多核心标签传播的复杂网络重叠社区识别方法

邓琨; 李文平; 余法红; 张健沛

doi:10.11959/j.issn.1000-436x.2017028

您当前的位置：

首页 >

文章列表页 >

基于多核心标签传播的复杂网络重叠社区识别方法

学术论文 | 更新时间：2024-06-05

- 基于多核心标签传播的复杂网络重叠社区识别方法
- Overlapping community detection in complex networks based on multi kernel label propagation
- 通信学报 2017年38卷第2期页码：53-66
- 作者机构：
  
  1. 嘉兴学院数理与信息工程学院，浙江嘉兴 314001
  2. 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001
- 作者简介：
  
  [ "邓琨（1980-），男，黑龙江哈尔滨人，博士，嘉兴学院讲师，主要研究方向为数据挖掘、复杂网络结构分析等。" ]
  [ "李文平（1979-），男，贵州大方人，博士，嘉兴学院讲师，主要研究方向为数据挖掘、隐私保护等。" ]
  [ "余法红（1977-），男，湖北监利人，嘉兴学院讲师，主要研究方向为复杂网络、智能计算、大数据分析等。" ]
  [ "张健沛（1956-），男，黑龙江哈尔滨人，博士，哈尔滨工程大学教授、博士生导师，主要研究方向为数据库理论与应用、数据挖掘、复杂网络等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61672179);国家自然科学基金资助项目(61370083);国家自然科学基金资助项目(61402126);教育部人文社会科学研究青年基金资助项目(15YJCZH088);浙江省自然科学基金资助项目(LY16F020027);浙江省教育厅科研基金资助项目(Y201636127);浙江省教育厅科研基金资助项目(Y201533771)
- DOI：10.11959/j.issn.1000-436x.2017028
  中图分类号： TP391
- 网络出版日期：2017-02，
  
  纸质出版日期：2017-02-25
- 稿件说明：
移动端阅览
邓琨, 李文平, 余法红, 等. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017,38(2):53-66.

Kun DENG, Wen-ping LI, Fa-hong YU, et al. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on communications, 2017, 38(2): 53-66.
邓琨, 李文平, 余法红, 等. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017,38(2):53-66. DOI： 10.11959/j.issn.1000-436x.2017028.

Kun DENG, Wen-ping LI, Fa-hong YU, et al. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on communications, 2017, 38(2): 53-66. DOI： 10.11959/j.issn.1000-436x.2017028.

摘要

针对传统基于标签传播的重叠社区识别方法存在较强的随机性，以及需要预设相关阈值来辅助完成社区识别等缺陷，提出基于多核心标签传播的重叠社区识别方法(OMKLP)。在分析节点度以及节点与邻居节点的局部覆盖密度后提出核心节点评价模型，并在此基础上给出局部核心节点识别方法；基于局部核心节点，提出新的面向重叠社区的异步标签传播策略，该策略能够快速地识别出社区内部节点与边界节点，以获得重叠社区结构；提出重叠节点分析方法，进一步提高识别重叠节点准确度。OMKLP 算法无需掌握任何先验知识，仅在掌握网络基本信息(点、边)基础上，便能够准确识别出重叠社区结构，从而有效解决了传统标签传播算法所存在的缺陷。在基准网络和真实网络上进行测试，并与多个经典算法进行对比分析，实验结果验证了所提算法的有效性和可行性。

Abstract

In view of the strong randomness and pre-setting the related threshold of traditional overlapping community detection method based on label propagation

overlapping community detection in complex networks based on multi kernel label propagation (OMKLP) was proposed.Evaluation model of kernel nodes was proposed after analyzing the node's degree and local covering density of nodes and their neighbor nodes.And on this basis

the detection method of local kernel nodes was also presented.Based on local kernel nodes

a new asynchronous label propagation strategy ori-ented to overlapping community was proposed

which can rapidly distinguish inner nodes and outer nodes of communi-ties so as to obtain overlapping community structure.The analysis method of overlapping nodes was proposed to increase the accuracy of detecting overlapping nodes.Without any prior knowledge

only on the basis of the basic network infor-mation (nodes and links)

the algorithm can detect the structure of overlapping communities accurately.Therefore

it ef-fectively solved the defect of the traditional label propagation algorithm.The algorithm was tested over benchmark net-works and real-world networks and also compared with some classic algorithms.The experiment results verify the valid-ity and feasibility of OMKLP.

关键词

Keywords

references

WATTS D J , STROGATZ S H . Collective dynamics of “small-world”networks [J ] . Nature , 1998 , 393 ( 84 ): 440 - 442 .

BARABÁSI A L , ALBERT R . Emergence of scaling in random networks [J ] . Science , 1999 , 286 ( 5439 ): 509 - 512 .

金弟 , 刘大有 , 杨博 , 等 . 基于局部探测的快速复杂网络聚类算法 [J ] . 电子学报 , 2011 , 39 ( 11 ): 2540 - 2546 .

JIN D , LIU D Y , YANG B , et al . Fast complex network clustering algorithm using local detention [J ] . Acta Electronica Sinica , 2011 , 39 ( 11 ): 2540 - 2546 .

WANG Z , ZHANG J . In search of the biological significance of modular structures in protein networks [J ] . Plos Computational Biology , 2007 , 3 ( 6 ): 1011 - 1021 .

FARUTIN V , ROBISON K , LIGHTCAP E , et al . Edge-count probabilities for the identification of local protein communities and their organization [J ] . Proteins Structure Function and Bioinformatics , 2006 , 62 ( 3 ): 800 - 818 .

QIAN C , CAO J D , LU J Q , et al . Adaptive bridge control strategy for opinion evolution on social networks [J ] . Chaos:An Interdisciplinary Journal of Nonlinear Science , 2011 , 21 ( 2 ):025116

SIDIROPOULOS A , PALLIS G , KATSAROS D , et al . Prefetching in content distribution networks via web communities identification and outsourcing [J ] . World Wide Web , 2008 , 11 ( 1 ): 39 - 70 .

NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks [J ] . Physical Review E , 2004 , 69 ( 2 ):026113.

NEWMAN M E J . Fast algorithm for detecting community structure in networks [J ] . Physical Review E , 2004 , 69 ( 6 ):066133.

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J ] . Journal of Statistical Mechanics Theory and Experiment , 2008 , 10 :10008.

RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks [J ] . Physical Review E , 2007 , 76 ( 3 ):036106

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 .

SHEN H W , CHENG X Q , GUO J F . Quantifying and identifying the overlapping community structure in networks [J ] . Journal of Statistical Mechanics-Theory and Experiment , 2009 , 53 ( 7 ):07042.

ZHANG Z W , WANG Z Y . Mining overlapping and hierarchical communities in complex networks [J ] . Physica A:Statistical Mechanics and its Applications , 2015 , 421 : 25 - 33 .

AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks [J ] . Nature , 2010 , 466 ( 7307 ): 761 - 764 .

MENG F , ZHANG F , ZHU M , et al . Incremental density-based link clustering algorithm for community detection in dynamic networks [J ] . Mathematical Problems in Engineering , 2016 , 2016 ( 6 ): 1 - 11 .

KIM P , KIM S . Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering [J ] . Physica A:Statistical Mechanics and its Applications , 2015 , 417 : 46 - 56 .

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.

WANG M , YANG S , WU L . Improved community mining method based on LFM and EAGLE [J ] . Computer Science and Information Systems , 2016 , 13 ( 2 ): 515 - 530 .

CAO X , WANG X , JIN D , et al . The (un)supervised detection of overlapping communities as well as hubs and outliers via (bayesian) NMF [C ] // International Conference on World Wide Web Companion . 2014 : 233 - 234 .

常振超 , 陈鸿昶 , 黄瑞阳 , 等 . 基于非负矩阵分解的半监督动态社团检测 [J ] . 通信学报 , 2016 , 37 ( 2 ): 132 - 142 .

CHANG Z C , CHEN H C , HUANG R Y , et al . Semi-supervised dynamic community detection bused on nonnegative matrix factoriza-tion [J ] . Journal on Communications , 2016 , 37 ( 2 ): 132 - 142 .

HE D , WANG H , JIN D , et al . A model framework for the enhancement of community detection in complex networks [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2016 , 461 : 602 - 612 .

GREGORY S . Finding overlapping communities in networks by label propagation [J ] . New Journal of Physics , 2010 , 12 ( 10 ):103018.

XIE J R , SZYMANSKI B K , LIU X . Slpa:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process [C ] // IEEE ICDM Workshop on DMCCI . IEEE,Vancouver,Canada , 2011 : 344 - 349 .

CHEN Q , WU T T . A method for local community detection by finding maximal-degree nodes [C ] // 9th International Conference on Machine Learning and Cybernetics . 2010 : 8 - 13 .

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,IEEE . Istanbul,Turkey , 2012 : 1171 - 1176 .

LEUNG I X , HUI P LIÒ P , et al . Towards real-time community detection in large networks [J ] . Physical Review E , 2009 , 79 ( 2 ): 853 - 857 .

XIE J , KELLEY S , SZYMANSKI B K . Overlapping community detection in networks:the state of the art and comparative study [J ] . Acm Computing Surveys , 2011 , 45 ( 4 ): 115 - 123 .

LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms [J ] . Physical Review E , 2008 , 78 ( 4 ):046110.

ZACHARY W W . An information flow model for conflict and fission in small groups [J ] . Journal of Anthropological Research , 1977 , 33 ( 4 ): 452 - 473 .

LUSSEAU D . The emergent properties of a dolphin social network [J ] . Proceedings of the Royal Society B:Biological Sciences , 2003 , 270 ( S2 ): 186 - 188 .

KNUTH D E . The Stanford graphbase:a platform for combinatorial computing [EB/OL ] . http://www-cs-faculty.stanford.edu/～uno/sgb.html http://www-cs-faculty.stanford.edu/～uno/sgb.html .

NEWMAN M E J . Modularity and community structure in networks [J ] . Proceedings of the National Academy of Science , 2006 , 103 ( 23 ): 8577 - 8582 .

GUIMERA R , DANON L DIAZ-GUILERA A , et al . Self-similar community structure in a network of human interactions [J ] . Physical Review E , 2003 , 68 ( 6 ):065103.

NEWMAN M E J . Network data from mark Newman's home page [EB/OL ] . http://www-personal.umich.edu/～mejn/netdata/ http://www-personal.umich.edu/～mejn/netdata/ .

NEWMAN M E J . Finding community structure in networks using the eigenvectors of matrices [J ] . Physical review E , 2006 , 74 ( 3 ):036104.

BOGUÑÁ M , PASTOR-SATORRAS R , DÍAZ-GUILERA A , et al . Models of social networks based on social distance attachment [J ] . Physical Review E , 2004 , 70 ( 5 ):056122. 056 - 122 .

浏览量

654

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于局部近邻传播及用户特征的社区识别算法

Internet的IP基密度分析