Local structure of directed networks

Abstract

Previous work on undirected small-world networks established the paradigm that locally structured networks tend to have 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 counterpart. These findings carry broad implications for structural and dynamical processes sustained by directed networks.

References in corpus (17)

• Emergence of scaling in random networks
• Dynamical and correlation properties of the Internet
• Cut-offs and finite size effects in scale-free networks
• Self-sustained activity in a small-world network of excitable neurons
• Synchronization is optimal in non-diagonalizable networks
• Topology of biological networks and reliability of information processing
• Generalized percolation in random directed networks
• Maximum Performance at Minimum Cost in Network Synchronization
• Number of loops of size h in growing scale-free networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Uncorrelated Random Networks
• Congestion-gradient driven transport on complex networks
• Statistics of Cycles: How Loopy is your Network?
• Random replicators with asymmetric couplings
• An algorithm for counting circuits: application to real-world and random graphs
• Perturbing General Uncorrelated Networks
• Mixing properties of growing networks and the Simpson's paradox

Cited by in corpus (32)

• Synchronization in complex networks
• Critical phenomena in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Controlling edge dynamics in complex networks
• Structure-based control of complex networks with nonlinear dynamics
• The entropy of network ensembles
• Potential Theory for Directed Networks
• Heterogeneous Bond Percolation on Multitype Networks with an Application to Epidemic Dynamics
• Inducing Effect on the Percolation Transition in Complex Networks
• Behavior patterns of online users and the effect on information filtering
• Epidemic threshold in directed networks
• Spectra of sparse regular graphs with loops
• Network structural origin of instabilities in large complex systems
• Sensitivity of directed networks to the addition and pruning of edges and vertices
• Enhancing synchronization by directionality in complex networks
• Analytical results for bond percolation and k-core sizes on clustered networks
• Universal driving structure of self-sustained oscillatory complex networks
• Inherent directionality explains the lack of feedback loops in empirical networks
• Sampling properties of directed networks
• Ranking by Loops: a new approach to categorization
• Circulation of a digital community currency
• Broken detailed balance and entropy production in directed networks
• From one-way streets to percolation on random mixed graphs
• Diversity of structural controllability of complex networks with given degree sequence
• Markov Chain Methods For Analyzing Complex Transport Networks
• Optimizing and controlling functions of complex networks by manipulating rich-club connections
• Improving controllability of complex networks by rewiring links regularly
• Unevenness of Loop Location in Complex Networks
• Generalized $k$-core pruning process on directed networks
• Characterizing cycle structure in complex networks
• The art of community detection
• TSAM: Temporal Link Prediction in Directed Networks based on Self-Attention Mechanism