Query-Centered Fairness-Aware Maximum Clique Search in Dynamic Attributed Graphs
摘要
On attributed graphs, fairness-aware maximal clique models which consider the fairness of members’ attributes in a clique, have a wide range of practical applications. Existing work has proposed efficient algorithms to enumerate all maximal fair cliques in static attributed graphs. However, the real-world graphs are often dynamic, including the insertion and deletion of vertices and edges over time. But existing work ignored how to efficiently search fair cliques in dynamic attributed graphs. In this paper, we focus on how to efficiently search maximum fair cliques which contain the given query vertex in a dynamic attributed graph. Firstly, we formalize the problem of query-centered maximum fair clique search in a dynamic attributed graph which is NP-hard. Then we give a basic algorithm to recalculate maximum fair cliques in the pruned search space each time inserting or deleting one edge. Furthermore, we develop two incremental algorithms with pruning and early termination strategies, both can avoid recalculating all results from scratch, and greatly reduce the time of searching maximum fair cliques each time inserting or deleting one edge. Extensive experiments on 6 real-world graphs show extremely higher efficiency and better scalability of our incremental algorithms compared to the basic algorithm.