Defining and evaluating network communities based on ground-truth

By Jaewon Yang, Jure Leskovec. 2012

2,350 citations recorded by the source corpus.

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 due to a plethora of definitions of network communities, intractability of methods for detecting them, and the issues with evaluation which stem from the lack of a reliable gold-standard ground-truth. In this paper, we distinguish between structural and functional definitions of network communities. Structural definitions of communities are based on connectivity patterns, like the density of connections between the community members, while functional definitions are based on (often unobserved) common function or role of the community members in the network. We argue that the goal of network community detection is to extract functional communities based on the connectivity structure of the nodes in the network. We then identify networks with explicitly labeled functional communities to which we refer as ground-truth communities. In particular, we study a set of 230 large real-world social, collaboration, and information networks where nodes explicitly state their community memberships. For example, in social networks, nodes explicitly join various interest-based social groups. We use such social 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 communities correspond to ground-truth functional communities. We study 13 commonly used structural definitions of 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 100 million nodes. The proposed method achieves 30 % relative improvement over current local clustering methods.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Hierarchical block structures and high-resolution model selection in large networks (2013, background): “[73] Jaewon Yang and Jure Leskovec, “Defining and evaluating network communities based on ground-truth,” in”
GraphMat: High performance graph analytics made productive (2015, methodology): “Friendster [34] 65,608,366 1,806,067,135 Pagerank, BFS Friendster community SSSP network”
Non-overlapping community detection (2018, neutral): “In (Yang and Leskovec 2012), eleven quality functions are reported.”
Community-Affiliation Graph Model for Overlapping Network Community Detection (2012, methodology): “We refer the reader to [30] for further discussion on the choice of definition of ground-truth for each network.”
Implicit Graph Neural Networks (2020, methodology): “For node classiﬁcation task, we consider the applications under both transductive (Amazon) (Yang and Leskovec, 2015) and inductive (PPI) (Hamilton et al., 2017) settings.”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, methodology): “As for social graphs, we collect Facebook and IMDB datasets from NetRep [44], as well as a LiveJournal dataset from SNAP [3].”
Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, background): “In our previous work [33, 34, 35] we found the above definitions of ground-truth to be reliable and robust.”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, background): “In addition to social-search, PPR is also used for a variety of other tasks across different domains: friend recommendation on Facebook [7], who to follow on Twitter [8], graph partitioning [9], community detection [10], and other applications [11].”
Graph Clustering with Graph Neural Networks (2020, neutral): “definition from [63]) and graph modularity [38].”
The ground truth about metadata and community detection in networks (2016, background): “Often in the community detection literature, several algorithms are tested on a range of networks to identify which performs best overall [12, 30, 31].”
Community Detection with Graph Neural Networks (2017, methodology): “Jure and his coauthors have done a lot of work in community detection in curating benchmark datasets, quantifying the quality of these datasets(Yang & Leskovec, 2012a), and also in making new algorithms for community detection by ﬁtting data to newly designed generative models (models that exhibit…”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “Which metric is used varies depending on the types of the community (i.e., disjoint or overlapping) and whether ground truth information is available [150].”
Structure and inference in annotated networks (2015, background): “This assumption, however, has been challenged by recent work that compared communities in real-world networks against “ground truth” metadata variables and found little correlation between the two [7, 8].”
Deep Twitter diving: exploring topical groups in microblogs at scale (2014, background): “In fact, the recent study [31] showed that communities iden-”
Community Discovery in Dynamic Networks (2017, neutral): “Studies about the relations between these quality functions can be found in (Creusefond et al. , 2016; Yang and Leskovec, 2015).”