Show simple item record

dc.contributor.authorSun, Hen
dc.contributor.authorZanetti, Lucaen
dc.date.accessioned2019-08-06T23:30:19Z
dc.date.available2019-08-06T23:30:19Z
dc.date.issued2019-10-01en
dc.identifier.issn2329-4949
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/295350
dc.description.abstractGraph clustering is a fundamental computational problem with a number of applications in algorithm design, machine learning, data mining, and analysis of social networks. Over the past decades, researchers have proposed a number of algorithmic design methods for graph clustering. Most of these methods, however, are based on complicated spectral techniques or convex optimisation, and cannot be directly applied for clustering many networks that occur in practice, whose information is often collected on different sites. Designing a simple and distributed clustering algorithm is of great interest, and has comprehensive applications for processing big datasets. In this paper we present a simple and distributed algorithm for graph clustering: for a wide class of graphs that are characterised by a strong cluster-structure, our algorithm finishes in a poly-logarithmic number of rounds, and recovers a partition of the graph close to optimal. One of the main procedures behind our algorithm is a sampling scheme that, given a dense graph as input, produces a sparse subgraph that provably preserves the cluster-structure of the input. Compared with previous sparsification algorithms that require Laplacian solvers or involve combinatorial constructions, this procedure is easy to implement in a distributed setting and runs fast in practice.
dc.rightsAll rights reserved
dc.rights.uri
dc.titleDistributed graph clustering and sparsificationen
dc.typeArticle
prism.issueIdentifier3en
prism.publicationDate2019en
prism.publicationNameACM Transactions on Parallel Computingen
prism.volume6en
dc.identifier.doi10.17863/CAM.42404
dcterms.dateAccepted2019-08-05en
rioxxterms.versionofrecord10.1145/3364208en
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2019-10-01en
dc.identifier.eissn2329-4957
rioxxterms.typeJournal Article/Reviewen
pubs.funder-project-idECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660)
cam.orpheus.successThu Jan 30 10:41:11 GMT 2020 - Embargo updated*
rioxxterms.freetoread.startdate2019-10-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record