计算机科学 ›› 2016, Vol. 43 ›› Issue (12): 153-157.doi: 10.11896/j.issn.1002-137X.2016.12.027

• 数据挖掘 • 上一篇    下一篇

基于引力因子的加权网络重叠社区识别算法

刘冰玉,王翠荣,王聪,苑迎   

  1. 东北大学信息科学与工程学院 沈阳110819,东北大学信息科学与工程学院 沈阳110819,东北大学信息科学与工程学院 沈阳110819,东北大学信息科学与工程学院 沈阳110819
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金(61300195),河北省自然科学基金(F2014501078,F2016501079),河北省科技计划项目(15210146),辽宁省教育厅科学研究一般项目(L2013099),秦皇岛市科技计划项目(201401A028)资助

Overlapping Community Recognition Algorithm of Weighted Networks Based on Gravity Factor

LIU Bing-yu, WANG Cui-rong, WANG Cong and YUAN Ying   

  • Online:2018-12-01 Published:2018-12-01

摘要: 通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。

关键词: 引力因子,社区识别,加权网络,重叠社区

Abstract: The recognition of community in complex social networks by mining big data can favor the quantitative research for economic,political and demographic problems.Community recognition algorithms have become a hot topic of current research.This paper focused on the research of overlapping community discovery,and proposed the overlapping community detection algorithm GWCR,which is based on gravity factor of weighted networks.Firstly,the GWCR algorithm selects the node with the largest gravitation factor as the center node,and uses the gravitation factor between one node and the central node as a measure.The node whose gravitation factor is larger than the threshold will be included in the community.Finally,overlapping communities are discovered by identifying overlapping nodes.Experimental results on three real network datasets show that,compared with conventional overlapping community detection algorithm,GWCR has higher modularity value.

Key words: Gravity factor,Community recognition,Weighted network,Overlapping community

[1] Liu Y,Liu Q,Qin Z.Community detecting and feature analysisin real directed weighted social networks [J].Journal of Networks,2013,8(6):1432-1439
[2] Palla,Gergely,et al.Uncovering the overlapping community stru-cture of complex networks in nature and society[J].Nature,2005,435(7043):814-818
[3] Chen Duan-bing,Shang Ming-sheng,Li Xia.Two-phase Strategy on Overlapping Communities Detection[J].Computer Science,2013,40(1):225-228(in Chinese) 陈端兵,尚明生,李霞.重叠社区发现的两段策略[J].计算机科学,2013,40(1):225-228
[4] Lancichinetti A,Radicchi F,Ramasco J J,et al.Finding statistically significant communities in networks[J].PloS one,2011,6(4):3360338
[5] Baumes J,Goldberg M,Magdon-Ismail M.Efficient identifica-tion of overlapping communities[C]∥Intelligence and Security Informatics.Springer Berlin Heidelberg,2005:27-36
[6] Kim Y,Jeong H.Map equation for link communities[J].Physical Review E Statistical Nonlinear & Soft Matter Physcis,2011,84(2):1402-1409
[7] Lv T Y,Xie W,Zheng W,et al.Analysis of community evaluation criterion and discovery algorithm of weighted complex network [J].Acta Physica Sinica,2012,1(21):210511(in Chinese) 吕天阳,谢文艳,郑纬民,等.加权复杂网络社团的评价指标及其发现算法分析[J].物理学报,2012,1(21):210511
[8] Lou X,Suykens J A.Finding communities in weighted networks through synchronization [J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2011,21(4):744-783
[9] Huang Jia-xin,Guo Kun,Guo Hong.Label Propagation Algo-rithm for Community Detection Based on Vertex Significance and Label Influence[J].Journal of Chinese Computer Systems,2015,36(6):1171-1175(in Chinese) 黄佳鑫,郭昆,郭红.融入节点重要性和标签影响力的标签传播社区发现算法[J].小型微型计算机系统,2015,36(6):1171-1175
[10] Cheng S X,Cai K,Hu M.Detect overlapping and hierarchicalcommunity structure in networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(8):1706-1712
[11] Newman M E J,Girvan M.Finding and evaluating communitystructure in networks[J].Physical review E,2004,69(2):26113
[12] Wu Zhi-hao,Lin You-fang,Wan Huai-yu,et al.Efficient overlapping community detection in huge real-world networks[J].Physica A:Statistical Mechanics and its Applications,2012,391(7):2475-2490
[13] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of nthropological Research,1977,33(4):452-473
[14] Leskovec J,Kleinberg J,Faloutsos C.Graphs over time:densification laws,shrinking diameters and possible explanations[C]∥Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.2005
[15] Opsahl T,Panzarasa P.Clustering in weighted networks[J].Social networks,2009,31(2):155-163
[16] Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2009,12(10):2011-2024
[17] Lancichinetti A,Fortunato S,Kertesz J.Detecting the over-lapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):19-44
[18] Adamcsek B,Palla G,Farkas I J,et al.CFinder:locating cliques and overlapping modules in biological netuork[J].Bioinforma-tics,2006,2(8):1021-1023

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 .