Detectability of macroscopic structures in directed asymmetric stochastic block model

We study the problem of identifying macroscopic structures in networks, characterizing the impact of introducing link directions on the detectability phase transition. To this end, building on the stochastic block model, we construct a class of nontrivially detectable directed networks. We find closed-form solutions by using the belief propagation method, showing how the transition line depends on the assortativity and the asymmetry of the network. Finally, we numerically identify the existence of a hard phase for detection close to the transition point.

Figure 1

Schematic showing a network generated with an asymmetric planted partition in the case of $q=3$. Probabilities of given edges are described by $p_{\text{in}}$, $p_{\text{out}}^{\left(1\right)}$, and $p_{\text{out}}^{\left(2\right)}$.

Figure 2

(a) Two-dimensional phase diagram of an asymmetric planted partition model with $q=3$ groups and average degree $c=6$, obtained numerically [23] for a network with $N=9\times {10}^4$ nodes. The color scale corresponds to the overlap between the inferred and the real nodes' assignment. The dashed black line represents the analytical approximation of Eq. (20). (b) Analytical critical lines with the number of groups equal to $q=3$ and varying average degree $c$. (c) Analytical critical lines with the network average degree $c=6$ and a varying number of groups $q$.

Figure 3

Phase diagrams of an asymmetric planted partition with $q=9$ groups and average degree $c=9$. Results obtained numerically [23], for networks with $N=3.6\times {10}^5$ nodes, using belief propagation with random initial conditions (red crosses) and initiated with the correct assignments (blue $\mathsf{X}$'s). The gray area approximates the hard phase regime, according to numerical results.