Graph clustering based on mixing time of random walks
Published 1 June 2014Open access
Konstantin Avrachenkov, Mahmoud El Chamie, Giovanni Neglia
Citations10
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering and proposes a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined.
Abstract
International audience
Keywords
Computer SciencePhysics and Astronomy
Journal of Statistical Mechanics Theory and ExperimentFast unfolding of communities in large networks
21,223 Citations2008Vincent D. Blondel, Jean‐Loup Guillaume +2 more
This work proposes a heuristic method that is shown to outperform all other known community detection methods in terms of computation time and the quality of the communities detected is very good, as measured by the so-called modularity.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
Proceedings of the International AAAI Conference on Web and Social MediaGephi: An Open Source Software for Exploring and Manipulating Networks
11,305 Citations2009Mathieu Bastian, Sébastien Heymann +1 more
This work presents several key features of Gephi in the context of interactive exploration and interpretation of networks, and highlights key aspects of dynamic network visualization.
Introduction to Data Mining
7,026 Citations2008
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
Proceedings of the National Academy of SciencesResolution limit in community detection
3,045 Citations2006Santo Fortunato, Marc Barthélemy
It is found that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.
Computer Science ReviewGraph clustering
1,574 Citations2007Satu Elisa Schaeffer
This survey overviews the definitions and methods for graph clustering, that is, finding sets of ''related'' vertices in graphs, and presents global algorithms for producing a clustering for the entire vertex set of an input graph.
Local Graph Partitioning using PageRank Vectors
967 Citations2006Reid Andersen, Fan Chung +1 more
An improved algorithm for computing approximate PageRank vectors, which allows us to find a cut with conductance at most oslash and approximately optimal balance in time O(m log4 m/oslash) in time proportional to its size.
SIAM Journal on Matrix Analysis and ApplicationsGraph Clustering Via a Discrete Uncoupling Process
744 Citations2008Stijn van Dongen
The MCL process is the engine for the graph clustering algorithm called the MCL algorithm, and the process (and algorithm) iterands posses structural properties generalizing the mapping from process limits onto clusterings.
On clusterings-good, bad and spectral
380 Citations2002Ramachandran Kannan, S. Vempala +1 more
Two results regarding the quality of the clustering found by a popular spectral algorithm are presented, one proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.
Journal of Applied ProbabilityOn Quasi-Stationary distributions in absorbing discrete-time finite Markov chains
348 Citations1965J. N. Darroch, E. Seneta
Acta InformaticaNP-hard problems in hierarchical-tree clustering
218 Citations1986Mirko Kr̆ivánek, Jaroslav Morávek
The main result establishes the NP-completeness of a problem of the best approximation of a symmetric relation on a finite set by an equivalence relation, thus answering in the negative a question proposed implicitly by C.T. Zahn.
Lecture notes in computer scienceIs There a Best Quality Metric for Graph Clusters?
121 Citations2011Hélio Marcos Paz de Almeida, Dorgival Guedes +2 more
The results show that currently used clustering algorithms and quality metrics do not behave as expected when cluster structures are different from the more traditional, clique-like ones, especially seen in larger networks.
Linear Algebra and its ApplicationsBounds for eigenvalues of certain stochastic matrices
94 Citations1981H. J. Landau, Andrew Odlyzko
SIAM Journal on Discrete MathematicsAn Interlacing Result on Normalized Laplacians
69 Citations2004Guantao Chen, George J. Davis +4 more
Cauchy interlacing-type properties of the normalized Laplacian are investigated, and the following result is established: $G$ is a graph with each component a nontrivial bipartite graph if and only if $2-\lambda$ is an eigenvalue of ${\cal L}(G)$ for each eigen value $\lambda$ of ${cal L }(G).