Measuring Edge Sparsity on Large Social Networks

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.