Graphlet-orbit Transitions (GoT): A fingerprint for temporal network comparison David Aparicio, Pedro Ribeiro and Fernando Silva 2018

Abstract

Given a set of temporal networks, from different domains and with different sizes, how can we compare them? Can we identify evolutionary patterns that are both (i) characteristic and (ii) meaningful? We address these challenges by introducing a novel temporal and topological network fingerprint named Graphlet-orbit Transitions (GoT). We demonstrate that GoT provides very rich and interpretable network characterizations. Our work puts forward an extension of graphlets and uses the notion of orbits to encapsulate the roles of nodes in each subgraph. We build a transition matrix that keeps track of the temporal trajectory of nodes in terms of their orbits, therefore describing their evolution. We also introduce a metric (OTA) to compare two networks when considering these matrices. Our experiments show that networks representing similar systems have characteristic orbit transitions. GoT correctly groups synthetic networks pertaining to well-known graph models more accurately than competing static and dynamic state-of-the-art approaches by over 30%. Furthermore, our tests on real-world networks show that GoT produces highly interpretable results, which we use to provide insight into characteristic orbit transitions.

Digital Object Identifier (DOI)

doi 10.1371/journal.pone.0205497

Publication in PDF format

pdf Download PDF

Journal/Conference/Book

PLoS One

Reference (text)

David Aparicio, Pedro Ribeiro and Fernando Silva. Graphlet-orbit Transitions (GoT): A fingerprint for temporal network comparison. In PLoS One, Vol. 13(10), e0205497, October, 2018.

Bibtex

@article{ribeiro-PLOS2018-GOT,
  author = {David Aparicio and  Pedro Ribeiro and Fernando Silva},
  title = {Graphlet-orbit Transitions (GoT): A fingerprint for temporal network comparison},
  doi = {10.1371/journal.pone.0205497},
  journal = {PLoS One},
  volume = {13},
  issue = {10},
  pages = {e0205497},
  month = {October},
  year = {2018}
}