Can we have null models of real networks? Maximum Entropy Random Loopy Graphs

18 February 2020
Fabián Aguirre-López

Real networks are highly clustered (large number of short cycles) in contrast with their random counterparts. The Erdős–Rényi model and the Configuration model will generate networks with a tree like structure, a feature rarely observed in real networks. This means that traditional random networks are a poor choice as null models for real networks. Can we do better than that? Maximum entropy random graph ensembles are the natural choice to generate such networks. By introducing a bias with respect to the number of short cycles in a degree constrained graph, we aim to get a random graph model with a tuneable number of short cycles [1,2]. Nevertheless, the story is not so simple. In the same way random unclustered graphs present undesired topology, highly clustered ones will do as well if one is not careful with the scaling of the control parameters relative to the system size. Additionally the techniques to generate and sample numerically from general biased degree constrained graph ensembles will also be discussed. The topological transition has an important impact on the computational cost to sample graphs from these ensembles. To take it one step further, a general approach using the eigenvalues of the adjacency matrix rather than just the number of short cycles will also be presented, [2].

[1] López, Fabián Aguirre, et al. "Exactly solvable random graph ensemble with extensively many short cycles." Journal of Physics A: Mathematical and Theoretical 51.8 (2018): 085101.
[2] López, Fabián Aguirre, and Anthony CC Coolen. "Imaginary replica analysis of loopy regular random graphs." Journal of Physics A: Mathematical and Theoretical 53.6 (2020): 065002.