Topological Deep Dive: Enhancing Social Recommendations on VK via Second-Order Proximity

TL;DR

Link prediction—the "People You May Know" feature—is the engine of social network growth. This research evaluates the efficacy of traditional structural similarity metrics (Jaccard, Adamic-Adar, etc.) on the VK (Vkontakte) platform and introduces a Second Common Neighbor approach. The study reveals that VK's sparse graph structure makes standard prediction significantly harder than on platforms like Facebook, demanding more expansive topological insights.

Problem & Motivation: The Sparsity Trap

Most recommendation research treats social graphs as static entities or uses artificial edge-deletion to test models. The authors identify a "Sparsity Trap": on VK, users tend not to add people simply because they share a single common acquaintance. The graph is characterized by highly concentrated local regions and vast "empty" spaces between clusters.

The researchers' intuition is that standard first-order metrics (Common Neighbors) are too narrow for such environments. To find "like-minded" people, the system needs to look at the friends of friends—moving from first-degree intersections to second-degree neighborhood overlaps.

Methodology: Beyond the Immediate Circle

The core contribution is the Second Common Neighbor Similarity. While standard metrics look at how many direct friends A and B share, this method looks at the intersection of the entire "ego-environs."

Mathematical Intuition

The formula is defined as: $\mathrm{SecondCommonNeighbors}(A,B)=|{\bigcup }_{i\in f(A)}f(i)\cap {\bigcup }_{j\in f(B)}f(j)|$ This measures the union of all friends of friends. If User A's network and User B's network have a massive overlap at the second degree, they are likely part of the same community or share niche interests, even if they don't share a single mutual friend yet.

Experiments: Real-World VK Snapshots

The authors didn't just simulate data; they collected four months of snapshots from VK (Dec 2016 to March 2017), filtering for "regular" users (excluding celebrities and bots with >500 friends).

The Performance Gap

The results highlight a stark contrast:

• On Facebook Data: Adamic-Adar and Jaccard remain robust.
• On VK Data: Precision and F1-scores were significantly lower. Adamic-Adar performed best on F1-score, while Jaccard led in Precision.

When comparing the proposed Second Neighbor approach against Shortest Path on Facebook data (representing a denser environment), the Second Neighbor method proved superior in identifying True Positives (1791) while maintaining a lower False Positive count compared to simple distance-based measures.

Critical Analysis & Conclusion

Takeaway

The primary value of this work lies in its honest evaluation of SOTA methods on non-Western datasets. It proves that network topology is not universal. A method that works for "People You May Know" on Facebook might fail on VK because the "social cost" or cultural behavior of adding friends differs.

Limitations

• Node Attributes: The current study focuses purely on graph topology (structural proximity). It ignores rich nodal data like wall posts, age, and location, which the authors admit could significantly boost accuracy.
• Computational Complexity: Calculating second-degree unions across 190,000+ nodes is computationally expensive compared to simple first-order overlaps.

Future Outlook

The next step for social recommendation systems is moving beyond "who is close in the graph" to "who is meaningful in the graph." Combining the Second Neighbor logic with User Preference Embedding (via Graph Neural Networks) could likely bridge the gap in sparse networks like VK.