Random Graphs with Motifs

Anatol Wegner

Contact the author: Please use for correspondence this email.
Submission date: 20. Sep. 2011 (revised version: September 2011)
Pages: 14
Bibtex
MSC-Numbers: 05C80, 05C82, 90B15
Keywords and phrases: random graphs, complex networks, network motifs
Download full preprint: PDF (527 kB)

Abstract:
We introduce and analyze a particular generalization of the Erdös-Rényi random graph model that is based on adding not only edges but also copies of small graphs onto the nodes of a graph. The resulting model is analytically tractable and can generate random graphs with a local structure that is not tree like. First, we introduce the simplest generalization called the triplet model corresponding to the addition of three node subgraphs and investigate some of its key properties. In the undirected model we obtain a random graph with non-zero clustering and assortativity while in the directed case we obtain a graph with triangular motifs. Then, we formulate our model in its full generality by allowing the addition of graphs of arbitrary size and generalize the results obtained for the triplet model.