Study on similarity indices for link prediction in opportunistic networks

Abstract

Link prediction aims to estimate the existence of links between nodes, using information of network structures and node properties. According to the characteristics of node mobility, node intermittent contact, and high delay of opportunistic network, novel similarity indices are constructed based on CN, AA, and RA. The indices CN, AA, and RA do not consider the historic information of networks. Similarity indices, T_CN, T_AA, and T_RA, based on temporal characteristics are proposed. These take the historic information of network evolution into consideration. Using historic information of the evolution of opportunistic networks and 2-hop neighbor information of the nodes, similarity indices based on the temporal-spatial characteristics, O_CN, O_AA, and O_RA, are proposed. Based on the imote traces cambridge (ITC) and detected social network (DSN) datasets, the experimental results indicate that similarity indices O_CN, O_AA, and O_RA outperform CN, AA, and RA. Furthermore, index O_AA has superior performance.

Introduction

Opportunistic network (ON) ¹ is a new type of network that is self-organizing and does not require complete connectivity, as communication between nodes is generated by their movement. The data transmission in ON occurs using a “store-carry-forward” routing mechanism. ON has an advantage in many applications compared to the established fully connected networks. Because of the development and low cost, ON has been applied across many fields, such as vehicular ad hoc networks, ² mobile data diversion, ³ information sharing, ⁴ and mobile computing. ⁵

The dynamic characteristics of ON lead to a difficulty in the selection of routing. The point to solve the problem is to predict the link through capturing the change law of network topology so that routing algorithm is supported.

Link prediction is to predict the probability of connection between nodes at the next moment through node attributes, network topology, and network historical information. According to the characteristics of node mobility and intermittent connectivity, this article studies the similarity indices of link prediction. Section “Related work” analyzes the studied reported in the literature to date. Section “Problem description” identifies the problems associated with link prediction. Section “Improvement of similarity indices” constructs improved similarity indices. Section “Experiments and analysis” describes the experimental data and analysis. Section “Conclusion” makes conclusions.

Related work

The methods of link prediction for ON primarily fall into the following categories: predictions based on similarity indices, node moving models, mixed frameworks, matrix and tensor decompositions, and machine learning. The study of similarity indices can be divided into local information similarity indices and path similarity indices.

Based on local information similarity indices

The similarity indices based on local information calculate the similarity between nodes using the following local information, such as the degree of nodes and common neighbors. The method is suitable for large-scale network applications because of its lower computational complexity.

The simplest index is CN^6,7 which means common neighbor. If there are many common neighbors between nodes x and y, the nodes x and y are similar, and the CN index is defined in equation (1)

$$S_{\mathrm{xy}}^{\mathrm{CN}}=|\mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)|$$

(1)

where $\mathrm{\Gamma }(x)$ is the neighbor set of node x, and $\mathrm{\Gamma }(y)$ is the neighbor set of node y. The CN index does not consider the influence of the node degree. On the basis of CN, there are some similarity indices which consider the influence of node degree, such as Jaccard’s Coefficient (JC) index, ⁸ Salton index, ⁹ and Leicht-Holme-Newman-I (LHN-I) index. ¹⁰ These similarity indices are defined in equation (2)–(4), respectively

$$S_{\mathrm{xy}}^{\mathrm{JC}}=\frac{|\mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)|}{|\mathrm{\Gamma }\left(x\right)\cup \mathrm{\Gamma }\left(y\right)|}$$

(2)

$$S_{\mathrm{xy}}^{\mathrm{Salton}}=\frac{|\mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)|}{\sqrt{k_x{k}_y}}$$

(3)

$$S_{\mathrm{xy}}^{\mathrm{LHN}-I}=\frac{2\times |\mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)|}{k_x+k_y}$$

(4)

The Adamic/Adar (AA) index^11,12 and resource allocation (RA) index^13,14 take into account the degree of the common neighbors. The AA index considers that the contribution of the common neighbors with a small degree is bigger than the common neighbors with a large degree. According to the degree of the common neighbors, each node is given a weight, and AA is defined in equation (5)

$$S_{\mathrm{xy}}^{\mathrm{AA}}=\sum _{z\in \mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)}\frac{1}{\log k_z}$$

(5)

The RA index is the same as the AA index, with the exception that the weight value of the RA index is equal to the reciprocal of the node degree, which is defined in equation (6)

$$S_{\mathrm{xy}}^{\mathrm{RA}}=\sum _{z\in \mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)}\frac{1}{k_z}$$

(6)

The difference between the AA index and the RA index is the weight given to the common neighbor. If the network clustering coefficient is small, link prediction primarily depends on the existence of common neighbors between the nodes in the network, resulting in the prediction results of index AA and RA being similar. If the network clustering coefficient is big, and the heterogeneity is large, the two indices are significantly different because of the different methods of weighting. The literature^15,16 suggests that the RA index is better in depicting the weighted network and community network.

The literature ¹⁷ analyzes the betweenness centrality of the nodes, in combination with the similarity index of CN. At the same time, considering the network topology features and local information of the nodes, and the optimization of the common neighbors weighting, it proposes an improved B-CN index to improve prediction accuracy. In the literature, ¹⁸ based on the AA index, it combines the frequency of connection among nodes with the degree of the common neighbors as the similarity index, and the characteristics of network history structure using kernel regression are extracted, improving the prediction accuracy of the link. Another study reported in the literature ¹⁹ is based on the AA index. This study proposes a hypothesis for network data flow regions and estimates the similarity among nodes using three stream-based methods. Three kinds of links have been proposed in the literature: ²⁰ periodic and frequent connection, non-periodic but frequent connection, and non-frequent connection. The method of periodic pattern recognition mining, decision tree, and the AA index is used to predict the link. The prediction efficiency and accuracy of the link are improved by selecting the optimal threshold, jitter tolerance ratio, and the time slice length.

Based on path similarity indices

The similarity indices based on the path primarily fall into the following categories: local path (LP) index, ²¹ Katz index, ²² LHN-II index. ¹⁰

The local path similarity index adds the path information with length 3 to the index CN, which is defined in equation (7)

$$S_{\mathrm{xy}}^{\mathrm{LP}}={\mathit{A}}^2+\alpha ·{\mathit{A}}^3$$

(7)

where $\alpha$ is an adjust parameter and $\mathit{A}$ is an adjacency matrix of the network.

The Katz index considers the n-hop paths, and its computational complexity increases in sequence, which is defined in equation (8)

$$S_{\mathrm{xy}}^{\mathrm{Katz}}=\sum _{t=1}^{\infty }{\alpha }^l·|{\mathrm{paths}}_{x,y}^{〈l〉}|$$

(8)

where $\alpha >0$ and denotes an adjust parameter that controls the weight of paths, $|\mathrm{paths}{}_{x,y}^{〈l〉}|$ indicates the set of paths with length $l(l=1,2,\dots ,n)$ between nodes x and y. If the above coefficients converge, the parameter α is less than the reciprocal of the largest eigenvalue of the adjacency matrix. The Katz index can also be defined in equation (9)

$$S_{\mathrm{xy}}^{\mathrm{Katz}}={(\mathit{I}-\alpha ·A)}^{-1}-\mathit{I}$$

(9)

where $\mathit{I}$ is an identity matrix. When the parameter $\alpha$ is very small, the contribution of the high-level paths is very small, which makes the result of prediction based on the Katz index similar to the LP index.

A link prediction algorithm based on matrix and tensor decomposition for intermittently connected wireless network has been proposed in the literature. ²³ It uses Katz as an index to predict the existence of the link in time slice $(T+1)\mathrm{th}$ . Experiments demonstrate the effectiveness of this method.

Based on the regular equivalence, the LHN-II index has been proposed in the literature. ¹⁰ If the neighbors of node x are similar to node y, then nodes x and y are similar. That is, the similarity of the nodes is transitive. LHN-II index is defined as in equation (10)

$$S_{\mathrm{xy}}^{\mathrm{LHN}-\mathrm{II}}=2M{\lambda }_1{\mathit{D}}^{-1}{(\mathit{I}-\frac{\varphi }{{\lambda }_1}\mathit{A})}^{-1}{\mathit{D}}^{-1}$$

(10)

where $\mathit{D}$ is the degree matrix, $\varphi$ is an adjust parameter and $0<\varphi <1$ , ${\lambda }_1$ is the largest eigenvalue of the adjacent matrix $\mathit{A}$ , and M is the total number of network edges.

Based on local information, similarity indices and path similarity indices show a good prediction performance for static networks or social networks with topology change slowly. However, these indices are not suitable for ON whose network topology changes over time. In this article, according to the characteristics of node mobility, node intermittent contact and high delay of ON, based on local information similarity indices, similarity indices based on temporal characteristics are proposed, which take the historic information of network evolution into account. Considering the 2-hop neighbor information of nodes, similarity indices based on spatial characteristics are calculated using the neighborhood expansion method. ²⁴ Considering the temporal and spatial characteristics, similarity indices based on temporal-spatial characteristics are proposed, which can obtain better performance for link prediction in the ON.

Problem description

ON is a typical, dynamic network. The network structure changes over time and it is characterized by a sequence of graphs. To depict the dynamic characteristics of ON, the ON is defined as $G(V,E)$ , V is a set of all nodes in the network, $V=\{v_1,v_2,v_3,\dots ,v_m\}$ , m is the number of nodes, E is a set of edges in the network, $E=\{〈v_a,v_b〉,v_a,v_b\in E\}(a=1,2,\dots ,m,b=1,2,\dots ,m,a\ne b)$ , $G=(G_1,G_2,\dots ,G_n)$ is an ordered atlas in the time slice T, $G_i=(V_i,E_i)(i=1,2,3,\dots ,n)$ is the topology graph of $G(V,E)$ at time i, $V_i$ is a set of vertices, and $E_i$ is a set of edges.

Link prediction of ON is to predict the network topology at time $T+1$ , using the nodes and network topology information in the time slice T. Link prediction can be defined as follows: given a set of network snapshots $G=(G_1,G_2,\dots ,G_n)$ , the change law of network snapshots is captured using the link prediction method, obtaining the network topology at time $T+1$ , as shown in Figure 1.

Figure 1.

ON link evolution.

In equation (11), $\mathit{A}$ is an adjacency matrix of $G(V,E)$ , which is defined below

$${\mathit{A}}_{i,j}=\{\begin{array}{c}\hfill 1〈v_i,v_j〉\in E\hfill \\ \multicolumn{1}{c}{0〈v_i,v_j〉\notin E}\end{array}$$

(11)

The similarity indices based on local information assume that the two frequent communication nodes have highly similarity of behavior in the network, which conform to the communication characteristics of ON.

Improvement of similarity indices

Based on the local information similarity indices, this article proposes improved similarity indices using the temporal, spatial, and temporal-spatial characteristics of ON.

The temporal characteristics of similarity indices

Indices CN, AA, and RA have good performance for link prediction with network topology change slowly. However, ON’s topology changes frequently and link status is time-varied. Therefore, similarity indices are improved by taking the historic information of network evolution into account.

As shown in Figure 2, the network structure at time $t_3$ is used to predict the link at the next moment, and then the possibility of generating a link between nodes S and D is small. However, if we combine the network topology of time $t_1$ , $t_2$ , and $t_3$ , the possibility of generating a link between nodes S and D becomes bigger. Therefore, the prediction accuracy of the link can be improved by using the historic information of multiple moments in the process of network evolution.

Figure 2.

Link change.

Based on the local information similarity indices CN, AA, and RA, improved similarity indices T_CN, T_AA, and T_RA are proposed, which take the following historic information of the network into account, such as the total length of contact time, the frequency of contact, and the most recent contact time in the evolution of network topology.

As shown in Figure 3, the length of T time slice $[t_S,t_E]$ is taken as an example, where $t_S$ is the beginning of the time slice, $t_E$ is the end of the time slice, $t_0$ is the beginning of contact, and $t_1$ is the end of contact.

Figure 3.

Temporal characteristic of link.

• 1. The total length of contact time

In equation (12), l denotes the total length of contact time, which is defined below

$$l=\sum _{i,j=1}^n(t_i-t_j)$$

(12)

where $i=1,2,3,\dots ,n$ , $j=1,2,3,\dots ,n$ . As shown in Figure 3, $l=(t_1-t_0)+(t_3-t_2)$ , if $t_0<t_s$ , it indicates that the node pair is connected before the time slice T, and $t_S$ is taken as the criterion, then $t_0=t_S$ . Similarly, if $t_1>t_E$ , then $t_1=t_E$ .

• 2. The frequency of contact

In equation (13), f denotes the frequency of contact, which is defined below

$$f=\mathrm{sum}\left(t_i\right)$$

(13)

where $t_i$ is the contact time of node pair $(x,y)$ in the time slice T. As shown in Figure 3, the contact frequency of node pair $(x,y)$ is 2 $(t_0\mathrm{and}{t}_2)$ and $f=2$ .

• 3. The most recent contact time

c is the most recent contact time. As shown in Figure 3, the contact frequency of node pair $(x,y)$ is 2; if the last time of contact is $t_3$ , then $c=t_3$ .

The above analysis suggests that the influence coefficient of the time parameters on the link is defined in equation (14)

$$\mathrm{HIC}=I_l+I_f+I_c$$

(14)

As an example of node pair $(x,y)$ , $I_l$ is the coefficient of the total length of contact time, which is defined in equation (15)

$$I_l=\frac{l}{(t_E-t_S)}$$

(15)

where $I_f$ is the coefficient of the frequency of contact, which is defined in equation (16)

$$I_f=\frac{f}{(k_x+k_y)}$$

(16)

where $k_x$ is the degree of node x, and $k_y$ is the degree of node y. $I_c$ is the coefficient of the most recent contact time, which is defined in equation (17)

$$I_c=\frac{(c-t_0)}{(t_E-t_S)}$$

(17)

This article combines the influence coefficient of the time parameters on the link with the indices CN, AA, and RA. Based on temporal characteristics, improved similarity indices T_CN, T_AA, and T_RA are proposed, which are defined in equations (18)–(20)

$$S_{\mathrm{xy}}^{T\_\mathrm{CN}}=|\mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)|·\mathrm{HI}{C}_{\mathrm{xy}}$$

(18)

$$S_{\mathrm{xy}}^{T\_\mathrm{AA}}=\sum _{z\in \mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)}\frac{\mathrm{HI}{C}_{\mathrm{xy}}}{\log k_z}$$

(19)

$$S_{\mathrm{xy}}^{T\_\mathrm{RA}}=\sum _{z\in \mathrm{\Gamma }\left(x\right)\cap \mathrm{\Gamma }\left(y\right)}\frac{\mathrm{HI}{C}_{\mathrm{xy}}}{k_z}$$

(20)

ON has a complex topology which changes frequently over time. Improved similarity indices of T_CN, T_AA, and T_RA consider the similarities of network structure and network history information of the link, which predicts the links in the ON effectively.

The spatial characteristics of similarity indices

In the ON, node mobility and intermittent contact lead to the network sparse. In a specific time slice, only a few node pairs are connected, and the spatial structure information is insufficient, leading to low accuracy of link prediction. To address the problem, the method of the neighborhood expansion ²⁴ has been proposed. The 2-hop neighbor information of the nodes can improve the indices of CN, AA, and RA.

The network is sparse, and its computational complexity increases as the number of neighbors increases. This article only considers the nodes with 1-hop neighbors and the nodes with 2-hop neighbors.

For arbitrarily node x, we define the 1-hop neighbors in equation (21)

$${\mathrm{\Gamma }}_1\left(x\right)=min\left(D_{\mathrm{zx}}\right)=1$$

(21)

where $D_{\mathrm{zx}}$ is the distance between nodes z and x. The 2-hop neighbors can be defined in equation (22)

$${\mathrm{\Gamma }}_2\left(x\right)=min\left(D_{\mathrm{zx}}\right)=2$$

(22)

The parameters $\theta ,\beta ,\gamma$ are taken as the weight of different order neighbors. The similarity indices E_CN, E_AA, and E_RA are proposed, which are defined in equation (23)–(25)

$$\begin{array}{c}\multicolumn{1}{c}{S_{\mathrm{xy}}^{E\_\mathrm{CN}}=(1-2\theta )|{\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)|}\\ +\theta |{\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_2\left(y\right)|\hfill \\ +\theta |{\mathrm{\Gamma }}_2\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)|\hfill \end{array}$$

(23)

$$\begin{array}{c}\multicolumn{1}{c}{S_{\mathrm{xy}}^{E\_\mathrm{AA}}=(1-2\beta )\sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{\log k_z}}\\ +\beta \sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_2\left(y\right)}\frac{1}{\log k_z}\hfill \\ +\beta \sum _{z\in {\mathrm{\Gamma }}_2\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{\log k_z}\hfill \end{array}$$

(24)

$$\begin{array}{c}\multicolumn{1}{c}{S_{\mathrm{xy}}^{E\_\mathrm{RA}}=(1-2\mathrm{\gamma })\sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{k_z}}\\ +\gamma \sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_2\left(y\right)}\frac{1}{k_z}\hfill \\ +\gamma \sum _{z\in {\mathrm{\Gamma }}_2\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{k_z}\hfill \end{array}$$

(25)

where the range of $\theta ,\beta ,\gamma$ is [0, 0.5].

The temporal-spatial characteristics of similarity indices

Similarity indices based on temporal characteristics take the historic information of network evolution into account, whereas similarity indices based on spatial characteristics consider the network spatial structure. Considering the historic information of ON evolution and 2-hop neighbor information of nodes, similarity indices based on temporal-spatial characteristics O_CN, O_AA, and O_RA are proposed.

According to equation (18)–(20) and (23)–(25), O_CN, O_AA, and O_RA are proposed, which are defined in equations (26)–(28)

$$S_{\mathrm{xy}}^{O\_\mathrm{CN}}=\left(\begin{array}{c}\hfill (1-2\theta )|{\mathrm{\Gamma }}_1(x)\cap {\mathrm{\Gamma }}_1(y)|\hfill \\ \multicolumn{1}{c}{+\theta |{\mathrm{\Gamma }}_1(x)\cap {\mathrm{\Gamma }}_2(y)|}\\ \multicolumn{1}{c}{+\theta |{\mathrm{\Gamma }}_2(x)\cap {\mathrm{\Gamma }}_1(y)|}\end{array}\right)•\mathrm{HI}{C}_{\mathrm{xy}}$$

(26)

$$S_{\mathrm{xy}}^{O\_\mathrm{AA}}=\left(\begin{array}{c}\hfill (1-2\beta )\sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{\log k_z}\hfill \\ \multicolumn{1}{c}{+\beta \sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_2\left(y\right)}\frac{1}{\log k_z}}\\ \multicolumn{1}{c}{+\beta \sum _{z\in {\mathrm{\Gamma }}_2\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{\log k_z}}\end{array}\right)•\mathrm{HI}{C}_{\mathrm{xy}}$$

(27)

$$S_{\mathrm{xy}}^{O\_\mathrm{RA}}=\left(\begin{array}{c}\hfill (1-2\gamma )\sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{k_z}\hfill \\ \multicolumn{1}{c}{+\gamma \sum _{z\in {\mathrm{\Gamma }}_1\left(x\right)\cap {\mathrm{\Gamma }}_2\left(y\right)}\frac{1}{k_z}}\\ \multicolumn{1}{c}{+\gamma \sum _{z\in {\mathrm{\Gamma }}_2\left(x\right)\cap {\mathrm{\Gamma }}_1\left(y\right)}\frac{1}{k_z}}\end{array}\right)•\mathrm{HI}{C}_{\mathrm{xy}}$$

(28)

where the range of $\theta ,\beta ,\gamma$ is $[0,0.5]$ , $k_z$ is the degree of node z, ${\mathrm{\Gamma }}_1(x)\cap {\mathrm{\Gamma }}_1(y)$ is the common neighbor between 1-hop neighbors of nodes x and y, ${\mathrm{\Gamma }}_1(x)\cap {\mathrm{\Gamma }}_2(y)$ is the common neighbor between 1-hop neighbors of node x and 2-hop neighbors of node y, and ${\mathrm{\Gamma }}_2(x)\cap {\mathrm{\Gamma }}_1(y)$ is the common neighbor between 2-hop neighbors of node x and 1-hop neighbors of node y.

Experiments and analysis

In this article, the area under the receiver operating characteristic curve (AUC) and precision of the receiver operating characteristic curve (ROC) are adopted as evaluation indices. In the different datasets, comparison experiments are used to verify the improved similarity indices.

Experimental datasets

The representative real trace datasets imote traces cambridge (ITC) and detected social network (DSN) are selected for the experiments. ITC is a dense dataset, which records the movement and interconnection of students on campus. DSN is a sparse dataset, which records network communication on campus scenes (Table 1).

Table 1.

Information of datasets.

Data set	ITC	DSN
Device	iMote	tMote
Mobile nodes	50	27
Duration (days)	12	79
Network type	Bluetooth	Wireless
Sample interval (s)	10	6.67

The ITC dataset records a 12-day visual trace of students on the Cambridge University campus. The experiment collects the movement trajectories and interconnection using 50 mobile iMote devices. The dataset is short duration and intensive data. A series of network snapshots of 2 days are selected from the ITC dataset, as shown in Figure 4.

Figure 4.

Snapshots of ITC.

The DSN dataset records 79 days of data of students on the St Andrews campus. The experiment collects communication over a wireless network using 27 mobile tMote devices. This dataset is longer and sparse data. A series of network snapshots of 2 days are selected from DSN dataset, as shown in Figure 5.

Figure 5.

Snapshots of DSN.

Experimental environment

MATLAB integrates many powerful functions such as numerical analysis, matrix calculation, scientific data visualization, modeling, and simulation of nonlinear dynamic system into an easy-to-use Windows environment. In this article, MATLAB is used to conduct comparative experiments on the similarity index between the indices CN, AA, and RA and the improved similarity indices. In total, 80% for training and 20% for testing are used in the ITC and DSN datasets.

Experimental results and analysis

In the ITC and DSN datasets, the improved similarity indices are compared to the indices CN, AA, and RA, and O_CN, O_AA, and O_RA are also compared.

Comparison with indices CN, AA, and RA

The AUC and precision are adopted to evaluate the performance of these similarity indices.

• 1. Comparison with index CN

In the ITC and DSN datasets, the different length of time slices is intercepted. The AUC and precision of CN, T_CN, E_CN, and O_CN are calculated. The results are shown in Figures 6–9.

Figure 6.

AUC comparison of CN and improved similarity index in ITC dataset.

Figure 7.

AUC comparison of CN and improved similarity index in DSN dataset.

Figure 8.

Precision comparison of CN and improved similarity index in ITC dataset.

Figure 9.

Precision comparison of CN and improved similarity index in DSN dataset.

From Figures 6 to 9, it shows that the prediction accuracy of indices CN, E_CN, and O_CN decreases with the increase in the time slice in the ITC dataset. And the prediction accuracy of four indices increases with the increase in the time slice in the DSN dataset.

The prediction accuracy of T_CN index increases with the increase in the time slice in ITC and DSN datasets, which indicates that the T_CN index is less affected by the degree of network. E_CN has little effect on the similarity of nodes in sparse networks, but has a significant effect in dense networks. In general, compared with the CN index, the similarity indices T_CN, E_CN, and O_CN have better performance, and the prediction accuracy of O_CN is greatest.

• 2. Comparison with index AA

In the ITC and DSN datasets, the different length of time slices is intercepted. The AUC and precision of AA, T_AA, E_AA, and O_AA are calculated. The results are show in Figures 10–13.

Figure 10.

AUC comparison of AA and improved similarity index in ITC dataset.

Figure 11.

AUC comparison of AA and improved similarity index in DSN dataset.

Figure 12.

Precision comparison of AA and improved similarity index in ITC dataset.

Figure 13.

Precision comparison of AA and improved similarity index in DSN dataset.

From Figures 10 to 13, it shows that the prediction accuracy of indices AA, E_AA, and O_AA decreases with the increase in the time slice in the ITC dataset. And the prediction accuracy of four indices increases with the increase in time slice in the DSN dataset.

The prediction accuracy of T_AA index increases with the increase in the time slice in the ITC and DSN datasets, which indicates that the T_AA index is less affected by the degree of network. E_AA has little effect on the similarity of nodes in sparse networks, but has a significant effect in dense networks. In general, compared with the AA index, the similarity indices T_AA, E_AA, and O_AA have better performance, and the prediction accuracy of O_AA is greatest.

• 3. Comparison with index RA

In ITC and DSN datasets, the different length of the time slices is intercepted. The AUC and precision of RA, T_RA, E_RA, and O_RA are calculated. The results are shown in Figures 14–17.

Figure 14.

AUC comparison of RA and improved similarity index in ITC dataset.

Figure 15.

AUC comparison of AA and improved similarity index in DSN dataset.

Figure 16.

Precision comparison of RA and improved similarity index in ITC dataset.

Figure 17.

Precision comparison of RA and improved similarity index in DSN dataset.

From Figures 14 to 17, it shows that the prediction accuracy of indices RA, E_RA, and O_RA decreases with the increase in the time slice in the ITC dataset. The prediction accuracy of four indices increase with the increase in the time slice in the DSN dataset.

The prediction accuracy of T_RA index increases with the increase in the time slice in the ITC and DSN datasets, which indicates that the T_RA index is less affected by the degree of network. E_RA has little effect on the similarity of nodes in sparse networks, but has significant effect in dense networks. In general, the similarity indices T_RA, E_RA, and O_RA have better performance compared to the RA index, and the prediction accuracy of O_RA is greatest.

The above experiments suggest that the improved similarity indices perform better in ITC and DSN datasets, comparing to the indices CN, AA, and RA. Particularly, the similarity indices O_CN, O_AA, and O_RA have the best performance.

Comparison with indices O_CN, O_AA, and O_RA

In the ITC and DSN datasets, the different length of time slices is intercepted, and the AUC and precision of O_CN, O_AA, and O_RA are calculated. The results are shown in Figures 18–21.

Figure 18.

AUC comparison of similarity index in ITC dataset.

Figure 19.

AUC comparison of similarity index in DSN dataset.

Figure 20.

Precision comparison of similarity index in ITC dataset.

Figure 21.

Precision comparison of similarity index in DSN dataset.

From Figures 18 to 21, the AUC and precision of O_AA index are better than O_CN, O_RA in the ITC and DSN datasets. Therefore, in the ON, the O_AA index has the superior performance.

Finally, based on the above experimental results, we can conclude that the similarity indices O_CN, O_AA, O_RA are superior to CN, AA, and RA, and the index O_AA is the best in the ON.

Conclusion

In this article, the similarity indices for link prediction of ON are analyzed. According to the temporal-spatial characteristics of ON, improved similarity indices are proposed, which outperform the indices CN, AA, and RA. Furthermore, index O_AA has the superior performance. The primary works in this article are as follows: (1) analyzing the similarity indices based on local information and on path, (2) describing an ON model and defining its network snapshots, (3) proposing similarity indices based on the temporal characteristics, T_CN, T_AA, and T_RA, which take historic information of network evolution into account, (4) proposing similarity indices based on the temporal-spatial characteristics, O_CN, O_AA, and O_RA, which consider the historic information of ON evolution and 2-hop neighbor information of the nodes, and (5) verifying these similarity indices using ITC and DSN datasets.

The shortcomings of this research are time slice segmentation and weight parameters based on temporal-spatial characteristic similarity indices. Therefore, the future research directions include (1) the method of time slice segmentation, and the appropriate time slice improves the accuracy of the similarity indices and (2) the selection of weight parameters. The appropriate weight parameters make the similarity indices represent the similarity between nodes more property.