2024 FFT

Modifications of the Chung-Lu Graph Model

Franklin Kenter (USNA)

Abstract: The Chung-Lu graph model specifies the expected degree of each vertex in a graph and, provided the degree distribution is not excessively skewed, generates a random graph where the existence of each edge is determined independently.

A common characteristic of many “real-world” graphs is a degree distribution that follows an inverse power law. Specifically, the number of vertices with degree $x$ is proportional to $x^\beta$, where $\beta$ typically ranges between 1 and 3. The Chung-Lu model offers a straightforward approach to capturing this power-law behavior in synthetic networks.

We extend the Chung-Lu model to random geometric graphs. In this extension, each vertex is assigned both an expected degree and a random position in Euclidean space according to a probability distribution. Once the vertices are placed, the realization of each edge occurs independently of others. We rigorously establish the conditions necessary to ensure that the assigned degrees align with the expected degrees. This geometric Chung-Lu model is tested on the connectome of the \emph{Drosophila} medulla (fruit fly), where the random model successfully replicates the graph-theoretical structure of the original network.

Additionally, we propose a modification of the Chung-Lu model for bipartite graphs, demonstrating that a quadratic power-law fit (rather than a strict linear power-law) provides a better fit for biologically-based bipartite networks.

This work is a collaboration with Susama Agarwala and Seth Hanson.