Reducing Degeneracy in Maximum Entropy Models of Networks

Based on Jaynes’s maximum entropy principle, exponential random graphs provide a family of principled models that allow the prediction of network properties as constrained by empirical data (observables). However, their use is often hindered by the degeneracy problem characterized by spontaneous symmetry breaking, where predictions fail. Here we show that degeneracy appears when the corresponding density of states function is not log-concave, which is typically the consequence of nonlinear relationships between the constraining observables. Exploiting these nonlinear relationships here we propose a solution to the degeneracy problem for a large class of systems via transformations that render the density of states function log-concave. The effectiveness of the method is demonstrated on examples.

Figure 1

Degenerate ERG models. Plots are from exact enumeration of all labeled graphs on $N=9$ nodes. (a) The counting function $\mathcal{N}(m_{|},m_{\vee })$. Color intensity is proportional to the value of $\mathcal{N}$, white means $\mathcal{N}=0$ there. (b) Distribution $p(\mathbf{m};\mathit{\beta })$ from $\mathrm{ERG}(m_{|},m_{\vee })$ at ${\beta }_{|}^0=2.20$ and ${\beta }_{\vee }^0=-0.313$, corresponding to the black dot. (c) $\mathcal{N}(m_{|},m_{▵})$. (d) $p(\mathbf{m};\mathit{\beta })$ from $\mathrm{ERG}(m_{|},m_{▵})$ with ${\beta }_{|}^0=1.24$ and ${\beta }_{\mathrm{\Delta }}^0=-0.610$ from the black dot. Insets show 3D versions of the intensity plots. Note from Eq. (4) that the domains of $\mathcal{N}$ and $p$ always coincide.

Figure 2

Domain $\mathcal{D}$ (black dots) and its convex hull (purple shading); the averages $⟨\mathbf{m}⟩$ take their values from the convex hull. The orange line is $m_{\vee }\sim {m_{|}}^2$. (a) $\mathrm{ERG}(m_{|},m_{\vee })$, in $(m_{|},m_{\vee })$ space. Note the large region of possible $⟨\mathbf{m}⟩$ values with no realizable graphs (no black dots). (b) $\mathrm{ERG}(m_{|}^2,m_{\vee })$, in $(m_{|}^2,m_{\vee })$ space. Now $\mathcal{D}$ and its convex hull almost coincide. (c) $\mathrm{ERG}(m_{|}^2,m_{\vee })$ in $(m_{|},m_{\vee })$, compare with (a).

Figure 3

Distribution of the edge count $m_{|}$ of the sampled graphs ($N=9$ nodes) in the $\mathrm{ERG}(m_{|},m_{|}^2)$ model at various parameter values, where $p(m_{|})\propto \mathcal{N}(m_{|})\exp (-\beta m_{|}-\gamma m_{|}^2)$.

Figure 4

Modeling the Zachary Karate Club data. Distributions for $\mathrm{ERG}(m_{|},m_{\vee })$ [(a), (c), (d)] and $\mathrm{ERG}(m_{|},\sqrt{m_{\vee }})$ [(b), (e)] after fitting. (a) $p(m_{|},m_{\vee })$ in $\mathrm{ERG}(m_{|},m_{\vee })$ and (b) $p(m_{|},m_{\vee })$ in $\mathrm{ERG}(m_{|},\sqrt{m_{\vee }})$. The crosshairs are at $(m_{|}^0,m_{\vee }^0)$. Insets are magnifications around $(m_{|}^0,m_{\vee }^0)$. Arrows (a) indicate the two modes of the degenerate distribution. (c)–(e) show $p(m_{\mathrm{\Delta }})$ in the two models. The red vertical lines are at $m_{\mathrm{\Delta }}^0$ and the dashed ones are model averages.