Ordered community detection in directed networks

We develop a method to infer community structure in directed networks where the groups are ordered in a latent one-dimensional hierarchy that determines the preferred edge direction. Our nonparametric Bayesian approach is based on a modification of the stochastic block model (SBM), which can take advantage of rank alignment and coherence to produce parsimonious descriptions of networks that combine ordered hierarchies with arbitrary mixing patterns between groups. Since our model also includes directed degree correction, we can use it to distinguish nonlocal hierarchical structure from local in- and out-degree imbalance—thus, removing a source of conflation present in most ranking methods. We also demonstrate how we can reliably compare with the results obtained with the unordered SBM variant to determine whether a hierarchical ordering is statistically warranted in the first place. We illustrate the application of our method on a wide variety of empirical networks across several domains.

Figure 1

Illustration of the properties of rank alignment and coherence. Each panel shows an affinity matrix $e_{rs}$ with upstream entries ($r>s$) and shown in blue and downstream entries ($r<s$) shown in red, and lateral entries ($r=s$) shown in gray, and area of the square corresponding to the entry magnitude. High rank alignment means an overall abundance of upstream edges, whereas high rank coherence means an overall uniformity of pairwise alignments, ${\mathrm{\Delta }}_{rs}=e_{rs}-e_{sr}$.

Figure 2

Description length contribution $\mathrm{\Sigma }\left(\mathit{e}\right)$, as a function of the rank alignment $\mathrm{\Delta }/(E^{+}+E^{-})$, considering both maximal (solid lines) and minimal (dashed lines) rank coherence, for different fractions of lateral edges (as indicated by the legend), and a value of $E=5\times {10}^6$ and $B=100$. The solid horizontal line marks the value ${log}_2\left(\left(\genfrac{}{}{0.0pt}{}{B^2}{E}\right)\right)$ given by Eq. (25), and the shaded region below it corresponds to a relative compression of the ordered parametrization.

Figure 3

Inferred ordered group structure of the food web of Little Rock lake. Panel (a) shows the identified groups for each taxon, with the rank labels shown on the nodes. The edge colors indicate the direction: upstream (blue), downstream (red), and lateral (gray). Panel (b) shows the marginal posterior distribution of rank positions ${\pi }_i\left(r\right)$ (semitransparent green symbols, with opacity indicating probability) and mean value ${\overline{b}}_i$ (solid black symbols), for each species.

Figure 4

(a) SpringRank values for a network sampled uniformly at random with imposed in/out-degrees themselves sampled from Eq. (29), with $k=50$ and $N=1000$. (b) Same as panel (a) but with 500 additional upstream edges added uniformly at random between nodes with index in the range $[1,N/20]$ (shown in red). (c) Distribution of SpringRank score values for networks sampled uniformly at random with imposed degree sequence identical to panel (a). The solid vertical line marks the value obtained for the network considered in panel (b). (d) Marginal rank ${\overline{b}}_i$ obtained with the DC-OSBM for the same network as in panel (b).

Figure 5

Comparison of Kendall's rank correlation coefficient $\tau$ between the degree imbalance $d_i$ and rank $b_i$ for each network in our dataset, for both the degree-corrected and non-degree-corrected version of our model. The sloped dashed line shows the diagonal where the two values are the same.

Figure 6

Inferred dominance hierarchy and community structure of antagonistic animal behavior. The columns from left to right contain the results of the non-degree-corrected ordered SBM (OSBM), the degree-corrected ordered SBM (DC-OSBM), and the degree-corrected SBM (DC-SBM). The rows, from top to bottom, show the antagonistic interactions for a group of yellow baboons [38], female bighorn sheep [40], and ant workers [41]. Each panel shows the identified groups for each individual, with the rank labels shown on the nodes—except for the rightmost column, where the groups are not ordered. For the first two leftmost columns, the edge colors indicate the direction: upstream (blue), downstream (red), and lateral (gray). The colors for the rightmost column match the maximum matching with the middle column, and with the unmatched nodes highlighted in red. The panels show also the description length value for each fit.

Figure 7

Comparison between models for 251 empirical directed networks, listed in Appendix pp3. The values shown are the description length differences with respect to the best model, as indicated in the legend. The networks are ordered by the minimum description length value. The left inset shows the counts that each model type yields a shorter description length, and the right inset shows the distribution of fraction of upstream edges [$E^{+}/(E^{+}+E^{-})$ or zero if $E=E^0$] for networks that are best modelled by the DC-OSBM.

Figure 8

Comparison between the difference in description lengths between the DC-OSBM (${\mathrm{\Sigma }}_{\text{DC-OSBM}}$) and DC-SBM (${\mathrm{\Sigma }}_{\text{DC-SBM}}$) and their respective difference in number of groups, $B_{\text{DC-OSBM}}$ and $B_{\text{DC-SBM}}$, obtained for the networks in Fig. 7 (each point corresponds to an individual network).