Understanding topological mesoscale features in community mining

Abstract

Community detection has been one of the major topics in complex network research. Recently, several greedy algorithms for networks of millions of nodes have been proposed, but one of their limitations is inconsistency of outcomes. Kwak et al. propose an iterative reinforcing approach to eliminate inconsistency in detected communities. In this paper we delve into structural characteristics of communities identified by Kwak's method with 12 real networks. We find that about 40% of nodes are grouped into communities in an inconsistent way in Orkut and Cyworld. Interestingly, they are only two out of 12 networks whose community size distribution follow power-law. As a first step towards interpretation of communities, we use Guimera and Amaral's method to classify nodes into seven classes based on the z-score and the participation coefficient. Using the z-P analysis, we identify the roles of nodes in Karate and Autonomous System (AS) networks and match them against known roles for evaluation. We apply topological mesoscale information to compare two AS produced by Oliveira et al., and Dhamdhere and Dovrolis We report that even though their AS graphs differ in size, their topological characteristics are very similar.