Efficient and Exact Local Search for Random Walk Based Top-K Proximity Query in Large Graphs

Area of Science:

• Graph algorithms
• Data mining
• Network analysis

Background:

• Top-k proximity queries are crucial for large graph analysis.
• Existing random walk measures face computational challenges on large datasets.
• Efficiently computing proximity measures on massive graphs remains an open problem.

Purpose of the Study:

• To develop an efficient and exact method for top-k proximity queries in large graphs.
• To address the computational limitations of existing proximity measures.
• To introduce a novel approach applicable to various proximity metrics.

Main Methods:

• Developed Fast Local Search (FLoS), an exact local search algorithm.
• Utilized the 'no local optimum' property of proximity measures.
• Introduced transition probability manipulation and developed tight lower/upper bounds.
• Extended FLoS for measures with local optima by exploring inter-measure relationships.

Main Results:

• FLoS guarantees exact solutions for top-k proximity queries.
• The method demonstrates efficiency and effectiveness on large-scale real and synthetic graphs.
• Lower and upper bounds monotonically converge to the exact proximity value.
• The approach is versatile, supporting various proximity measures.

Conclusions:

• FLoS offers an efficient and exact solution for top-k proximity queries in large graphs.
• The proposed method overcomes the scalability issues of traditional approaches.
• FLoS provides a robust framework for proximity analysis in complex networks.