Random walks

Chapter 3: RANDOM WALKS IN SOCIAL NETWORKS AND THEIR APPLICATIONS: A SURVEY

Abstract

• Various real-world applications, such as friend suggestion, keyword search, and web-spam detection can be viewed through the lens of ranking entities in graphs.

• Graph-theoretic measures of similarity are essential for these rankings, especially those capturing the structural information within the graph.

• Random walks have emerged as a powerful mathematical method for analyzing the paths among entities in graphs and are a prominent area of research due to the complexity of real-world graphs.

• This chapter describes various random walk-based proximity measures, their applications, and algorithms for their computation.

1. Introduction

• Key practical problems include link prediction in social networks, personalized search, spam detection, and collaborative filtering.

• Examples include friend suggestions in social media and recommendation systems in platforms like Netflix.

• The underlying question is determining which nodes in a graph are similar, ideally through measures capturing graph structures such as shared neighbors or direct paths.

• Given the size and complexity of real-world graphs, effective proximity measures and computation algorithms are necessary.

• Random walks act as a foundational framework for aggregating information about paths connecting two entities.

2. Random Walks on Graphs: Background

• A graph G = (V, E) consists of vertices V and edges E, with adjacency matrices denoting weights.

• The diagonal matrix D tracks node degrees, while the Laplacian L is utilized for many machine learning tasks.

• The transition probability matrix P defines the behavior in a random walk, facilitating analysis based on vertex relationships.

• Stationary distributions are critical as they define long-term behavior in random walks on irreducible, aperiodic graphs.

2.1 Random Walk based Proximity Measures

• Proximity measures like personalized PageRank, hitting and commute times, and SimRank will be elaborately described, focusing on their applicability beyond mere theoretical exploration.

• Personalized PageRank utilizes a non-uniform restart probability to yield a refined importance measure for nodes within a graph.

• Hitting time estimates the expected count of steps to reach a node in random walks from a starting node, while commute time sums hitting times between nodes.

3. Related Work: Algorithms

• The computation of proximity measures draws upon fixed-point algorithms, linear systems, dynamic programming approaches, and sampling techniques.

• Key computational challenges arise in expansive graphs, where both speed and memory efficiency are coveted attributes in algorithm development.

3.1 Algorithms for Hitting and Commute Times

• Traditional exhaustive methods for calculating commute and hitting times are impractical for large graphs.

• Efficient techniques range from sparse matrix manipulations to approximate algorithms yielding constant factor approximations.

• The need for approximations highlights the complexity inherent in executing computations over extensive networks.

4. Related Work: Applications

• Random walk-based methodologies have successfully penetrated various fields, notably in social network analysis, computer vision, personalized search mechanisms, and spam detection.

• Applications such as graph representations of images and keyword searches in databases exemplify the versatility of random walks in processing complex data structures.

4.1 Application in Computer Vision

• Graph representation of images facilitates methods for shape characterization and robust motion tracking, employing random walk metrics such as hitting times.

5. Evaluation: Link Prediction

• Link prediction experiments serve as a means to quantify the effectiveness of proximity measures, through strategies like holding out links and analyzing prediction accuracy.

• Empirical findings suggest simpler measures may outperform more complex approaches in various datasets, emphasizing the significance of focused path analysis over extensive ones.

6. Conclusion and Future Work

• Future exploration routes include designing more efficient algorithms suitable for external memory and addressing semi-supervised graph learning problems through the prism of random walk measures.

• Investigating the interplay between random walks, graph theory, and machine learning is poised to yield practical improvements and insights into effective learning across expansive datasets.