The maximum clique problem (MCP) has various applications to reveal the structure and function of graphs. Graphs are constantly updated in the real life. However, no algorithm is specifically designed for dynamic graph. AlthoughMCPin dynamic graphs can be solved by simply invoking a state-of-the-art static approach, such asPMC, when the graph is updated, such an approach of simply re-calculating from scratch is inefficient. The key issue withMCPalgorithm is to find a large clique, namely aseed, as fast as possible. Thus, search space can be pruned based on the seed. Size of the seed greedily found byPMCcannot be guaranteed, as it fluctuates considerably. Moreover, the time required to find a seed underPMCis up to$O(| E| \cdot \Delta (G))$, where$\Delta (G)$is the highest degree inG. In this article, we intend to find a sizable seed by updating the previous maximum clique with the incident vertices of the inserted/deleted edge. Size of the seed now is guaranteed to be no less than$\omega (G^{\prime})\; - \;1$, where$\omega (G^{\prime})$is the size of the maximum clique on the updated graph. Moreover, the seed can be found in a time complexity of$O(\Delta (G)^{2})$. Two other crucial issues related to theMCPin dynamic graphs are refreshing rate and refreshing overhead. After a tight upper bound is imposed on$\omega (G^{\prime})$, the necessity of refreshing is evaluated by comparing the seed with its largest challenger, then unnecessary refreshing is wiped out effectively. The size of the largest challenger is judiciously estimated using a lazy growth strategy. Subsequently, the search space in refreshing is confined on a much smaller subgraph using a local refreshing strategy. Extensive experiments indicate that the proposed approach outperforms the baseline algorithm by approximately one order of magnitude.

Maximal Clique Enumeration (MCE) is a long standing problem in database community. Though it is extensively studied, almost all researches focus on calculating maximal cliques as a one-time effort. MCE on dynamic graph has been rarely discussed so far, the only work on this topic is to maintain maximal cliques with graph evolving. The key within this problem is to find maximal cliques that contains vertices incident to the inserted edge when edge insertion happens. Up to O(W2) candidates are generated in prior method based on Cartesian product, the overall complexity is O(W2n2) where n, W represents the number of vertices and maximal cliques on the graph. Besides, maximality verification of candidate is conducted frequently by global search. Change of maximal clique induced by graph's updating presents some localities. We propose novel local construction strategy to generate candidates based on linear scan, number of candidates is reduced to O(W), the overall complexity is then reduced to O(Wn2). Furthermore, we present heuristics to reduce the cost incurred by maximality verification. Theoretical analysis and experiments on real graphs indicate that our proposals are effective and efficient.