Snakdd

Randomized Greedy Modularity Optimization for Group Detection in Huge Social Networks

Michael Ovelgönne

Karlsruhe Institute of Technology Kaiserstrasse 12 76128 Karlsruhe, Germany

Andreas Geyer-Schulz

Karlsruhe Institute of Technology Kaiserstrasse 12 76128 Karlsruhe, Germany

Martin Stein

Karlsruhe Institute of Technology Kaiserstrasse 12 76128 Karlsruhe, Germany

michael.ovelgoenne@kit.edu ABSTRACT

andreas.geyerschulz@kit.edu

martin.stein@kit.edu

Due to the increasing availability of very large data sets of social networks, there is a need for scalable algorithms that are able to analyze these networks with reasonable resource requirements. Finding ’natural groups’ in these networks has gotten much attention lately. We present an algorithm that detects communities by optimizing the modularity, which is a measure for the quality of a given decomposition of a network into clusters. As the calculation of the clustering with maximal modularity is NP-hard, various heuristic algorithms have been proposed. Still, the time or memory complexity of those algorithms does not allow finding communities in huge networks. In this article we present a memory-efficient randomized greedy algorithm to gain a speed-up compared to the state-of-the-art while the achieved cluster quality remains very high. The algorithm is compared to the previously best algorithms on 9 publicly available data sets and shown to be of comparable performance while being faster and using considerably less memory.

Categories and Subject Descriptors

H.3.3 [Information Search and Retrieval]: Clustering; G.2.2 [Graph Theory]: Graph Algorithms

Keywords

Community detection, graph clustering, modularity, randomized algorithm

1. INTRODUCTION

Community detection has been used in social network analysis to answer a wide range of questions regarding the behavior and interaction patterns of people. Community analysis gives insights into the structures of complex social networks by...