Sampling cohesive communities in unbounded networks

Abstract

With today’s social networks measuring up to millions and billions of nodes and edges, it becomes essential to devise methodologies to obtain a subgraph with the required properties. Network sampling is often one of the most important stages of obtaining and studying a network since the properties of a sampling scheme used directly influence the properties of the network under consideration. Driven by insights from studies on homophily and opinion formation, we introduce a variant of snowball sampling specifically tailored to prioritize the inclusion of entire cohesive communities. This approach deliberately avoids traditional aims like representativeness, breadth, or depth of coverage, which have been the focus of extensive research in the past. We propose the sampling scheme in the context of Twitter - a conceptually unbounded network, that can be transferred to other types of social networks with different types of interactions. The study is undertaken in two stages - we combine multiplex forms of interactions observed between users to construct a simple network, followed by using a variation of snowball sampling to iteratively sample nodes based on a priority determined by their connectivity with the currently sampled network. The efficacy and limitations of this approach are demonstrated through empirical analysis on synthetic networks, which are unweighted and undirected, generated via the Stochastic Block Model. Moreover, we utilize variants of our proposed sampling technique to gather dataset(s) from Twitter. The experiments in both real and synthetic networks suggest that the scheme behaves as desired.