Source-linked AI summary
The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter
Daniel M. Romero, Jon Kleinberg
TL;DR
The paper addresses the limited empirical evidence for directed closure, in which information-network links shortcut existing two-step paths. It formalizes and tests the process using temporal edge-order data, finding above-chance closure and strong heterogeneity on Twitter, then evaluates network-formation models intended to capture these patterns.
Problem
Directed closure is an important but little-studied hypothesis that information-network links form by shortcutting existing two-step paths through implicit link copying.
Method
The authors define closure temporally, compare Twitter observations with a random-ordering baseline, and analyze preferential-attachment models with fitness and community structure.
Results
Twitter links to micro-celebrities exhibit above-chance directed closure, while closure ratios vary substantially across users and relate more closely to followers’ summed in-degrees than to follower count.
Takeaways & Limitations
Directed closure is an important and heterogeneous feature of Twitter’s follower network, and generalized preferential-attachment models provide partial explanations for its structural patterns.
Takeaways & Limitations
The causes of heterogeneous closure ratios and the applicability of these measures to other information networks remain directions for further work.
Abstract
from arXiv · showhide
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 paper formalizes directed closure in information networks, where a link completes an existing two-step path, and develops temporal tests for detecting it. Twitter data show above-chance closure, substantial user-to-user heterogeneity, and model relationships involving followers’ in-degrees.
- Information and Social Networks: Twitter combines social and information-network properties because following links are directed and concentrate heavily on celebrities and automated news sources.This hybrid structure motivates studying directed closure in Twitter’s follower network.
- Link Formation in Information Networks: Directed closure occurs when a link from A to C arrives after an existing two-step path from A through B to C.Unlike undirected triadic closure, evaluating directed closure requires knowing the order in which edges formed.
- The Directed Closure Process: The authors compare observed triangle-closing edges with the expected number under a random edge-arrival order to test for above-chance closure.An edge exhibits closure if, when it forms, it completes a directed two-step path between its endpoints.
- Empirical Analysis: Edges to Twitter micro-celebrities exhibit more closure than the random-ordering baseline, despite the competing tendency to link directly to prominent users first.Micro-celebrities are users with between 10,000 and 50,000 followers.
- Heterogeneity in Directed Closure: Closure ratios stabilize early but vary considerably across micro-celebrities and are not closely related to follower count.Some popular users receive a clear majority of incoming links through directed-triangle closure, while others receive much smaller proportions this way.
- Models and Network Structure: Preferential attachment predictions relate closure ratios more closely to the sum of followers’ in-degrees than to a user’s own follower count, but basic preferential attachment cannot explain all observed diversity.The paper therefore analyzes fitness and community-structure extensions that do not explicitly encode copying.
Twitter Data and Micro-Celebrities
The study samples Twitter µ-celebrities and identifies incoming edges exhibiting directed closure from chronologically ordered follower and following lists. Closure fractions often stabilize quickly, but their stable values vary substantially across µ-celebrities.
- The sample comprises Twitter µ-celebrities with between 10,000 and 50,000 followers.
- An edge from A to C exhibits closure when an earlier follower B of C was also followed earlier by A.
- Determining closure requires chronologically ordered follower lists and chronologically ordered lists of users followed by each follower.
- Figure 3 plots the running fraction of closure-exhibiting edges as each µ-celebrity’s followers arrive chronologically.
- The closure fraction usually reaches a relatively stable value quickly, and that value differs substantially across µ-celebrities.
Evidence for Directed Closure
The paper tests directed closure against randomized edge-creation orders and evaluates closure among users grouped by how many followers of a target they also follow. The expected closure fraction is estimated by simulation for groups with more than ten users.
- The randomization test uniformly permutes edge-creation orders in the subgraph induced by a target C and its followers.
- A user A is k-linked to C when A follows C and also follows k followers of C.
- For each k with |S_k| > 10, simulation approximates the expected closure fraction f_k under uniformly random edge-creation orders.
Preferential attachment
The preferential-attachment model combines random and in-degree-weighted attachment, then predicts closure through a heuristic based on the probability that earlier outgoing edges point to followers of a target. It reproduces some saturation and heterogeneity, but its closure pattern does not match micro-celebrity data.
- Model definition: The model adds each new node with D directed edges, choosing endpoints through a mixture of uniform attachment and current in-degree weighting.With probability α, endpoints are chosen uniformly; with probability 1−α, they are sampled according to current in-degree.
- Model evaluation: Preferential attachment fails to reproduce the observed micro-celebrity pattern: substantial closure appears mainly for very high-in-degree nodes, with closure increasing monotonically with final in-degree.For high-in-degree nodes, closure saturates over edge-arrival time, but the resulting degree relationship differs from the data’s weak association with total in-degree.
- Heuristic calculation: The heuristic estimates closure from the probability that an earlier edge from the same source points to a node that points to the target.For an edge in position d, the conditional closure probability is 1 − (1 − S_t(j))^(d−1), and averaging over equally likely positions gives C_t,e(j).
- Heuristic calculation: For sufficiently large N, the model predicts that node j’s final closure ratio is approximately C_N−1(j).The approximation follows from the limiting behavior of C_t(j) as t grows.
- Model evaluation: The approximation closely fits the actual closure ratios generated by the preferential-attachment model.Figure 6 compares the model’s actual node-level closure ratios with the C_N−1(j) approximation.
Preferential Attachment with Fitness
Preferential attachment with fitness removes the correlation between a node’s final closure ratio and in-degree, but still produces almost no substantial closure among µ-celebrities. The closure ratio instead tracks the total in-degree of a node’s incoming neighbors.
- Model: The fitness model assigns each node a uniformly random fitness parameter and selects endpoints through random or fitness-weighted preferential attachment.At each step, a new node creates D directed edges; with probability α, an endpoint is uniform, otherwise node i is weighted by d_i f_i.
- Results: Fitness removes the correlation between final closure ratio and final in-degree, matching the Twitter data.The model improves on simple preferential attachment in this respect.
- Results: Very few nodes obtain nontrivial closure ratios, and µ-celebrity-level nodes have an essentially zero fraction.This remains inconsistent with the Twitter data, where µ-celebrities can have very large closure ratios.
- Results: For small α, closure ratio is more strongly related to the sum of the in-degrees of a node’s incoming neighbors than to its own in-degree.The heuristic closure-ratio calculation remains accurate for preferential attachment with fitness.
Preferential Attachment with Communities
Preferential attachment with communities produces many nodes with nontrivial closure ratios, including µ-celebrity-level nodes, while changing which incoming-neighbor degrees matter most. Closure correlates more closely with same-community follower degrees than with all follower degrees.
- Results: µ-celebrity-level nodes can have reasonably large closure ratios in the community model.The model therefore generates many nodes with nontrivial closure ratios, unlike the preceding fitness model.
- Model: The community model assigns each node randomly to a community and makes attachment more likely within that community.Endpoints are selected using both community preference β and preferential or random attachment governed by α.
- Results: Simulations produce closure ratios that converge as in-degree increases and are not closely related to in-degree itself.This differs from simple preferential attachment, where closure ratios are closely tied to in-degree.
- Results: Closure ratio correlates more closely with the summed in-degrees of same-community followers than with the summed in-degrees of all followers.Community structure changes the relevant follower-degree quantity rather than eliminating its role.
Conclusion
The paper defines and measures directed closure in Twitter, finds substantial variation across follower sets, and uses generalized preferential-attachment models to explain these patterns. The models identify the sum of followers’ in-degrees as a parameter related to directed closure, while community-specific predictions remain open for further study.
- Conclusion: The paper develops a definition and methodology for directed closure and provides evidence that it occurs in Twitter’s follower network.It also finds that closure varies considerably across follower sets of different popular users.
- Conclusion: Generalized preferential-attachment models provide explanations for the observed findings and identify the sum of one’s followers’ in-degrees as related to directed closure.The community model further narrows this relationship to followers from the same community.
- Conclusion: Further work is needed to understand heterogeneity among Twitter µ-celebrities and test community-based model predictions using Twitter’s community structure.Comparative analysis on other information networks is also proposed.