Random graph ensembles with many short loops

¹ Institute for Mathematical and Molecular Biomedicine, King’s College London, Hodgkin Building, London SE1 1UL, United Kingdom
² Randall Division of Cell and Molecular Biophysics, King’s College London, New Hunts House, London SE1 1UL, United Kingdom
³ London Institute for Mathematical Sciences, 35a South St, Mayfair, London W1K 2XF, United Kingdom

Abstract

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.

Résumé

Les réseaux observés dans la Nature ont souvent des cycles courts. Ceci contredit le postulat de hiérarchie sur lequel se base la majorité des modèles de réseaux aléatoires et la plupart des méthodes utilisées pour leur analyse. Dans cet article, nous esquissons des directions de recherches possibles, afin de progresser sur les réseaux contenant beaucoup de cycles courts, faisant appel à des modèles de réseaux aléatoires éprouvés ou nouveaux, et des idées pour de nouvelles méthodes mathématiques. Nous ne présentons pas de solutions définitives, mais notre but est d’encourager et de stimuler de nouveaux travaux dans ce que nous croyons être une direction de recherche importante, bien que insuffisamment explorée. Nous discutons en détail le modèle de Strauss, qui peut être considéré comme ‘l’oscillateur harmonique’ des réseaux aléatoires ‘à boucles’, ainsi qu’un modèle immunologique soluble exactement qui comporte des réseaux aléatoires avec de nombreux cliques et cycles courts.