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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Query-Centered Fairness-Aware Maximum Clique Search in Dynamic Attributed Graphs

  • Jingwen Chen,
  • Jianuo Xu,
  • Xinrui Wang,
  • Hong Gao,
  • Dongxiao Yu

摘要

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.