Timezone: »

 
Poster
Community Detection on Evolving Graphs
Stefano Leonardi · Aris Anagnostopoulos · Jakub Łącki · Silvio Lattanzi · Mohammad Mahdian

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #96
in Monday Posters »

Clustering is a fundamental step in many information-retrieval and data-mining applications. Detecting clusters in graphs is also a key tool for finding the community structure in social and behavioral networks. In many of these applications, the input graph evolves over time in a continual and decentralized manner, and, to maintain a good clustering, the clustering algorithm needs to repeatedly probe the graph. Furthermore, there are often limitations on the frequency of such probes, either imposed explicitly by the online platform (e.g., in the case of crawling proprietary social networks like twitter) or implicitly because of resource limitations (e.g., in the case of crawling the web). In this paper, we study a model of clustering on evolving graphs that captures this aspect of the problem. Our model is based on the classical stochastic block model, which has been used to assess rigorously the quality of various static clustering methods. In our model, the algorithm is supposed to reconstruct the planted clustering, given the ability to query for small pieces of local information about the graph, at a limited rate. We design and analyze clustering algorithms that work in this model, and show asymptotically tight upper and lower bounds on their accuracy. Finally, we perform simulations, which demonstrate that our main asymptotic results hold true also in practice.

Keywords: Clustering · (Other) Probabilistic Models and Methods · (Application) Social Networks · Large Scale Learning and Big Data · Stochastic Methods · Graph-based Learning
[ PDF] 

Author Information

Stefano Leonardi (Sapienza University of Rome)
Aris Anagnostopoulos (Sapienza University of Rome)
Jakub Łącki (Sapienza University of Rome)
Silvio Lattanzi (Google)
Mohammad Mahdian (Google Research)

More from the Same Authors