---
res:
bibo_abstract:
- Diffusions and related random walk procedures are of central importance in many
areas of machine learning, data analysis, and applied mathematics. Because they
spread mass agnostically at each step in an iterative manner, they can sometimes
spread mass “too aggressively,” thereby failing to find the “right” clusters.
We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both
faster and stays more local than the classical spectral diffusion process. As
an application, we use our CRD Process to develop an improved local algorithm
for graph clustering. Our local graph clustering method can find local clusters
in a model of clustering where one begins the CRD Process in a cluster whose vertices
are connected better internally than externally by an O(log2n) factor, where n
is the number of nodes in the cluster. Thus, our CRD Process is the first local
graph clustering algorithm that is not subject to the well-known quadratic Cheeger
barrier. Our result requires a certain smoothness condition, which we expect to
be an artifact of our analysis. Our empirical evaluation demonstrates improved
results, in particular for realistic social graphs where there are moderately
good—but not very good—clusters.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Di
foaf_name: Wang, Di
foaf_surname: Wang
- foaf_Person:
foaf_givenName: Kimon
foaf_name: Fountoulakis, Kimon
foaf_surname: Fountoulakis
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
- foaf_Person:
foaf_givenName: Michael W.
foaf_name: Mahoney, Michael W.
foaf_surname: Mahoney
- foaf_Person:
foaf_givenName: ' Satish'
foaf_name: Rao , Satish
foaf_surname: 'Rao '
bibo_volume: 70
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2640-3498
dct_language: eng
dct_publisher: ML Research Press@
dct_title: Capacity releasing diffusion for speed and locality@
...