Clara Stegehuis: Optimal constrained and unconstrained subgraph structures

Abstract

Subgraphs contain important information about network structures and their functions. We investigate the presence of subgraphs in a random graph model with infinite-variance degrees. We introduce an optimization problem which identifies the dominant structure of any given subgraph. The unique optimizer describes the degrees of the vertices that together span the most likely subgraph and allows us count and characterize all subgraphs.

We then show that this optimization problem easily extends to other network structures, such as clustering, which expresses the probability that two neighbors of a vertex are connected. The optimization problem is able to find the behavior of network subgraphs in a wide class of random graph models.