Empirical analysis of K-Betweenness

Empirical analysis of K-Betweenness Abian M. Blome October 1, 2007 Contents 1 Introduction and motivation 2 2 Tests 9 2.1 Distance of clusterings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Relation between distance and k . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Good cuts in dendrograms . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Modularity .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Inter-cluster conductance . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.3 Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Relation between quality indices and k . . . . . . . . . . . . . . . . . . . . 20 2.4.1 Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Inter-cluster conductance . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.3 Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Optimizing K-Betweenness 26 4 Results 27 5 chapter 28 1 1 Introduction and motivation This paper presents the K-Betweenness algorithm and shows the evidence gathered on its performance. The goal of the algorithm is to divide a graph into a number of clusters, each consisting of nodes and being pairwise disjoint, which closely reflect the inherent community structure of the graph. We are basically trying to identify the key groups of the graph using only the information contained within it: the nodes and the edges connecting them. This separates it from the well-known concept of graph partitioning where usually the number of groups and their size is at least known...

Website: i11www.iti.uni-karlsruhe.de | Filesize: -
No of Page(s): 32
Download Empirical analysis of K-Betweenness.pdf