The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter

Daniel M. Romero, Jon Kleinberg

Abstract

It has often been taken as a working assumption that directed links in information networks are frequently formed by "short-cutting" a two-step path between the source and the destination -- a kind of implicit "link copying" analogous to the process of triadic closure in social networks. Despite the role of this assumption in theoretical models such as preferential attachment, it has received very little direct empirical investigation. Here we develop a formalization and methodology for studying this type of directed closure process, and we provide evidence for its important role in the formation of links on Twitter. We then analyze a sequence of models designed to capture the structural phenomena related to directed closure that we observe in the Twitter data.

Introduction: The Concept of Directed Closure

In the study of social networks, the principle of triadic closure is well-established: if Alice knows Bob and Bob knows Charlie, there is a heightened probability that Alice will eventually meet Charlie. This process creates triangles in undirected graphs. However, in directed information networks like Twitter or the World Wide Web, the dynamics are more complex.

The equivalent process in these networks is directed closure. If user A follows user B, and user B follows user C, user A may eventually follow user C directly. This "short-cutting" of a two-step path is often modeled as "link copying." While many theoretical growth models, such as preferential attachment, rely on this assumption, empirical evidence has been sparse. This paper provides a formal framework to measure this process and applies it to real-world data from Twitter.

The transition from undirected triadic closure to directed closure in information networks.

Methodology: A Temporal Framework

To rigorously study directed closure, the authors introduced a temporal framework. A directed triangle (A → B, B → C, A → C) only counts as an instance of closure if the shortcut edge (A → C) is created after the two-step path (A → B → C) is already in place.

The primary metric used is the Closure Ratio: the fraction of a node’s incoming edges that exhibit closure at the moment of their formation. To ensure that observed closure rates aren't merely a byproduct of high network density, the researchers employed a Randomization Test. By comparing the actual arrival order of edges against a random-ordering baseline, they could determine if an active mechanism—like a user browsing their friends' follow lists—was driving link formation.

Empirical Evidence from Twitter

The study focused on a sample of Twitter "$μ$-celebrities"—users with 10,000 to 50,000 followers. This demographic represents a diverse cross-section of the network, including journalists, artists, and niche experts, providing a richer dataset than global superstars.

The Heterogeneity Surprise

The data revealed that directed closure is a significant and non-random force on Twitter. However, the results also uncovered a surprising level of heterogeneity. Closure ratios are not uniform across the network; instead, different users exhibit vastly different "intrinsic" closure rates.

Empirical closure ratios for various Twitter micro-celebrities, showing stability and significant heterogeneity.

Key observations include:

  • Stability: For most users, the closure ratio stabilizes to a constant value relatively early in their growth. This suggests that the ratio is a stable property of a user's position within the network's social structure.
  • Follower Influence: A user's closure ratio is not determined by their total follower count. Rather, it correlates with the "fame" of their followers (the sum of their followers' in-degrees). Users followed by well-connected individuals are more likely to be discovered via directed closure.

Modeling the Network: The Role of Community

To explain these empirical observations, the authors tested three variations of network growth models:

  1. Standard Preferential Attachment: Failed to replicate the data, predicting closure ratios near zero for most nodes.
  2. Fitness-based Model: While accounting for node "attractiveness," it still could not produce the observed diversity in closure ratios.
  3. Community-based Model: By introducing a latent community structure where nodes are more likely to link within their own "topic" or "group," the model successfully generated the wide range of stable closure ratios seen in the Twitter data.

This suggests that the "link copying" process is heavily mediated by the underlying community structure of the network.

Conclusion and Future Directions

This research provides the first large-scale empirical validation of directed closure as a fundamental mechanism in network evolution. The discovery of stable yet heterogeneous closure ratios challenges simple growth models and highlights the necessity of incorporating community structure into our understanding of social-information networks.

Future work may explore the specific social or technical drivers of these patterns—such as Twitter's "Who to follow" recommendations—and examine whether these dynamics hold true across other platforms like citation networks or professional social media.

Summary updated

Abstract

It has often been taken as a working assumption that directed links in information networks are frequently formed by "short-cutting" a two-step path between the source and the destination -- a kind of implicit "link copying" analogous to the process of triadic closure in social networks. Despite the role of this assumption in theoretical models such as preferential attachment, it has received very little direct empirical investigation. Here we develop a formalization and methodology for studying this type of directed closure process, and we provide evidence for its important role in the formation of links on Twitter. We then analyze a sequence of models designed to capture the structural phenomena related to directed closure that we observe in the Twitter data.
BibTeX
@inproceedings{romero2010directed,
  author = {Daniel M. Romero and Jon Kleinberg},
  title = {{The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/icwsm.v4i1.14015},
}
Figure