Multigraph Sampling of Online Social Networks
State-of-the-art techniques for probability sampling of users of Online Social Networks (OSNs) are based on random walks on a single social relation (typically friendship). While powerful, these methods rely on the social graph being fully connected. Furthermore, the mixing time of the sampling process strongly depends on the characteristics of this graph. In this paper, the authors observe that there often exist other relations between OSN users, such as membership in the same group or participation in the same event. They propose to exploit the graphs these relations induce, by performing a random walk on their union multi-graph.