Finding Statistically Significant Communities in Networks with Weighted Label Propagation
Open Access
- 1 January 2013
- journal article
- Published by Scientific Research Publishing, Inc. in Social Networking
- Vol. 02 (03), 138-146
- https://doi.org/10.4236/sn.2013.23012
Abstract
Various networks exist in the world today including biological, social, information, and communication networks with the Internet as the largest network of all. One salient structural feature of these networks is the formation of groups or communities of vertices that tend to be more connected to each other within the same group than to those outside. Therefore, the detection of these communities is a topic of great interest and importance in many applications and different algorithms including label propagation have been developed for such purpose. Speaker-listener label propagation algorithm (SLPA) enjoys almost linear time complexity, so desirable in dealing with large networks. As an extension of SLPA, this study presented a novel weighted label propagation algorithm (WLPA), which was tested on four real world social networks with known community structures including the famous Zachary's karate club network. Wilcoxon tests on the communities found in the karate club network by WLPA demonstrated an improved statistical significance over SLPA. Withthehelp of Wilcoxon tests again, we were able to determine the best possible formation of two communities in this network relative to the ground truth partition, which could be used as a new benchmark for assessing community detection algorithms. Finally WLPA predicted better communities than SLPA in two of the three additional real social networks, when compared to the ground truth.Keywords
This publication has 14 references indexed in Scilit:
- Significant Communities in Large Sparse NetworksPLOS ONE, 2012
- Finding Statistically Significant Communities in NetworksPLOS ONE, 2011
- Community detection in graphsPhysics Reports, 2009
- Towards real-time community detection in large networksPhysical Review E, 2009
- Modularity-maximizing graph communities via mathematical programmingZeitschrift für Physik B Condensed Matter, 2008
- Local method for detecting communitiesPhysical Review E, 2005
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Objective Criteria for the Evaluation of Clustering MethodsJournal of the American Statistical Association, 1971
- A Method for the Analysis of the Structure of Complex OrganizationsAmerican Sociological Review, 1955
- The Identification of Blocs in Small Political BodiesAmerican Political Science Review, 1927