TY - JOUR
TI - Approximability of modularity clustering and related results
DO - https://doi.org/doi:10.7282/T3FF3QCC
PY - 2013
AB - For the problem of Modularity Clustering, first introduced by Newman and Girvan in 2004, we are given a graph and the goal is to partition the vertex set into an unknown number of clusters such that we maximize a certain objective function which evaluates the fitness of the clusters. This fitness function measures the statistically surprising distribution of edges between different clusters and in the clusters themselves. Despite having found widespread popularity in the fields of biology and social sciences, this problem is known to be NP-hard and up till the work in this thesis, only heuristics were known. In this thesis, we initiate a study of the approximability of modularity clustering. We give the first approximation algorithms and the first hardness of approximation results for the problem. In doing so, we employ various techniques like semidefinite programming and the regularity lemma. Our main results in- clude a factor 1.0009 inapproximability for dense graphs and a logarithmic (in the degree) approximation for sparse graphs. We also extend some of these results to directed and weighted graphs and the more general problem of Max-cut where negative edge weights are allowed.
KW - Computer Science
KW - Computer algorithms
KW - Cluster analysis--Computer programs
LA - eng
ER -