File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection

TitleImplicit models, latent compression, intrinsic biases, and cheap lunches in community detection
Authors
Issue Date23-Aug-2023
PublisherAmerican Physical Society
Citation
Physical Review E, 2023, v. 108, n. 2 How to Cite?
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, while 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. Here we present a solution to this problem that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows us to compute 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. Our 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 our framework, we compare a number of community detection methods on artificial networks and on a corpus of over 500 structurally diverse empirical networks. We find that more expressive community detection methods exhibit consistently superior compression performance on structured data instances, without having degraded performance on a minority of situations where more specialized algorithms perform optimally. Our results undermine the implications of the “no free lunch” theorem for community detection, both conceptually and in practice, since it is confined to unstructured data instances, unlike relevant community detection problems which are structured by requirement.


Persistent Identifierhttp://hdl.handle.net/10722/338081
ISSN
2023 Impact Factor: 2.2
2023 SCImago Journal Rankings: 0.805

 

DC FieldValueLanguage
dc.contributor.authorTiago, P Peixoto-
dc.contributor.authorAlec, Kirkley-
dc.date.accessioned2024-03-11T10:26:07Z-
dc.date.available2024-03-11T10:26:07Z-
dc.date.issued2023-08-23-
dc.identifier.citationPhysical Review E, 2023, v. 108, n. 2-
dc.identifier.issn2470-0045-
dc.identifier.urihttp://hdl.handle.net/10722/338081-
dc.description.abstract<p>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, while 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. Here we present a solution to this problem that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows us to compute 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. Our 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 our framework, we compare a number of community detection methods on artificial networks and on a corpus of over 500 structurally diverse empirical networks. We find that more expressive community detection methods exhibit consistently superior compression performance on structured data instances, without having degraded performance on a minority of situations where more specialized algorithms perform optimally. Our results undermine the implications of the “no free lunch” theorem for community detection, both conceptually and in practice, since it is confined to unstructured data instances, unlike relevant community detection problems which are structured by requirement.<br></p>-
dc.languageeng-
dc.publisherAmerican Physical Society-
dc.relation.ispartofPhysical Review E-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.titleImplicit models, latent compression, intrinsic biases, and cheap lunches in community detection-
dc.typeArticle-
dc.identifier.doi10.1103/PhysRevE.108.024309-
dc.identifier.scopuseid_2-s2.0-85169300119-
dc.identifier.volume108-
dc.identifier.issue2-
dc.identifier.eissn2470-0053-
dc.identifier.issnl2470-0045-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats