Effective and Efficient Random Walk Proximity Measures for Graph Analytics
COM1 Level 3
MR1, COM1-03-19
Abstract:
Graphs are fundamental data structures for representing relationships between objects across diverse domains, such as social science, web link analysis, bioinformatics, and transportation. Random walks have proven to be a powerful technique for measuring proximity in graph analytics, yet they face challenges, including the need for tailored proximity variants and significant computational overhead, especially with large graphs.
This thesis utilizes random walk proximities to reveal complex connections within graphs, simultaneously addressing these challenges. It transitions from comprehensive visual exploration to more granular analysis. For graph visualization, it introduces PDist, a novel node distance measure based on personalized PageRank, which enhances visualization quality and efficiency, supported by the Tau-Push algorithm. In edge analysis, the thesis refines spanning centrality, a critical measure of edge importance, through the TGT and TGT+ algorithms, significantly reducing computational overhead while ensuring accuracy. Additionally, it proposes new measures of friendship closeness, inspired by social identity theory, to improve behavior analysis in social graphs. Extensive experiments confirm that these methods outperform existing techniques in both visualization and computation, with practical deployment in Tencent online games.