Source-linked AI summary
Link Prediction with Node Clustering Coefficient
Zhihao Wu, Youfang Lin, Jing Wang, Steve Gregory
TL;DR
Link prediction seeks to estimate missing links, while efficient methods remain challenging and CAR’s use of links between common neighbors has computational costs. This paper introduces CCLP, which uses common-neighbor clustering coefficients to capture local structure. Across real-world networks, CCLP is broadly comparable to CAR, complements it on networks with not very high LCP-corr, and is more efficient.
Problem
Link prediction estimates the likelihood of links between nodes, but efficient prediction remains a challenge, and calculating links between common neighbors makes CAR less efficient.
Source: §I · pp. 1–2Method
CCLP uses clustering coefficients of common neighbors to convey local link and triangle information beyond links between common neighbors.
Source: §I · p. 2Results
CCLP performs comparatively with CAR overall and has better link-prediction accuracy on networks with not very high LCP-corr.
Source: §IV · p. 7Takeaways & Limitations
CCLP is a more efficient complement to CAR for networks with not very high LCP-corr.
Source: §I · p. 2, §IV · p. 7
Abstract
from arXiv · showhide
Predicting missing links in incomplete complex networks efficiently and accurately is still a challenging problem. The recently proposed CAR (Cannistrai-Alanis-Ravai) index shows the power of local link/triangle information in improving link-prediction accuracy. With the information of level-2 links, which are links between common-neighbors, most classical similarity indices can be improved. Nevertheless, calculating the number of level-2 links makes CAR index not efficient enough. Inspired by the idea of employing local link/triangle information, we propose a new similarity index with more local structure information. In our method, local link/triangle structure information can be conveyed by clustering coefficient of common neighbors directly. The reason why clustering coefficient has good effectiveness in estimating the contribution of a common-neighbor is because that it employs links existing between neighbors of the common-neighbor and these links have the same structural position with the candidate link to this common-neighbor. Ten real-world networks drawn from five various fields are used to test the performance of our method against to classical similarity indices and recently proposed CAR index. Two estimators: precision and AUP, are used to evaluate the accuracy of link prediction algorithms. Generally speaking, our new index only performs competitively with CAR, but it is a good complement to CAR for networks with not very high LCP-corr, which is a measure to estimate the correlation between number of common-neighbors and number of links between common-neighbors. Besides, the proposed index is also more efficient than CAR index.
I. INTRODUCTION
Link prediction estimates whether a link exists between two nodes, supporting applications such as friend recommendations and protein-interaction prediction. The paper introduces CCLP, which uses common-neighbor clustering coefficients to convey local structure, and reports advantages over CAR in some networks at lower computational cost.
I. INTRODUCTION
- Similarity-based link prediction assumes that more similar nodes are more likely to be linked, and this paper focuses on measures based on network topology.Classical local indices use degrees or common neighbors; CAR uses links between common neighbors to improve them.Source: §I · p. 1
- Using more information and features in prediction may increase time and space costs.Source: §I · p. 2
- Efficient link prediction remains challenging; local methods are considered useful candidates for large networks, while choosing among community-detection algorithms is unclear.Some methods combine detected communities with similarity indices, but rely on selecting a community-detection algorithm.Source: §I · p. 2
- CCLP uses common-neighbor clustering coefficients to represent local link/triangle structure and performs better than CAR on networks with not very high LCP-corr, at lower computational cost.The authors test it on 10 real-world networks from five fields.Source: §I · p. 2
A. Definition
The section sets up link prediction on an unweighted, undirected simple network by assigning scores to node pairs. Nonexistent links are ranked by score, with higher scores representing greater similarity.
A. Definition
- For each pair of nodes in an unweighted, undirected simple network, the framework assigns a score and ranks nonexistent links in decreasing score order.Links at the top of the ranking are treated as most likely to exist.Source: A. Definition · p. 2
- The framework treats a higher score as higher similarity.Source: A. Definition · p. 2
- In the supplied passages, two named items are Preferential Attachment (PA) and Resource Allocation (RA); these excerpts do not state what they measure or compare.Source: A. Definition · p. 2
B. Similarity index based on clustering coefficient
CCLP extends local link and triangle information beyond links between common neighbors. It uses the clustering coefficient of common neighbors to capture triangles in their local neighborhoods and links in positions structurally similar to candidate links.
B. Similarity index based on clustering coefficient
- The authors motivate efficient local methods by noting that sophisticated techniques may be too costly for very large networks.They describe such techniques as potentially informative about link formation and predictability, but costly to apply.Source: B. Similarity index based on… · p. 2
- The method uses a common neighbor’s clustering coefficient to convey the density of triangles in its local neighborhood.The coefficient is based on the triangles passing through the node and its degree.Source: B. Similarity index based on… · p. 3
- CCLP extends local structure information to links between other neighbors of a common neighbor, or other triangles passing through that common neighbor.These are level-3 links, distinct from links between seed nodes and common neighbors or between common neighbors.Source: B. Similarity index based on… · p. 3, Figure 1 · p. 3
- Links between other neighbors of a common neighbor have a structural position similar to the candidate link associated with that common neighbor.The authors cite this similarity in structural position as the key reason to consider level-3 links.Source: Figure 1 · p. 3, B. Similarity index based on… · p. 4
C. Estimation
The evaluation estimates link-prediction accuracy using precision, AUP, and AUC. It withholds observed links for testing and averages results over repeated random runs.
C. Estimation
- The evaluation randomly withholds 10% of observed links as a probe set and averages results over 1000 runs for networks under 1000 nodes or 300 runs for larger networks.The remaining links form the training set; probe links are not used for prediction.Source: C. Estimation · p. 4
- Precision is the fraction of the top-L predicted links that are relevant, with L set to 20 for networks under 1000 links and 100 for larger networks.Source: C. Estimation · p. 4
- AUP is the area under a precision curve evaluated at ten L values, while AUC measures area under the ROC curve.The AUC interpretation compares scores for a randomly chosen missing link and a randomly chosen nonexistent link.Source: C. Estimation · p. 4
D. Datasets
The study tests 10 real-world networks from five fields and reports their basic topological features, including an index of the relationship between common neighbors and links between them.
D. Datasets
- The 10 networks span food webs, social networks, neural networks, electronic information systems, and artificial infrastructure.They are Food, Grassland, Dolphins, Jazz, Macaque, Mouse, PB, Email, Grid, and INT.Source: D. Datasets · p. 4
- The reported topological features include node and link counts, average degree, average shortest distance, clustering coefficient, and LCP-corr.LCP-corr estimates the correlation between the number of common neighbors and the number of links between common neighbors.Source: Table I · p. 4
- The LCP-corr definition uses covariance, with the passage also identifying standard deviation as a quantity in its equation.The supplied equation is LCP-corr = cov(CN, LCL).Source: D. Datasets · p. 4, Table I · p. 4
A. Accuracy
Across the ten networks, CCLP and CAR outperform classical indices on precision and AUP, with CCLP often scoring higher; CCLP also complements CAR on networks with relatively small LCP-corr.
A. Accuracy
- The comparison includes CN, AA, RA, and CAR, with a random predictor also reported.The authors select CN, AA, and RA as classical common-neighbor indices because they have performed better than other classical indices.Source: A. Accuracy · pp. 4–5
- On precision, CCLP and CAR each achieve four best results, while CCLP scores higher than CAR on six networks; on AUP, CCLP has six best results and CAR three.CCLP’s large improvements over CAR recur on Grassland and INT.Source: Table II · p. 5, Table III · p. 5, A. Accuracy · p. 5
- On Food networks, classical similarity indices perform worse than the random predictor under both precision and AUP, while CCLP provides useful structural information.AA and RA outperform CN there but remain below the random predictor.Source: A. Accuracy · p. 5
- CCLP performs better than CAR on Grassland, INT, and Grid, while CAR performs better on PB and Dolphins; CCLP complements CAR on networks with relatively small LCP-corr.The precision curves are generally stable across changes in L on Grassland, while precision decreases as L increases on almost all other tested networks.Source: A. Accuracy · p. 5, Figure 2 · p. 6
- CCLP performs better than CAR by AUC, while RA achieves the best AUC results and differences among RA, AA, and CCLP are very small.AUC evaluates accuracy across the whole ranking.Source: A. Accuracy · pp. 5–6
B. Efficiency
CCLP reduces the preprocessing work for local structure relative to CAR, but reported implementation timings show only a modest difference. The tables compare computation time across ten networks under loop-based and matrix-operation implementations.
B. Efficiency
- CCLP calculates node clustering coefficients in O(N) steps, versus O(N^2) steps for CAR’s pairwise LCL calculation.Both methods still have average final-score assignment complexity O(N^2⟨k⟩^2), shared by most common-neighbor indices.Source: B. Efficiency · p. 6
- In loop-based MATLAB implementations, CAR is the most complex index but costs only a bit more time than other indices.Table V reports computation time in seconds for similarity matrices on ten tested networks.Source: B. Efficiency · p. 7, Table V · p. 7
- Table VI reports computation times for indices other than CAR when implemented with matrix operations.The passage provides no specific timing comparisons or values.Source: B. Efficiency · p. 7, Table VI · p. 7
IV. CONCLUSION
CCLP performs competitively with CAR overall and complements it on networks with not very high LCP-corr. The conclusion links this difference to CCLP’s less pair-specific structural information and identifies combining both factors as a possible direction.
IV. CONCLUSION
- Sophisticated methods can offer insights into link formation and predictability, but the paper argues efficient link prediction should not be neglected while computational complexity remains problematic.The conclusion includes HSM, SBM, and SPM among such methods.Source: §IV · p. 7
- CCLP performs competitively with CAR overall and has better link-prediction accuracy as a complement on networks with not very high LCP-corr.The conclusion describes CAR as suitable for networks with high LCP-corr.Source: §IV · p. 7
- Unlike CAR’s pair-specific LCL, CCLP uses a common-neighbor clustering coefficient that is the same across different candidate-node pairs.The authors suggest this may explain why CCLP does not significantly outperform CAR.Source: §IV · p. 7
- Combining CAR’s pair-specific information with CCLP’s clustering-coefficient information is proposed as a direction for future similarity indices.Source: §IV · p. 7