Please register for the CV & Online Identity Workshop below.

Subgraphs contain important information about network structures and their functions. But where can we find these subgraphs in random graphs? We investigate this by using optimization problems that identifies the dominant structure of any given subgraph. The optimizer describes the degrees and the spatial locations of the vertices that together create the most likely subgraph. On the popular hyperbolic random graph model, our optimization method shows the trade-off between geometry and popularity: some subgraphs are most likely formed by vertices that are close by, whereas others are most likely formed by vertices of high degree. This insight makes it possible to create new statistics that detect the presence of an underlying hyperbolic spatial structure, and is also able to detect global network phenomena such as maximal clique structures.