Introduction {#Sec1}
============

Many social, biological, and food-chain systems can be well described by networks, where nodes denote individuals, biological elements, and so on, and links represent the relations between nodes. The complex networks has therefore become a popular focus of many branches of science. An attractive research topic is link prediction, whose purpose is to predict the possibility or necessity of forming links between unconnected node pairs via the information of complex networks^[@CR1],[@CR2]^. Thus Link prediction can predict the existing yet unknown links (the missing links) and the links that may appear in the future (the future links)^[@CR3],[@CR4]^. With the amount of data increasing nowadays, Link prediction plays a more crucial role in recommendation system, data mining, complex networks, and so on. For instance, in the protein-protein interaction network of Yeast, 80% of the molecular interactions are still unknown. Whether a link between two nodes exists must be demonstrated by field and/or laboratorial experiments^[@CR5]^. However, if the accurate prediction results are applied into the laboratorial experiments instead of blindly checking all possible interactions, the costs will be sharply reduced^[@CR6]^. In the scientists cooperation network, link prediction helps to find the potential cooperation between scientists^[@CR7],[@CR8]^. Besides, link prediction is also employed in recommending friends for online social networks^[@CR9],[@CR10]^ and identifying spurious links in a noisy environment^[@CR11],[@CR12]^.

Until now, many indexes for link prediction have been proposed. Generally, they are classified into three main models: models based on Markov chains^[@CR13]--[@CR15]^, models based on machine learning^[@CR16],[@CR17]^ and models based on the similarity of topological structure^[@CR1],[@CR18]^. Though the first two have high prediction accuracy in many networks, they don't apply to the large-scale networks due to their high computational complexity. Nevertheless, models based on similarity can avoid such problems and easily obtain the information of networks. For instance, the Common Neighbor (CN) index, which is the most widely used index, just counts the number of common neighbors between node pair. Newman^[@CR19]^ used this quantity in the study of collaboration networks, showing a positive correlation between the number of common neighbors and the probability that two scientists will collaborate in the future. By taking into account the common neighbors number and the degrees of two nodes, Salton et al. pointed out the Salton index^[@CR20]^; Leicht, Holme and Newman proposed the LHN index^[@CR21]^. To characterize the topological similarity between reactants in the metabolic network, Ravasz E. and Somera A. L. et al. proposed the hub promoted index (HPI)^[@CR22]^. HPI index insists that the links adjacent to hubs are likely to be assigned high scores since the denominator is determined by the common neighbors number and the lower degree. To measure with the opposite effect of hubs, Zhou and Lü et al. put forward the hub depressed index (HDI)^[@CR23]^. Furthermore, they proposed the resource allocation index (RA)^[@CR23]^. Motivated by the resource allocation dynamics on complex networks, the RA index can effectively improve the accuracy by restraining the contributions of large-degree common neighbors. Additionally, Liu et al. proposed a Local Naive Bayes (LNB) model^[@CR24]^, which insists that different common neighbors play different roles and make different contributions. Based on the LNB model, they improved the CN, RA and AA index. As the similarity indexes can predict links in networks, we can apply the similarity indexes to evaluate the evolving mechanisms for the evolving networks^[@CR1]^.

Obviously, similarity-based algorithms for link prediction can predict the future links by using the current common neighbors information^[@CR25]^. However, on above principles of the similarity indexes, some nodes, currently not common neighbors, can turn into the common neighbors in the future. More importantly, these nodes raise a series of new questions worth exploring. First of all, it is whether these nodes contribute to the current prediction between node pair. Although the previous algorithms have proved that the current common neighbors can promote two nodes to connect, people still doubt whether nodes, which are currently not a common neighbor but can become a common neighbor in the future, are also helpful in the current link prediction. Second, if they do make contribution, then how we can locate these nodes and measure their contribution, simultaneously. Previous algorithms can easily count the number of the current common neighbors by only analyzing the network topology. However, the nodes described above have not yet become the common neighbors, and they can get different topology structures when they are together with the node pairs and their surrounding nodes. These lead to the challenge of locating these nodes and measuring their contributions via a simple method.

To address the above problems clearly, firstly, we define nodes, which are currently not common neighbors but can turn into the common neighbors in the future, as the future common neighbors and divide them into three types according to their topology structure with other nodes. Second, we propose the similarity-based future common neighbors (SFCN) model for link prediction. The SFCN model accurately finds out all the future common neighbors, besides the current common neighbors. And simultaneously, it can also measure their contributions by only using the existing similarity indexes. We also design and observe three MATLAB simulation experiments. First, we conduct a priori experiment on *α* and *β* in FWFB network. The results provide strong evidence that the future common neighbors have more positive contribution than the common neighbors in complex networks. Second, by comparing the SFCN model with eight similarity-based algorithms in five networks, we find that the SFCN model has higher prediction accuracy from the whole perspective. Third, the experiments, where we change the ratio of the training set to the probe set in five networks, also demonstrates that the SFCN model has better performance robustness. So, the proposed SFCN model has higher accuracy and performance robustness than popular algorithms, and the future common neighbors is necessary to be considered for link prediction in evolving networks.

Results {#Sec2}
=======

Network and problem description {#Sec3}
-------------------------------

A network can be represented by an undirected network *G*(*V*, *E*) without self-connections and multiple links between node pair. In *G*(*V*, *E*), *V* is the set of nodes, and *E* is the set of links. Then \|*V*\| represents the quantity of nodes in *V*. Define the fully connected network as *U* that contains (\|*V*\|(\|*V*\| − 1))/2 links. So, *U-E* is the set of the nonexistent links. To evaluate the prediction accuracy of algorithms, we divide the observed link set *E* into the training set *E*^*T*^ and the probe set *E*^*P*^ randomly. *E*^*T*^ is the known information while *E*^*P*^ is the unknown information. Obviously, *E* = *E*^*P*^ ∪ *E*^*T*^, and *ϕ* = *E*^*P*^ ∩ *E*^*T*^. Accurately detecting the missing links or the future links from *U-E* is the purpose of link prediction. Give the link between node pair (*x*, *y*) in *U* a score (*s*~*x*,*y*~), which is calculated by the link prediction algorithm. All the nonexistent links are sorted in descending order according to their scores, and the links at the top are most likely to exist.

The future common neighbors {#Sec4}
---------------------------

Most similarity-based algorithms for link prediction predict the future links by using the current common neighbors. However, on the prediction principles of the above similarity indexes, some nodes, which are currently not common neighbors, can turn into the common neighbors in the future. To analyze whether such nodes are factors that contribute to the current prediction between node pair, and in order to accurately locate these nodes to measure their contribution, we define them as the future common neighbors and propose the similarity-based future common neighbors model for link prediction in evolving networks.

The future common neighbors are nodes that are currently not the common neighbors but can turn into the common neighbors in the future on the principle of the similarity index. According to their topology with other nodes, the future common neighbors are divided into three types shown in Fig. [1](#Fig1){ref-type="fig"}, where *x* and *y* are the target node pair for link prediction. The first future common neighbor, like node *i* in Fig. [1(a)](#Fig1){ref-type="fig"}, has a direct link with *x* while no direct link with *y*. Currently, the similarity score between *i* and *y* is *s*~*i*,*y*~. According to the prediction principle of the similarity algorithm, *i* and *y* may form a link in the future (the greater the *s*~*i*,*y*~, the greater the probability of forming a link). Therefore, *i* has connected with *y* and turn into the common neighbor between *x* and *y* in a future time. The second future common neighbor, like *i* in Fig. [1(b)](#Fig1){ref-type="fig"}, has direct link with *y* while no direct link with *x*. The third future common neighbors does not connect with both *x* and *y*, seen node *i* in Fig. [1(c)](#Fig1){ref-type="fig"}. According to the existing similarity indexes for link prediction, if *s*~*x*,*i*~ and *s*~*i*,*y*~ are great enough, *i* are will form links with both *x* and *y*. Thus, the *i* in Fig. [1(c)](#Fig1){ref-type="fig"} are also a common neighbor between *x* and *y* in a future time.Figure 1Three types of the future common neighbors.

Similarity-based future common neighbors model {#Sec5}
----------------------------------------------

Combining the future common neighbors topology with the similarity-based indexes, this paper designs the similarity-based future common neighbors model. The model is to accurately find out all the future common neighbors in complex networks and effectively measure their contributions.

Taking the chaotic network in Fig. [2](#Fig2){ref-type="fig"} as an example, for node *i* (*i* = 1, 2, 3, ..., \|*V*\|), we assume that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}$$\end{document}$ is a similarity score between *x* and *i*, and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}$$\end{document}$ is calculated by any classical similarity-based algorithms that we mark as *C*2. Therefore, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}$$\end{document}$ also symbolizes the possibility of forming a link between *x* and *i* on the principle of *C*2 when the network is evolving. We make *r*~*i*,*y*~ indicate whether *i* and *y* are connected (*r*~*i*,*y*~ = 1 if *i* and *y* are connected, otherwise *r*~*i*,*y*~ = 0), which can be obtained from the observed networks. Similarly, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{i,y}^{C2}$$\end{document}$ is a similarity score between *i* and *y* calculated by algorithms *C*2; *r*~*x*,*i*~ represents whether *x* and *i* are connected.Figure 2The process of identifying the future common neighbors from the chaotic network. The yellow nodes are the future common neighbors between *x* and *y*.

The SFCN model identifies the above three types of the future common neighbors from chaotic network by employing their topological rules. (1) *i* is the first type of the future common neighbor only when $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}\cdot {r}_{i,y}\ne 0$$\end{document}$. It is necessary to note that we set $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}=0$$\end{document}$ and *r*~*i*,*y*~ = 0 when *i* = *x* or *i* = *y* in order to keep non self-connections. (2) The rest rules can be deduced by analogy, *i* is the second type of the future common neighbor if $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${r}_{x,i}\cdot {s}_{i,y}^{C2}\ne 0$$\end{document}$. (3) And *i* is the third type of the future common neighbor if and only if $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,i}^{C2}\cdot {s}_{i,y}^{C2}\ne 0$$\end{document}$.

To accumulate the contributions of the future common neighbors, which meet the above rules, we construct four vectors for *x* and *y* in eqs [1](#Equ1){ref-type=""}, [2](#Equ2){ref-type=""}, [3](#Equ3){ref-type=""}, [4](#Equ4){ref-type=""}.$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{l}{{\boldsymbol{\Gamma }}}_{{\bf{x}}}=({r}_{x\mathrm{,1}}\,\cdots \,{r}_{x,x-1}\,0\,{r}_{x,x+1}\,\cdots \,0),\end{array}$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{c}{({{\boldsymbol{\Gamma }}}_{{\bf{y}}})}^{T}={({r}_{1,y}\cdots {r}_{y-1,y}0{r}_{y+1,y}\cdots 0)}^{T},\end{array}$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\bf{S}}}_{{\bf{x}}}^{{\bf{C}}{\bf{2}}}=({s}_{x\mathrm{,1}}^{C2}\,\cdots \,{s}_{x,x-1}^{C2}\,0\,{s}_{x,x+1}^{C2}\,\cdots \,0),$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{c}{({{\bf{S}}}_{{\bf{y}}}^{{\bf{C}}{\bf{2}}})}^{T}={({s}_{1,y}^{C2}\cdots {s}_{y-1,y}^{C2}0{s}_{y+1,y}^{C2}\cdots 0)}^{T},\end{array}$$\end{document}$$where the superscript ^*T*^ denotes matrix transposition, and the black highlighted parts are the row vectors or column vectors. **Γ**~***x***~ stores the connections of *x* to all nodes. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\bf{S}}}_{{\bf{x}}}^{{\bf{C}}{\bf{2}}}$$\end{document}$ stores the similarity scores of *x* to all nodes. Similarly, (**Γ**~***y***~)^*T*^ stores the connections of *y* to all nodes. And $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${({{\bf{S}}}_{{\bf{y}}}^{{\bf{C}}{\bf{2}}})}^{T}$$\end{document}$ stores the similarity scores between *y* and all other nodes.

Therefore, we get the similarity-based future common neighbors model as eq. [5](#Equ5){ref-type=""}:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{rcl}{s}_{x,y}^{SFCN} & = & \alpha \cdot {s}_{x,y}^{C1}+\beta \cdot ({{\boldsymbol{\Gamma }}}_{{\bf{x}}}\cdot {({{\bf{S}}}_{{\bf{y}}}^{{\bf{C}}{\bf{2}}})}^{T}+{{\bf{S}}}_{{\bf{x}}}^{{\bf{C}}{\bf{2}}}\cdot {({{\boldsymbol{\Gamma }}}_{{\bf{y}}})}^{T}+{{\bf{S}}}_{{\bf{x}}}^{{\bf{C}}{\bf{2}}}\cdot {({{\bf{S}}}_{{\bf{y}}}^{{\bf{C}}{\bf{2}}})}^{T})\\  & = & \alpha \cdot {s}_{x,y}^{C1}+\beta \cdot \sum _{i=1}^{|V|}({r}_{x,i}\cdot {s}_{i,y}^{C2}+{s}_{x,i}^{C2}\cdot {r}_{i,y}+{s}_{x,i}^{C2}\cdot {s}_{i,y}^{C2}),\end{array}$$\end{document}$$where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{C1}$$\end{document}$ is the similarity score between *x* and *y*, and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{C1}$$\end{document}$ is calculated by any similarity algorithm that we temporarily mark as *C*1. C1 and C2 are two similarity algorithms, and they can be the same or different. The two free parameters, *α* and *β*, is to adjust the contributions of the current common neighbors and the future common neighbors, respectively. When *α* ≠ 0 and *β* = 0, the model only considers the current common neighbors contributions. When *α* = 0 and *β* ≠ 0, the model only considers the future common neighbors contributions. Both C1 and C2 are the. A special case, when both *C*1 and *C*2 are represented by CN algorithm and only the first class of the future common neighbors are considered, the model degenerates into the LP index. In a word, the SFCN model, employed in evolving networks, takes into account the contributions of the future common neighbors besides the current common neighbors.

Example 1 {#Sec6}
---------

This section gives an example of how to find the future common neighbors between node pair and how to measure the contributions of three future common neighbors. Suppose *C*1 and *C*2 are the LHN and RA algorithms, respectively. Take the network in Fig. [2](#Fig2){ref-type="fig"} as an example and treat nodes (1, 3) as the target node pair (*x*, *y*). Then we can get four vectors:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{l}{{\boldsymbol{\Gamma }}}_{{\bf{1}}}=(0\,1\,0\,1\,0\,0\,0\,0\,0\,0),\end{array}$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{c}{({{\boldsymbol{\Gamma }}}_{3})}^{T}={(0100100000)}^{T},\end{array}$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{l}{{\bf{S}}}_{{\bf{1}}}^{{\bf{C}}{\bf{2}}}=(0\,0\,0\,0\,\frac{1}{5}\,0\,\frac{1}{5}\,\frac{1}{5}\,0\,\frac{1}{5}),\end{array}$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${({{\bf{S}}}_{{\bf{3}}}^{{\bf{C}}{\bf{2}}})}^{T}={(000\frac{1}{6}0\frac{1}{6}0\frac{1}{6}\frac{1}{6}\frac{1}{6})}^{T}.$$\end{document}$$

From the calculation process (eq. [10](#Equ10){ref-type=""}), it is easy to observe that only node 4 is the first type of the future common neighbors. And the contribution of node 4 to (1, 3) is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{6}\cdot \beta $$\end{document}$.$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{l}{{\boldsymbol{\Gamma }}}_{{\bf{1}}}\cdot {({{\bf{S}}}_{{\bf{3}}}^{{\bf{C}}{\bf{2}}})}^{T}=\sum _{i=1}^{|V|}\,({r}_{\mathrm{1,}i}\cdot {s}_{i\mathrm{,3}}^{C2})={r}_{\mathrm{1,4}}\cdot {s}_{\mathrm{4,3}}^{C2}=\frac{1}{6}\mathrm{.}\end{array}$$\end{document}$$

We can also observe that only node 5 is the second type of the future common neighbors from the eq. [11](#Equ11){ref-type=""}:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{c}{{\bf{S}}}_{{\bf{1}}}^{{\bf{C}}{\bf{2}}}\cdot {({{\boldsymbol{\Gamma }}}_{{\bf{3}}})}^{T}=\sum _{i=1}^{|V|}\,({s}_{1,i}^{C2}\cdot {r}_{i,3})={r}_{1,5}\cdot {s}_{5,3}^{C2}=\frac{1}{5}.\end{array}$$\end{document}$$

At last, we can check out that 8 and 10 are the third type of the future common neighbors through eq. [12](#Equ12){ref-type=""}:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{c}{{\bf{S}}}_{{\bf{1}}}^{{\bf{C}}{\bf{2}}}\cdot {({{\bf{S}}}_{{\bf{3}}}^{{\bf{C}}{\bf{2}}})}^{T}=\sum _{i=1}^{|V|}\,({s}_{1,i}^{C2}\cdot {s}_{i,3}^{C2})={s}_{1,8}^{C2}\cdot {s}_{8,3}^{C2}+{s}_{1,10}^{C2}\cdot {s}_{10,3}^{C2}=\frac{1}{15}.\end{array}$$\end{document}$$

Therefore, the contribution of the future common neighbors is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\beta \cdot (\frac{1}{6}+\frac{1}{5}+\frac{1}{15})=\frac{13}{30}\cdot \beta $$\end{document}$.

Evaluation Metrics {#Sec7}
------------------

In the Experiments, we introduce two standard metrics to quantify the prediction accuracy: the *AUC*^[@CR26]^ (area under the receiver operating characteristic curve) and *precision*^[@CR27]^. The AUC evaluate the algorithms performance according to the whole list. The AUC is comprehended as the probability that a link randomly chosen from set *E*^*T*^ has a much higher score than a link randomly chosen from nonexistent link *U-E*. In the *n* times independent comparisons, we select a link from *E*^*T*^ and *U-E* respectively. Define their similarity scores as *S*1 and *S2*. When *S*1 \> *S2*, set *n*′ = *n*′ + *1*; when *S1*  = *S2*, set *n*″ = *n*″ + *1* (*n*′ and *n*″ are initialed as 0, *n* = *n*′ + *n*″). So, the *AUC* can be defined as eq. [13](#Equ13){ref-type=""}:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{array}{l}{\rm{AUC}}=(n^{\prime} +0.5n^{\prime\prime} )/n\mathrm{.}\end{array}$$\end{document}$$

Different from the AUC, precision focuses on the links with top ranks or highest scores. It is the ratio of correct links recovered out of the top *L* links in the candidate list generated by each link predictor. Assume *L*~*r*~ links are accurately predicted among the top-*L* links. Then the precision can be defined as eq. [14](#Equ14){ref-type=""}:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rm{Precision}}=\frac{{L}_{r}}{L}\mathrm{.}$$\end{document}$$

Datasets of real networks {#Sec8}
-------------------------

In order to compare the prediction accuracy of the SFCN model with the eight mainstream indexes mentioned in this paper, we do MATLAB simulation experiments in five real networks: the network of scientific communication (NS)^[@CR28]^, the US political blogs network (PB)^[@CR29]^, the protein interaction network (Yeast)^[@CR30]^, the neural network of C.elegans (CE)^[@CR31]^, the food web network of florida bay (FWFB)^[@CR32]^. All datasets of the five networks can be seen in the electronic supplementary material. The basic features of those networks are summarized in Table [1](#Tab1){ref-type="table"}.Table 1Details of networks.Networks\|*V*\|\|*E*\|\<*d*\>\<*k*\>\<*H*\>\<*C*\>\<*r*\>CE29721482.4614.46461.80080.3079−0.163FWFB12820751.7832.42191.23700.3346−0.112NS3799144.934.821.660.798−0.082PB1222167142.7427.35522.97070.3600−0.221Yeast2375116935.099.84673.47560.38830.454\|*V*\| and \|*E*\| are the number of nodes and links, respectively. \<*d*\> is the average shortest distance between node pairs. \<*k*\> is the average degree, and \<*H*\> denotes the degree heterogeneity. \<*C*\> represents the clustering coefficient. \<*r*\> is the assortative coefficient.

The metrics that characterize the networks can be seen in the caption of Table [1](#Tab1){ref-type="table"}. We find that NS, PB and CE have similar characteristics, including the high clustering coefficient. Nevertheless, for FWFB network, the relation between predator and prey makes the network have a larger average degree and a shorter average distance between node pair.

Existing similarity indexes based on topological structure {#Sec9}
----------------------------------------------------------

Here, we introduce eight mainstream similarity indexes to compare with the SFCN model.CN. Let Γ~*x*~ be the set of neighbors of *x*. The CN index proposes that node pair (*x*, *y*) are more likely to connect if they have more common neighbors, namely:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{CN}=|{{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}|\mathrm{.}$$\end{document}$$Salton^[@CR20]^. It is defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{Salton}=\frac{|{{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}|}{\sqrt{{k}_{x}{k}_{y}}},$$\end{document}$$where *k* ~*x*~ is the degree of node *x*.RA^[@CR23]^. The RA index assumes each transmitter has a unit of resource and will equally distributed to all its neighbors, concluded as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{RA}={\sum }_{z\in {{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}}\,\frac{1}{{k}_{z}}.$$\end{document}$$HPI^[@CR22]^. It is defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{HPI}=\frac{|{{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}|}{{\rm{\min }}\,\{{k}_{x},{k}_{y}\}}\mathrm{.}$$\end{document}$$HDI^[@CR23]^. It is defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{HDI}=\frac{|{{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}|}{{\rm{\max }}\,\{{k}_{x},{k}_{y}\}}\mathrm{.}$$\end{document}$$Leicht-Holme-Newman index (LHN)^[@CR21]^. The LHN index is defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{LHN}=\frac{|{{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}|}{{k}_{x}{k}_{y}}\mathrm{.}$$\end{document}$$LNBRA^[@CR24]^. The LNBRA index is an improvement in RA index based on the LNB model, defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{LNBRA}=\sum _{z\in {{\rm{\Gamma }}}_{x}\cap {{\rm{\Gamma }}}_{y}}\,\frac{1}{{k}_{z}}({\mathrm{log}}_{2}\eta +{\mathrm{log}}_{2}{R}_{z}),$$\end{document}$$where *η* and R ~*z*~ are defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\eta =\frac{|V|(|V|-1)}{2|{E}^{T}|}-1,$$\end{document}$$$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${R}_{z}=\frac{{N}_{{\rm{\Delta }}z}+1}{{N}_{\nabla z}+1},$$\end{document}$$where *N* ~Δ*z*~ and *N* ~▽*z*~ are respectively the numbers of connected and disconnected node pairs which have a common neighbor *z*.Local Path (LP)^[@CR33]^. This index considers the number of different orders, defined as:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${s}_{x,y}^{LP}={({A}^{2})}_{x,y}+\alpha \cdot {({A}^{3})}_{x,y},$$\end{document}$$where *α* is an adjustable parameter and *A* is the adjacency matrix of network. (*A*^*i*^)~*x*,*y*~ represents the quantity that the order length is equal to *i* between *x* and *y*.

Experiments and performance analysis {#Sec10}
------------------------------------

In this section, we do three experiments and make corresponding analysis for three purposes. In the first and second experiments, the *E*^*T*^ contains 90% of links, while the remaining 10% of links constitute the *E*^*P*^. In addition, all the following results are returned with the average over 100 independent experiments.

For the first experiment, to verify whether the contribution of the future common neighbors is necessary, we conducted priori experiments on *α* and *β* in FWFB network. Step 1, since the training set (*E*^*T*^) is known, we divide *E*^*T*^ into the sub-training set (*E*^*T*1^) and the sub-probe set (*E*^*P*1^) to learn the values of *α* and *β* in step 2. Step 2, we apply the SFCN model to the sub-training set in order to obtain the similarity scores of the sub-probe set and get the AUC that varies with *α* and *β*. In this way, it is easy to select the numerical values of *α* and *β* with high AUC for the SFCN model. The experimental results are shown in Fig. [3](#Fig3){ref-type="fig"}. Before that, it is necessary to consider the two limit problems. When *α* = 0, the current common neighbors in the SFCN model do not make any contribution, and only the future common neighbors make contributions. When *β* = 0, there are only contribution from the current common neighbors, and the future common neighbors do not make any contributions for link prediction. We can get two results from the Fig. [3](#Fig3){ref-type="fig"}. First, the AUC when *β* = 0 is much lower than that when *β*≠0. Second, the SFCN model can obtain highest AUC when *α* and *β* are adjust to a suitable value. For example, for the SFCN-CN-RA, SFCN-Salton-HDI, and SFCN-LNBRA-LHN algorithms, we should set *α* smaller and *β* larger to get a higher prediction accuracy in FWFB network. These two results illustrate the important contribution of the future common neighbors.Figure 3AUC sensitivity analysis of the SFCN model in FWFB network. X-axis is the *α* value that is taken from 0 to 15 at intervals of 3. Y-axis is the *β* value that is taken from 0 to 2 at intervals of 0.4.

Therefore, in the second and the third experiments later, we set *α* = 9 and *β* = 1, which meet the above condition.

The second experiment is to compare the SFCN model with other eight similarity-based indexes, including the CN, HDI, HPI, LP, RA, Salton, LNBRA and LHN index. The prediction results of AUC and precision are listed in Tables [2](#Tab2){ref-type="table"} and [3](#Tab3){ref-type="table"} for details, respectively. Most comparative experiments, in the Table [2](#Tab2){ref-type="table"}, clearly demonstrate that the SFCN model has the best or close to the best AUC, especially in the FWFB and Yeast networks. Taking the FWFB network as an example for analysis, we can see that there are 2075 links but only 128 nodes from the Table [1](#Tab1){ref-type="table"}. And the average degree is as high as 32.422 while the average aggregation coefficient is low to 0.3346, which indicate that there are many random connections and high obscure similarity between the clusters in the FWFB network. These are the reasons why all nodes in the FWFB network have the tendency to gather and form some unknown clusters with the network evolving. The SFCN model takes into account the network evolution tendency via the principle of similarity index. In detail, the model has greatly improved the AUC in FWFB network by regarding the future common neighbors as the evolution direction. Moreover, Table [3](#Tab3){ref-type="table"} demonstrates that 90% of the precision results, predicted based on the SFCN model, are equal to or higher than that predicted based their original algorithm. For example, the precision results of the SFCN-HDI-RA algorithm are much higher than those of the original HDI algorithm in most network, because the contributions of the future common neighbors are taken into account.Table 2There are the prediction accuracy results, measured by AUC, of classic indexes and corresponding algorithms based on the SFCN model in five real networks.AUCCEFWFBNSPBYeastCN0.8460.6160.9890.9250.917SFCN-CN-RA0.8760.6590.9890.9390.971Salton0.8020.5320.9840.8800.914SFCN-Salton-HDI0.8510.7930.9840.9370.974RA0.8710.5980.9770.9270.924SFCN-RA-HDI0.8720.7940.9910.9380.975LP0.8610.6330.9800.9380.971SFCN-LP-RA0.8720.6660.9900.9420.978HPI0.8040.5280.9790.8550.912SFCN-HPI-HPI0.8110.7620.9850.9010.972SFCN-HPI-RA0.8650.7900.9890.9450.974HDI0.7750.5270.9800.8730.914SFCN-HDI-HDI0.8490.7820.9850.9350.976SFCN-HDI-RA0.8890.7950.9900.9470.977LNBRA0.8630.6590.9800.9280.920SFCN-LNBRA-RA0.8830.7960.9930.9490.977SFCN-LNBRA-HDI0.8810.8090.9920.9420.975SFCN-LNBRA-LHN0.8780.8430.9890.9410.975LHN0.7250.3900.9740.7660.906SFCN-LHN-LHN0.8100.8910.9830.8910.974SFCN-LHN-RA0.8760.7970.9920.9470.977SFCN-LHN-LP0.8060.7040.9740.9280.961SFCN-LHN-HDI0.8390.7980.9840.9360.976Table 3There are the prediction accuracy results, measured by precision (top-100), of classic indexes and corresponding algorithms based on the SFCN model in five real networks.PrecisionCEFWFBNSPBYeastCN0.1980.0940.3960.4600.678SFCN-CN-RA0.2020.1080.4040.4640.766Salton0.0120.0080.2900.0000.024SFCN-Salton-HDI0.0120.0100.2600.0000.032RA0.1240.0940.5640.2560.520SFCN-RA-HDI0.1300.0980.5660.2780.440LP0.1240.1120.3120.4000.654SFCN-LP-RA0.1400.1120.3240.4100.696HPI0.0260.0680.5560.2240.860SFCN-HPI-HPI0.0360.3880.1920.2240.868SFCN-HPI-RA0.1160.3820.1620.5660.896HDI0.0320.0080.3100.0020.030SFCN-HDI-HDI0.0860.3600.3200.5160.900SFCN-HDI-RA0.1060.3600.2940.5900.882LNBRA0.1310.1620.5440.2520.586SFCN-LNBRA-RA0.1360.1660.5540.2500.580SFCN-LNBRA-HDI0.1300.1640.5640.2780.602SFCN-LNBRA-LHN0.1320.1540.5800.2600.586LHN0.0000.0140.1380.0000.010SFCN-LHN-LHN0.0000.0260.1380.0000.014SFCN-LHN-RA0.0000.0140.1380.0000.012SFCN-LHN-LP0.0000.0200.1380.0000.012SFCN-LHN-HD0.0000.0180.1400.0000.010

Finally, in order to explore the robustness, we change the ratio of training set to probe set in the third experiment. The lower the ratio, the more links information that should be predicted^[@CR34]^. That is to say, there are less number of the known connected links and more number of the unknown links when the ratio is small. It is obviously to obtain two results from the Fig. [4](#Fig4){ref-type="fig"}. On the one hand, when the ratio is the same, the algorithms based on SFCN model have higher prediction accuracy results (measured by AUC) than their corresponding original algorithms. For instance, the SFCN-LHN-RA, SFCN-LHN-LP and SFCN-LHN-HDI algorithms have higher AUC compared with the original LHN algorithms when the ratio is the same. On the other hand, even when the ratio is low, the algorithms based on SFCN model still get high AUC, which indicates that the SFCN model has higher stability. Therefore, the SFCN model has better performance in prediction accuracy and stability even when there is few links information.Figure 4The AUC of different algorithms with different ratio of training sets to probe sets in real networks. X-axis is the ratio, and Y-axis is the each algorithm.

Discussion {#Sec11}
==========

Exploring what factors can provide a positive impact on link prediction is an important and challenging problem. In this paper, we firstly discover the existence of the future common neighbors, which are classified into three types according to their topological structure with other nodes. Then, to investigate whether the future common neighbors can make positive contribution for current link prediction, we propose the similarity-based future common neighbors model (SFCN), which accurately locates all the future common neighbors and effectively measure their contributions in complex networks, besides the current common neighbors.

We design three simulation experiments via the MATLAB for three different purposes. First, we conduct priori experiments on *α* and *β* in FWFB network. The results provide strong evidence that the future common neighbors can make great contribution than current common neighbors in complex networks. In the second experiments, we compare the SFCN model with eight algorithms in five networks, finding that the SFCN model has higher prediction accuracy, especially the AUC in the FWFB and Yeast networks. Third, in order to verify whether the SFCN model can get great accuracy when the known link information is little, we change the ratio of the training set to the probe set in five networks. And the experiment results show that the SFCN model has better performance robustness, even when the ratio is low to 0.45, compared with eight similarity-based algorithms. Therefore, the proposed SFCN model has higher accuracy and performance robustness than popular similarity-based algorithms, and the future common neighbors make more positive contribution than the current common neighbors that is widely used nowadays.

Some extensions of this work deserve further exploration. One is that we are limited to the current common neighbors and the future common neighbors in evolving networks. It is meaningful to research the contribution of the future nodes and the future links. For example, current path-based algorithms only consider the contribution of the existing paths currently, so it is significative to further exploit whether and how much the future paths, which are not existing currently but will exist after once prediction, can make a positive impact on current link prediction.

Methods {#Sec12}
=======

Algorithm of the SFCN model for link prediction {#Sec13}
-----------------------------------------------

The adjacency matrix *E* is a sparse matrix of the complex network. And the pseudocode of the SFCN model is presented in algorithm 1.Algorithm 1Algorithm of the proposed SFCN framework.

Complexity analysis {#Sec14}
-------------------

This part give a simple complexity analysis of the proposed SFCN model. The most time-consuming part occurs in computing the contribution of the future common neighbors. The time cost of ($\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\boldsymbol{S}}}_{{\boldsymbol{y}}}^{{\boldsymbol{C}}{\bf{2}}}$$\end{document}$) is *O*(\|*V*\|\|*V*\|), and the time cost of ($\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\boldsymbol{S}}}_{{\boldsymbol{x}}}^{{\boldsymbol{C}}{\bf{2}}}$$\end{document}$) is *O*(\|*V*\|\|*V*\|). Thus the total time cost of the future common neighbors is 3⋅*O*(\|*V*\|\|*V*\|\|*V*\|). Since complex network can be simplified as an sparse matrix, the final computational complexity is much less than 3⋅*O*(\|*V*\|\|*V*\|\|*V*\|).

Electronic supplementary material
=================================

 {#Sec15}

Data sets of five networks.zip

**Publisher's note:** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Zhigang Zhang, Jianhang Liu, Tingpei Huang and Haihua Chen contributed equally.

Electronic supplementary material
=================================

**Supplementary information** accompanies this paper at 10.1038/s41598-018-35423-2.

This work is supported by the National Natural Science Foundation of China under Grant Nos 61402433 and 61601519; The Fundamental Research Funds for the Central University, with No. 18CX02134A, No.18CX02137A, No.18CX02133A.

S.L. and Z.Z. conceived the study; S.L., J.H. and Z.Z. designed the experiments and algorithms; J.H. prepared figures and tables; S.L. and Z.Z. collected data; S.L. and J.H. wrote the paper. J.L., T.H. and H.C. modified the pictures and paper. All authors reviewed the manuscript.

Competing Interests {#FPar1}
===================

The authors declare no competing interests.
