Built independently by an author, for readers. Read the story and support ChapterPal

keyword

ground-truth communities

Ground-truth communities are groups of nodes in a network whose shared memberships or functional affiliations are known, observed, or explicitly established rather than inferred purely from the connectivity structure. In network science and graph analysis, these predetermined groupings serve as empirical baselines or gold standards used to benchmark, validate, and evaluate the accuracy of community detection algorithms. While algorithmic methods identify communities based on topological patterns, such as the density of links between nodes, ground-truth communities reflect authentic functional or social groupings, such as explicitly declared user interest groups, institutional departments, or biological modules. They provide a critical reference point for assessing how effectively mathematical and structural definitions of network clustering correspond to real-world relationships and functional organization.

1 item

Defining and evaluating network communities based on ground-truth

Defining and evaluating network communities based on ground-truth

Jaewon Yang, Jure Leskovec

OrganizationsStanford University

Why you should read this

Evaluates thirteen structural definitions of network communities against ground-truth data from 230 real-world networks, identifying the most reliable topological metrics and introducing a parameter-free community detection algorithm that scales to hundreds of millions of nodes.

Nodes in real-world networks organize into densely linked communities where edges appear with high concentration among the members of the community. Identifying such communities of nodes has proven to be a challenging task mainly due to a plethora of definitions of a community, intractability of algorithms, issues with evaluation and the lack of a reliable gold-standard ground-truth. In this paper we study a set of 230 large real-world social, collaboration and information networks where nodes explicitly state their group memberships. For example, in social networks nodes explicitly join various interest based social groups. We use such groups to define a reliable and robust notion of ground-truth communities. We then propose a methodology which allows us to compare and quantitatively evaluate how different structural definitions of network communities correspond to ground-truth communities. We choose 13 commonly used structural definitions of network communities and examine their sensitivity, robustness and performance in identifying the ground-truth. We show that the 13 structural definitions are heavily correlated and naturally group into four classes. We find that two of these definitions, Conductance and Triad-participation-ratio, consistently give the best performance in identifying ground-truth communities. We also investigate a task of detecting communities given a single seed node. We extend the local spectral clustering algorithm into a heuristic parameter-free community detection method that easily scales to networks with more than hundred million nodes. The proposed method achieves 30% relative improvement over current local clustering methods.

Added

2026-09-15