FriendTNS: Bridging the Gap Between Local and Global Overlap in Social Link Prediction
Transitive node similarity for link prediction in social networks with positive and negative links
The paper introduces FriendTNS (Friend Transitive Node Similarity), a link prediction algorithm that combines local node proximity with global graph structure. It achieves SOTA performance in friend recommendation tasks on social networks like Facebook, Hi5, and Epinions, notably extending its logic to signed networks with positive and negative links.
TL;DR
FriendTNS is a hybrid link prediction algorithm that solves the "generic recommendation" problem in social networks. By combining a degree-weighted local similarity measure with multiplicative transitivity along shortest paths, it outperforms both local indices (like Adamic/Adar) and global models (like Random Walk with Restart). Crucially, it demonstrates that negative links (enemies) provide vital context for predicting positive links (friends).
The "Common Friend" Paradox
Most Online Social Networks (OSNs) like Facebook or Hi5 historically relied on the "Friend of a Friend" (FOAF) approach. If you and a stranger share a common friend, you get a recommendation. But what if you have one common friend who is a "social butterfly" (connected to everyone) versus one common friend who is very selective?
Current local methods treat these scenarios as equal. Global methods, while more thorough, often drown out these local nuances in heavy matrix computations. The authors argue that a recommendation should be proportional to the path length and the individual "strength" of each hop in that path.
Methodology: Transitive Node Similarity
The core innovation lies in the two-step similarity calculation:
1. Basic Node Similarity (The Local Hook)
Instead of just counting neighbors, FriendTNS uses the inverse sum of degrees. This ensures that links between "exclusive" nodes carry more weight than links involving high-degree hubs.
2. Extended Similarity (The Global Reach)
For nodes not directly connected, the similarity is the product of the basic similarities along the shortest path. This transitive property allows the "trust" or "familiarity" to decay naturally as the distance increases, while still maintaining the weighted influence of each node's degree.
Figure 1: Motivation - Why local path length 2 is insufficient for ranking recommendations.
Handling the "Enemies": Signed Networks
A standout feature of this research is its application to Signed Networks (networks with +1 and -1 edges). Utilizing Status Theory, the authors adjust the similarity measure:
- Positive in-degree increases status.
- Negative out-degree decreases status.
By following the logic that "the enemy of my enemy is my friend" (Structural Balance Theory), FriendTNS can predict friendship links more accurately by observing who users distrust.
Experimental Battleground
The authors tested FriendTNS against industry standards (FOAF, Adamic/Adar) and heavy-duty academic models (Random Walk with Restart - RWR).
Figure 2: Precision-Recall curves on Facebook and Epinions datasets, showing FriendTNS (solid line) consistently on top.
Key Findings:
- Accuracy: FriendTNS dominated in "Small World" networks (Facebook, Epinions) where clustering is high.
- Efficiency: While local methods (FOAF) are faster, FriendTNS is significantly more efficient than RWR because it avoids the computationally prohibitive matrix inversion, relying instead on optimized shortest-path trees ().
- The Negative Edge Boost: In the Epinions 132K dataset, incorporating negative edges improved prediction precision significantly compared to using only positive data.
Critical Insight & Conclusion
FriendTNS proves that you don't need a "black box" global model to achieve SOTA results in link prediction. By intelligently weighting local degrees and propagating that value transitively, we can capture the organic flow of social influence.
The most profound takeaway for modern AI engineers is the value of negative signal. In an era of "Like" buttons, the "Dislike" or "Ignore" signals are often discarded, but as this paper shows, they are the keys to refining the latent manifold of social relationships.
Limitations: The performance drops in highly sparse networks (like the Hi5 dataset), where the average degree is too low to establish meaningful transitive paths. Future work should likely look at incorporating node metadata (photos, tags) to densify these sparse connection matrices.