Vi studerar en lämplig klass av välklustrade grafer som medger bra k-way partitioner och presentera den första nästan linjära tid algoritm för med nästan optimal approximation garanterar partitionering sådana grafer. En bra k-way partition är en partition av hörnen i en graf i separata kluster (undergrupper), så att varje kluster är bättre ansluten på insidan än mot utsidan. Detta problem är en viktig byggsten inom algoritmdesign, och har breda tillämpningar inom community detektering och nätverksanalys. Nyckeln till vårt resultat är ett teorem på multi-cut och eigenvector struktur grafen Laplacians av dessa välklustrade grafer. Baserat på detta teorem, ger vi de första rigorösa garantierna på approximation förhållandet mellan de allmänt använda k-medel kluster algoritmer. Vi ger också en nästan linjär tidsalgoritm baserad på inbäddningar av värmekärnor och ungefärliga närmaste granndatastrukturer.
Peng m.fl. I REF studerade eigenvector strukturer i Laplacian av välklustrade grafer (som är mycket relaterad till vår definition av klusterable grafer) och approximation förhållandet av k-means kluster algoritmer på dessa grafer.
Partitioning Well-Clustered Graphs with k-Means and Heat Kernel
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}