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.
Random Graphs with Motifs
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.