Journal
SCIENCE ADVANCES
Volume 3, Issue 5, Pages -Publisher
AMER ASSOC ADVANCEMENT SCIENCE
DOI: 10.1126/sciadv.1602548
Keywords
-
Categories
Funding
- Interuniversity Attraction Poles (Belgian Scientific Policy Office)
- Actions de Recherche Concertees (Federation Wallonia-Brussels)
- Santa Fe Institute Omidyar Fellowship
- NSF grant [IIS-1452718]
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1452718] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 commonto 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, ormetadata, as ground truth. We show that metadata are not the same as ground truth and that treating themas such induces severe theoretical and practical problems. Weprove that no algorithmcan uniquely solve community detection, and we prove a general No Free Lunch theoremfor 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 ofmodels. We demonstrate these techniques using both synthetic and real-world networks, and formultiple types ofmetadata and community structures.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available