From http://techtalks.tv/talks/a-local-algorithm-for-finding-well-connected-clusters/58322/

- A good cluster should have few edges going relative to the size of the size of the cluster
- Called the conductance (clustering by cutting according to that criteria)
- Google research, so google scale, doesn’t want even linear data cost
- Algorithm is initialized on some vertex, moves around locally, and then finally produces some set S, hopefully with a low conductance
- Has theoretical bounds, cant do better than that due to Cheeger’s inequality
- Algs have runtime linear in size of cluster made from starting point
- Algorithm is quite simple
- Proposes a different metric than standard conductance; connectivity
- Want small conductance and high connectivity (imposed by a relative combination); want better connection inside than outside
- This metric improves theoretical bounds, this beats other random walk based spectral algorithms
- Use of this extra data allows for tighter bounds
- <Proofs>
- Claim a followup work that is local but is big-O optimal based on flow analysis

### Like this:

Like Loading...

*Related*