George Tsatsaronis
Kjetil Nørvåg
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.
- V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of community hierarchies in large networks. Journal of Statistical Mechanics: Theory and Experiment, 10, 2008.Google Scholar
- M. Ciglan and K. Nørvåg. Fast detection of size-constrained communities in large networks. In WISE, pages 91--104, 2010. Google ScholarDigital Library
- A. Condon and R. M. Karp. Algorithms for graph partitioning on the planted partition model. Random Struct. Algorithms, 18(2):116--140, 2001. Google ScholarDigital Library
- M. Girvan and M. Newman. Community structure in cosial and biological networks. Proc. Natl. Acad. Sci. USA, 99:7821--7826, 2002.Google ScholarCross Ref
- A. Lancichinetti and S. Fortunato. Community detection algorithms: a comparative analysis. Phys Rev E Stat Nonlin Soft Matter Phys, 80(5 pt 2):056117, 2009.Google Scholar
- U. Raghavan, R. Albert, and S. Kumara. Near liner time algorithm to detect community structures in large-scale networks. Phys. Rev. E, 76(3):036106, 2007.Google ScholarCross Ref
- P. Ronhovde and Z. Nussimov. Multiresolution community detection for megascale netwroks by information-based replica correlations. Phys. Rev. E, 80(1):016109, 2009.Google ScholarCross Ref
- L. Royer, M. Reimann, B. Andreopoulos, and M. Schroeder. Unraveling protein networks with power graph analysis. PLoS Computational Biology, 4(7):e1000108, 2008.Google ScholarCross Ref
- G. Tsatsaronis, I. Varlamis, S. Torge, M. Reimann,K. Nørvåg, M. Schroeder, and M. Zschunke. How to become a group leader? or modelling author types based on graph mining. In Proc. of TPDL, 2011. Google ScholarDigital Library
Index Terms
- Efficient community detection using power graph analysis
Recommendations
Mining hidden community in heterogeneous social networks
LinkKDD '05: Proceedings of the 3rd international workshop on Link discoverySocial network analysis has attracted much attention in recent years. Community mining is one of the major directions in social network analysis. Most of the existing methods on community mining assume that there is only one kind of relation in the ...
Mining frequent cross-graph quasi-cliques
Joint mining of multiple datasets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in bioinformatics, jointly mining multiple gene expression datasets obtained by different ...
A Random Network Ensemble Model Based Generalized Network Community Mining Algorithm
ASONAM '11: Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and MiningThe ability to discover community structures from explorative networks is useful for many applications. Most of the existing methods with regard to community mining are specifically designed for assortative networks, and some of them could be applied to ...
Comments