Evolving networks—Using past structure to predict the future

• Published in: Physica A 2016-08, Vol.455, p.120-135
• Main Authors: Shang, Ke-ke, Yan, Wei-sheng, Small, Michael
• Format: Article
• Language: English
• Subjects: Algorithms; Evolution; Evolving network; Human factors; Link prediction; Links; Network structure; Networks; Robustness; Social networks; Statistical mechanics; Unweighted network; Weighted network
• ISSN: 0378-4371; 1873-2119
• DOI: 10.1016/j.physa.2016.02.067

Many previous studies on link prediction have focused on using common neighbors to predict the existence of links between pairs of nodes. More broadly, research into the structural properties of evolving temporal networks and temporal link prediction methods have recently attracted increasing attention. In this study, for the first time, we examine the use of links between a pair of nodes to predict their common neighbors and analyze the relationship between the weight and the structure in static networks, evolving networks, and in the corresponding randomized networks. We propose both new unweighted and weighted prediction methods and use six kinds of real networks to test our algorithms. In unweighted networks, we find that if a pair of nodes connect to each other in the current network, they will have a higher probability to connect common nodes both in the current and the future networks—and the probability will decrease with the increase of the number of neighbors. Furthermore, we find that the original networks have their particular structure and statistical characteristics which benefit link prediction. In weighted networks, the prediction algorithm performance of networks which are dominated by human factors decrease with the decrease of weight and are in general better in static networks. Furthermore, we find that geographical position and link weight both have significant influence on the transport network. Moreover, the evolving financial network has the lowest predictability. In addition, we find that the structure of non-social networks has more robustness than social networks. The structure of engineering networks has both best predictability and also robustness. •We can use the links between a pair of nodes to predict their common neighbors.•We find that the link weight have significant influence on our prediction.•The rules of weighted networks which are dominated by human differ from other networks.•The location and weight both have significant influence on the transport network.•The structure of engineering networks has both best predictability and robustness.