-
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
Catalog
Metrics
- Abstract views: 7947
- PDF Downloads: 4247
- Cited By: 0
下载:
