Slither: finding local dense subgraphs measured by average degree

摘要

Searching for dense subgraphs is the crux of a variety of graph mining applications. It is also meaningful to investigate problems of finding local dense subgraphs related to particular nodes, especially for large real-world graphs. However, none of the problems focus on maximizing the average degrees of the found subgraphs. We formulate the MDS-N problem, which aims to find such a subgraph with the maximum average degree, near or containing a given node in an undirected graph. We propose the Slither algorithm and the Slither PageRank (PR) algorithm, built on a reduction from the MDS-N problem to the minimum conductance problem and the Lovász-Simonovits Theorem of random walks. A simple hierarchically repetition frame is also proposed to advance the two algorithms. Experiments conducted on both unipartite graphs and bipartite graphs show the effectiveness, stability, and scalability of our algorithms. Additionally, we verify the MDS-N problem and the proposed algorithms on a large social network Twitter, the experimental results of which show our algorithms can successfully detect local fraud-related subgraphs based on particular fraudulent user accounts.