Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
1
-
$\begingroup$ @RB Yes, I was wondering if it is possible to avoid checking the whole graph with each update (at the expense of memory needed for storing existing cliques) by inspecting only cliques existing in the neighborhood of the added edge, e.g. joining cliques when edge is added, dividing when edge is removed. $\endgroup$– gornikmAug 21, 2014 at 19:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
First of all I think you mean a maximum clique, not all cliques (and even not maximal cliques). As otherwise e.g in $K_n$ there are $2^n−1$ cliques.
If the question is the one that I said, then there is no polynomial time online algorithm for update (unless P=NP). If there is such an algorithm $A$, given a graph $G$, we can find a maximum clique of $G$ in polynomial time. Just start from a graph on $n$ vertex without any edge and add edges of $G$ one by one and update information in each step by $A$. After adding all edges we have a maximum clique. Note that if we use exponential memory at some steps we can do this, but to write on exponential memory we need exponential time as well.
Maybe there are some heuristics.
$\begingroup$
$\endgroup$
here are two refs with some analysis of this problem and the first shows/ measures performance improvements over batch algorithms.
Incremental K-clique clustering in dynamic social networks Duan, Li, Lu
Based on the change stream model, the incremental version of a well known k-clique clustering problem is studied and incremental k-clique clustering algorithms are proposed based on local DFS (depth first search) forest updating technique. It is theoretically proved that the proposed algorithms outperform corresponding static ones and incremental spectral clustering algorithm in terms of time complexity. ... Experimental results show that incremental k-clique clustering algorithms are much more efficient than corresponding static ones, and have no accumulating errors that incremental spectral clustering algorithm has and can capture the evolving details of the clusters that snapshot graph model based algorithms miss.
A Realtime Clique Detection Algorithm: Time-Based Incremental Label Propagation Pang, Chen, Wei
