The ground truth about metadata and community detection in networks

By Leto Peel, Daniel B. Larremore, Aaron Clauset. 2016

472 citations recorded by the source corpus.

Troubles with community detection in networks: No ground truth, no free lunch, and the complex coupling of metadata with structure. 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 these 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. 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 structures.

Subfields: Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

1. Nistor Grozavu
2. Younès Bennani
3. Issam Falih
4. Rushed Kanawati

In Statistical and Nonlinear Physics

1. Nistor Grozavu
2. Younès Bennani
3. Issam Falih
4. Rushed Kanawati

Citations in the corpus

• Community Discovery in Dynamic Networks (2017, unknown): “Although several criticisms were opposed to this evaluation methodology (Peel et al., 2017) (e.”
• Community detection in Attributed Network (2018, background): “Recently, only few recent studies have addressed the problem of clustering in attributed networks [24]; [4]; [21].”