节点不对称转移概率的网络社区发现算法
作者:
作者简介:

许平华(1995-),男,湖北荆州人,学士,主要研究领域为复杂网络;胡文斌(1976-),男,博士,教授,博士生导师,主要研究领域为人工智能,智能仿真优化,大数据与数据挖掘;邱振宇(1992-),男,博士生,主要研究领域为社会网络;聂聪(1993-),男,硕士,主要研究领域为智能仿真与优化;唐传慧(1995-),男,学士,CCF学生会员,主要研究领域为智能交通;高旷(1994-),男,学士,主要研究领域为复杂网络,车载自组织网络;刘中舟(1993-),男,学士,主要研究领域为生物信息学,复杂网络.

通讯作者:

胡文斌,E-mail:hwb@whu.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61711530238,61572369);国家重点基础研究发展计划(973)(2012CB719905)


Community Detection Algorithm Based on Asymmetric Transition Probability of Nodes
Author:
Fund Project:

National Natural Science Foundation of China (61711530238, 61572369); National Program on Key Basic Research Project of China (973) (2012CB719905)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [38]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    社区发现是当前社会网络研究领域的一个热点和难点,现有的研究方法包括:(1)优化以网络拓扑结构为基础的社区质量指标;(2)评估节点间的相似性并进行聚类;(3)根据特定网络设计相应的社区模型等.这些方法存在如下问题:(1)通用性不高,难以同时在无向网络和有向网络上发挥出好的效果;(2)无法充分利用网络的结构信息,在真实数据集上表现不佳.针对上述问题,提出一种基于节点不对称转移概率的网络社区发现算法CDATP.该算法通过分析网络拓扑结构来设计节点转移概率,并使用random walk方法评估节点对网络社区的重要性.最后,以重要性较高的节点作为核心构造网络社区.与现有的基于random walk的方法不同,CDATP为网络中节点设计的转移概率具有不对称性,并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明,CDATP在人工模拟数据集和真实数据集上均比其他最新算法有更好的表现.

    Abstract:

    Community detection is a popular and difficult problem in the field of social network analysis. Most of the current researches mainly focus on optimizing the modularity index, evaluating the similarity of nodes, and designing different models to fit particular networks. These approaches usually suffer from following problems:(1) just a few of them can deal with directed networks as well as undirected networks; and (2) real-world networks being more complex than synthetic networks, many community detection strategies cannot perform well in real-world networks. To solve these problems, this paper presents an algorithm for community detection in complex networks based on random walk method. Different from existing methods based on random walk method, the asymmetric transition probability is designed for the nodes according to network topology and other information. The event propagation law is also applied to the evaluation of nodes importance. The algorithm CDATP performs well on both real-world networks and synthetic networks.

    参考文献
    [1] Newman MEJ, Girvan M. Finding and evaluating community structure in networks, Physical Review E, 2004,69:026113.
    [2] Li ZP, Wang RS, Zhang SH, Zhang XS. Quantitative function and algorithm for community detection in bipartite networks. Information Sciences, 2016,367(C):874-889.
    [3] You T, Cheng HM, Ning YZ, Shia BC, Zhang ZY. Community detection in complex networks using density-based clustering algorithm and manifold learning. Physica A:Statistical Mechanics and its Applications, 2016,464:221-230.
    [4] Amiri B, Hossain L, Crawford JW, Wigand RT. Community detection in complex networks:Multi-objective enhanced firefly algorithm. Knowledge-Based Systems, 2013,46(1):1-11.
    [5] Huang FL, Zhang SC, Zhu XF. Discovering network community based on multi-objective optimization. Ruan Jian Xue Bao/Journal of Software, 2013,24(9):2062-2077(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4400.htm[doi:10.3724/SP.J.1001.2013.04400]
    [6] Fortunato S, Barthélemy M. Resolution limit in community detection. Proc. of the National Academy of Sciences, 2007,104:36-41.
    [7] Bagrow JP. Communities and bottlenecks:Trees and treelike networks have high modularity. Physical Review E, 2012,85:066118.
    [8] Pons P, Latapy M. Computing communities in large networks using random walks. In:Proc. of the Int'l Symp. on Computer and Information Sciences. Springer-Verlag, 2005. 284-293.
    [9] Lai D, Lu H, Nardini C. Finding communities in directed networks by PageRank random walk induced network embedding. Physica A:Statistical Mechanics and Its Applications, 2010,389(12):2443-2454.
    [10] Jiao QJ, Huang Y, Shen HB. Community mining with new node similarity by incorporating both global and local topological knowledge in a constrained random walk. Physica A:Statistical Mechanics and Its Applications, 2015,424:363-371.
    [11] Huang X, Cheng H, Yu JX. Dense community detection in multi-valued attributed networks. Information Sciences, 2015,314(C):77-99.
    [12] Su C, Jia X, Xie X, Yu Y. A new random-walk based label propagation community detection algorithm. In:Proc. of the IEEE/WIC/ACM Int'l Conf. on Web Intelligence and Intelligent Agent Technology. IEEE, 2015. 137-140.
    [13] Jin D, Yang B, Liu J, Liu DY, He DX. Ant colony optimization based on random walk for community detection in complex networks. Ruan Jian Xue Bao/Journal of Software, 2012,23(3):451-464(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3996.htm[doi:10.3724/SP.J.1001.2012.03996]
    [14] Wang W, Liu D, Liu X, Pan L. Fuzzy overlapping community detection based on local random walk and multidimensional scaling. Physica A:Statistical Mechanics and Its Applications, 2013,392(24):6578-6586.
    [15] Xin Y, Xie ZQ, Yang J. The adaptive dynamic community detection algorithm based on the non-homogeneous random walking. Physica A:Statistical Mechanics and Its Applications, 2016,450:241-252.
    [16] Meo PD, Ferrara E, Fiumara G, Provetti A. Enhancing community detection using a network weighting strategy. Information Sciences:An Int'l Journal, 2013,222(3):648-668.
    [17] Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E, 2004,70:66111.
    [18] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth. In:Proc. of the IEEE Int'l Conf. on Data Mining. IEEE Computer Society, 2012. 745-754.
    [19] Bai L, Cheng X, Liang J, Guo Y. Fast graph clustering with a new description model for community detection. Information Sciences, 2017,s 388-389(C):37-47.
    [20] Fortunato S. Community detection in graphs. Physics Reports, 2010,486:75-174.
    [21] Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007,76(3 Pt 2):036106.
    [22] Malliaros FD, Vazirgiannis M. Clustering and community detection in directed networks:A survey. Physics Reports, 2013,533(4):95-142.
    [23] Leicht EA, Newman MEJ. Community structure in directed networks. Physical Review Letters, 2007,100(11):118703.
    [24] Rosvall M, Bergstrom CT. An information-theoretic framework for resolving community structure in complex networks. Proc. of the National Academy of Sciences, 2007,104:7327.
    [25] Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S. Finding statistically significant communities in networks. PloS One, 2011, 6(4):e18961.
    [26] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 2009,80:016118.
    [27] Santos CP, Carvalho DM, Nascimento MCV. A consensus graph clustering algorithm for directed networks. Expert Systems with Applications, 2016,54:121-135.
    [28] Zhang J, Liu B, Tang J, Chen T, Li J. Social influence locality for modeling retweeting behaviors. In:Proc. of the Int'l Joint Conf. on Artificial Intelligence. AAAI Press, 2013. 2761-2767.
    [29] Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1997,33:452-473.
    [30] Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003,54(4):396-405.
    [31] Krebs B. Books about US Politics. 2004. http://www.orgnet.com/
    [32] Adamic LA, Glance N. The political blogosphere and the 2004 US election. In:Proc. of the WWW 2005 Workshop on the Weblogging Ecosystem. 2005.
    [33] Kumar P, Gupta S, Bhasker B. An upper approximation based community detection algorithm for complex networks. Decision Support Systems, 2017. 103-118.
    [34] Tesmer M, Perez CA, Zurada JM. Normalized mutual information feature selection. IEEE Trans. on Neural Networks, 2009,20(2):189.
    [35] Yang Y, Sun PG, Hu X, Li ZJ. Closed walks for community detection. Physica A:Statistical Mechanics and Its Applications, 2014, 397(3):129-143.
    附中文参考文献:
    [5] 黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法.软件学报,2013,24(9):2062-2077. http://www.jos.org.cn/1000-9825/4400.htm[doi:10.3724/SP.J.1001.2013.04400]
    [13] 金弟,杨博,刘杰,等.复杂网络簇结构探测——基于随机游走的蚁群算法.软件学报,2012,23(3):451-464. http://www.jos.org.cn/1000-9825/3996.htm[doi:10.3724/SP.J.1001.2012.03996]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

许平华,胡文斌,邱振宇,聂聪,唐传慧,高旷,刘中舟.节点不对称转移概率的网络社区发现算法.软件学报,2019,30(12):3829-3845

复制
分享
文章指标
  • 点击次数:1649
  • 下载次数: 6297
  • HTML阅读次数: 1799
  • 引用次数: 0
历史
  • 收稿日期:2017-09-04
  • 最后修改日期:2018-02-03
  • 在线发布日期: 2019-12-05
文章二维码
您是第19701247位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号