Efficient Community Detection Using Power Graph Analysis
Proceedings of the 9th Workshop on Large-Scale and Distributed Informational Retrieval, page 21–26. New York, NY, USA, Association for Computing Machinery, (2011)DOI: 10.1145/2064730.2064738
Abstract
Understanding the structure of complex networks and uncovering the properties of their constituents has been for many decades at the center of study of several fundamental sciences, such as discrete mathematics and graph theory. Especially during the previous decade, we have witnessed an explosion in complex network data, with two cornerstone paradigms being the biological networks and the social networks. The large scale, but also the complexity, of these types of networks constitutes the need for efficient graph mining algorithms. In both examples, one of the most important tasks is to identify closely connected network components comprising nodes that share similar properties. In the case of biological networks, this could mean the identification of proteins that bind together to carry their biological function, while in the social networks, this can be seen as the identification of communities. Motivated by this analogy, we apply the Power Graph Analysis methodology, for the first time to the best of our knowledge, to the field of community mining. The model was introduced in bioinformatics research and in this work is applied to the problem of community detection in complex networks. The advances in the field of community mining allow us to experiment with widely accepted benchmark data sets, and our results show that the suggested methodology performs favorably against state of the art methods for the same task, especially in networks with large numbers of nodes.