Link Prediction Using Triangle Subgraph Index

Link prediction has become increasingly popular in complex networks due to its wide application, including extracting missing information, identifying spurious interactions and so on. The simplest framework of link prediction methods are based on similarity index. Most similarity indices are obtained by using the basic topological feature of network, which ignores the impact of some special local structure. Moreover, similarity-based methods may perform well in a specific network, but they are not suitable to other types of network. In this paper, for the first time, we propose a similarity index called Triangle Subgraph index (TS) from the view point of a special network local structure, triangle. Along the way, we study link prediction as a supervised learning problem. A set of key features are identified according to the similarity index we propose and five other well-known similarity indices. We then apply supervised learning algorithms in six different complex networks, and prove that supervised learning algorithm using the TS feature can improve the accuracy of link prediction. Moreover, compared to similarity-based methods, this method can still get a high accuracy compared to similarity-based methods when applied in various networks. In the end, we investigate the supervised learning algorithms' robustness under different ratio between the size of training set and test set, and find that it can still get a high accuracy under a series of experimental setups.