TL;DR
This paper distinguishes between reciprocal (mutual) and parasocial (one-way) relationships in online social networks, revealing how their structures and evolution differ. It proposes a novel outlier detection approach for predicting reciprocal relationships, outperforming existing methods by avoiding issues with sampled negative examples.
What Problem Does This Paper Address?
Online social networks (OSNs) are inherently directed, meaning a connection from user A to user B doesn't guarantee a connection back from B to A. This creates two types of connections: reciprocal (mutual friendships) and parasocial (one-way followings). While understanding these relationships is crucial for applications like friend recommendation, existing research has largely treated them similarly or focused on basic structural properties. This paper aims to bridge this gap by systematically comparing the structures and evolution of reciprocal and parasocial edges, identifying factors that drive the formation of reciprocal links, and proposing a more robust method for predicting them. A key challenge is that previous prediction methods, which rely on sampling negative examples (parasocial edges that don't become reciprocal), often misclassify these sampled edges as positive in later stages, leading to poor generalization.
Methods
The authors introduce a novel approach to reciprocal edge prediction by framing it as an outlier detection problem. Instead of trying to distinguish between positive (reciprocal) and negative (parasocial) examples, they train a model using only the known positive (reciprocal) examples and identify parasocial edges that deviate significantly from this "normal" reciprocal behavior as potential future reciprocal links. They use a One-Class Support Vector Machine (OC-SVM) for this purpose.
They also propose a comprehensive set of features for prediction, categorized into:
- Single-node features: Including indegree, outdegree, and local reciprocity measures (how likely a user is to accept or make friend requests).
- Node-pair features:
- Structural features: Standard link prediction metrics like common neighbors, Jaccard's coefficients, Adamic-Adar, and preferential attachment, adapted for directed networks.
- Node-attribute features: Leveraging user profile information (school, major, employer, city) to capture commonalities.
- Edge-attribute features: Primarily focusing on the "age" of a parasocial edge.
Datasets
The study utilizes two datasets:
- Google+ dataset: A novel, large-scale dataset crawled by the authors, consisting of 79 daily snapshots spanning 98 days. This dataset represents the early stage of an OSN.
- Flickr dataset: A publicly available dataset with 102 daily snapshots, representing the steady stage of an OSN.
These datasets complement each other, allowing for the study of both nascent and mature social network dynamics.
Key Insights and Ideas
- Distinct Network Structures: Reciprocal edges tend to connect users with similar degrees (homophily), while parasocial edges are more likely to link ordinary users with popular ones (heterophily).
- Evolutionary Differences: The assortativity (degree homophily) of reciprocal edges is consistently high positive, indicating strong intra-group connections, whereas parasocial assortativity is neutral, reflecting connections across groups. This difference evolves over time, particularly with network growth.
- Factors Driving Reciprocity: User behavior (local reciprocity), node attributes (e.g., shared school), and edge attributes (e.g., edge age) all significantly influence whether a parasocial edge becomes reciprocal. For instance, sharing a school triples the likelihood of a reciprocal link.
- Edge Age Matters: Newer parasocial edges are much more likely to become reciprocal than older ones, suggesting edge age is a strong predictive feature.
- Outlier Detection Superiority: Framing reciprocal edge prediction as an outlier detection problem, rather than supervised or semi-supervised learning, avoids the pitfall of using future positive examples as training negatives, leading to better generalization.
Key Results
- Performance Comparison: The proposed OC-SVM approach consistently outperforms previous supervised (SVM) and semi-supervised (TriFG) methods in terms of F1 scores on both Google+ and Flickr datasets.
- Google+ vs. Flickr: Reciprocal edge prediction is generally easier in Google+ (higher Precision/Recall/F1) than in Flickr. This is attributed to Google+'s node attributes and its early-stage network dynamics.
- Edge-Age Sampling: Using edge age to sample negative examples for training supervised models (SVM-A, TriFG-A) improves Recall compared to random sampling (SVM-R, TriFG-R), though it can sometimes hurt Precision.
- Attribute Impact: Sharing a "School" attribute triples the linking-back probability, while sharing a "City" attribute provides a smaller boost. This highlights the importance of considering specific attribute types.
Limitations and Future Work
- Node Attributes: The Google+ dataset has node attributes, while Flickr does not. This difference impacts performance and suggests that node attributes are crucial for accurate prediction. The authors acknowledge that their results for Google+ would decrease if node attributes were excluded.
- Sampling Bias: While edge-age sampling improves recall, it can negatively impact precision for some methods (like SVM), suggesting a trade-off.
- Future Work: The authors suggest developing directed network models that capture both directed and undirected network metrics, incorporating structural balance features into outlier detection, and exploring applications in user lifestyle discovery and cross-community linking.
Summary updated