Geospatial Structure of a Planetary-Scale Social Network - Leskovec, Jure; Horvitz, Eric (IEEE Transactions on Computational Social Systems, 2014)
Little is known about geographic properties of large-scale social networks. In this paper, we examine the geospatial attributes of a planetary-scale social network of 240 million people and 1.3 billion edges. We study the interplay among topological, geographical, and algorithmically generated paths connecting pairs of nodes in a social network. Starting in the realm of cyberspace, we ﬁnd that topologically shortest paths of average length of 6.6 exist between pairs of nodes in the network and that the average degree of separation among nodes is robust to removal of hub nodes. Moving to the realm of locations and distances in geographic space, we ﬁnd that topologically shortest paths in the social graph grow with increasing geographic distance between path’s endpoint nodes. We discover that shortest topological paths are geographically inefﬁcient, but that geography provides an important cue for local algorithmic policies for navigating between source and target nodes. Local algorithmic strategies for navigating the larger network structure in the absence of global navigation procedures have varying success. At the early stages of the navigation, navigating to a hub node helps, while in the middle stage, geography provides the most important clue. While local algorithms for navigating have trouble reaching the target node, they are successful in reaching nodes that are geographically close to the target. Taken together, our results demonstrate a complex interplay between topological and geographical properties of social networks and explain the success of local strategies for navigating such networks.