Length of clustering algorithms based on random walks with an application to neuroscience

In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.

► Study of the choice of the length used by a clustering algorithm called Walktrap. ► Study of the convergence rate of random walks on graph. ► Description of the cutoff phenomenon for random walks on graph. ► Introduction of a dynamical hierarchical clustering algorithm for finite sequences of graphs.