LOCATING COMMUNITIES ON REAL DATASET GRAPHS USING SYNTHETIC COORDINATES
Abstract
One of the fundamental problems in social networking with a lot of potential applications is to detect effectively the communities that are created by the users' interaction. Other applications, such as finding web communities, uncovering the structure of social networks, or even analyzing a graph's structure to uncover Internet attacks are equally as important. All these problems converge to a common goal, the development of flexible and efficient local community detection algorithms. In this paper, we demonstrate the performance of an algorithm that uncovers the entire community structure of a network, based solely on local interactions between neighboring nodes and a distributed clustering algorithm. The proposed algorithm, named VCD, is based on the distributed computation of a synthetic coordinates for each graph node. Experimental results and comparisons with another method from the literature (Lancichinetti et al.) are presented. The algorithm is also tested on two real dataset graphs from the SNAP: Stanford Large Network Dataset Collection. In all cases the experimental results demonstrate the high performance of our algorithm in terms of accuracy to detect communities, and its computational efficiency.
This project is implemented through the Operational Program "ARCHIMEDE III: Education and Lifelong Learning" (project P2PCOORD) and is co-financed by the European Union (European Social Fund) and Greek national funds (National Strategic Reference Framework 2007 - 2013).
References
- Journal of Convergence Volume 2(1), (2011). Google Scholar
- F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM '04 Conference, August 2004 . Google Scholar
- IEEE Computer 35, 66 (2002), DOI: 10.1109/2.989932. Crossref, ISI, Google Scholar
- Proceedings of the National Academy of Sciences of the United States of America 99(12), 7821 (2002), DOI: 10.1073/pnas.122653799. Crossref, ISI, Google Scholar
- IEEE Transactions on Knowledge and Data Engineering 21, 137 (2009), DOI: 10.1109/TKDE.2008.92. Crossref, ISI, Google Scholar
- Physical Review E 80(5 Pt 2), 056117 (2009), DOI: 10.1103/PhysRevE.80.056117. Crossref, ISI, Google Scholar
- New Journal of Physics 11(3), 033015+ (2009), DOI: 10.1088/1367-2630/11/3/033015. Crossref, ISI, Google Scholar
- Physical Review E 69(2), 026113 (2004), DOI: 10.1103/PhysRevE.69.026113. Crossref, ISI, Google Scholar
- H. Papadakis, C. Panagiotakis, and P. Fragopoulou. Distributed community detection: Finding neighborhoods in a complex world using synthetic coordinates. Sixteenth IEEE Symposium on Computers and Communications (ISCC 2011), Corfu, Greece, June 2011 . Google Scholar
- Computer Science Review 1(1), 27 (2007), DOI: 10.1016/j.cosrev.2007.05.001. Crossref, ISI, Google Scholar
- International Journal of Information Technology, Communications and Convergence 1(1), 66 (2010), DOI: 10.1504/IJITCC.2010.035227. Crossref, ISI, Google Scholar


