Directed closure measures for networks with reciprocity

Abstract

The study of triangles in graphs is a standard tool in network analysis, leading to measures such as the \emph{transitivity}, i.e., the fraction of paths of length $2$ that participate in triangles. Real-world networks are often directed, and it can be difficult to "measure" this network structure meaningfully. We propose a collection of \emph{directed closure values} for measuring triangles in directed graphs in a way that is analogous to transitivity in an undirected graph. Our study of these values reveals much information about directed triadic closure. For instance, we immediately see that reciprocal edges have a high propensity to participate in triangles. We also observe striking similarities between the triadic closure patterns of different web and social networks. We perform mathematical and empirical analysis showing that directed configuration models that preserve reciprocity cannot capture the triadic closure patterns of real networks.

Updated version; new results on expected directed closures for reciprocal configuration model

References in corpus (4)

• Clustering in Complex Directed Networks
• Signed Networks in Social Media
• Triadic Measures on Graphs: The Power of Wedge Sampling
• A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal

Cited by in corpus (7)

• Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
• Using Triangles to Improve Community Detection in Directed Networks
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling
• Reciprocal versus Parasocial Relationships in Online Social Networks
• Detecting highly cyclic structure with complex eigenpairs
• A space efficient streaming algorithm for triangle counting using the birthday paradox