Random graph ensembles with many short loops

The analysis of real networks which contain many short loops requires novel methods, because they break the assumptions of tree-like models.

ESAIM: Proceedings and surveys 47, 97 (2014)

E. Roberts, T. Coolen

Random graph ensembles with many short loops

Networks observed in the real world often have many short loops. This violates the tree-like assumption that underpins the majority of random graph models and most of the methods used for their analysis. In this paper we sketch possible research routes to be explored in order to make progress on networks with many short loops, involving old and new random graph models and ideas for novel mathematical methods. We do not present conclusive solutions of problems, but aim to encourage and stimulate new activity and in what we believe to be an important but under-exposed area of research. We discuss in more detail the Strauss model, which can be seen as the ‘harmonic oscillator’ of ‘loopy’ random graphs, and a recent exactly solvable immunological model that involves random graphs with extensively many cliques and short loops.

More in Intelligence of graphs

  • Journal of Physics A

    Exactly solvable random graphs

    An explicit analytical solution reproduces the main features of random graph ensembles with many short cycles under strict degree constraints.

  • Journal of Physics A

    Tailored random graph ensembles

    New mathematical tools quantify the topological structure of large directed networks which describe how genes interact within a cell.

  • Journal of Physics A

    Entropies of graph ensembles

    Explicit formulae for the Shannon entropies of random graph ensembles provide measures to compare and reproduce their topological features.

  • Physical Review E

    Unbiased randomization

    Unbiased randomisation processes generate sophisticated synthetic networks for modelling and testing the properties of real-world networks.

  • Journal of Physics A

    Spin systems on Bethe lattices

    Exact equations for the thermodynamic quantities of lattices made of d-dimensional hypercubes are obtainable with the Bethe-Peierls approach.