-
节点的聚集现象是复杂网络的重要特性. 以往研究主要发现无权复杂网络中的社团, 较少涉及加权网络的社团发现. 由于加权网络的复杂性远高于无权网络, 一般认为加权网络的社团发现是一个较难的问题. 本文基于统一的数据基础, 从社团评价指标的有效性和现有算法的效果两个角度开展研究. 首先, 总结了加权网络三种常见的社团评估指标, 并在社团大小、密度和局域特点均不同的模拟数据集上分析指标的有效性; 其次, 针对5个数据集, 分析现有的3种加权复杂网络社团发现算法的效果. 研究表明: 上述指标无论在评价最基本的社团结构, 还是在分析结构复杂的社团时都有较大缺欠; 现有的加权网络社团发现算法的泛化能力不强.The clustering of nodes is an important feature of complex network. Previous researches mainly focus on community discovery in unweighted network, with little attention paid to the weighted network because of the complexity of weighted network. The community discovery of the weighted network is believed to be a much more difficult task. In this paper, we perform a study on the effectivenesses of community evaluation criterion and the performances of the existing discovery algorithms. First, we summarize three classical community evaluation criterions of weighted network, and analyze their effectivenesses according to a simulated noisy dataset, which has different community sizes, densities and local characteristics. Second, we adopt five datasets to compare the performances of three typical community discovery algorithms. The study shows that the existing criterions encounter difficulties in evaluating the basic community structure and in evaluating the weighted community with complex structure, and the generalization ability of the typical community discovery algorithm of weighted network is unsatisfactory.
-
Keywords:
- complex network /
- community discovery /
- clustering coefficient /
- modularity
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115
[3] Granovetter M 1973 Am. J. Soc. 78 1360
[4] Barabasi A L, Albert R 1999 Science 286 509
[5] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[6] Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54 (in Chinese) [杨博, 刘大有, Liu Jiming, 金弟, 马海宾 2009 软件学报 20 54]
[7] Cheng X Q, Shen H W 2011 Complex Syst. Complexity Sci. 8 57 (in Chinese) [程学旗, 沈华伟 2011 复杂系统与复杂性科学 8 57]
[8] Barrat A, Barthélemy M, Vespignani A 2004 Phys. Rev. E 70 066149
[9] Antoniou I E, Tsompa E T 2008 Dis. Dyn. Nat. Soc. 2008 194
[10] Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901 (in Chinese) [田柳, 狄增如, 姚虹 2011 60 028901]
[11] Newman M E J 2004 Phys. Rev. E 70 056131
[12] Li X J, Zhang P, Di Z R, Fan Y 2008 Complex Sys. Complexity Sci. 5 19 (in Chinese) [李晓佳, 张鹏, 狄增如, 樊瑛 2008 复杂系统与复杂性科学 5 19]
[13] Wang X F, Li X, Chen G R 2006 Complex Network Theory and Its Application (1st Edn.) (Beijing: Tsinghua University Press) p10 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (第一版) (北京: 清华大学出版社) 第10页]
[14] Zhang B, Horvath S 2005 Stat. Appl. Genet. Mol. 4 1128
[15] Onnela J-P, Saramäki J, Kertész J, Kaski K 2005 Phys. Rev. E 71 065103
[16] Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A 2004 PNAS (USA) 101 3747
[17] Holme P, Park S M, Kim B J, Edling C R 2007 Physica 373 821
[18] Kalna G, Higham D J 2006 SNANSE pp45-50
[19] Lopez-Fernandez L, Robles G, Gonzalez-Barahona J M 2004 Proc. of the 1st Intl. Workshop on MSR pp101-105
[20] Serrano M A, Boguñá M, Pastor-Satorras R 2006 Phys. Rev. E 74 055101
[21] Filippo R, Claudio C, Federico C, Vittorio L, Domenico P 2004 PNAS 101 2658
[22] Lü T Y, Huang S B, Wu P, Jia Y R 2010 Proc. SKG pp211-218
[23] Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Ed.) (Indianapolis: Addison-Wesley Professional) pp15
[24] Newman M E J 2006 Phys. Rev. E 74 036104
[25] Kevin D, Steven C 2004 NDPLS 8 259
-
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115
[3] Granovetter M 1973 Am. J. Soc. 78 1360
[4] Barabasi A L, Albert R 1999 Science 286 509
[5] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[6] Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54 (in Chinese) [杨博, 刘大有, Liu Jiming, 金弟, 马海宾 2009 软件学报 20 54]
[7] Cheng X Q, Shen H W 2011 Complex Syst. Complexity Sci. 8 57 (in Chinese) [程学旗, 沈华伟 2011 复杂系统与复杂性科学 8 57]
[8] Barrat A, Barthélemy M, Vespignani A 2004 Phys. Rev. E 70 066149
[9] Antoniou I E, Tsompa E T 2008 Dis. Dyn. Nat. Soc. 2008 194
[10] Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901 (in Chinese) [田柳, 狄增如, 姚虹 2011 60 028901]
[11] Newman M E J 2004 Phys. Rev. E 70 056131
[12] Li X J, Zhang P, Di Z R, Fan Y 2008 Complex Sys. Complexity Sci. 5 19 (in Chinese) [李晓佳, 张鹏, 狄增如, 樊瑛 2008 复杂系统与复杂性科学 5 19]
[13] Wang X F, Li X, Chen G R 2006 Complex Network Theory and Its Application (1st Edn.) (Beijing: Tsinghua University Press) p10 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (第一版) (北京: 清华大学出版社) 第10页]
[14] Zhang B, Horvath S 2005 Stat. Appl. Genet. Mol. 4 1128
[15] Onnela J-P, Saramäki J, Kertész J, Kaski K 2005 Phys. Rev. E 71 065103
[16] Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A 2004 PNAS (USA) 101 3747
[17] Holme P, Park S M, Kim B J, Edling C R 2007 Physica 373 821
[18] Kalna G, Higham D J 2006 SNANSE pp45-50
[19] Lopez-Fernandez L, Robles G, Gonzalez-Barahona J M 2004 Proc. of the 1st Intl. Workshop on MSR pp101-105
[20] Serrano M A, Boguñá M, Pastor-Satorras R 2006 Phys. Rev. E 74 055101
[21] Filippo R, Claudio C, Federico C, Vittorio L, Domenico P 2004 PNAS 101 2658
[22] Lü T Y, Huang S B, Wu P, Jia Y R 2010 Proc. SKG pp211-218
[23] Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Ed.) (Indianapolis: Addison-Wesley Professional) pp15
[24] Newman M E J 2006 Phys. Rev. E 74 036104
[25] Kevin D, Steven C 2004 NDPLS 8 259
计量
- 文章访问数: 7961
- PDF下载量: 4247
- 被引次数: 0
下载:
