Measuring directed triadic closure with closure coefficients

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

• The Collegial Phenomenon

  E Lazega•The collegial phenomenon•2001

  Añadir item

• Social Network Analysis

  Open Access•Stanley Wasserman, Katherine Faust•Social Network Analysis•1994

  Añadir item

• Graphs over time

  Open Access•Jure Leskovec, Jon Kleinberg et al.•Proceedings of the eleventh ACM…•2005

  Añadir item

• Network Motifs

  Open Access•Ron Milo, S Shen-Orr et al.•Science•2002

  Añadir item

• Complex networks

  Open Access•Silvy Boccaletti, Latora et al.•Physics Reports•2006

  Añadir item

• Meeting Strangers and Friends of Friends

  Matthew O Jackson, Brian W Rogers•American Economic Review•2007

  Añadir item

• Community detection in graphs

  Open Access•Santo Fortunato•Physics Reports•2010

  Añadir item

• Random graphs with arbitrary degree distributions and their applications

  Open Access•M E J Newman, Steven H Strogatz et al.•Physical Review E•2001

  Añadir item

• Regularization Paths for Generalized Linear Models via Coordinate Descent

  Open Access•Jerome Friedman, Jerome H Friedman et al.•Journal of Statistical Software•2010

  Añadir item

• Collective dynamics of ‘small-world’ networks

  Open Access•Duncan J Watts, Steven H Strogatz•Nature•1998

  Añadir item

• The Structure and Function of Complex Networks

  M Newman, M E J Newman•SIAM Review•2003

  Añadir item

• Trust Management for the Semantic Web

  Open Access•Matthew Richardson, Rakesh Agrawal et al.•The semantic web•2003

  Añadir item

• Friendship networks and social status

  Open Access•Brian Ball, M E J Newman•Network Science•2013

  Añadir item