Markus FrankeAn Update Algorithm for Restricted Random Walk ClustersAn Update Algorithm forRestricted Random Walk Clustersby Markus FrankeDissertation, Universität Karlsruhe (TH)Fakultät für Wirtschaftswissenschaften, 2007Tag der mündlichen Prüfung: 28.02.2007Referenten: Prof. Dr. Andreas Geyer-Schulz, Prof. Dr. Karl-Heinz WaldmannImpressumUniversitätsverlag Karlsruhec/o UniversitätsbibliothekStraße am Forum 2D-76131 Karlsruhewww.uvka.deDieses Werk ist unter folgender Creative Commons-Lizenz lizenziert: http://creativecommons.org/licenses/by-nc-nd/2.0/de/Universitätsverlag Karlsruhe 2007 Print on DemandISBN: 978-3-86644-183-5Contents1 Motivation 11.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Related Work 112.1 Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . 122.1.1 Random Walks . . . . . . . . . . . . . . . . . . . . . . . 122.1.2 The Restricted Random Walk Used for Clustering . . . . . 132.1.3 Other Concepts of “Restricted Random Walks” . . . . . . 142.1.4 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . 152.2 Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Cluster Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.1 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . 232.3.2 Single Pass Clustering . . . . . . . . . . . . . . . . . . . 242.3.3 Hierarchical Agglomerative Clustering . . . . . . . . . . 252.