Efficient Community Detection

Abstract

Given a large network, local community detection aims at finding the community that contains a set of query nodes and also maximises (minimises) a goodness metric. Furthermore, due to the inconvenience or impossibility of obtaining the complete network information in many situations, the detection becomes more challenging. This problem has recently drawn intense research interest. Various goodness metrics have been proposed. And most of them base on the statistical features of community structures, such as the internal density or external spareness. However, the metrics often result in unsatisfactory results by either including irrelevant subgraphs of high density, or pulling in outliers which accidentally match the metric for the time being. Further more, when in a highly overlapping environment such as social networks, the unconventional community structures make these metrics usually end up with a quite trivial detection result. In our work, we go for a alternative point of view on the formation of the communities, namely the assembly of nodes with different roles in the structure. With the new view point, we present two metrics which are proved to perform superiorly in traditional and complex environment respectively. Moreover, on realising a single metric is whatsoever limited in effectiveness as well as scope of application, we raise up a complete framework for the collaboration ofmetrics in the field, which also lands a base-stone for future innovations. The experiment results collected from Amazon, DBLP, Youtube and LivingJournal well certifies the effectiveness of the metrics. Show more