Graph clustering
Computer Science ReviewPublished 1 August 2007
Satu Elisa Schaeffer
Citations1,574
SJR quartileQ1
SJR score3.28
SNIP6.22
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 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.
Abstract
In this survey we overview the definitions and methods for graph clustering, that is, finding sets of "related" vertices in graphs. We review the many definitions for what is a cluster in a graph and measures of cluster quality. Then we present global algorithms for producing a clustering for the entire vertex set of an input graph, after which we discuss the task of identifying a cluster for a specific seed vertex by local computation. Some ideas on the application areas of graph clustering algorithms are given. We also address the problematics of evaluating clusterings and benchmarking cluster algorithms.
Keywords
Computer SciencePhysics and Astronomy
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
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.
ACM Computing SurveysData clustering
13,184 Citations1999Anil K. Jain, M. Narasimha Murty +1 more
An overview of pattern clustering methods from a statistical pattern recognition perspective is presented, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners.
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
SociometryA Set of Measures of Centrality Based on Betweenness
10,249 Citations1977Linton C. Freeman
A family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced, used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Cluster Separation Measure
8,543 Citations1979David L. Davies, Donald W. Bouldin
A measure is presented which indicates the similarity of clusters which are assumed to have a data density which is a decreasing function of distance from a vector characteristic of the cluster which can be used to infer the appropriateness of data partitions.
Physical Review EFinding community structure in very large networks
7,484 Citations2004Aaron Clauset, M. E. J. Newman +1 more
A hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure.
BMC BioinformaticsAn automated method for finding molecular complexes in large protein interaction networks
6,293 Citations2003Gary D. Bader, Christopher W.V. Hogue
A novel graph theoretic clustering algorithm, "Molecular Complex Detection" (MCODE), that detects densely connected regions in large protein-protein interaction networks that may represent molecular complexes is described.
Physical Review EFast algorithm for detecting community structure in networks
5,491 Citations2004M. E. J. Newman
An algorithm is described which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms.
Bell System Technical JournalAn Efficient Heuristic Procedure for Partitioning Graphs
5,218 Citations1970Brian W. Kernighan, Shang Min Lin
A heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems is presented.
Physical Review LettersEfficient Behavior of Small-World Networks
5,151 Citations2001Vito Latora, Massimo Marchiori
It is shown that the underlying general principle of their construction is in fact a small-world principle of high efficiency, which gives a clear physical meaning to the concept of "small world," and also a precise quantitative analysis of both weighted and unweighted networks.
Journal of Mathematical SociologyA faster algorithm for betweenness centrality*
4,926 Citations2001Ulrik Brandes
New algorithms for betweenness are introduced in this paper and require O(n + m) space and run in O(nm) and O( nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links.
Physical Review EFinding community structure in networks using the eigenvectors of matrices
4,801 Citations2006M. E. J. Newman
A modularity matrix plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations, and a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong are proposed.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
ACM Computing SurveysVoronoi diagrams—a survey of a fundamental geometric data structure
4,317 Citations1991Franz Aurenhammer
Pattern Classification
3,739 Citations2001Shigeo Abe
Algorithms on strings, trees, and sequences: computer science and computational biology
3,529 Citations1997Dan Gusfield
IEEE Transactions on Pattern Analysis and Machine IntelligenceA validity measure for fuzzy clustering
3,380 Citations1991Xiao‐Zhu Xie, G. Beni
The authors present a fuzzy validity criterion based on a validity function which identifies compact and separate fuzzy c-partitions without assumptions as to the number of substructures inherent in the data.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems
3,133 Citations1997Dorit S. Hochba
This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.
Journal of Statistical Mechanics Theory and ExperimentComparing community structure identification
2,877 Citations2005León Danon, Albert Dı́az-Guilera +2 more
It is found that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
The Computer JournalHow Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis
2,519 Citations1998Chris Fraley
The problems of determining the number of clusters and the clustering method are solved simultaneously by choosing the best model, and the EM result provides a measure of uncertainty about the associated classification of each data point.
Advances In PhysicsCharacterization of complex networks: A survey of measurements
2,456 Citations2007Luciano da Fontoura Costa, Francisco A. Rodrigues +2 more
This article presents a survey of measurements capable of expressing the most relevant topological features of complex networks and includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements.
Canadian Journal of MathematicsMaximal Flow Through a Network
2,340 Citations1956L. R. Ford, D. R. Fulkerson
Theoretical Computer ScienceSome simplified NP-complete graph problems
2,068 Citations1976M. R. Garey, David S. Johnson +1 more
This paper shows that a number of NP - complete problems remain NP -complete even when their domains are substantially restricted, and determines essentially the lowest possible upper bounds on node degree for which the problems remainNP -complete.
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
The European Physical Journal BDetecting community structure in networks
2,022 Citations2004M. E. J. Newman
A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.
Ad Hoc Networking
1,909 Citations2008Charles E. Perkins
Journal of the ACMA new approach to the maximum-flow problem
1,877 Citations1988Andrew V. Goldberg, Robert E. Tarjan
An alternative method based on the preflow concept of Karzanov, which runs as fast as any other known method on dense graphs, achieving an O(n) time bound on an n-vertex graph and faster on graphs of moderate density.
Probability and Random Processes
1,858 Citations2001Geoffrey Grimmett, David Stirzaker
Birkhäuser Boston eBooksMaximal Flow Through a Network
1,856 Citations2009L. R. Ford, D. R. Fulkerson
Proceedings of the National Academy of SciencesThe worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
1,780 Citations2005Roger Guimerà, Stefano Mossa +2 more
It is found that the worldwide air transportation network is a scale-free small-world network, and it is demonstrated that the most connected cities are not necessarily the most central, resulting in anomalous values of the centrality.
The Carus mathematical monographsRandom Walks and Electric Networks
1,776 Citations1984Peter G. Doyle, J. Laurie Snell
IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters
1,741 Citations1971C. T. Zahn
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.
Theoretical Computer ScienceClustering to minimize the maximum intercluster distance
1,725 Citations1985Teofilo F. Gonzalez
An O(kn) approximation algorithm that guarantees solutions with an objective function value within two times the optimal solution value is presented and it is shown that this approximation algorithm succeeds as long as the set of points satisfies the triangular inequality.
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
IEEE Transactions on Pattern Analysis and Machine IntelligenceUnsupervised optimal fuzzy clustering
1,643 Citations1989Isak Gath, Amir B. Geva
The unsupervised fuzzy partition-optimal number of classes algorithm performs well in situations of large variability of cluster shapes, densities, and number of data points in each cluster.
How to Solve It: Modern Heuristics
1,633 Citations2004Zbigniew Michalewicz, David B. Fogel
This book discusses computational experiments with heuristic methods for solving practical problems and basic concepts of probability and Statistics, as well as an Evolutionary approach to decision-making.
Graph Clustering by Flow Simulation
1,608 Citations2000S.M. van Dongen
IEEE Journal on Selected Areas in CommunicationsAdaptive clustering for mobile wireless networks
1,523 Citations1997Chun‐Hung Richard Lin, Mário Gerla
This paper describes a self-organizing, multihop, mobile radio network which relies on a code-division access scheme for multimedia support that provides an efficient, stable infrastructure for the integration of different types of traffic in a dynamic radio network.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
1,468 Citations1989David S. Johnson, C. Aragon +2 more
This paper discusses annealing and its parameterized generic implementation, describes how this generic algorithm was adapted to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAssessing a mixture model for clustering with the integrated completed likelihood
1,455 Citations2000Christophe Biernacki, Gilles Celeux +1 more
An assessing method of mixture model in a cluster analysis setting with integrated completed likelihood appears to be more robust to violation of some of the mixture model assumptions and it can select a number of dusters leading to a sensible partitioning of the data.
Computers & Mathematics with ApplicationsComplexity and approximation: Combinatorial optimization problems and their approximability properties
1,289 Citations2000
Machine LearningCorrelation Clustering
1,091 Citations2004Nikhil Bansal, Avrim Blum +1 more
This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible; it can also be viewed as a kind of “agnostic learning” problem.
ComputerSelf-organization and identification of Web communities
1,007 Citations2002Gary William Flake, Sandra Lawrence +2 more
This work shows that the Web self-organizes and its link structure allows efficient identification of communities and is significant because no central authority or process governs the formation and structure of hyperlinks.
The Maximum Clique Problem
975 Citations1999Immanuel M. Bomze, Marko Budinich +2 more
This paper considers the problem of finding the largest clique in a graph using the notation ES to represent the subset of edges which have both endpoints in clique S, and concludes that the induced graph GS = ( S, ES ) is complete.
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.
Journal of the Society for Industrial and Applied MathematicsMulti-Terminal Network Flows
940 Citations1961Ralph E. Gomory, T. C. Hu
Journal of the Operational Research SocietyFuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition
929 Citations2000V. J. Rayward‐Smith, Frank Höppner +3 more
This paper presents a meta-modelling framework that automates the very labor-intensive and therefore time-heavy and therefore expensive process of rule generation and estimation in the context of cluster dynamics.
Cambridge University Press eBooksIntroduction to algorithms
809 Citations2018Giuseppe C. Calafiore, Laurent El Ghaoui
Physical Review EFinding local community structure in networks
789 Citations2005Aaron Clauset
This work defines both a measure of local community structure and an algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time, and uses this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
784 Citations2004Daniel A. Spielman, Shang‐Hua Teng
This paper presents algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where ε is the condition number of the matrix defining the linear system.
Scaling clustering algorithms to large databases
709 Citations1998Patricia Bradley, Usama M. Fayyad +1 more
A scalable clustering framework applicable to a wide class of iterative clustering that requires at most one scan of the database and is instantiated and numerically justified with the popular K-Means clustering algorithm.
IEEE Transactions on Fuzzy SystemsRobust clustering methods: a unified view
708 Citations1997Rajesh N. Davé, Raghu Krishnapuram
This paper analyzes several popular robust clustering methods and concludes that they have much in common, establishing a connection between fuzzy set theory and robust statistics, and pointing out the similarities between robust clusters methods and statistical methods.
Linear Algebra and its ApplicationsWhich graphs are determined by their spectrum?
677 Citations2003Edwin van Dam, Willem H. Haemers
BioinformaticsProtein complex prediction via cost-based clustering
668 Citations2004Andrew D. King, Nataša Pržulj +1 more
The RNSC algorithm is developed to efficiently partition networks into clusters using a cost function and provides an accurate and scalable method of detecting and predicting protein complexes within a PPI network.
A Random Walks View of Spectral Segmentation.
631 Citations2001Marina Meilă, Jianbo Shi
It is proved that the Normalized Cut method arises naturally from the framework and a complete characterization of the cases when the Normalization Cut algorithm is exact is provided.
Clustering data streams
628 Citations2002Suvajyoti Guha, Nita Mishra +2 more
This work gives constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass, and shows negative results implying that these algorithms cannot be improved in a certain sense.
ACM Computing SurveysGraph mining
621 Citations2006Deepayan Chakrabarti, Christos Faloutsos
This survey gives an overview of the incredible variety of work that has been done on graph problems and one of the main contributions is the integration of points of view from physics, mathematics, sociology, and computer science.
Spectral partitioning of random graphs
615 Citations2001Frank McSherry
This paper shows that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density.
ACM Computing SurveysA survey of graph layout problems
607 Citations2002Josep Dı́az, Jordi Petit +1 more
A complete view of the current state of the art with respect to layout problems from an algorithmic point of view is presented.
AlgorithmicaThe Dense k -Subgraph Problem
602 Citations2001Uriel Feige, David Peleg +1 more
An approximation algorithm is developed for the problem of computing the dense k -vertex subgraph of a given graph, namely, the subgraph with the most edges, with approximation ratio O(nδ) , for some δ < 1/3 .
SIAM Journal on ComputingA Fast Parametric Maximum Flow Algorithm and Applications
585 Citations1989Giorgio Gallo, Michael D. Grigoriadis +1 more
It is shown that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst-case time bound.
On the bursty evolution of blogspace
561 Citations2003Ravi Kumar, Jasmine Novak +2 more
An Impossibility Theorem for Clustering
514 Citations2002Jon Kleinberg
A formal perspective on the difficulty in finding a unified framework for reasoning about clustering at a technical level is suggested, in the form of an impossibility theorem: for a set of three simple properties, it is shown that there is no clustering function satisfying all three.
BMC BioinformaticsDevelopment and implementation of an algorithm for detection of protein complexes in large interaction networks
500 Citations2006Md. Altaf‐Ul‐Amin, Yoko Shinbo +3 more
The proposed algorithm makes it possible to detect clusters of proteins in PPI networks which mostly represent molecular biological functional units, and they are also useful to understand and explain certain biological processes.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsProperties of highly clustered networks
490 Citations2003M. E. J. Newman
The results indicate that increased clustering leads to a decrease in the size of the giant component of the network, and clustering causes epidemics to saturate sooner, meaning that they infect a near-maximal fraction of thenetwork for quite low transmission rates.
Information Processing LettersA clustering algorithm based on graph connectivity
487 Citations2000Erez Hartuv, Ron Shamir
A novel algorithm for cluster analysis that is based on graph theoretic techniques and produces a solution with some provably good properties and performs well on simulated and real data.
The uncapacitated facility location problem
482 Citations1990Gérard Cornuéjols, George L. Nemhauser +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectra of “real-world” graphs: Beyond the semicircle law
481 Citations2001Illés J. Farkas, Imre Derényi +2 more
Methods to determine the eigenvalues of networks comparable in size to real systems are developed, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs.
Machine LearningClustering Large Graphs via the Singular Value Decomposition
477 Citations2004Petros Drineas, Alan Frieze +3 more
This paper considers the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters, and considers a continuous relaxation of this discrete problem: find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points, and argues that the relaxation provides a generalized clustering which is useful in its own right.
The European Physical Journal BFinding communities in linear time: a physics approach
456 Citations2004F. Wu, Bernardo A. Huberman
The European Physical Journal B (EPJ B) publishes regular articles and colloquia in Condensed Matter and Complex Systems on the range of topics including Solid State and Materials, Computational Methods, Statistical and Nonlinear Physics, and Interdisciplinary Physics.
ACM SIGKDD Explorations NewsletterState of the art of graph-based data mining
446 Citations2003Takashi Washio, Hiroshi Motoda
This article introduces the theoretical basis of graph based data mining and surveys the state of the art of graph-based data mining.
IEEE Transactions on Information TheoryA note on the maximum flow through a network
445 Citations1956P. Eliáš, Amiel Feinstein +1 more
The main result is a theorem: the maximum possible flow from left to right through a network is equal to the minimum value among all simple cut-sets.
Proteins Structure Function and BioinformaticsDetection of functional modules from protein interaction networks
444 Citations2003José B. Pereira‐Leal, Anton J. Enright +1 more
This study successfully isolate 1046 functional modules from the known protein interaction network of Saccharomyces cerevisiae involving 8046 individual pair‐wise interactions by using an entirely automated and unsupervised graph clustering algorithm.
ACM SIGCOMM Computer Communication ReviewA cluster-based approach for routing in dynamic networks
438 Citations1997P. Venkata Krishna, Nitin H. Vaidya +2 more
This work proposes a new methodology for routing and topology information maintenance in dynamic networks by dividing the graph into a number of overlapping clusters and presenting algorithms for creation of clusters, as well as algorithms to maintain them in the presence of various network events.
Random Structures and AlgorithmsAlgorithms for graph partitioning on the planted partition model
433 Citations2001Anne Condon, Richard M. Karp
UC BerkeleyLearning Spectral Clustering
431 Citations2003Francis R. Bach, Michael I. Jordan
A new cost function for spectral clustering is derived based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem.
Optimal algorithms for approximate clustering
419 Citations1988Tomás Feder, Daniel Greene
This work gives a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1 for a fixed cluster size.
Spectral partitioning works: planar graphs and finite element meshes
406 Citations1996Daniel A. Spielman, Shang‐Hua Teng
It is proved that spectral partitioning techniques can be used to produce separators whose ratio of vertices removed to edges cut is O(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 1/d/) for well-shaped d-dimensional mesh.
Journal of the ACMApproximation algorithms for classification problems with pairwise relationships
405 Citations2002Jon Kleinberg, Éva Tardos
Linear Algebra and its ApplicationsOld and new results on algebraic connectivity of graphs
383 Citations2006Nair Maria Maia de Abreu
Birkhäuser Boston eBooksAlgorithms for Random Generation and Counting: A Markov Chain Approach
381 Citations1993Alistair Sinclair
The Markov chain approach to generation problems and self-embeddable relations, a robust notion of approximate counting, and direct applications.
Operations ResearchHub Location and the <i>p</i>-Hub Median Problem
378 Citations1996James F. Campbell
A p-hub median is defined, analogous to a p-median, and integer programming formulations for the multiple and single allocation p-Hub median problems are presented, and two new heuristics for the single allocations p- hub median problem are evaluated.
Learning Segmentation by Random Walks
370 Citations2000Marina Meilă, Jianbo Shi
This interpretation shows that spectral methods for clustering and segmentation have a probabilistic foundation and proves that the Normalized Cut method arises naturally from the framework.
Journal of Statistical Mechanics Theory and ExperimentDetecting network communities: a new systematic and efficient algorithm
364 Citations2004Luca Donetti, Miguel A Muñoz
Incremental clustering and dynamic information retrieval
358 Citations1997Moses Charikar, Chandra Chekuri +2 more
This work considers the problem of clustering dynamic point sets in a metric space and proposes a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications.
…