Source-linked AI summary
Predicting missing links and their weights via reliable-route-based method
Jing Zhao, Lili Miao, Haiyang Fang, Qian-Ming Zhang, Min Nie, Tao Zhou
TL;DR
Link prediction targets missing or future links, and this paper also addresses predicting their weights. It extends local similarity indices to weighted networks with a reliable-route-based method and uses similarity scores to estimate weights; weighted resource allocation performs best for existence, while its reliable-route variant performs best for weights.
Problem
Link prediction seeks missing or future links, and this paper addresses the additional task of predicting their weights.
Source: Introduction. – · p. 1Method
The paper generalizes local similarity indices to weighted networks with a reliable-route-based method and makes predicted link weights proportional to similarity scores.
Source: Introduction. – · pp. 1–2Results
The weighted resource allocation index performs best for link existence, while the reliable-route-based weighted resource allocation index performs best for weight prediction.
Source: Introduction. – · p. 2Takeaways & Limitations
Across real networks, resource-allocation indices perform best overall for both tasks, and larger clustering coefficients correspond to higher prediction accuracy.
Source: Conclusion and Discussion. – · p. 5
Abstract
from arXiv · showhide
Link prediction aims to uncover missing links or predict the emergence of future relationships according to the current networks structure. Plenty of algorithms have been developed for link prediction in unweighted networks, with only a very few of them having been extended to weighted networks. Thus far, how to predict weights of links is important but rarely studied. In this Letter, we present a reliable-route-based method to extend unweighted local similarity indices to weighted indices and propose a method to predict both the link existence and link weights accordingly. Experiments on different real networks suggest that the weighted resource allocation index has the best performance to predict the existence of links, while the reliable-route-based weighted resource allocation index performs noticeably better on weight prediction. Further analysis shows a strong correlation for both link prediction and weight prediction: the larger the clustering coefficient, the higher the prediction accuracy.
Introduction. –
The paper addresses predicting missing links and their weights, extending local similarity indices to weighted networks with a reliable-route-based method. Its experiments identify different resource-allocation indices as strongest for link existence and weight prediction.
Introduction. –
- Link prediction can identify missing data and inform understanding of network evolution, but node attributes are often unavailable or unreliable, motivating topology-based methods.Source: Introduction. – · p. 1
- Similarity-based link prediction is the mainstream topological approach, using local, global, or quasi-local information to compute indices.Source: Introduction. – · p. 1
- Earlier weighted-index studies did not address predicting link weights, although weight prediction is important alongside link-existence prediction.Source: Introduction. – · p. 1
- The method generalizes unweighted similarity indices to weighted ones using a reliable-route-based approach.It is inspired by the most reliable route problem in communication networks.Source: Introduction. – · p. 1
- The weighted resource allocation index performs best for link existence, while the reliable-route-based weighted resource allocation index performs best for weight prediction.The authors evaluate the methods on six real networks.Source: Introduction. – · p. 2
Problem and Metrics. –
The section defines how unconnected pairs are scored and ranked for missing-link prediction, then describes the train-test evaluation and the scaling-based approach to estimating link weights.
Problem and Metrics. –
- For each unconnected node pair, the similarity index S_xy quantifies missing-link likelihood, and pairs are ranked by decreasing score.Source: Problem and Metrics. – · p. 2
- The link set is randomly split into 90% training and 10% test links, and precision is the fraction of predicted top-L links that appear in the test set.Source: Problem and Metrics. – · p. 2
- Because link weights measure affinity, the method estimates missing-link weights by fitting a function of the training-set likelihood scores to test-set weights.Source: Problem and Metrics. – · p. 2
- The weight prediction function is F(W_T) = λ · S(W_T), with λ selected by minimizing the Frobenius-norm difference under an upper bound based on maximum matrix values.Source: Problem and Metrics. – · p. 2
- Weight-prediction accuracy is measured by the Pearson correlation between predicted and known test-set link weights.Source: Problem and Metrics. – · p. 2
Methods. –
The method extends local similarity indices to weighted networks using reliable-route ideas. It builds on common-neighbor indices and adapts their treatment of neighbor weights and strengths.
Methods. –
- Common Neighbors counts shared neighbors, while Adamic-Adar and Resource Allocation reduce the contributions of high-degree common neighbors.Resource Allocation penalizes high-degree common neighbors more strongly than Adamic-Adar.Source: Methods. – · p. 2
- Earlier weighted CN, AA, and RA indices incorporate the weights of links from each common neighbor to both nodes.Their formulas use the strength of the common neighbor, defined as the sum of its incident link weights.Source: Methods. – · p. 2
- Reliable-route-based weighted similarity measures use products of link weights along paths to score the affinity of unconnected node pairs.The approach adapts the most-reliable-route idea, where route reliability is the product of edge weights.Source: Methods. – · p. 3
- For networks with weights outside [0,1], the method maps weights into (0,1) before calculating reliable-route-based indices.The mapping is one-to-one, so the original weight can be recovered from the regulated weight.Source: Methods. – · p. 3
Results. –
Across six real weighted networks, resource-allocation methods perform best overall for link and weight prediction, with reliable-route-based weighted resource allocation particularly strong for weight prediction. Prediction accuracy is also higher in more highly clustered networks, though the proposed explanation for Corum’s performance is tentative.
Results. –
- In Cel, Geom, and Corum, link weights represent synapse counts, coauthored publications, and shared-complex counts, respectively.These weights are transformed to the interval (0,1) before the experiments.Source: Results. – · pp. 3–4
- Each of six real weighted networks was evaluated using repeated random splits of links into 90% training and 10% test sets.The process was repeated 100 times; link prediction was measured by precision and weight prediction by Pearson correlation between predicted and known test-link weights.Source: Results. – · pp. 3–4
- RA-series algorithms perform overall best for link and weight prediction; rWRA significantly outperforms other indices in weight prediction.The reported exceptions are Cel for link prediction and hsaPPI for weight prediction, where rWAA performs best.Source: Results. – · p. 4, Table 2 · p. 4, Table 3 · p. 4
- Prediction accuracy is remarkably higher for Corum than for the other networks, possibly because Corum contains many cliques and has large clustering coefficients.The authors describe the clique explanation as a possibility, not a demonstrated cause.Source: Results. – · p. 4
- Highest precision results for link and weight prediction are strongly positively correlated with network clustering coefficients.The authors further infer, but do not establish, that weighted clustering may characterize accuracy better than unweighted clustering.Source: Results. – · p. 4, Table 2 · p. 4, Table 3 · p. 4
Conclusion and Discussion. –
The conclusion reports that resource-allocation indices perform best overall for both link and weight prediction, while accuracy also varies with clustering and network background.
- Higher clustering coefficients are associated with higher prediction accuracy, as assessed against the highest accuracies in Tables 2 and 3.Source: Table 4 · p. 5, Conclusion and Discussion. – · p. 5
- The resource-allocation indices perform overall best in both link prediction and weight prediction.Source: Conclusion and Discussion. – · p. 5
- Prediction accuracy varies with network background: hsaPPI and STRING have relatively poor accuracy, while CORUM is described as more regularly organized and easier to predict.The authors suggest sparsity may help explain hsaPPI's results and noise and diverse organizing principles may help explain STRING's.Source: Conclusion and Discussion. – · p. 5