Empirical comparison of algorithms for network community detection

By Jure Leskovec, Kevin J. Lang, Michael W. Mahoney. The Web Conference, 2010

1,079 citations recorded by the source corpus.

Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that "look like" good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.

Subfields: Computer Science Applications, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/3577c922fa467a3b0528bae0ba59252a3d0e753b

How researchers see this paper

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

In Computer Science Applications

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Big Data: A Survey (2014, background): “A community is represented by a subgraphic matrix, in which edges connecting vertexes in the sub-graph feature high density while the edges between two sub-graphs feature much lower density [142].”
Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec (2017, methodology): “Spectral Clustering has been widely used in fields such as community detection [20] and image segmentation [31].”
Defining and evaluating network communities based on ground-truth (2012, background): “Identifying such communities in networks [14], [6], [26], [9] has proven to be a challenging task [10], [18], [17] due to three reasons: There exist multiple structural deﬁnitions of network communities [5], [24]; Even if we would agree on a single common structural deﬁnition ( i.e. , a single…”
A survey of community search over big graphs (2019, methodology): “For a detailed survey of CD, please refer to the following survey and empirical evaluation papers: [8,44,48,71,83,88, 110,112,123,152,154,156,158,163,194,197].”
Uncover Topic-Sensitive Information Diffusion Networks (2013, methodology): “We compare it to the state-of-the-art method NETRATE [4] and MoNET [17], and then we show that TOPICCASCADE can perform significantly better in terms of both recovering the network structures and predicting the transmission time.”
Deep Twitter diving: exploring topical groups in microblogs at scale (2014, background): “These metrics [18] indicate the quality of the community structure (within the global Twitter network) formed by the members of these topical groups and hint at the potential detectability of these topical groups using graph theoretic approaches.”
Overlapping Communities Explain Core–Periphery Organization of Networks (2014, background): “Dense community overlaps also explain the mixed success of present community detection methods when applied to large networks [24], [27].”
Efficient community detection in large networks using content and links (2012, background): “compared a multitude of community discovery algorithms based on conductance sco re, and discovered the trade-off between clustering objective and community comp actness [16].”
An analysis of social network-based Sybil defenses (2010, background): “perform better (especially since different community detection algorithms have been shown to perform better on different networks [15]).”
Toward Scalable Systems for Big Data Analytics: A Technology Tutorial (2014, methodology): “Many methods have been proposed and compared for community detection [232], most of which are topology-based and rely on an objective function that captures the concept of the community structure.”
Clustering attributed graphs: Models, measures and methods (2015, methodology): “A comparison of clustering algorithms and measures has been provided by Leskovec et al. (2010), and more details concerning the limitations of these measures can be found in the works by Gaertler (2005) and Brandes et al. (2008).”
Graph based anomaly detection and description: a survey (2014, background): “…Dhillon et al., 2003], and its distributed variants [Papadimitriou and Sun, 2008]; dynamic community detection algorithms Tantipathananandh and Berger-Wolf [2009, 2011], Tantipathananandh et al. [2007], and empirical comparison of methods for network community detection [Leskovec et al., 2010].”
A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects (2013, background): “[51] compared several community detection methods by treating community quality as a function of size.”
On the permanence of vertices in network communities (2014, methodology): “Here we compare the optimal value of permanence for the obtained communities versus three popular scoring functions, namely modularity (Mod) [21], conductance (Con) [18] and cut-ratio (Cut) [19].”