微信服务号

微信订阅号

2025年6月15日 9:46 星期日
首页 > 过刊浏览>2009年第20卷第8期 >2241-2254
PDF HTML阅读 XML下载 导出引用 引用提醒
一种基于拓扑势的网络社区发现方法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60675032 (国家自然科学基金); the National Basic Research Program of China under Grant Nos.2007CB310800, 2007CB311003 (国家重点基础研究发展计划(973))

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

    从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n3/γ)～O(n2),n为网络节点数,m为边数,2<γ<3为一个常数.

    Abstract:

    Inspired from the idea of data fields, a community discovery algorithm based on topological potential is proposed. The basic idea is that a topological potential function is introduced to analytically model the virtual interaction among all nodes in a network and, by regarding each community as a local high potential area, the community structure in the network can be uncovered by detecting all local high potential areas margined by low potential nodes. The experiments on some real-world networks show that the algorithm requires no input parameters and can discover the intrinsic or even overlapping community structure in networks. The time complexity of the algorithm is O(m+n3/γ)～O(n2), where n is the number of nodes to be explored, m is the number of edges, and 2<γ<3 is a constant.

    参考文献
    [1] Watts DJ, Strogatz SH. Collective dynamics of small world networks. Nature, 1998,393(4):440?442.
    [2] Barabási AL, Albert R. Emergence of scaling in random networks. Science, 1999,286(5439):509?512.
    [3] Barabási A, Bonabeau E. Scale-Free networks. Scientific American, 2003,288(5):60?69.
    [4] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. ACM SIGCOMM Computer Communication Review, 1999,29(4):251?262.
    [5] Newman MEJ. The structure and function of complex networks. SLAM Review, 2003,45(2):167?256.
    [6] Zhou T, Bai WJ, Wang BH, Liu ZJ, Yan G. A brief review of complex networks. Physics, 2005,34(1):31?36 (in Chinese with English abstract).
    [7] Borgs C, Chayes J, Mahdian M, Saberi A. Exploring the community structure of newsgroups. In: Kim W, Kohavi R, Gehrke J, DuMouchel W, eds. Proc. of the 10th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Seattle: AAAI, 2004. 783?787.
    [8] Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. of the National Academy of Sciences of the United States of America, 2002,99(12):7821?7826.
    [9] Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004,69(2). 026113.
    [10] Newman MEJ. Modularity and community structure in networks. Proc. of the National Academy of Sciences of the United States of America, 2006,103(23):8577?8582.
    [11] Wang L, Dai GZ. Community finding in complex networks: theory and applications. Science & Technology Review, 2005,23(8): 62?66 (in Chinese with English abstract).
    [12] Scott J. Social Network Analysis: A Handbook. 2nd ed., London: Sage Publications, 2000.
    [13] West DB. Introduction to Graph Theory. Upper Saddle River: Prentice Hall, 2001.
    [14] Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E, 2004,69(6). 066133.
    [15] Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E, 2004,70(6). 066111.
    [16] Duch J, Arenas A. Community identification using extremal optimization. Physical Review E, 2005,72(6). 027104.
    [17] Guimera R, Amaral LAN. Functional cartography of complex metabolic networks. Nature, 2005,433(7028):895?900.
    [18] Ruan JH, Zhang WX. Identification and evaluation of weak community structures in networks. In: Proc. of the 21st National Conf. on Artificial Intelligence (AAAI 2006). The AAAI Press, 2006. 470?475.
    [19] White S, Smyth P. A spectral clustering approach to finding communities in graph. In: Kargupta H, Srivastava J, Kamath C, Goodman A, eds. Proc. of the SIAM Int’l Conf. on Data Mining. Newport Beach: SIAM, 2005. 76?84.
    [20] Danon L, Díaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechanics, 2005, 2005(9). P09008.
    [21] Muff S, Rao F, Caflisch A. Local modularity measure for network clusterizations. Physical Reviews E, 2005,72(5). 056107.
    [22] Fortunato S, Barthelemy M. Resolution limit in community detection. Proc. of the National Academy of Sciences of the United States of America, 2007,104(1):36?41.
    [23] Arenas A, Danon L, Díaz-Guilera A, Gleiser PM, Guimerà R. Community analysis in social networks. European Physics Journal B, 2004,38(2):373?380.
    [24] Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A. Self-Similar community structure in organizations. Preprint cond-mat/0211498, 2002. http://arxiv.org/abs/cond-mat/0211498
    [25] Gan WY. Study on the clustering problem in data mining [Ph.D. Thesis]. Nanjing: University of Science and Technology, 2003 (in Chinese with English abstract).
    [26] Gan WY, Li DY, Wang JM. An hierarchical clustering method based on data fields. Chinese Journal of Electronics, 2006,34(2): 258?262 (in Chinese with English abstract).
    [27] Newman MEJ, Strogatz SH, Watts DJ. Random graphs with arbitrary degree distributions and their applications. Physical Review E, 2001,64(2). 026118.
    [28] Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977,33(4):452?473.
    [29] Newman MEJ. Detecting comunity structure in networks. European Physics Journal B, 2004,38(2):321?330.
    [30] Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality. Physical Review E, 2004,70(5). 056104.
    [31] Gfeller D, Chappelier JC, Rios PDL. Finding instabilities in the community structure of complex networks. Physical Review E, 2005,72(5). 056135.
    [32] Danon L, Díaz-Guilera A, Arenas A. Effect of size heterogeneity on community identification in complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2006,2006(11). P11010.
    [33] Newman MEJ, Girvan M. Mixing patterns and community structure in networks. Preprint cond-mat/0210146, 2002. http://arxiv.org/abs/cond-mat/0210146
    [34] Bagrow JP, Bollt EM. A local method for detecting communities. Physical Review E, 2005,72(4). 046108.
    [35] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU. Complex networks: Structure and dynamics. Physics Reports, 2006, 424(4-5):175?308.
    [36] 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—Can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology, 2003,54(4):396?405.
    [37] Lusseau D, Newman MEJ. Identifying the role that animals play in their social networks. Proc. of the Royal Society B: Biological Sciences, 2004,271(Suppl_6):S477?S481.
    [38] He N, Gan WY, Li DY, Kang JC. The topological analysis of a small actor collaboration network. Complex Systems and Complexity Science, 2006,3(4):1?10 (in Chinese with English abstract).
    [39] Guimera R, Danon L, Díaz-Guilera A, Giralt F, Arenas A. Self-Similar community structure in organizations. Preprint cond-mat/0211498, 2002. http://arxiv.org/abs/cond-mat/0211498 附中文参考文献:
    [6] 周涛,柏文洁,汪秉宏,刘之景,严钢.复杂网络研究概述.物理,2005,34(1):31?36.
    [11] 王林,戴冠中.复杂网络中的社区发现——理论与应用.科技导报,2005,23(8):62?66.
    [25] 淦文燕.聚类——数据挖掘中的基础理论问题研究[博士学位论文].南京:解放军理工大学,2003.
    [26] 淦文燕,李德毅,王建民.一种基于数据场的层次聚类方法.电子学报,2006,34(2):258?262.
    [38] 赫南,淦文燕,李德毅,康建初.一个小型演员合作网的拓扑性质分析.复杂系统与复杂性科学,2006,3(4):1?10.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

淦文燕,赫南,李德毅,王建民.一种基于拓扑势的网络社区发现方法.软件学报,2009,20(8):2241-2254

复制
分享
文章指标
  • 点击次数:7152
  • 下载次数: 19274
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2007-07-02
  • 最后修改日期:2008-03-14
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第20050223位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号