2018/05/13 by Rajagopal Venkatesaramani, Venkatesaramani, Rajagopal, Yevgeniy Vorobeychik +1
Computer Science · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Human Mobility and Location-Based Analysis #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1805.04920
arxiv created 2018/05/13 · openalex publication_date 2018/05/13 · arxiv updated 2018/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Community detection remains an important problem in data mining, owing to the lack of scalable algorithms that exploit all aspects of available data - namely the directionality of flow of information and the dynamics thereof. Most existing methods use measures of connectedness in the graphical structure. In this paper, we present a fast, scalable algorithm to detect communities in directed, weighted graph representations of social networks by simulating flow of information through them. By design, our algorithm naturally handles undirected or unweighted networks as well. Our algorithm runs in O(|E|) time, which is better than most existing work and uses O(|E|) space and hence scales easily to very large datasets. Finally, we show that our algorithm outperforms the state-of-the-art Markov Clustering Algorithm (MCL) in both accuracy and scalability on ground truth data (in a number of cases, we can find communities in graphs too large for MCL).