{'fraction_non_alphanumeric': 0.021223857474825716, 'fraction_numerical': 0.004647560030983733, 'mean_word_length': 4.828893905191873, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Research on Link Prediction Based on Similarity Index Algorithm

For social network with no rights and no directions, link prediction has lower computational complexity and higher link prediction accuracy by using similarity metrics. The existing local information-based similarity metrics are mostly calculated by the common neighbors of the pair of nodes to be predicted when performing link prediction, but these methods do not consider the influence of the relationship between the common neighbors. Aiming at this problem, this paper proposes a new link prediction algorithm based on the existing local information-based similarity measurement method, which not only considers the number and degree of common neighbors between the pairs of nodes to be predicted, but also considers the relationship between common neighbors. In order to verify the effectiveness of the algorithm, the proposed algorithm is compared with the original algorithm and other methods based on the similarity measure of local information in this paper. The experimental results demonstrate the effectiveness of the algorithm.


Introduction
In the real world, relationships between entities can be abstracted into various complex networks such as online social networks, power networks, aviation networks and protein networks. Link prediction refers to the possibility of predicting two unconnected nodes that are hidden or may generate links in the future through the structural information or their information of the nodes. The problem of link prediction has great application value in real life. It can be used to recommend products to customers [1] and can be used for e-mail prediction [2]. It also can help to understand the micro-mechanism of network modeled and provide a theoretical basis for modeling social networks.
Link prediction for social networks is a hot topic which has being researched currently. The methods of link prediction mainly include similarity-based metrics, matrix-based factorization, and probabilitybased graph models. The methods of calculating the similarity value mainly include the similarity index based on the local information and the similarity index based on the path. Among them, the similarity index based on local information mainly includes common neighbor (CN) index [3], Jaccard index [4], resource allocation (RA) index [5], etc. Path-based similarity index includes local path (LP). Indicator [6], Katz indicator [7], etc. The methods based on matrix factorization include spectral transformation [8] and matrix decomposition [9][10][11][12][13], but the computational complexity of such methods is generally high. The methods based on probability map model include local probability map model [14], potential friend propagation model [15], and random walk [16] and so on. For social networks with no rights and direction, the method for link prediction based on similarity measure has lower computational complexity and higher prediction accuracy, so people tend to choose method of calculating the similarity value to do link prediction of graphs which not be weighted and directed with the method of measuring the similarity of information or local paths. The existing local information-based link prediction method obtains the similarity value of the node to be predicted by calculating the common neighbor between the pairs of nodes to be predicted. But in the process, the common neighbor node is often considered as an independent node without considering the relationship between themselves. Aiming at this problem, this paper proposes a new link prediction algorithm based on the existing local information-based similarity measure method. In this algorithm, the relationship between public neighbors is considered in the calculation of similar values. And the accuracy of link prediction can be improved by using this algorithm.

Link prediction
A social network is defined as G (V, E), where V represents the set of nodes of the network and E represents the set of relationships (directed or undirected) between the nodes in the network. The social network is divided into directed network and undirected network according to whether the edges have direction between the nodes or not, and is divided into a right network and an unprivileged network according to whether the edge exists values which are calculated by some information. Link prediction refers to a probability can be calculated through a link prediction algorithm that two points that are connected or may generate a relationship at the next moment. This article focuses on research on social networks which have no rights and direction. All the link prediction processes can be visually represented as

The similarity indexes based on local information
The method based on the similarity measure considers that the higher similarity values of the two nodes, the more likely they would have a relationship at the next moment. There are several methods for the similarity index based on local information that are well known today: 1. Common Neighbors (CN) algorithm. This algorithm considers the number of common neighbors between two nodes to be predicted. If the number of common neighbors is higher, the more similar they are and the more likely the link between them will be. Assuming that the nodes to be predicted are and , the similarity value of the nodes and can be calculated as shown in equation (1).
Where CN represents the number of common neighbors of nodes and , ( ) represents the neighbor of node , and represents the neighbor node of node . 2. Adamic-Adar (AA) algorithm. This algorithm is still considered the common neighbors between the nodes which would be predicted. But this algorithm not only considers the number of common neighbors, but also considers the degree of the single neighbor node in the common neighbors. The main idea is that the neighbor nodes with small degree in the network have more influence on the similarity than the neighbor nodes with large degree. Assuming that the nodes to be predicted are and , the similarity value of the nodes and can be calculated as shown in equation (2).
Where AA represents the similarity value of nodes and , ( ) represents the common neighbors of nodes and , and ( ) represents the degree of public neighbors. 3. Jaccard algorithm. This algorithm calculates the ratio of the number of common neighbors between nodes to be predicted to the number of neighbors to be predicted. Assuming that the nodes to be predicted are and , the similarity values of nodes and can be calculated as shown in equation (3).
A B N1 N2 Figure 2. The processes of link prediction Where Jaccard represents the similarity value of nodes and , ( ) represents the neighbor of node , and represents the neighbor node of node . 4. Resource Allocation (RA) algorithm. This algorithm considers the effect of common neighbor degree on similarity when calculating similar values. It is assumed that the node passes the resource to through the common neighbor nodes with , and the common neighbor would divide the resource equally to its neighbor node. The similarity value can be calculated as shown in formula (4).
Where RA represents the similarity value of nodes and , ( ) represents the common neighbors of nodes and , and ( ) represents the degree of common neighbors.

Algorithm Inprovement
For two nodes that are not related to each other, the common neighbors between them is an important medium for the transfer relationship so that the calculation of the common neighbor is the main factor affecting the size of the similarity value. However, it is not enough just using the number and degree of common neighbors when do link prediction. For example, there are multiple common neighbors for the nodes to be predicted and , the relationship between and will be less than expected if only the number of common neighbor nodes is considered, regardless of the common neighbor nodes. For a real network, there is often a high correlation between neighbors that is these neighbors are connected to each other. So that the relationship between the public neighbor nodes should be fully considered when calculating similar values by the neighbor nodes. In order to solve the above problems, an improved algorithm is proposed to consider the relationship between common neighbor nodes in the calculation of similarity value based on RA which can improve the prediction accuracy.
As shown in Figure 2. The traditional RA algorithm considers that the common neighbors between nodes A and B are independent and have no relationship. Therefore, when calculating the similarity value, it is not necessary to consider A B N1 N2 Figure 3. The processes of link prediction The influence of the connection between the common neighbor nodes on the similarity value. But in real life, the common neighbors between the two nodes A and B are usually connected. As shown in Figure 3, According to the idea of the RA algorithm, when the node A passes the resource to the node B through the common neighbor node N1, the node N1 may also transfer the resource to the node B through the node N2.
Assuming that the nodes to be predicted are and , the similarity value of the nodes and can be calculated as shown in equation (5).
Where NRA represents the similarity value of nodes and , ( ) represents the common neighbors of nodes and , ( ) represents a set of partial neighbor nodes of the common neighbor which is a subset of ( ). And ( ) represents the degree of common neighbor.

Datasets
In order to verify the effect of the proposed algorithm, the proposed algorithm and the other similar methods based on local information calculations mentioned in this paper are compared on multiple datasets. The datasets which are used in this experiment are the American Aviation Network (USAir),

Evaluation Index
The commonly used evaluation indexes for link prediction are P value and AUC value, but the size of P has a great relationship with the number of positive samples obtained so that is has great randomness. The value of AUC can measure the accuracy of the algorithm as a whole degree so that this paper chooses AUC as the evaluation index of the algorithm. The specific calculation method is shown in formula (5).
This formula means: randomly select an edge from the test set and non-existent edge set in order. After independently selecting n times, represents how many times the score of the test edge is larger than that of the non-existent edge and represents how many times the score of test edge is equal to that of non-existent edge. Obviously, AUC ≈ 0.5 for random edge selection algorithm. Thus, the accuracy of the prediction algorithm depends on whether its AUC is significantly greater than 0.5 or not.

Experimental Results
The algorithm (NRA), CN algorithm, AA algorithm, Jaccard algorithm and RA algorithm are used to link prediction on the four kinds of datasets which are not considered node attributes and edge attributes. We use evaluation index AUC to judge the pros and cons of the algorithm and the comparison results are shown in Table 2. It can be seen from Table 2 that the proposed algorithm has better link prediction results than the other four algorithms for link prediction whether in the Air network dataset or in the other three datasets. Especially that the AUC on the dataset ACF reaches score with 0.9328. NRA is superior to other algorithms because the NRA algorithm fully considers the topology information between neighbor nodes.
In order to make the results look more intuitive, the AUC value of each link prediction algorithm on each dataset is represented by a line graph.

Analysis
It can be seen from Table 2 that the proposed algorithm has better link prediction results than the other four algorithms for link prediction whether in the Air network dataset or in the other three datasets. NRA is superior to other algorithms because the NRA algorithm fully considers the topology information between neighbor nodes.
As shown in figure 4, figure 5, figure 6 and figure 7, even though the original RA algorithm has a good prediction result, the result of the NRA algorithm is still better than the result of RA algorithm.

Conclusion
The NRA algorithm proposed in this paper not only considers the degree of public neighbor nodes, but also fully considers the relationship between common neighbor nodes. Experimental results show that the proposed algorithm has higher prediction accuracy.
The research in this paper is based on the social network without power and undirected. In fact, every node and edge have attributes, and there may has multiple relationships between nodes and nodes in real life. If multiple attributes are considered, there will be multiple edges, which are ignored in the study of this paper. In future research, more practical problems will be considered to improve the accuracy of link prediction.