计算机科学 ›› 2016, Vol. 43 ›› Issue (3): 33-37, 71.doi: 10.11896/j.issn.1002-137X.2016.03.006

• 第十五届中国机器学习会议 • 上一篇    下一篇

一种面向度中心性及重叠网络社区的发现算法

刘井莲,王大玲,赵卫绩,冯时,张一飞   

  1. 东北大学信息科学与工程学院 沈阳110819;绥化学院信息工程学院 绥化152061,东北大学信息科学与工程学院 沈阳110819;东北大学医学影像计算教育部重点实验室 沈阳110819,绥化学院信息工程学院 绥化152061,东北大学信息科学与工程学院 沈阳110819;东北大学医学影像计算教育部重点实验室 沈阳110819,东北大学信息科学与工程学院 沈阳110819;东北大学医学影像计算教育部重点实验室 沈阳110819
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金(61370074,61402091)资助

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

摘要: 针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。

关键词: 社会网络,社区发现,度中心性,重叠度,偏离度

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   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .