11 - Structure of random directed networks: the bow tie

Summary

Many real complex networks have directed links, a property that affects the network's navigability and large-scale topology. Here we present the percolation properties of such directed scale-free networks with correlated in- and out-degree distributions [SCbA⁺02]. We derive a phase diagram that indicates the existence of three regimes, determined by the values of the degree exponents. In the first regime, we attain the known directed percolation mean-field exponents. In contrast, the second and third regimes are characterized by anomalous mean-field exponents that we calculate analytically. In the third regime the network is resilient to random dilution, i.e., the percolation threshold is p_c → 0.

Introduction

Real networks are sometimes directed; for example, in social and economical networks, a node A gains information or acquires physical goods from node B, but node B does not necessarily get similar input from node A. Likewise, most metabolic reactions are one directional. Thus, changes in the concentration of molecule A affect the concentration of its product B, but the reverse is not true. Despite the directedness of many real networks, the modeling literature, with few notable exceptions [CRS⁺03, DMS01b, NSW01, SCbA⁺02], has focused mainly on undirected networks.