2014/07/11 by Matteo Ceccarello, Andrea Pietracaprina, Ceccarello, Matteo +5
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Advanced Graph Neural Networks #Caching and Content Delivery #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1407.3144
openalex publication_date 2014/07/11 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
We develop a novel parallel decomposition strategy for unweighted, undirected\ngraphs, based on growing disjoint connected clusters from batches of centers\nprogressively selected from yet uncovered nodes. With respect to similar\nprevious decompositions, our strategy exercises a tighter control on both the\nnumber of clusters and their maximum radius.\n We present two important applications of our parallel graph decomposition:\n(1) k-center clustering approximation; and (2) diameter approximation. In\nboth cases, we obtain algorithms which feature a polylogarithmic approximation\nfactor and are amenable to a distributed implementation that is geared for\nmassive (long-diameter) graphs. The total space needed for the computation is\nlinear in the problem size, and the parallel depth is substantially sublinear\nin the diameter for graphs with low doubling dimension. To the best of our\nknowledge, ours are the first parallel approximations for these problems which\nachieve sub-diameter parallel time, for a relevant class of graphs, using only\nlinear space. Besides the theoretical guarantees, our algorithms allow for a\nvery simple implementation on clustered architectures: we report on extensive\nexperiments which demonstrate their effectiveness and efficiency on large\ngraphs as compared to alternative known approaches.\n