Source-linked AI summary
Edge direction and the structure of networks
Jacob G. Foster, David V. Foster, Peter Grassberger, Maya Paczuski
TL;DR
The paper addresses the lack of a disciplined approach to assortativity in directed networks, where edge direction is important for representing asymmetric interactions. It defines four directed assortativity measures and evaluates their significance against randomized networks across three network classes. The results reject a purely assortative-or-disassortative classification, revealing class-specific mixtures and exposing limitations in several theoretical models.
Problem
Directed-network assortativity had lacked a disciplined approach despite edge direction’s importance for representing asymmetric interactions and analyzing network structure.
Method
The paper defines four source-target degree correlations and assigns their significance by comparison with randomized networks preserving the in- and out-degree sequence.
Results
Many directed networks are mixtures of assortative and disassortative tendencies, while the measures reveal class patterns, separate similarly grouped networks, and expose model limitations.
Takeaways & Limitations
Directed networks should not be classified as purely assortative or disassortative; directed assortativity profiles provide benchmarks for comparing network classes and formation models.
Abstract
from arXiv · showhide
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.
Introduction
Assortativity captures whether similarly connected nodes link, but directed networks require separate degree correlations for source and target roles. The paper introduces statistically tested directed measures and applies them across network classes to reveal class-specific structure and challenge simple classifications.
- Motivation: Assortativity measures whether nodes with similar numbers of edges tend to connect, influencing network structure and dynamics.In undirected networks, positive Pearson correlation indicates assortativity, while negative correlation indicates disassortativity.
- Motivation: Edge direction is essential for analyzing asymmetric interactions, yet prior assortativity studies ignored direction or measured only some degree correlations.Direction also affects motif and community analysis in directed networks.
- Approach: The paper defines four directed measures: r(out, in), r(in, out), r(out, out), and r(in, in), pairing source and target degree types.The first index denotes the source-node degree and the second the target-node degree.
- Findings: Across online/social, food-web, and word-adjacency networks, the measures reveal common class patterns, distinguish networks previously grouped together, and test theoretical models.They identify substantially different profiles among online and social networks despite similar motif structure.
- Approach: Statistical significance is assessed against randomized networks preserving each network’s in- and out-degree sequence, then summarized in an Assortativity Significance Profile.The Z-score measures the real-world correlation’s deviation from the randomized ensemble in standard-deviation units.
Online and social networks.
Directed assortativity distinguishes network classes and reveals structure beyond ordinary degree correlations. Food webs combine multiple assortative and disassortative tendencies, while theoretical models reproduce some but not all observed patterns.
- Online and social networks: WWW assortativity links authorities with useful pages, and more than half of in-hubs are also out-hubs.These multihubs connect preferentially, while low in-degree pages connect preferentially to low out-degree pages.
- Online and social networks: The online-network analysis connects directed assortativity patterns to Web navigation and the bowtie structure.A densely interconnected, navigable core contrasts with less trusted or useful pages in small clusters or chains.
- Food webs: Food webs are disassortative in r(out, in), but their Z-adjusted values range from disassortative to assortative.After accounting for degree sequence, no common pattern remains for this measure.
- Food webs: Food webs are disassortative in r(in, out) and assortative in r(out, out) and r(in, in).The cross-degree pattern captures trophic-level structure, while same-degree assortativity may indicate interactions among similar trophic levels.
- Food webs: The cascade and niche models were tested against the directed assortativity patterns of the St. Marks food web.The passage identifies the models and comparison but does not state their quantitative agreement.
Word-adjacency networks.
Word-adjacency networks show strong disassortativity across directed measures, while model comparisons test whether frequency structure and proposed mechanisms reproduce the observed patterns. These results support using directed assortativity to evaluate network models.
- Word-adjacency networks: Word-adjacency networks are strongly disassortative in both raw directed assortativity and its assortativity significance profile.The effects on links between high-degree nodes range from a 3.8% to a 15.8% decrease.
- Word-adjacency networks: 3.8% to 15.8% decreases occur for high-degree links, from English-book to Japanese-book out-hub connections.These values describe the range reported for out-hub-to-out-hub linking effects.
- Word-adjacency networks: High word frequency increases both in-degree and out-degree, producing rauto > 0.86.Very frequent words generally have grammatical function but low semantic content.
- Word-adjacency networks: The Bipartite model generates negative values across all directed assortativity measures while reproducing the networks’ motif pattern.Its two node types represent high-frequency grammatical words and low-frequency content words with alternating adjacency constraints.
- Conclusions: Neither the Bipartite nor Scrambled text model reproduces realistic patterns in both r(α, β) and ASP(α, β).The paper notes that creating a mixture of assortative and disassortative behavior is non-trivial.
- Conclusions: Directed assortativity measures can test theoretical models for directed networks and help validate or falsify prevailing explanations.The paper also reports that the measures are computationally more tractable and scalable than motif analysis.
Cascade and Niche Models.
The supporting material documents the networks, directed-assortativity results, and model variability used to assess cascade and niche models alongside additional comparative figures. It reports that these models reproduce most common food-web behaviors, while the broader figures compare network similarities and class separation.
- Comparative Figures: Figure 5 measures pairwise network similarity using the dot product between normalized Assortativity Significance Profiles.The resulting correlation R_ij ranges from −1 to 1, with 1 indicating highly correlated profiles, and the three network classes are clearly visible with some overlap.
- Cascade and Niche Models: 500 instances per real-world network provide standard deviations for cascade- and niche-model r(α, β) values.The instances follow the procedures described for the two food-web models.
- Cascade and Niche Models: Cascade and niche models reproduce most common directed-assortativity behaviors in food webs robustly.The food-web model analysis includes standard deviations across model ensembles, with especially large standard deviations reported for the niche model.
- Comparative Figures: Omitting ASP(out, in) from the similarity calculation makes network classes more clearly visible.The additional directed measures therefore show greater discriminatory power than the typical assortativity measure, while political blogs remain separate from the other online networks.
- Supporting Tables: Tables 1 and 2 provide network properties and directed-assortativity results, while Table 3 reports food-web model standard deviations.Table 1 also documents trophic aggregation of identical-interaction species and removal of parasites from the Ythan food web.