Statistical properties of community structure in large social and information networks

TLDR

Community detection has been extensively studied, with communities defined as groups of nodes that exhibit denser internal connections than external ones. The study aims to characterize how the statistical and structural properties of communities vary with their size. The authors introduce the network community profile plot, based on conductance, and analyze it across 70 large sparse real‑world networks from diverse domains. The results reveal a more nuanced view of community structure in large real‑world networks than previously recognized.

Abstract

A large body of work has been devoted to identifying community structure in networks. A community is often though of as a set of nodes that has more connections between its members than to the remainder of the network. In this paper, we characterize as a function of size the statistical and structural properties of such sets of nodes. We define the network community profile plot, which characterizes the "best" possible community - according to the conductance measure - over a wide range of size scales, and we study over 70 large sparse real-world networks taken from a wide range of application domains. Our results suggest a significantly more refined picture of community structure in large real-world networks than has been appreciated previously.