Limited Random Walk Algorithm for Big Graph Data Clustering

Abstract

Graph clustering is an important technique to understand the relationships between the vertices in a big graph. In this paper, we propose a novel random-walk-based graph clustering method. The proposed method restricts the reach of the walking agent using an inflation function and a normalization function. We analyze the behavior of the limited random walk procedure and propose a novel algorithm for both global and local graph clustering problems. Previous random-walk-based algorithms depend on the chosen fitness function to find the clusters around a seed vertex. The proposed algorithm tackles the problem in an entirely different manner. We use the limited random walk procedure to find attracting vertices in a graph and use them as features to cluster the vertices. According to the experimental results on the simulated graph data and the real-world big graph data, the proposed method is superior to the state-of-the-art methods in solving graph clustering problems. Since the proposed method uses the embarrassingly parallel paradigm, it can be efficiently implemented and embedded in any parallel computing environment such as a MapReduce framework. Given enough computing resources, we are capable of clustering graphs with millions of vertices and hundreds millions of edges in a reasonable time.

12 pages, 3 figures, 7 tables, journal paper

References in corpus (14)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• A smart local moving algorithm for large-scale modularity-based community detection
• What's in a crowd? Analysis of face-to-face behavioral networks
• A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
• Effect of size heterogeneity on community identification in complex networks
• Constrained fractional set programs and their application in local clustering and community detection
• Defining and Evaluating Network Communities based on Ground-truth