The artificial intelligence of graphs

Predicting the behaviour of graphs and processes on them by treating topological patterns as constraints on a random graph ensemble.

Most real-world networks are either a snapshot of a graph that evolves over time, or one instance of a collection of related graphs. Some aspects of the graph are random while others—such as the connectivity or density of cycles—are fixed. The trick is to figure out which is which. By treating a graph as a random variable, it is possible to deduce the constraints by comparing the behaviour they give rise to with real data. This is hard, and nearly all random graphs that can be solved analytically are locally tree-like. But empirically we know that realistic graphs have short loops.

In this project we develop sophisticated mathematical methods for deducing the behaviour of graphs and processes on them. By treating topological patterns as constraints on a random graph ensemble, we go beyond the replica trick and cavity method to handle graphs with a finite fraction of short loops. We start with triangles, the “harmonic oscillator” of loopy random graphs, and proceed to larger loops, along the way introducing the imaginary replica technique.

The theory of tailored graph ensembles offers a deeper understanding of graph structure. It enables us to predict the null behaviour of neural and genetic regulatory networks and to detect network communities. It also offers an indirect approach to longstanding problems on lattices, like the 3D Ising model.

The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs
The artificial intelligence of graphs

Related papers

  • Placeholder

    Sub. to JPhys Complexity

    Transitions in loopy graphs

    The generation of large graphs with a controllable number of short loops paves the way for building more realistic random networks.

  • Placeholder

    Journal of Economic Interaction and Coordination

    Bursting dynamic networks

    A mathematical model captures the temporal and steady state behaviour of networks whose two sets of nodes either generate or destroy links.

  • Placeholder

    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.

  • Placeholder

    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.

  • Placeholder

    ESAIM: Proceedings and surveys

    Random graphs with short loops

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

  • Placeholder

    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.

  • Placeholder

    Physical Review E

    Unbiased randomization

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

  • Placeholder

    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.