Understanding the network formation pattern for better link prediction

Networks are widely used in different fields for their powerful ability to model entity relationships that are constantly changing over time, resulting in networks being highly dynamic and complex [1]. The link prediction problem refers to using the information of the observed network, like the properties of the nodes and edges, to predict the existence of edges between pairs of unconnected nodes [2][3]. For static networks, these missing edges may indicate missing information. When we utilize networks to approximately model some complicated systems, for example, missing or redundant edges will inevitably exist due to the complexity of the real systems. For dynamic networks, the structures and properties of the network may be dynamically changing, and some potential edges may appear only in the future. Biological network databases, for example, are constantly updated and enriched as human cognitive capacities improve. Therefore, studying these missing edges is an entry point for studying the link prediction problem, which is crucial for understanding the network formation mechanism. Most link prediction methods are developed based on common neighbors, with the underlying assumption that the network structure is dominated by the Triadic Closure Principle (TCP): friends of mine are more likely to be friends of each other [4]. However, while this deeply rooted principle is interpretable in some social networks, it’s not always reasonable in other networks. For example, Kovács et al. pointed out that in Protein-Proteins Interaction (PPI) networks, the link prediction task should rely on paths of length three (L3) rather than length two, because similar proteins tend to recognize the same binding sites [5]. This breaks the long-standing trust of using information of common neighbors. These two opposing ideas are shown in Fig. 1(a), with nodes connected by paths of length two for TCP-based methods and paths of length three for L3 method, and we refer to these two scenarios as the second-order and the third-order information dominated networks, respectively. However, not all connectivity mechanisms of networks have been researched as much as social networks or PPI networks. When given an arbitrary network whose nodes and edges are of unknown significance, can we make the data tell us whether the second-order neighbors information or the third-order neighbors information is * lywu@amss.ac.cn Understanding the network formation pattern for better link prediction