Research PapersNo Access

QUANTITATIVE MEASURE FOR COMMUNITY DETECTION IN WEIGHTED NETWORKS

SHUZHONG YANG

Department of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044, China

Corresponding author.

Search for more papers by this author

and

SIWEI LUO

Department of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044, China

Search for more papers by this author

https://doi.org/10.1142/S0217984909021247Cited by:5 (Source: Crossref)

Abstract

Detecting communities in weighted networks is becoming a challenging and interesting work. In this paper, a novel quantitative measure called weighted normalized modularity density is proposed and optimized to detect communities in weighted networks. Both theoretical certifications on simple schematic examples and numerical experiments on a suit of simulated networks and real-world networks show that the proposed quantitative measure not only improves the resolution limit in optimizing weighted modularity, but also avoids the emergence of negative communities in optimizing weighted modularity density.

Keywords:

References

S. Zhanget al., Proteomics 7, 2856 (2007). Crossref, Web of Science, Google Scholar
H. Balakrishnan and N. Deo, Discovering communities in complex networks, Proc. 44th ACM Southeast Conf. (2006) pp. 280–285. Google Scholar
L. Danonet al., J. Stat. Mech. Theory & Experiment P09008 (2005). Google Scholar
S. Fortunato and C. Castellano, Community Detection in Graphs http://arxiv.org/abs/, 2007 , arXiv:0712.2716 . Google Scholar
I. Farkas, G. Palla and T. Vicsek, New J. Phys. 9(6), 180 (2007). Crossref, Web of Science, Google Scholar
Y. Fanet al., Physica A 377, 363 (2007). Crossref, Web of Science, ADS, Google Scholar
T. Heimoet al., J. Stat. Mech.: Theory & Experiment P08007 (2008). Google Scholar
S. Fortunato and M. Barthàlemy, PNAS 104, 36 (2007). Crossref, Web of Science, ADS, Google Scholar
J. M. Kumpulaet al., Eur. Phys. J. B 56, 41 (2007). Crossref, Web of Science, ADS, Google Scholar
Z. Liet al., Phys. Rev. E 77, 036109 (2008). Crossref, Web of Science, Google Scholar
M. Girvan and M. E. J. Newman, PNAS 99, 7821 (2002). Crossref, Web of Science, ADS, Google Scholar
M. E. J. Newman, Phys. Rev. E 69, 066133 (2004). Crossref, Web of Science, Google Scholar
R. Guimera and L. A. N. Amaral, Nature 433, 895 (2005). Crossref, Web of Science, ADS, Google Scholar
R. Guimera and L. A. N. Amaral, J. Stat. Mech. P02001 (2005). Google Scholar
J. Duch and A. Arenas, Phys. Rev. E 72, 027104 (2005). Crossref, Web of Science, Google Scholar
J. Shi and J. Malik, IEEE Trans. PAMI 22(8), 888 (2000). Crossref, Web of Science, Google Scholar
I. Dhillon, Y. Guan and B. Kulis, A unified view of kernel k-means, Spectral Clustering and Graph Cuts, UTCS Tech. Report #TR-04-25, 2004 . Google Scholar
A. J. Enright and C. A. Ouzounis, Bioinformatics 17(9), 853 (2001). Crossref, Web of Science, Google Scholar
M. E. J. Newman, Phys. Rev. E 036104 (2006). Google Scholar
S. Muff, F. Rao and A. Caflisch, Phys. Rev. E 72, 056107 (2005). Crossref, Web of Science, Google Scholar
H. Djidjev, A scalable multilevel algorithm for graph clustering and community structure detection, WAW (2006) pp. 117–128. Google Scholar
V. D. Blondelet al., J. Stat. Mech. P10008 (2008). Google Scholar