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 transitivity, i.e., the fraction of paths of length two that participate in triangles. Real-world networks are often directed, and it can be difficult to meaningfully understand this network structure. We propose a collection of 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.

@article{SePiDuKo16,  
author = {C. Seshadhri and Ali Pinar and Nurcan Durak and Tamara G. Kolda}, 
title = {Directed Closure Measures for Networks with Reciprocity}, 
journal = {Journal of Complex Networks}, 
volume = {5}, 
number = {1}, 
pages = {32-47}, 
month = {April}, 
year = {2016},
doi = {10.1093/comnet/cnv032},
eprint = {1302.6220},
eprintclass = {cs.SI},
}