Random graph ensembles with many short loops

DOI10.1051/PROC/201447006MaRDI QIDQ3467502zbMATH OpenOpenAlexFDO

Authors Eric S. Roberts, A. C. C. Coolen

Publication date 2 February 2016

Published in ESAIM: Proceedings and Surveys (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1404.2769

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

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.

Recommendations

• Loops of any size and Hamilton cycles in random scale-free networks
• Circuits in random graphs: from local trees to global loops
• Exactly solvable random graph ensemble with extensively many short cycles
• Random graph models of social networks
• Random graphs and complex networks. Volume 1

Cited in

(3)

• Ensemble nonequivalence in random graphs with modular structure
• Circuits in random graphs: from local trees to global loops
• Imaginary replica analysis of loopy regular random graphs

This page was built for publication: Random graph ensembles with many short loops

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467502)