The week's pick
Reseach Article
A new Pre-processing Strategy for Improving Community Detection Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 119 - Number 16 |
| Year of Publication: 2015 |
| Authors: A . Meligy, Ahmed H. Samak, Mai E. Saad |
10.5120/21151-4144
|
A . Meligy, Ahmed H. Samak, Mai E. Saad . A new Pre-processing Strategy for Improving Community Detection Algorithms. International Journal of Computer Applications. 119, 16 ( June 2015), 16-20. DOI=10.5120/21151-4144
Abstract
In the study of complex networks, a network is said to have community structure if it divides naturally into groups of nodes with dense connections within groups and only sparser connections between them. Detecting communities from complex networks has attracted attention of researchers in a wide range of research areas, from biology to sociology and computer science. In this paper, we introduce a new approach to make existing community detection algorithms execute with better results. Our method enhancing community detection algorithms by applying a pre-processing step that exploits betweenness for nodes and edges, to maps unweighted graph onto a weighted graph. It has been tested in conjunction with four algorithms, namely the Louvain method, SOM algorithm, VOS clustering, and Danon algorithm. Experimental results show that our edge weighting strategies raises modularity for existing algorithms.
References
- F. Borko, "Hand book of Social Network Technologies and Applications" 2010, Springer.
- M. Girvan, M. E. J. Newman, "Community structure in social and biological networks", Proceedings of the National Academy of Sciences (PNAS), 99(12), 7821–7826, 2002.
- M. E. J. Newman, "Modularity and community structure in networks", Proceedings of theNational Academy of Sciences (PNAS), 103(23), 8577–8582, 2006
- S. Fortunato, M. Barthelemy, "Resolution limit in community detection" , Proceedings of the National Academy of Sciences (PNAS), 104(1), 36–41, 2007
- A. Clauset, M. E. J. Newman, C. Moore, " Finding community structure in very large networks ",Physical Review E, 70(066111), 1–6, 2004.
- J. Duch, A. Arenas," Community identification using extremal optimization", Physical Review E, 72 (027104) , (2005).
- V. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, "Fast unfolding of communities in large networks, Journal of Statistical Mechanics", Theory and Experiment ,10, (P10008), (2008).
- F. Radicchi, C. Castellano , F. Cecconi , V. Loreto , D. Parisi ," Self-contained algorithms to detect communities in networks", Proceedings of the National Academy of Sciences,101:2658, USA 2004.
- G. Palla, I. Derenyi, I. Farkas, T. Vicsek. "Uncovering the overlapping community structure of complex networks in nature and society", Nature 435, 814 (2005).
- L. Donetti, MA. Munoz," Detecting network communities: a new systematic and efficient algorithm", Journal of Statistical MechanicsP10012, 2004.
- S. Gregory, "Finding overlapping communities in networks by label propagation". New Journal of Physics 12:103018, 2010.
- P. DeMeo, E. Ferrara, G. Fiumara, A. Ricciardello, "A novel measure of edge centrality in social networks", Knowledge-Based Systems 136–150. (2012).
- P DeMeo, E. Ferrara, G. Fiumara, and A. Provetti," Enhancing community detection using a network weighting strategy" . Information Sciences, 222:648-668, (2013).
- P DeMeo, E Ferrara, G Fiumara, and A Provetti. "Mixing local and global information for community detection in large networks". Journal of Computer and System Sciences, 2012.
- M. Rosvall, CT. Bergstorm, "Maps of random walks on complex networks reveal community structure", Proceedings of the National Academy of Sciences;105:1118–23 ,USA 2008.
- M. Porter, J. Onnela, P. Mucha, Communities in networks, Notices of the American Mathematical Society 56 (9) 1082–1097,(2009).
- S. Fortunato," Community detection in graphs", Physics Reports 486 (3–5) 75–174,(2010).
- Z. Wang, A. Scaglione, and R. J. Thomas, "Electrical CentralityMeasures for Electric Power Grid Vulnerability Analysis," presented at the 49th IEEE Conference on Decision and Control , pp. 5792-5797, 15-17 Dec. 2010.
- Z. Li, R. Wang, X. Zhang, and L. Chen, "Self-organizing map of complex networks for community detection", Journal of Systems Science and Complexity, 23(5), 931-941, 2010.
- N. J. Van Eck, L. Waltman, "VOS: A new method for visualizing similarities between objects. In H. -J. Lenz & R. Decker (Eds. ), Advances in data analysis", Proceedings of the 30th Annual Conference of the German Classification Society (pp. 299–306) , Springer (2007).
- L. Danon, A. Díaz-Guilera, A. Arenas," The effect of size heterogeneity on community identification in complex networks" , J. Stat. Mech. 11 (2006).
- L. Waltman, , N. J. van Eck, and E. Noyons, " A unified approach to mapping and clustering of bibliometric networks", Journal of Informetrics,. 4(4): p. 629-6352010.
- M. E. J. Newman," Fast algorithm for detecting community structure in networks", Phys. Rev. E 69 (6) 066133,(2004).
- W. Zachary, "An information flow model for conflict and fission in small groups", Journal of Anthropological Research, 33:452–473, 1977.
- D. Lusseau, K. Schneider, J. Oliver Boisseau, P. Haase, E. Slooten, and S. Dawson," The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations", Behavioral Ecology and Sociobiology, 54(4):396–405, 2003.
- V. Krebs, [http://www. orgnet. com/].
- M. E. J. Newman. "Finding community structure in networks using the eigenvectors of matrices" ,Phys. Rev. E, 74:036104, 2006.
- P. Gleiser and L Danon. " Community structure in jazz", Advances in Complex Systems, 06(04):565–573, 2003.
Index Terms
Keywords