Research PapersNo Access

Estimating the optimal number of communities by cluster analysis

Dong Liu

School of Computer and Information Engineering, Henan Normal University, Xinxiang, Henan 453007, P. R. China

Engineering Technology Research Center for Computing Intelligence and Data Mining, Xinxiang, Henan 453007, P. R. China

E-mail Address: liudonghtu@gmail.com

Corresponding author.

Search for more papers by this author

Chuan Wang

School of Computer and Information Engineering, Henan Normal University, Xinxiang, Henan 453007, P. R. China

E-mail Address: wangch@htu.edu.cn

Search for more papers by this author

, and

Yun Jing

School of Computer and Information Engineering, Henan Normal University, Xinxiang, Henan 453007, P. R. China

E-mail Address: jingyun1991@hotmail.com

Search for more papers by this author

https://doi.org/10.1142/S0217979216500375Cited by:8 (Source: Crossref)

Abstract

How to identify community structure in complex network is of theoretical significance, which relates to help to analyze the network topology and understand the network works. Determining the optimal number of communities is a nontrivial problem in detecting community structure. In this paper, we propose a novel method for detecting the optimal number of communities. Based on the local random walk (LRW) measurement, the distance index between each pair of nodes of a network is calculated firstly. Then the optimal number of communities can be found based on the idea that community centers are characterized by a higher density than their neighbors and by a relatively large distance from nodes with higher densities. The experimental results show that the method is effective and efficient in both artificial and real-world networks.

Keywords:

PACS: 89.75.Fb

You currently do not have access to the full text article.
Recommend the journal to your library today!

References

1. M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. USA 99(12), 7821 (2002). Crossref, Web of Science, ADS, Google Scholar
2. M. Newman, Nature Phys. 8(1), 25 (2011). Crossref, Web of Science, ADS, Google Scholar
3. S. Fortunato, Phys. Rep. Rev. Sec. Phys. Lett. 486(3–5), 75 (2010). Crossref, Web of Science, ADS, Google Scholar
4. M. Chen, K. Kuzmin and B. K. Szymanski, IEEE Trans. 1(1), 46 (2014). Google Scholar
5. M. E. J. Newman, Proc. Natl. Acad. Sci. USA 103(23), 8577 (2006). Crossref, Web of Science, ADS, Google Scholar
6. Y. Xu, L. Chen and B. Li, Inf. Sci. 317, 278 (2015). Crossref, Web of Science, Google Scholar
7. U. Brandes et al., http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/3255. Google Scholar
8. S. Fortunato and M. Barthlemy, Proc. Natl. Acad. Sci. 104(1), 36 (2007). Crossref, Web of Science, ADS, Google Scholar
9. B. Karrer and M. E. J. Newman, Phys. Rev. E 83(1), 016107 (2011). Crossref, Web of Science, ADS, Google Scholar
10. Z.-Y. Zhang, Y. Wang and Y.-Y. Ahn, Phys. Rev. E 87(6), 062803 (2013). Crossref, Web of Science, ADS, Google Scholar
11. D. He et al., Plos One 9(1), e86899 (2014). Crossref, Web of Science, ADS, Google Scholar
12. Y. Wang and P. J. Bickel, arXiv:1502.02069 [math.ST]. Google Scholar
13. Y.-Y. Ahn, J. P. Bagrow and S. Lehmann, Nature 466(7307), 761 (2010). Crossref, Web of Science, ADS, Google Scholar
14. M. E. J. Newman, Phys. Rev. E 69(6), 066133 (2004). Crossref, Web of Science, ADS, Google Scholar
15. Z. Li et al., Physica A 391(4), 1770 (2012). Crossref, Web of Science, ADS, Google Scholar
16. B. He, L. Gu and X.-D. Zhang, J. Stat. Mech.: Theory Exp. 2012(02), P02012 (2012). Crossref, Web of Science, Google Scholar
17. K. Chen and J. Lei, arXiv:1411.1715 [Stat.ME]. Google Scholar
18. C. M. Le and E. Levina, arXiv:1507.00827 [Stat.ML]. Google Scholar
19. W. Liu and L. Lue, Eurphys. Lett. 89(5), 58007 (2010). Crossref, ADS, Google Scholar
20. W. Wang et al., Physica A 392, 6578 (2013). Crossref, Web of Science, ADS, Google Scholar
21. A. Rodriguez and A. Laio, Science 344(6191), 1492 (2014). Crossref, Web of Science, ADS, Google Scholar
22. D. J. Klein and M. Randic, J. Math. Chem. 12, 81 (1993). Crossref, Web of Science, Google Scholar
23. H. J. Zhou, Phys. Rev. E 67(6), 061901 (2003). Crossref, Web of Science, ADS, Google Scholar
24. L. Yen et al., Graph nodes clustering based on the commute-time kernel advances, in Advances in Knowledge Discovery and Data Mining, (eds.) Z.-H. Zhou, H. Li and Q. Yang (Springer, Berlin, 2007), pp. 1037–1045. Crossref, Google Scholar
25. F. Fouss et al., IEEE Trans. Knowl. Data Eng. 19, 355 (2007). Crossref, Web of Science, Google Scholar
26. L. Yen et al., Data Knowl. Eng. 68, 338 (2009). Crossref, Web of Science, Google Scholar
27. H. J. Zhou, Phys. Rev. E 67(4), 041908 (2003). Crossref, Web of Science, ADS, Google Scholar
28. W. Zachary, J. Anthropol. Res. 33(4), 452 (1977). Crossref, Web of Science, Google Scholar
29. D. Lusseau et al., Behav. Ecol. Sociobiol. 54(4), 396 (2003). Crossref, Web of Science, Google Scholar
30. A. Lancichinetti, S. Fortunato and F. Radicchi, Phys. Rev. E 78(4), 046110 (2008). Crossref, Web of Science, ADS, Google Scholar