TL;DR
This paper tackles the challenge of predicting missing links in social networks where data is collected through egocentric sampling (asking individuals about their connections). They introduce a novel, computationally efficient algorithm that estimates the network's underlying probability matrix by focusing on its row space, outperforming existing methods on this specific data collection paradigm.
What Problem Does This Paper Address?
Link prediction is a crucial task in network analysis, aiming to identify missing or future connections between nodes. Traditional methods often assume that observed network data is a noisy version of a complete network where missing links are scattered randomly. However, in many real-world scenarios, especially in social science research, data is collected via egocentric sampling. This means a subset of individuals (egos) are surveyed, and they report their connections (alters). This sampling method introduces a specific type of bias and missingness pattern that standard link prediction algorithms, designed for randomly missing data, struggle to handle effectively. This paper addresses this gap by developing a method tailored for the unique characteristics of egocentrically sampled networks.
Methods
The core of the proposed method, termed "subspace estimation" (SE), lies in leveraging the structure of egocentrically sampled data. Instead of trying to reconstruct the entire network's probability matrix directly, SE focuses on estimating the row space of this matrix. The authors model the observed data as a subset of rows from the full adjacency matrix. They then use a two-stage approach:
- Estimate the row space: They first estimate the principal subspace of the observed rows, which is assumed to approximate the row space of the underlying probability matrix. This is achieved through a low-rank approximation of the observed submatrix.
- Construct a plug-in estimator: Using the estimated row space, they construct a plug-in estimator for the full probability matrix. This involves a specific matrix decomposition and reconstruction process.
This approach is computationally efficient and specifically designed to handle the non-random missingness introduced by egocentric sampling.
Datasets
The authors evaluate their method on both synthetic and real-world datasets:
- Synthetic Networks: They generate networks using three common models:
- Distance Model: Based on distances between node features.
- Product Model: Similar to the distance model but with a different functional form.
-
Stochastic Block Model (SBM): Networks with community structures. They vary sampling rates and average degrees to test performance under different conditions.
-
Real-world Networks:
- Residence Hall Network: Friendship network within a residence hall.
- Adolescent Health Network: Social network among students.
- Wikipedia Election Network: Voting network from Wikipedia admin elections.
For real-world datasets, they sampled 5% to 50% of nodes to create egocentric samples.
Key Insights and Ideas
- Egocentric sampling requires specialized methods: The paper strongly demonstrates that standard link prediction techniques, designed for randomly missing data, perform poorly on egocentrically sampled networks. This highlights the importance of accounting for the specific sampling mechanism.
- Row space estimation is key: By focusing on estimating the row space of the underlying probability matrix, the method effectively captures the essential structure of the network despite the biased sampling. This is a more robust approach than trying to fill in missing entries directly.
- Subspace estimation denoises the observed data: The method inherently denoises the observed sampled rows, essentially performing matrix completion on the sampled portion first. This makes it more resilient to noise and missing values within the sampled rows themselves.
- Computational efficiency matters: The proposed algorithm is designed to be computationally efficient, making it practical for large networks where traditional methods might be too slow.
Key Results
- Superior performance: The proposed subspace estimation (SE) method consistently outperforms benchmark algorithms (CUR, USVT, MC-IALM, NS) on egocentrically sampled networks across various synthetic network models and real-world datasets.
- Robustness to sampling rates: SE shows strong performance even at low sampling rates (e.g., 5% of nodes), where other methods struggle significantly.
- Impact of sampling scheme: The paper shows that the performance of generic matrix completion methods (USVT, MC) can differ substantially when applied to egocentrically sampled data versus data with uniform missingness, underscoring the need for tailored approaches.
- Computational cost: The computational cost of SE is only slightly higher than that of the CUR decomposition, which is already known for its efficiency.
Limitations and Future Work
- Limitations:
- The paper acknowledges that while egocentric sampling without replacement is a step towards realism, it may still not perfectly capture all real-world survey scenarios.
- For real datasets, Kendall's tau could not be computed due to the unavailability of the true probability matrix.
- Some benchmark methods were omitted for certain real datasets due to high computational cost.
- Future Work:
- Importance Sampling: Investigating survey procedures that incorporate importance sampling, potentially using preliminary data to pre-compute node weights, similar to how it's done in CUR decomposition.
- Other Sampling Schemes: Extending the link prediction framework to other sampling schemes, such as snowball sampling.
Summary updated