| INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
Prev
Next
|
|
|
An improvement of the fast uncovering community algorithm |
| Wang Li (王莉)a b, Wang Jiang (王将)a b, Shen Hua-Wei (沈华伟)b, Cheng Xue-Qi (程学旗)b |
a College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024, China;
b Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China |
|
|
|
|
Abstract Community detection methods have been used in computer, sociology, physics, biology, and brain information science areas. Many methods are based on the optimization of modularity. The algorithm proposed by Blondel et al. (Blondel V D, Guillaume J L, Lambiotte R and Lefebvre E 2008 J. Stat. Mech. 10 10008) is one of the most widely used methods because of its good performance, especially in the big data era. In this paper we make some improvements to this algorithm in correctness and performance. By tests we see that different node orders bring different performances and different community structures. We find some node swings in different communities that influence the performance. So we design some strategies on the sweeping order of node to reduce the computing cost made by repetition swing. We introduce a new concept of overlapping degree (OV) that shows the strength of connection between nodes. Three improvement strategies are proposed that are based on constant OV, adaptive OV, and adaptive weighted OV, respectively. Experiments on synthetic datasets and real datasets are made, showing that our improved strategies can improve the performance and correctness.
|
Received: 14 May 2013
Revised: 09 June 2013
Accepted manuscript online:
|
|
PACS:
|
89.75.Fb
|
(Structures and organization in complex systems)
|
| |
89.75.Hc
|
(Networks and genealogical trees)
|
|
| Fund: Project supported by the Major State Basic Research Development Program of China (Grant Nos. 2013CB329602 and 2012CB316303), the Science Research Foundation for the Returned Overseas Chinese Scholars, China (Grant No. 2010-31), the International Collaborative Project of Shanxi Province, China (Grant No. 2011081034), and the National Natural Science Foundation of China (Grant Nos. 61232010 and 61202215). |
Corresponding Authors:
Wang Li
E-mail: wangli2011@ict.ac.cn
|
Cite this article:
Wang Li (王莉), Wang Jiang (王将), Shen Hua-Wei (沈华伟), Cheng Xue-Qi (程学旗) An improvement of the fast uncovering community algorithm 2013 Chin. Phys. B 22 108903
|
| [1] |
Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113
|
| [2] |
Kernighan B W and Lin S 1970 Bell System Teeh. 49 291
|
| [3] |
Barnes E R 1982 SIAM J. Algebr. Discrete Methods 3 541
|
| [4] |
Flake G W, Lawrence S and Giles C L 2000 Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 20-23, 2000, Boston, USA, p. 150
|
| [5] |
Flake G W, Lawrence S, Giles C L and Coetzee F M 2002 IEEE Computer 35 66
|
| [6] |
Girvan M and Newman M.E.J 2002 Proc. Natl. Acad. Sci. USA 99 7821
|
| [7] |
Wang X H, Jiao L C and Wu J S 2010 Chin. Phys. B 19 020501
|
| [8] |
Fan C X, Wan Y H and Jiang G P 2012 Chin. Phys. B 21 020510
|
| [9] |
Cheng X Q and Shen H W 2011 Complex Systems and Complexity Science 8 46 (in Chinese)
|
| [10] |
Newman M E J 2004 Phys. Rev. E 69 066133
|
| [11] |
Clauset A, Newman M E J and Moore C 2004 Phys. Rev. E 70 066111
|
| [12] |
Danon L, Díaz-Guilera A and Arenas A 2006 J. Stat. Mech. 11 11010
|
| [13] |
Pujol J M, Bèjar J and Delgado J 2006 Phys. Rev. E 74 016107
|
| [14] |
Du H, Feldman M W, Li S and Jin X 2007 Complexity 12 53
|
| [15] |
Wakita K and Tsurumi T 2008 Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science 5211 408
|
| [16] |
Xiang B, Chen E H and Zhou T 2009 Studies in Computational Intelligence 207 73
|
| [17] |
Blondel V D, Guillaume J L, Lambiotte R and Lefebvre E 2008 J. Stat. Mech. 10 10008
|
| [18] |
Chen D, Shang M, Lü Z and Fu Y 2010 Physica A 389 4177
|
| [19] |
Li W 2011 Expert Systems with Applications 38 94
|
| [20] |
Shen H W, Cheng X Q, Cai K and Hu M B 2009 Physica A 388 1706
|
| [21] |
Li W, Bi Y J, Wu W L, Lian B and Xu W 2013 International Computing and Combinatorics Conference (COCOON), June 21-23, Hangzhou, China, p. 821
|
| [22] |
Santo F and Claudio C 2009 Encyclopedia of Complexity and Systems Science 25 1141
|
| [23] |
Fortunato S and Barthèlemy M 2007 Proc. Natl. Acad. Sci. USA 104 36
|
| [24] |
Guimer’a R, Pardo S M and Amaral L A N 2004 Phys. Rev. E 70 025101
|
| [25] |
Andrea L and Santo F 2011 Phys. Rev. E 84 066122
|
| [26] |
Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577
|
| [27] |
Danon L, Duch L, Guilera A D and Arenas A 2005 J. Stat. Mech. 9 P09008
|
| [28] |
Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110
|
| [29] |
Lancichinetti A and Fortunato S 2009 Phys. Rev. E 80 016118
|
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
