One model to rule them all in network science?

Abstract

If you have ever used a social network platform, you know that you are regularly prompted about people you may know in the network. Sometimes these recommendations are striking—we get a suggestion for a person we have met only once, or an old acquaintance that we have not seen in years. How could anyone (let alone a computer) possibly guess? Predicting acquaintances in a social network is just one example of the general problem of link prediction (1⇓⇓⇓–5), which consists of predicting connections (links) in a network (6) from the observation of other connections (Fig. 1). Besides social networking, the problem of link prediction occurs in many contexts, from recommender systems, where customers are recommended (linked to) items based on their previous ratings or purchases (7), to the prediction of unknown harmful (or perhaps synergistic) interactions between drugs (8). Fig. 1. In the problem of link prediction, we are asked to identify which unobserved links in a network are more likely to exist. Nodes could represent individuals or drugs, and links could represent, respectively, friendship relationships in a social network or harmful drug–drug interactions. In this example, links <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi><mml:mi>B</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>C</mml:mi><mml:mi>D</mml:mi></mml:math> exist but have not been observed, so we aim to predict them. Model 1 pays attention only to the connectivity of nodes, and it captures that many nodes are connected to A, so it correctly predicts the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi><mml:mi>B</mml:mi></mml:math> link. However, since there is nothing especial about the connectivity of C and D, it misses the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>C</mml:mi><mml:mi>D</mml:mi></mml:math> link. Conversely, model 2 pays attention only to group structure, so it realizes that all nodes in the group at Right are connected to each other, and it predicts the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>C</mml:mi><mml:mi>D</mml:mi></mml:math> link. However, since in the group at Left many pairs of nodes are … [↵][1]1Email: roger.guimera{at}urv.cat. [1]: #xref-corresp-1-1

Topics & Concepts