Source-linked AI summary
Link Prediction Based on Local Random Walk
Weiping Liu, Linyuan Lu
TL;DR
Missing-link prediction must handle sparse, very large complex networks while maintaining useful accuracy. The paper proposes local-random-walk similarity indices and evaluates them against established local, global, and hierarchical methods. Across five real networks, the proposed indices provide strong prediction performance with lower computational complexity than global random-walk methods.
Problem
Missing-link prediction in complex networks must address network sparsity and huge size while designing methods that are both effective and efficient.
Method
The paper proposes Local Random Walk (LRW) and Superposed Random Walk (SRW) similarity indices based on few-step local random walks.
Results
Across five real networks, LRW and SRW give overall better AUC and precision predictions than other methods, while SRW exceeds LRW accuracy.
Takeaways & Limitations
LRW and SRW can provide slightly better prediction than global methods while using lower computational complexity.
Takeaways & Limitations
The evaluation’s AUC metric assumes independent link-existence events, an assumption that may not hold in real-world networks.
Abstract
from arXiv · showhide
The problem of missing link prediction in complex networks has attracted much attention recently. Two difficulties in link prediction are the sparsity and huge size of the target networks. Therefore, the design of an efficient and effective method is of both theoretical interests and practical significance. In this Letter, we proposed a method based on local random walk, which can give competitively good prediction or even better prediction than other random-walk-based methods while has a lower computational complexity.
Introduction. –
Missing-link prediction addresses incomplete complex networks, where identifying likely interactions can reduce costly experimental checking. The central challenge is balancing prediction accuracy with computational efficiency, especially in sparse, large networks.
- Motivation: Missing-link prediction estimates the likelihood that an absent link exists between two nodes.In biological networks, discovering interactions can be costly and current network knowledge is substantially incomplete.
- Similarity assumptions: Similarity-based methods often assume that connected nodes are similar and transfer similarity through network links.Structural equivalence captures similarity through shared or equivalent network structure.
- Similarity assumptions: Regular equivalence treats nodes as similar when they connect to similar nodes, but predicting links under this notion remains open.This study focuses on structural equivalence rather than regular equivalence.
- Efficiency and accuracy: Local indices use limited neighborhood information and are computationally efficient, whereas global indices can provide broader structural information.The supplied passages contrast efficiency from locality with potential accuracy benefits from more information.
- Proposed approach: The proposed local-random-walk method targets lower complexity than other random-walk methods while empirical tests compare it with local, global, and hierarchical approaches.Experiments on five real networks report that the proposed method performs best.
Similarity Based on Local Random Walk. –
The method defines link-prediction similarity from short random walks on an undirected simple network. It normalizes degree-based walk resources, while limiting propagation to local steps to reduce sensitivity to distant network regions.
- Scoring framework: Candidate nonexistent links receive similarity scores and are ranked in descending order, with highest-scoring links considered most likely.The framework directly identifies similarity with the prediction score.
- Random-walk process: A random walk uses transition probability P_xy = a_xy/k_x, where a_xy indicates adjacency and k_x is the degree of node x.The walk probability describes movement from node x to node y in one step.
- Resource initialization: The initial resource starts at node x and is set proportional to its degree before normalization produces the similarity between x and y.The initial state is represented by a one-hot vector, while degree weighting supplies the initial resource.
- Locality choice: The similarity is symmetric, s_xy = s_yx, and the method focuses on few-step walks rather than the stationary state.The stationary state is associated with preferential attachment through degree information.
- Locality choice: Long random walks can reach regions far from target nodes, potentially lowering accuracy when networks favor nearby connections.This motivates restricting the walk’s dependence on distant network structure.
- Variants: Superposed random walk (SRW) is the named abbreviation for the superposed-walk variant.
Metrics. –
Prediction accuracy is evaluated by holding out observed links and ranking candidates with AUC and precision. AUC measures overall ranking quality, while precision focuses on the top-L predictions.
- Evaluation protocol: Observed links are randomly split into training and probe sets, with E = E_T ∪ E_P and E_T ∩ E_P = ø.Algorithms train on E_T and evaluate recovered probe links among nonexistent candidates.
- AUC: AUC is the probability that a randomly selected missing link receives a higher score than a randomly selected nonexistent link.It evaluates the overall ranking produced by the algorithm.
- AUC: AUC ≈ 0.5 corresponds to chance performance, so exceeding 0.5 indicates improvement over pure chance.
- Caveat: AUC assumes independence among link-existence events, which may not hold in real-world networks.This is an author-identified limitation of the evaluation metric.
- Precision: Precision is computed after ranking nonexistent links and selecting the top-L candidates, with L = 100 in this study.It is the ratio of successfully predicted relevant items to selected items.
Data. –
The study uses five real networks from disparate fields to evaluate link-prediction methods. The dataset descriptions include transportation, scientific collaboration, and infrastructure networks, among others.
- Real networks: Five representative networks from disparate fields are used, including USAir, NetScience, and the western US Power Grid.USAir contains 332 airports and 2126 airlines; NetScience contains 1589 scientists, including 128 isolated nodes.
Results and Discussion. –
The study compares local, global, hierarchical, and random-walk-based link-prediction methods, finding that LRW and SRW provide strong accuracy with lower computational complexity. Their optimal walk length increases with average shortest distance and with sparser training data.
- Comparison setup: LRW and SRW are compared with CN, RA, LP, ACT, RWR, and HSM using AUC and precision on five real networks.Table 2 uses 90% of known links for training, averages 1000 random divisions, and reports optimal LRW and SRW steps in parentheses.
- Accuracy results: LRW and SRW give overall better predictions than the other methods for both AUC and precision, with SRW sometimes exceeding LRW.The comparison includes three local indices, two global random-walk indices, and the hierarchical structure method.
- Accuracy results: LRW and SRW retain their advantage across different training-set densities in the USAir and C.elegans networks.Figure 1 varies the proportion of links used for training and evaluates AUC and precision.
- Step selection: The optimal LRW step positively correlates with average shortest distance and increases as the training-set proportion decreases.For p = 0.9, the optimal steps are 2 for USAir and 3 for C.elegans; the power grid reaches a near optimum at step 16 when average shortest distance is about 16.
- Step selection: For the power grid, one additional step beyond 16 yields only a 0.2% improvement in AUC.The power grid has average shortest distance approximately 16, and its AUC reaches a near optimum at step 16.
- Computational complexity: The time complexity of n-step LRW or SRW is approximately O(N⟨k⟩^n), compared with O(N^3) for inverse or pseudoinverse calculation.Because average degree is usually much smaller than network size, LRW and SRW can run much faster than ACT and RWR, especially on large sparse networks.
- Computational complexity: LRW for the power grid is thousands of times faster than ACT at n = 10, while LRW and SRW can handle networks with tens of thousands of nodes.HSM requires sampling many dendrograms and can reasonably handle networks only up to a few thousand nodes.
Conclusion. –
The proposed LRW and SRW indices improve link-prediction performance over local similarity methods and slightly outperform global methods while requiring lower computational complexity.
- LRW and SRW give remarkably better predictions than three local similarity indices.
- Against three global methods, LRW and SRW achieve slightly better prediction with lower computational complexity.
- The study evaluates the proposed indices on five real networks against six well-known methods.