Efficient orbit-aware triad and quad census in directed and undirected graphs

Ortmann, Mark; Brandes, Ulrik

doi:10.1007/s41109-017-0027-2

by Mark Ortmann, Ulrik Brandes

Abstract:

The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches.

View PDF

Reference:

Mark Ortmann, Ulrik Brandes, "Efficient orbit-aware triad and quad census in directed and undirected graphs", Applied Network Science, vol. 2, no. 1, Jun 2017, pp. 13.

Bibtex Entry:

@article{ob-tqdug-16,
  author    = {Ortmann, Mark
               and Brandes, Ulrik},
  title     = {Efficient orbit-aware triad and quad census in directed and undirected graphs},
  journal   = {Applied Network Science},
  year      = {2017},
  month     = {Jun},
  day       = {15},
  volume    = {2},
  number    = {1},
  pages     = {13},
  abstract  = {The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches.},
issn={2364-8228},
  doi       = {10.1007/s41109-017-0027-2},
  url       = {http://dx.doi.org/10.1007/s41109-017-0027-2}
}