MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Random Graphs with Motifs

Anatol Wegner


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.

Sep 20, 2011
Sep 26, 2011
MSC Codes:
05C80, 05C82, 90B15
random graphs, complex networks, network motifs

Related publications

2011 Repository Open Access
Anatol E. Wegner

Random graphs with motifs