Local Structure of Directed Networks

2007/07/31 by Ginestra Bianconi, Natali Gulbahce, Adilson E. Motter · 5 citations
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · #Algorithm #Complex Network Analysis Techniques #Complex network #Computer science #Directed graph #Evolving networks #Gene Regulatory Network Analysis #Interdependent networks #Opinion Dynamics and Social Influence #Physics #Statistical physics #Theoretical computer science #Work (physics) #cond-mat.dis-nn #physics.soc-ph

paper · pdf · doi:10.1103/physrevlett.100.118701

published as Phys. Rev. Lett. 100, 118701 (2008)

openalex publication_date 2008/03/20 · arxiv created 2008/04/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• An algorithm for counting circuits: Application to real-world and random graphs
• Loops of any size and Hamilton cycles in random scale-free networks
• Synchronization is optimal in nondiagonalizable networks
• Dynamical and Correlation Properties of the Internet
• Emergence of scaling in random networks
• Cut-offs and finite size effects in scale-free networks
• Perturbing general uncorrelated networks

Cited by

• Controlling edge dynamics in complex networks
• Potential Theory for Directed Networks
• Changing motif distributions in complex networks by manipulating rich-club connections
• Entropy of network ensembles
• Identifying polycentric urban structure using the minimum cycle basis of road network as building blocks

Related

• Networks, Dynamics, and the Small‐World Phenomenon
• Growing Directed Networks: Organization and Dynamics
• Larger holes as narrower degree distributions in complex networks
• Networks and their degree distribution, leading to a new concept of small worlds
• Directed Cycles as Higher-Order Units of Information Processing in Complex Networks