Measuring directed triadic closure with closure coefficients

Bibliographic Data

ID6161371
AuthorsHao Yin (0000-0001-5305-0069, Institute of Mathematical Statistics), Austin R Benson (0000-0001-6110-1583, Cornell University), Johan Ugander (0000-0001-5655-4086, Stanford University, corresponding author)
Year2020
Volume8
Issue4
Pages551-573
Publication date2020-06-01
Peer ReviewedYes
Open AccessYes
TypeARTICLE
VenueNetwork Science (JOURNAL)
Journal identifiersISSN: 2050-1250 • E-ISSN: 2050-1242
PublisherCambridge University Press (PUBLISHER • US)
DOI10.1017/nws.2020.20
OpenAlexW2945032504
LanguageEN
References cited15

Recent work studying triadic closure in undirected graphs has drawn attention to the distinction between measures that focus on the “center” node of a wedge (i.e., length-2 path) versus measures that focus on the “initiator,” a distinction with considerable consequences. Existing measures in directed graphs, meanwhile, have all been center-focused. In this work, we propose a family of eight directed closure coefficients that measure the frequency of triadic closure in directed graphs from the perspective of the node initiating closure. The eight coefficients correspond to different labeled wedges, where the initiator and center nodes are labeled, and we observe dramatic empirical variation in these coefficients on real-world networks, even in cases when the induced directed triangles are isomorphic. To understand this phenomenon, we examine the theoretical behavior of our closure coefficients under a directed configuration model. Our analysis illustrates an underlying connection between the closure coefficients and moments of the joint in- and out-degree distributions of the network, offering an explanation of the observed asymmetries. We also use our directed closure coefficients as predictors in two machine learning tasks. We find interpretable models with AUC scores above 0.92 in class-balanced binary prediction, substantially outperforming models that use traditional center-focused measures

Advanced Graph Neural Networks · Complex Network Analysis Techniques · Graph theory and applications