{'fraction_non_alphanumeric': 0.03747782377291543, 'fraction_numerical': 0.015745121230041396, 'mean_word_length': 4.7084388185654005, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Link Prediction via controlling the leading eigenvector

Link prediction is a fundamental challenge in network science. Among various methods, similarity-based algorithms are popular for their simplicity, interpretability, high efficiency and good performance. In this paper, we show that the most elementary local similarity index Common Neighbor (CN) can be linearly decomposed by eigenvectors of the adjacency matrix of the target network, with each eigenvector's contribution being proportional to the square of the corresponding eigenvalue. As in many real networks, there is a huge gap between the largest eigenvalue and the second largest eigenvalue, the CN index is thus dominated by the leading eigenvector and much useful information contained in other eigenvectors may be overlooked. Accordingly, we propose a parameter-free algorithm that ensures the contributions of the leading eigenvector and the secondary eigenvector the same. Extensive experiments on real networks demonstrate that the prediction performance of the proposed algorithm is remarkably better than well-performed local similarity indices in the literature. A further proposed algorithm that can adjust the contribution of leading eigenvector shows the superiority over state-of-the-art algorithms with tunable parameters for its competitive accuracy and lower computational complexity.


Introduction
The booming of network science has brought about a new vision to explore and tackle problems existed in biology [1,2,3], economics [4,5,6,7], social science [8,9], data science [10,11,12] and so on. As an increasing number of datasets are structured by networks (e.g., protein-protein interaction networks, miRNA-disease association networks, drug-target networks, user-product networks, company investment networks, collaboration networks, citation networks, etc.), link prediction [13,14] has found wide applications in many scenarios. For example, in laboratorial experiments, instead of blindly checking all possible interactions among proteins, predicting potential interactions based on existed interactions can sharply reduce experimental costs if the prediction is accurate enough [15]. In social websites, academic websites and e-commerce platforms, a good recommendation of friends, citations, collaborators and products can enhance the loyalties and experience of users and the conversion rate in trading platforms [7]. In sentiment analysis, an effective link prediction algorithm can well capture the relevance of different sentences [16]. In addition, link prediction is also helpful in probing network evolution mechanisms [17,18] and estimating the extent of the regularity of the network formation [19,20]. In a word, link prediction is a significant and challenging problem in network science.
Various methods are proposed, including similarity-based algorithms [21,22,23], probabilistic models [24,25], maximum likelihood methods [26,27,28], network embedding [29,30,31] and other representatives [32,33,34,35]. Among them, similarity-based algorithms are popular for its simplicity, interpretability, high efficiency and satisfactory performance. In this paper, we show that the most elementary index, namely the common neighbor (CN) index [21], is dominated by the leading eigenvector of the adjacency matrix A of the target network, which is caused by the huge gap between the largest eigenvalue and the second largest eigenvalue in many real networks [36]. We propose a parameterfree algorithm that adopts a recently proposed enhancement framework for local similarity indices [37] and ensures the contributions of the leading eigenvector and the secondary eigenvector the same. This algorithm is abbreviated as CLE because its underlying idea is controlling the leading eigenvector. Extensive experiments on real networks demonstrate that the prediction performance of CLE is remarkably better than well-performed local similarity indices and their enhanced versions. We further propose a parameter-dependent algorithm with adjustable contribution of the leading eigenvector, which outperforms elaborately designed algorithms that also have tunable parameters.

Methods
The CN index directly counts the number of common neighbors between two nodes, as where x and y are two arbitrary nodes and Γ x is the set of neighbors of x. The CN matrix S CN can be decomposed as where N is the number of nodes, λ d and v d are the dth eigenvalue and the corresponding orthogonal and normalized eigenvector of A, and λ 2 1 ≥ λ 2 2 ≥ · · · ≥ λ 2 N . Notice that, node x can be represented by the N eigenvectors as where v dx is the xth element of the dth eigenvector. Then, S CN xy is the dot product of w x and w y , as Accordingly, the contribution of each eigenvector to CN is proportional to the square of its eigenvalue. Therefore, the gap between λ 2 1 and λ 2 2 for many real networks [36] leads to the dominant contribution of the leading eigenvector.
Take the email communication network DNC [38] as an example (the detailed circle is proportional to its corresponding value in y-axis. There exists a huge gap between λ 2 1 and λ 2 2 , and thus the correlation coefficient r between S CN and S (1) is larger than the correlation between S CN and S (d) for d > 1. description of this network is shown later), λ 2 1 of DNC is 2.13 times larger than λ 2 2 . As a result, the Pearson correlation coefficient r between S CN and S (1) is much higher than correlation coefficients between S CN and others (see Fig. 1).
The dominant role of the leading eigenvector may oversuppress useful information contained in other eigenvectors, and thus to depress the contribution of the leading eigenvector may better characterize the node similarity. The most straightforward way to tackle this problem is to make the contribution of S (1) the same as S (2) . Accordingly, a parameter-free similarity matrix can be obtained asS It is natural to extendS to a parameter-dependent similarity matrix as where α is a tunable parameter controlling the contribution of v 1 .
Very recently, an enhancement framework, named self-included collaborative filtering (SCF), is proposed for local similarity indices [37]. Given a similarity where I is the identity matrix. This framework largely improves the prediction performance and the robustness of local similarity indices. By applying the enhancement framework onS andS * , we can obtain a parameter-free algorithm (CLE) as and a parameter-dependent algorithm (CLE*) as Clearly, CLE* reduces to CLE when α = λ 2 2 /λ 2 1 , and toS CN when α = 1 (S CN is the SCF-enhanced CN index).

Results
To test the algorithmic performance, 18 networks from disparate fields are considered, including (1)  The elementary statistics are shown in Table 1.
Consider a network G(V, E) with V the set of nodes and E the set of links. To evaluate the algorithmic performance, E is randomly divided into two parts: the training set E T contains the known topology, and the testing set E P is treated as missing links that cannot be used in the prediction. Obviously, E T ∪ E P = E and E T ∩ E P = ∅. Many link prediction algorithms will assign a score to each link and the top-L links (i.e., the L links with highest scores and not belonging to E T ) are the predicted links. Two metrics, AUC and AUPR, are used to evaluate the algorithmic performance [46,47,48,49]. AUC denotes the probability that a randomly chosen missing link is assigned a higher score than a randomly chosen nonexistent link. To calculate AUC, we randomly select n pairs of links respectively from E P and U − E, where U is the universal set containing all the N (N − 1)/2 potential links. If there are n 1 times the missing link has higher score and n 2 times the missing link has the same score compared to the nonexistent link, the corresponding AUC is (n 1 +0.5n 2 )/n. If all scores of the candidate links are randomly generated from an independent and identical distribution, the AUC value should be 0.5, and the value exceeds 0.5 indicates the extent that the considered algorithm outperforms the pure chance. AUPR is the area under the precision-recall curve [49]: the larger the value, the better the performance. Precision is defined as the ratio of relevant links selected to the number of links selected. If L r links among the top-L selected links are correctly predicted, precision is L r /L. Recall is defined as the ratio of relevant links selected to the total number of relevant links, say L r /|E P |. Compared to the direct usage of precision and recall, AUPR does not depend on the choice of L and shows a more comprehensive evaluation by considering a range of L.
Eight parameter-free local similarity indices are used to compare with CLE, including the CN index [21], the Adamic-Adar (AA) index [50], the resource allocation (RA) index [22], the CRA index [23] and their SCF-enhanced versions.
AA differentiates the role of common neighbors by depressing the contributions of large-degree nodes, as where k z is the degree of node z. RA quantifies node similarity by a resource allocation process [51], where each neighbor of x allocates one unit resource equally to its neighbors, and the similarity of x and y is the resource that y receives from x, namely CRA prefers node pairs with densely connected common neighbors [23], as where AUC and AUPR of 9 indices are reported in Table 2 and Table 3     and ER are very small (corresponding to large δ, see Table 1), the effect from controlling the leading eigenvector may be insignificant resulting in unsatisfied performance of CLE. HG is a special case, which is sparse yet highly clustered ( c =0.6327). Its first-order null model (with same degree sequence obtained by link-crossing operations, see the method proposed in Ref. [52]) is of almost the same clustering coefficient ( c =0.6320), and thus we think the degree information largely determines the linking pattern. We have tested the preferential attachment (PA) index [53], which is It performs very badly in most networks but achieves even higher AUPR (0.6333, close to the best result) than CLE for HG. Due to the leading eigenvector is strongly correlated with degree vector, to weaken the contribution of leading eigenvector may not work well for HG.
To be fair, we compare CLE* with 3 parameter-dependent benchmarks, including the Katz index [54], the local path (LP) index [55] and the linear optimization (LO) algorithm [56]. The Katz index considers all paths with exponentially damped contributions along with their lengths, as where β is a tunable parameter. To avoid the degeneracy of states in CN and make similarities more distinguishable, LP considers both contributions from 2-hop and 3-hop paths, as where ǫ is a tunable parameter. LO assumes that the existence likelihood of a link is a linear summation of contributions of all its neighbors. By solving a corresponding optimization function, the analytical expression of the predicted matrix (can be treated as a similarity matrix) is where α is a free parameter. The AUC values and the AUPR values of CLE* and three compared algorithms are reported in Table 4. CLE* outperforms all others subject to AUC, and is the runner-up subject to AUPR. Overall speaking, CLE* and LO (the latter is known to be one of the most accurate algorithms thus far) are competitive in accuracy, and they are remarkably better than LP and Katz indices. We first test the robustness of the considered algorithms against the data sparsity by varying the size of the training set from 50% to 95%. Fig. 2(a) and Fig. 2(b) show the result for DNC. CLE and CLE* are relatively insensitive to the data sparsity subject to AUC, and they always perform best compared to other considered algorithms. Fig. 2(c) and Fig. 2 As a result, the time consumption of CLE and CLE* mainly comes from the calculation of the leading eigenvector, the largest eigenvalue and the second largest eigenvalue, which can be quickly obtained by the Lanczos method through repeated matrix-vector multiplication [57]. Therefore, the time complexity of CLE and CLE* is O(N 2 ). CPU times of the 13 algorithms are compared in Fig. 3. CRA andS CRA take the longest times for large-scale networks, and the CPU time ofS CRA is slight longer than CRA (the difference is too small to differentiate in Fig. 3 We finally compare the parameter-free algorithm CLE and the parameterdependent algorithm CLE*. To our surprise, CLE performs almost the same to CLE* on all considered networks. Taking DNC as a typical example, as shown in Fig. 4(a) and Fig. 4(b), AUC and AUPR of CLE are very close to CLE*, while AUC and AUPR ofS CN are much lower. Fig. 4(c) and Fig. 4(d) separately compare AUC and AUPR of CLE and CLE* on all 18 real networks.
It is observed that almost all data points are located on diagonal lines with the mean difference between their AUC values being only 0.0025, and the mean difference between their AUPR values being only 0.0099. The Mann-Whiteny U Test [58] also suggests that there is no significant difference between CLE and CLE* subject to AUC and AUPR (p-value > 0.05).

Conclusion
This paper proposes two algorithms, CLE (parameter-free) and CLE* (parameter-dependent), by controlling the leading eigenvector of the adjacency network of CLE and CLE* is highly competitive. In addition to the high prediction accuracy, CLE and CLE* have lower time complexity than many known global algorithms (e.g., LO and the Katz index) and thus can be applied at least to mid-sized networks.