Efficient Community Detection by Exploiting Structural Properties of Real-World User-Item Graphs

摘要

In this paper, we study the problem of detecting communities in real-world user-item graphs, i.e., bipartite graphs that represent interactions between a user and an item. Instead of developing a generic clustering algorithm for arbitrary graphs, we tailor our algorithm for user-item graphs by taking advantage of the inherent structural properties that exist in real-world networks. Assuming the existence of the core-periphery structure that has been experimentally and theoretically studied, our algorithm is able to extract the vast majority of the communities existing in the network by performing dramatically less computational work compared to conventional graph-clustering algorithms. The proposed algorithm achieves a subquadratic runtime (with respect to the number of vertices) for processing the entire graph, which makes it highly practical for processing large-scale graphs which typically arise in real-world applications. The performance of the proposed algorithm, in terms of both community-detection accuracy and efficiency, is experimentally evaluated with real-world datasets.