Abstract
Social networks play a key role in studying various individual and social behaviors. To use social networks in a study, their structural properties must be measured. For offline social networks, the conventional procedure is surveying/interviewing a set of randomly-selected respondents. In many practical applications, inferring the network structure via sampling is too prohibitively costly. There are also applications in which it simply fails. For example, for optimal vaccination or employing influential spreaders for public health interventions, we need to efficiently and quickly target well-connected individuals, which random sampling does not accomplish. In a few studies, an alternative sampling scheme (which we dub 'alter sampling') has proven useful. This method simply targets randomly-chosen neighbors of the randomly-selected respondents. A natural question that arises is: to what extent does this method generalize? Is the method suitable for every social network or only the very few ones considered so far? In this paper, we demonstrate the robustness of this method across a wide range of networks with diverse structural properties. The method outperforms random sampling by a large margin for a vast majority of cases. We then propose an estimator to assess the advantage of choosing alter sampling over random sampling in practical scenarios, and demonstrate its accuracy via Monte Carlo simulations on diverse synthetic networks.
1. Introduction
Identifying influential, highly connected individuals within a social network is a cornerstone of modern public health and marketing strategies. Whether the goal is optimizing vaccine distribution to halt an epidemic or seeding information for a viral marketing campaign, the ability to reach "hubs"—individuals with high centrality—is critical. However, mapping the full topology of a social network, particularly offline ones, is often prohibitively expensive and time-consuming.
Standard random sampling typically fails to capture these hubs because most nodes in a network have a relatively low degree. An alternative approach, known as "alter sampling" or acquaintance immunization, leverages the sociological "friendship paradox": the observation that, on average, your friends have more friends than you do. By randomly sampling individuals and then targeting their named acquaintances (alters), researchers can theoretically reach more connected nodes. While this has been observed in specific cases like H1N1 tracking, this study investigates whether the advantage is universal across diverse network topologies.
2. Methodology
To evaluate the effectiveness of alter sampling, the authors define a metric called "local gain" ($\mathscr{G}_x$), representing the ratio of the connectivity of a node's neighbors to the node's own degree. A gain $\mathscr{G}_x > 1$ indicates that alter sampling is superior to random sampling for that specific node.
2.1 Empirical Validation
The study analyzes massive real-world datasets across two categories:
- Directed Networks: GitHub (followership), Pokec (Slovakian social network), and Twitter.
- Undirected Networks: IMDB Film Actor Network, Scientific Collaboration (arXiv), LiveJournal, Friendster, and Orkut.
2.2 Theoretical Estimation and Simulation
The authors derive a mathematical estimator for expected global gain ($\mathscr{G}$) that requires only the self-reported degree of an initial random sample. To validate this estimator, Monte Carlo simulations were performed on synthetic networks generated via four models: Small-world, Preferential Attachment, Holme-Kim (high clustering), and Klemm-Eguiluz.
3. Empirical Results
3.1 Directed Networks
In directed networks, the study found that over 85% of the population yields a local gain greater than 1. This suggests that for the vast majority of users on platforms like Twitter or GitHub, their followers or followees are significantly more connected than they are. This effect is consistent across almost all in-degree percentile ranks, except for the very highest-degree hubs.
3.2 Undirected Networks
The results for undirected networks are even more pronounced. In these environments, nearly 95% of the population provides a local gain $> 1$. Crucially, this advantage persists whether using the mean or the median degree of neighbors, proving that the effect is not merely a statistical artifact driven by a few extreme outliers.
4. Key Insights
- Universality: Alter sampling is robust regardless of a network's specific clustering, density, or assortativity. It is a fundamental property of social network structures.
- Magnitude of Improvement: For most nodes, the gain is not marginal but substantial, often providing an order of magnitude ($O(10^1)$) improvement in reaching high-degree nodes compared to random sampling.
- Practical Utility: The proposed estimator allows researchers to quantify the sampling advantage in real-time. By simply asking an initial sample "how many friends do you have?", one can accurately predict the expected degree of the alters with an error rate of less than 10%.
5. Conclusion and Future Work
Alter sampling is a universally effective strategy for identifying influential nodes without the need for full network mapping. However, practical implementation faces challenges such as imperfect recall (respondents forgetting friends) and truncated data (surveys capping the number of friends listed). Future research must address these statistical inference problems to refine the estimator for real-world survey conditions where only a fraction of links are reported.
Summary updated