graphspaces

Metadata and Network Community Detection

Do you really think that's ground truth you're detecting? - Morpheus, The Matrix (1999) [unverified].

This paper is all about how we validate community detection algorithms. After derivation, analysis, and testing on synthetic data, what we really want to do is figure out how well our community detection algorithm works when confronted with real-world networks. After all, that's the whole point: to use community detection in the wild. But how do we know when an algorithm is doing a good job on real-world data?

Often, community detection algorithms are measured by their ability to recover the same groups as in a set of known node labels, also called metadata. Examples include gender labels in a social network, or trophic levels in a food web. While it is tempting to use metadata as the "correct" or "ground-truth" communities, we explain in this paper why this is generally not a good idea. We first do this using straightforward non-mathematical arguments, and then reinforce those arguments using rigorous mathematics.

However, all is not lost! Metadata are still useful. But rather than using as ground truth for validating algorithms, we introduce two new ways to learn about the network by learning about the metadata. These algorithms, called the Blockmodel Entropy Significance Test (BESTest) and the neoSBM, are derived in detail in the paper, and code for them is below.

Theorems, including a No Free Lunch Theorem for community detection, are paraphrased in the body of the paper, but their proofs are in the Supplementary Materials.

Publication

Code

In the paper, we describe two algorithms. Implementations of the Blockmodel Entropy Significance Test (BESTest) and the neoSBM are written in MATLAB and Python respectively.

If you are interested in porting the neoSBM to MATLAB or the BESTest to Python, please do so! We would be happy to acknowledge your contribution here!

Data

In the paper, we refer to data from the Zachary Karate Club, the Lazega Lawyers, and the Malaria var genes. Below, we provide our copies of those datasets and the correct citations for each.

  • [Karate Club .txt data]
  • W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res. pp. 452-473 (1977).
  • [Lazega Lawyers .mat data]
  • E. Lazega, The collegial phenomenon: The social mechanisms of cooperation among peers in a corporate law partnership (Oxford University Press on Demand, 2001).
  • [Malaria var .txt and .mat data]
  • D. B. Larremore, A. Clauset, C. O. Buckee, A network approach to analyzing highly re- combinant malaria parasite genes, PLoS Comput Biol 9, e1003268 (2013).

Abstract

Across many scientific domains, there is a common need to automatically extract a simplified view or coarse-graining of how a complex system's components interact. This general task is called community detection in networks and is analogous to searching for clusters in independent vector data. It is common to evaluate the performance of community detection algorithms by their ability to find so-called ground truth communities. This works well in synthetic networks with planted communities because such networks' links are formed explicitly based on those known communities. However, there are no planted communities in real world networks. Instead, it is standard practice to treat some observed discrete-valued node attributes, or metadata, as ground truth. Here, we show that metadata are not the same as ground truth, and that treating them as such induces severe theoretical and practical problems. We prove that no algorithm can uniquely solve community detection, and we prove a general No Free Lunch theorem for community detection, which implies that there can be no algorithm that is optimal for all possible community detection tasks. However, community detection remains a powerful tool and node metadata still have value so a careful exploration of their relationship with network structure can yield insights of genuine worth. We illustrate this point by introducing two statistical techniques that can quantify the relationship between metadata and community structure for a broad class of models. We demonstrate these techniques using both synthetic and real-world networks, and for multiple types of metadata and community structure.

Get in touch

larremore(at)santafe.edu