Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times\left( 2+ \alpha (G) \right)+n)$ to $O(m+n)$ for any given value of $\varepsilon$ for a complete signed graph with $n$ vertices and $m$ positive edges where $\alpha(G)$ is the arboricity of the graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting where edge sign flipping and vertex addition/removal are allowed. Constructing this index costs $O(m)$ memory and $O(m\times\alpha(G))$ time. We also studied the structural properties of the non-agreement measure used in the approximation algorithm. The theoretical results are accompanied by a full set of experiments concerning seven real-world graphs. These results shows superiority of our index-based algorithm to the non-index one by a decrease of %34 in time on average.
Code (1)
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
Online Correlation Clustering for Dynamic Complete Signed Graphs
In the correlation clustering problem for complete signed graphs, the input is a complete signed graph with edges weighted as $+1$ (denote recommendation to put this pair in the same cluster) or $-1$ (recommending to put…
ClusteringHigh-order Correlation Preserved Incomplete Multi-view Subspace Clustering
Incomplete multi-view clustering aims to exploit theinformation of multiple incomplete views to partition data into their clusters. Existing methods only utilize the pair-wise sample correlation and pair-wise view correl…
ClusteringIncomplete multi-view clusteringMulti-view Subspace ClusteringVocal Bursts Intensity PredictionFully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
We study the dynamic correlation clustering problem with $\textit{adaptive}$ edge label flips. In correlation clustering, we are given a $n$-vertex complete graph whose edges are labeled either $(+)$ or $(-)$, and the go…
Adversarial RobustnessClusteringMotif and Hypergraph Correlation Clustering
Motivated by applications in social and biological network analysis, we introduce a new form of agnostic clustering termed~\emph{motif correlation clustering}, which aims to minimize the cost of clustering errors associa…
ClusteringCorrelation Clustering with Random Partial Information
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the …