Evolutionary clustering

By Deepayan Chakrabarti, Ravi Kumar, Andrew Tomkins. Knowledge Discovery and Data Mining, 2006

716 citations recorded by the source corpus.

We consider the problem of clustering data over time. An evolutionary clustering should simultaneously optimize two potentially conflicting criteria: first, the clustering at any point in time should remain faithful to the current data as much as possible; and second, the clustering should not shift dramatically from one timestep to the next. We present a generic framework for this problem, and discuss evolutionary versions of two widely-used clustering algorithms within this framework: k-means and agglomerative hierarchical clustering. We extensively evaluate these algorithms on real data sets and show that our algorithms can simultaneously attain both high accuracy in capturing today's data, and high fidelity in reflecting yesterday's clustering.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/3f1f762b2b6750f2feb1ca2e021b2a3e798774a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

A classification for community discovery methods in complex networks (2011, methodology): “F ea tu re D is ta n ce Evolutionary* X X O(n(2)) 5k ? 2006 [21] MSN-BD X X O(n(2)ck) 6k 3M 2006 [22] SocDim X X X O(n(2) logn)∗ 80k 6M 2009 [23] PMM X X O(mn(2)) 15k 27M 2009 [24] MRGC X X X X O(mD) 40k ? 2007 [25] Infinite Relational X X O(nD) 160 ? 2006 [26] Find-Tribes X X O(mnK(2)) 26k 100k 200”
Community detection in networks: A user guide (2016, background): “An interesting implementation of this strategy is evolutionary clustering [188].”
Tracking the Evolution of Communities in Dynamic Social Networks (2010, background): “Notably, Chakrabarti et al. [6] proposed an “evolutionary clustering” framework to handle this problem, whereby both current and historic information was incorporated into the objective of the clustering process.”
Graph based anomaly detection and description: a survey (2014, methodology): “…1996]; frequent subgraph mining [Kuramochi and Karypis, 2001]; spectral clustering [Ng et al., 2001, Shi and Malik, 1997]; evolutionary clustering [Chakrabarti et al., 2006]; the Newman’s algorithms for community detection in complex systems [Newman and Girvan, 2004],[Newman, 2004],[Newman,…”
Detecting communities and their evolutions in dynamic social networks—a Bayesian approach (2011, background): “Chakrabarti et al. (2006) proposed the first evolutionary clustering methods where the cluster membership at time t is influenced by the clusters at time t − 1.”
Representation Learning for Dynamic Graphs: A Survey (2019, methodology): “, Chamberlain et al. (2017)). Different spaces offer different properties. Note that all these four combination functions are symmetric, i.e., f(zv, zu) = f(zu, zv) where f is any of the above functions. This is an important property when the graph is undirected. For link prediction in digraphs, it ”
Outlier Analysis (2013, methodology): “An example of such an approach is provided in [99].”
Analyzing communities and their evolutions in dynamic social networks (2009, background): “It turns out that the model described by Equation (2) has a close connection to the evolutionary clustering framework ([Chakrabarti et al. 2006; Chi et al. 2007]).”
Community Detection and Mining in Social Media (2010, background): “Another approach to find latent community structure at each snapshot is evolutionary clustering (Chakrabarti et al., 2006).”
Evolutionary spectral clustering by incorporating temporal smoothness (2007, background): “[3], in which they propose an evolutionary hierarchical clustering algorithm and an evolutionary k-means clustering algorithm.”
TextFlow: Towards Better Understanding of Evolving Topics in Text (2011, background): “Evolutionary clustering [5] [6] [31] [32] [34] focuses the problem of processing temporal data to produce a sequence of clusters.”
Multitask Bregman clustering (2010, methodology): “Then based on the general Bregman divergences, the within-task loss is defined as the average Bregman divergence from a data sample to its cluster centroid.”
Event Detection in Social Streams (2012, methodology): “Some clustering methods have recently also been designed for dynamic networks [8, 9], though they do not use the content of the underlying network for the mining process.”
Mining Query Logs: Turning Search Usage Data into Knowledge (2010, neutral): “This would result in a sort of signal to which standard temporal series techniques may be applied [59, 85, 222, 223, 243].”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “A common approach to leverage the temporal aspect of DTDGs is to use time as a regularizer to impose a smoothness constraint over the embeddings of each node over consecutive snapshots [31, 43, 120, 86, 242, 259, 257].”
A survey on data stream clustering and classification (2015, background): “first introduced the problem and proposed a framework for evolutionary clustering [23].”