B1361
Title: Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection in networks
Authors: Tiago Peixoto - CEU GmbH (Austria) [presenting]
Alec Kirkley - University of Hong Kong (Hong Kong)
Abstract: The task of community detection, which aims to partition a network into clusters of nodes to summarize its large-scale structure, has spawned the development of many competing algorithms with varying objectives. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model. In contrast, other methods are descriptive, dividing a network according to an objective motivated by a particular application, making it challenging to compare these methods on the same scale. A solution to this problem is presented that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows computing the description length of a network and its partition under arbitrary objectives, providing a principled measure to compare the performance of different algorithms without the need for ground truth labels. The approach also gives access to instances of the community detection problem that are optimal to any given algorithm and, in this way, reveals intrinsic biases in popular descriptive methods, explaining their tendency to overfit. Using the framework, a number of community detection methods are compared on artificial networks and a corpus of over 500 structurally diverse empirical networks. More expressive community detection methods consistently perform superior compression on structured data instances.
