April 26–30, 2010, Raleigh, North Carolina, USA | Jure Leskovec, Kevin J. Lang, Michael W. Mahoney
This paper presents an empirical comparison of algorithms for network community detection. The goal is to understand the performance and biases of various community detection methods on different types of networks. The authors evaluate several common objective functions used to formalize the notion of community quality and examine different classes of approximation algorithms that aim to optimize these functions. They also consider a size-resolved version of the optimization problem, which provides a finer lens for examining community detection algorithms.
The paper compares two graph partitioning algorithms: a spectral-based Local Spectral method and a flow-based Metis+MQI algorithm. It also considers several heuristic-based clustering algorithms that perform well in practice. The authors analyze the structural properties of clusters identified by these algorithms and how they depend on the size of the cluster.
The paper also discusses various objective functions used to measure community quality, including conductance, expansion, internal density, cut ratio, normalized cut, and maximum-ODF. These objective functions are compared to understand their performance and biases in identifying community-like clusters.
The authors also compute theoretical lower bounds on the conductance of cuts, which provide insights into the performance of graph partitioning algorithms. These lower bounds are used to evaluate the quality of clusters identified by different algorithms.
The paper concludes that the shape of the network community profile (NCP) is an intrinsic property of large networks and not an artifact of the approximation algorithm or the objective function. The NCP shows a "V" shape, indicating that small clusters are more community-like than larger clusters. This suggests that large real-world networks do not contain community-like sets of nodes that are better connected internally than externally, except at very small size scales.This paper presents an empirical comparison of algorithms for network community detection. The goal is to understand the performance and biases of various community detection methods on different types of networks. The authors evaluate several common objective functions used to formalize the notion of community quality and examine different classes of approximation algorithms that aim to optimize these functions. They also consider a size-resolved version of the optimization problem, which provides a finer lens for examining community detection algorithms.
The paper compares two graph partitioning algorithms: a spectral-based Local Spectral method and a flow-based Metis+MQI algorithm. It also considers several heuristic-based clustering algorithms that perform well in practice. The authors analyze the structural properties of clusters identified by these algorithms and how they depend on the size of the cluster.
The paper also discusses various objective functions used to measure community quality, including conductance, expansion, internal density, cut ratio, normalized cut, and maximum-ODF. These objective functions are compared to understand their performance and biases in identifying community-like clusters.
The authors also compute theoretical lower bounds on the conductance of cuts, which provide insights into the performance of graph partitioning algorithms. These lower bounds are used to evaluate the quality of clusters identified by different algorithms.
The paper concludes that the shape of the network community profile (NCP) is an intrinsic property of large networks and not an artifact of the approximation algorithm or the objective function. The NCP shows a "V" shape, indicating that small clusters are more community-like than larger clusters. This suggests that large real-world networks do not contain community-like sets of nodes that are better connected internally than externally, except at very small size scales.