Detecting the Structure of Social Networks using (\alpha, \beta)-Communities

An (\alpha,\beta)-community is a subset of vertices C with each vertex in C connected to at least \beta vertices of C (self-loops counted) and each vertex outside of C connected to at most \alpha vertices of C (\alpha<\beta). In this paper, we present a heuristic (\alpha,\beta)-Community algorithm, which in practice successfully finds (\alpha,\beta)-communities of a given size. The structure of (\alpha,\beta)-communities in several large-scale social graphs is explored, and a surprising core structure is discovered by taking the intersection of a group of massively overlapping (\alpha,\beta)-communities. For large community size k, the (\alpha,\beta)-communities are well clustered into a small number of disjoint cores, and there are no isolated (\alpha,\beta)-communities scattered between these densely-clustered cores. The (\alpha,\beta)-communities from the same group have significant overlap among them, and those from distinct groups have extremely small pairwise resemblance. The number of cores decreases as k increases, and there are no bridges of intermediate (\alpha,\beta)-communities connecting one core to another. The cores obtained for a smaller k either disappear or merge into the cores obtained for a larger $k$. Further, similar experiments on random graph models demonstrate that the core structure displayed in various social graphs is due to the underlying social structure of these real-world networks, rather than due to high-degree vertices or a particular degree distribution.This research was partially supported by the U.S. Air Force Office of Scientific Research under Grant FA9550-09-1-0675, the National Natural Science Foundation of China under Grant 60553001, and the National Basic Research Program of China under Grant 2007CB807900 and 2007CB807901