Edge direction and the structure of networks
arXiv:0908.4288 · doi:10.1073/pnas.0912671107
Abstract
Directed networks are ubiquitous and are necessary to represent complex systems with asymmetric interactions---from food webs to the World Wide Web. Despite the importance of edge direction for detecting local and community structure, it has been disregarded in studying a basic type of global diversity in networks: the tendency of nodes with similar numbers of edges to connect. This tendency, called assortativity, affects crucial structural and dynamic properties of real-world networks, such as error tolerance or epidemic spreading. Here we demonstrate that edge direction has profound effects on assortativity. We define a set of four directed assortativity measures and assign statistical significance by comparison to randomized networks. We apply these measures to three network classes---online/social networks, food webs, and word-adjacency networks. Our measures (i) reveal patterns common to each class, (ii) separate networks that have been previously classified together, and (iii) expose limitations of several existing theoretical models. We reject the standard classification of directed networks as purely assortative or disassortative. Many display a class-specific mixture, likely reflecting functional or historical constraints, contingencies, and forces guiding the system's evolution.
13 pages, 6 figures, 3 tables
References in corpus (10)
- Community structure in directed networks
- Module identification in bipartite and directed networks
- Preferential attachment in the growth of social networks: the case of Wikipedia
- Wikipedias: Collaborative web-based encyclopedias as complex networks
- LinkRank: Finding communities in directed networks
- Random graph models for directed acyclic networks
- Networks of Recurrent Events, a Theory of Records, and an Application to Finding Causal Signatures in Seismicity
- Disassortative mixing in online social networks
- Graph animals, subgraph sampling and motif search in large networks
- Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
Cited by in corpus (47)
- Clustering and Community Detection in Directed Networks: A Survey
- Consistency and differences between centrality measures across distinct classes of networks
- Nestedness in complex networks: Observation, emergence, and implications
- Effect of correlations on network controllability
- Graph Neural Networks for Financial Fraud Detection: A Review
- Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph
- Characterizing and modeling an electoral campaign in the context of Twitter: 2011 Spanish Presidential Election as a case study
- Clustering Drives Assortativity and Community Structure in Ensembles of Networks
- Degree correlations in directed scale-free networks
- Regional and Sectoral Structures and Their Dynamics of Chinese Economy: A Network Perspective from Multi-Regional Input-Output Tables
- Structure controllability of complex network based on preferential matching
- Modeling the Network Dynamics of Pulse-Coupled Neurons
- Network-based statistical comparison of citation topology of bibliographic databases
- Sampling properties of directed networks
- Jointly they edit: examining the impact of community identification on political interaction in Wikipedia
- Randomizing growing networks with a time-respecting null model
- Circulation of a digital community currency
- Network properties of healthy and Alzheimer's brains
- Recurrent patterns of user behavior in different electoral campaigns: A Twitter analysis of the Spanish general elections of 2015 and 2016
- Emergence of scale-free close-knit friendship structure in online social networks
- Path-dependent connectivity, not modularity, consistently predicts controllability of structural brain networks
- Exploring the randomness of Directed Acyclic Networks
- Follow Whom? Chinese Users Have Different Choice
- Quantifying the consistency of scientific databases
- Node mixing and group structure of complex software networks
- The evolution of network controllability in growing networks
- Phase transitions for scaling of structural correlations in directed networks
- Local community extraction in directed networks
- More than Meets the Tie: Examining the Role of Interpersonal Relationships in Social Networks
- Improving controllability of complex networks by rewiring links regularly
- Assortativity measures for weighted and directed networks
- Mechanisms for tuning clustering and degree-correlations in directed networks
- The network asymmetry caused by the degree correlation and its effect on the bimodality in control
- Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
- How visas shape and make visible the geopolitical architecture of the planet
- Higher order assortativity for directed weighted networks and Markov chains
- Robustness and Directed Structures in Ecological Flow Networks
- Adversarial Attack on Large Scale Graph
- On the relationship between set-based and network-based measures of gender homophily in scholarly publications
- Analysing Collective Behaviour in Temporal Networks Using Event Graphs and Temporal Motifs
- The network structure of mathematical knowledge according to the Wikipedia, MathWorld, and DLMF online libraries
- Average shortest-path length in word-adjacency networks: Chinese versus English
- Effect of correlations on controllability transition in network control
- Genotype networks drive oscillating endemicity and epidemic trajectories in viral evolution
- Not all paths lead to Rome: Analysing the network of sister cities
- Evaluating the effects of high-throughput structural neuroimaging predictors on whole-brain functional connectome outcomes via network-based vector-on-matrix regression
- Superbubbles as an Empirical Characteristic of Directed Networks