Hyperbolae are no hyperbole: Modelling communities that are not cliques

Saskia Metzler, Stephan Günnemann, Pauli Miettinen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

Cliques are frequently used to model communities: A community is a set of nodes where each pair is equally likely to be connected. But studying real-world communities reveals that they have more structure than that. In particular, the nodes can be ordered in such a way that (almost) all edges in the community lie below a hyperbola. In this paper we present three new models for communities that capture this phenomenon. Our models explain the structure of the communities differently, but we also prove that they are identical in their expressive power. Our models fit to real-world data much better than traditional block models or previously-proposed hyperbolic models, both of which are a special case of our model. Our models also allow for intuitive interpretation of the parameters, enabling us to summarize the shapes of the communities in graphs effectively.

Original languageEnglish
Title of host publicationProceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
EditorsFrancesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages330-339
Number of pages10
ISBN (Electronic)9781509054725
DOIs
StatePublished - 2 Jul 2016
Event16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain
Duration: 12 Dec 201615 Dec 2016

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
Volume0
ISSN (Print)1550-4786

Conference

Conference16th IEEE International Conference on Data Mining, ICDM 2016
Country/TerritorySpain
CityBarcelona, Catalonia
Period12/12/1615/12/16

Fingerprint

Dive into the research topics of 'Hyperbolae are no hyperbole: Modelling communities that are not cliques'. Together they form a unique fingerprint.

Cite this