Abstract
How strong are the connections between individuals? This is a fundamental question in the study of social networks. In this work, we take a topological view rooted in the idea of local sparsity to answer this question on large social networks to which we have only incomplete access. Prior approaches to measuring network structure are not applicable to this setting due to the strict limits on data availability. Therefore, we propose a new metric, the Edgecut Weight, for this task. This metric can be calculated efficiently in an online fashion, and we empirically show that it captures important elements of communities. Further, we demonstrate that the distribution of these weights characterizes connectivity on a network. Subsequently, we estimate the distribution of weights on Twitter and show both a lack of strong connections and a corresponding lack of community structure.
Introduction
In the early days of social media research, scientists could often download entire network topologies. Today, "data lockdown" is the norm. Social media giants restrict data collection via strict API limits, making it impossible to calculate traditional global metrics like betweenness centrality or conductance—which require knowing the whole graph—on a massive scale. This research addresses a fundamental question: How can we understand the "strength" of connections and the overall topology of a network when we can only see a tiny, local slice of it at a time?
Methodology: The Edgecut Weight
The authors introduce Edgecut Weight, a purely local metric rooted in the concept of edge sparsity.
The Intuition
Imagine two people, Alice and Bob, connected by a single edge. If they are part of a dense community, there should be many other short paths between them. If they are the only bridge between two distant groups, there are very few alternate paths. This distinction between "community" edges and "bridge" or "cut" edges is central to understanding network topology.
The Mechanism
To measure this, the authors start simultaneous random walks from both endpoints of an edge. These walks have a random stopping probability ($\rho$). If the two walks "collide" (intersect at any node) before stopping, the edge is considered well-connected (low weight). If they never meet, the edge is likely a "cut" edge in a sparse region (high weight).
Calculating this analytically is computationally expensive. To solve this, the authors utilize the EBGStop algorithm (Empirical Bernstein Stopping). This allows for approximating the weight with a near-optimal number of samples, making it feasible to compute directly via social network APIs without full graph access.
Empirical Analysis and Results
The study evaluates the metric across several diverse network types, including collaboration networks (GrQc, HepPh), social networks (Slashdot, Facebook), and a complete Twitter follower graph from 2010 alongside a newly collected 2020 sample.
Local Metric, Global Story
A key finding is that the distribution of these local weights effectively characterizes the global connectivity of a network. Many networks exhibit an "elbow" in their weight distribution, representing a core-periphery structure: a small, dense core (low-weight edges) and a massive amount of peripheral "whiskers" (high-weight edges).
Twitter's Surprising Sparsity
One of the most striking findings is that the Twitter follower network is almost entirely sparse. It lacks the dense triadic closure (the "friend of a friend is my friend" effect) seen in collaboration networks. Comparing 2010 data to the 2019/2020 sample, the authors found that Twitter’s fundamental topology hasn't changed much—it remains a "strikingly sparse" network where nearly 90% of edges are indistinguishable from pure "cuts" (weights near 1.0).
Performance and Scalability
Compared to the gold-standard Brandes algorithm for betweenness, Edgecut Weight achieved speedups ranging from 94x to over 1,650x. The authors were able to calculate weights for Twitter in about 5 hours, while state-of-the-art approximation methods for betweenness failed to finish within 24 hours on the same hardware.
Conclusion
Edgecut Weight provides a powerful tool for analyzing modern social networks under data constraints. The discovery that Twitter is overwhelmingly sparse challenges assumptions about dense community structures in large-scale social media. Future work may explore why social processes on these platforms do not lead to the expected topological communities and how sampling strategies can be further refined to provide even deeper insights into global structures.
Summary updated