Length of clustering algorithms based on random walks with an application to neuroscience |
| |
| Authors: | Michèle Thieullen Alexis Vigot |
| |
| Institution: | 1. Laboratoire de Probabilités et Modèles Aléatoires, Université Pierre et Marie Curie, 4, Place Jussieu, 75252 Paris cedex 05, France;2. Laboratoire de Probabilités et Modèles Aléatoires, Boite 188, 4, Place Jussieu, Université Pierre et Marie Curie, 75252 Paris cedex 05, France;1. Ecole National Superieure, 46 rue d''Ulm, 75230 Paris, France;2. Hopital de la Salpetriere, 47 bd. de l''Hopital, 75651 Paris Cedex 13, France;3. CNRS&Universite 7-Denis Diderot, 10 rue Alice Domon et Leonie Duquet, 75205 Paris Cedex 13, France;1. Department of Automation and Biomechanics, Technical University of ?ód?, 1/15 Stefanowski St., 90-924 Lodz, Poland;2. Saratov State Technical University, Department of Mathematics and Modeling, Politehnicheskaya 77, 410054 Saratov, Russian Federation;3. Engels Institute of Technology (Branch) Saratov State Technical University, Department of Higher Mathematics and Mechanics, Ploschad Svobodi 17, 413100 Engels, Saratov Region, Russian Federation;1. Facultad de Ingenier?´a, Universidad Autónoma de Querétaro, Centro Universitario Cerro de las Campanas, 76010 Santiago de Querétaro, Mexico;2. Depto. de Electrónica, CUCEI, Universidad de Guadalajara, Av. Revolución 1500, 44430 Guadalajara, Jal., Mexico |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
