Scalable Algorithms for Community Detection in Very Large Graphs [Elektronische Ressource] / Michael Ovelgönne. Betreuer: A. Geyer-Schulz

Scalable Algorithms for CommunityDetection in Very Large GraphsZur Erlangung des akademischen Grades einesDoktors der Wirtschaftswissenschaften(Dr. rer. pol.)von der Fakult¨at fu¨rWirtschaftswissenschaftenam Karlsruher Institut fu¨r TechnologiegenehmigteDissertationvonDipl.-Inform.Wirt Michael Ovelg¨onneTag der mu¨ndlichen Pru¨fung: 14. Juli 2011Referent: Prof. Dr. Andreas Geyer-SchulzKorreferent: Prof. Dr. Karl-Heinz WaldmannKarlsruhe, 2011Contents1 Motivation 12 Introduction to Graph Clustering 52.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.1 Clustering with Distance Measures . . . . . . . . . 72.2 Graph Clustering . . . . . . . . . . . . . . . . . . . . . . . 92.2.1 Terminology Graphs . . . . . . . . . . . . . . . . . 112.2.2 Terminology Graph Clustering . . . . . . . . . . . . 132.2.3 Graph Properties . . . . . . . . . . . . . . . . . . . 142.2.4 Graph Clusters as Cohesive Subgroups . . . . . . . 172.2.5 Cluster Hierarchy . . . . . . . . . . . . . . . . . . . 182.2.6 Graph Clustering Algorithms . . . . . . . . . . . . 192.2.7 Clustering Quality . . . . . . . . . . . . . . . . . . 283 Modularity Clustering 313.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1.1 Optimization Problem . . . . . . . . . . . . . . . . 333.1.2 Clustering Quality of Modularity . . . . . . . . . . 343.1.3 Problems of Modularity Clustering . . . . . . . . . 363.1.4 Generalizations of Modularity Clustering . . . .