Local Structure of Directed Networks

Previous work on undirected small-world networks established the paradigm that locally structured networks tend to have a high density of short loops. On the other hand, many realistic networks are directed. Here we investigate the local organization of directed networks and find, surprisingly, that real networks often have very few short loops as compared to random models. We develop a theory and derive conditions for determining if a given network has more or less loops than its randomized counterparts. These findings carry broad implications for structural and dynamical processes sustained by directed networks.

Figure 1

Number of short directed and undirected loops in several networks, where different symbols correspond to the numerically determined values for the real and random counterparts of the networks. The lines indicate the theoretical predictions in Eqs. (1, 2) for random networks. Points on the $x$ axis indicate no loops.

Figure 2

Underlooped, overlooped, and undetermined regions in the ${\lambda }_{\mathrm{short}}\equiv \overline{\lambda }/(⟨k_{\mathrm{in}}{k}_{\mathrm{out}}⟩/⟨k_{\mathrm{in}}⟩)$ vs ${\lambda }_{\mathrm{long}}\equiv L_{\max }^{\mathrm{real}}/⟨L_{\max }^{\mathrm{rand}}⟩$ diagram, where $L_{\max }^{\mathrm{real}}$ and $L_{\max }^{\mathrm{rand}}$ are predicted using the BP algorithm. The points correspond to the predictions for both short and long loops for the networks in Table , except for the ND WWW, which is over-shortlooped and is not shown because it is difficult to calculate its ${\lambda }_{\mathrm{long}}$. The actual counting of the loops confirms the predictions (Table ).