ReDirect: Unveiling the Proposer and Responder in Social Networks

TL;DR

Is a social tie truly "undirected"? While platforms like Facebook show friends as a mutual link, every relationship has an origin—a proposer and a responder. This paper introduces ReDirect, a framework that infers hidden directions in undirected networks by observing structural patterns. By distinguishing between "active" and "passive" friends, the model significantly boosts the accuracy of link prediction and user profiling.

Background: The Invisible Directionality

We often view social networks as flat surfaces. However, for every co-authored paper, a junior researcher likely invited a senior one. For every Facebook friendship, one user clicked "Add Friend" first. These hidden "proposer-to-responder" arrows carry vital information about social status, influence, and user intentions. The authors argue that ignoring this directionality is a missed opportunity for higher-order network analysis.

The Core Insight: Four Patterns of Social Motion

The authors analyzed six massive directed networks (like Twitter and LiveJournal) to find the "physics" of social tie creation. They summarized their findings into four consistency patterns:

1. Degree Consistency: Active proposers tend to have high out-degrees but low in-degrees (they reach out a lot, but are less reached out to).
2. Triad Status Consistency: Social "status" forms a hierarchy; thus, directed links rarely form closed loops (if $AoB$ and $BoC$, then $CoA$ is unlikely).
3. Similarity Consistency: Users who "behave" similarly in how they propose to others are likely similar in the latent space.
4. Collaborative Consistency: You share more common interests with the people you chose to follow than with those who simply chose to follow you.

Methodology: The ReDirect Family

The researchers proposed two main technical paths to solve the Tie Direction Inference (TDI) problem:

ReDirect-N (Node-Centric)

This approach uses Matrix Factorization. It decomposes the probabilistic adjacency matrix into latent preference vectors. It doesn't just look at local pairs; it learns global representations of users to predict who is likely to initiate a link.

ReDirect-T (Tie-Centric)

This is a more local, iterative approach. It estimates the probability of direction for each specific tie by looking at the neighborhood structures and checking them against the four patterns mentioned above.

Figure 1: Conceptual illustration of the four consistency patterns used for inference.

Experiments and Breakthroughs

The team tested their methods on diverse datasets, including microblogs (Sina, Twitter) and consumer review sites (Epinions).

1. Robustness Against Baselines

Unlike simple "Degree" or "PageRank" heuristics—which often fail if the network is sparse or biased—ReDirect proved stable. In the Sina Weibo dataset, ReDirect-N/SF achieved an accuracy of 85.5% in direction recovery, while traditional PageRank-based inference dropped to nearly 21%.

2. Boosting Link Prediction

The most impressive result came from applying inferred directions to Link Prediction. By simply "preprocessing" a network with ReDirect before running standard algorithms like Jaccard Coefficient or Matrix Factorization, the authors saw a consistent increase in AUC.

Figure 2: Performance comparison showing that "recovered" directed networks (sm-directed) provide superior predictive signals.

Critical Perspective

While the paper provides a breakthrough in utilizing topology alone, there are inherent limitations:

• Cold Start: The model relies on structural patterns; for isolated "islands" or very new users with few links, the inference remains challenging.
• Self-Supervision Noise: The self-supervised variant (ReDirect-SF) relies on degree ratios. If the degree ratio threshold is set too high, it introduces noise that can propagate through the network.

Conclusion

The ReDirect family proves that "undirected" is often just a lack of observation. By mathematically enforcing social consistency patterns, we can recover the hidden arrows of interaction. This work serves as a foundational tool for anyone building recommendation systems: to understand a user, look at who they choose to follow, not just who follows them.