Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
61/2011

Random Graphs with Motifs

Anatol Wegner

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.

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

Related publications

Preprint
2011 Repository Open Access
Anatol E. Wegner

Random graphs with motifs