.png){kind=icon}
返回
Query-Centered Fairness-Aware Maximum Clique Search in Dynamic Attributed Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-5640-3_43.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Dynamic Attributed Graphs
Fairness
Maximum Clique Search
Incremental Algorithms
期刊
W
IF:
0
论文数:
32
被引数:
0
机构
引用论文
.png){kind=icon}
The worst-case time complexity for generating all maximal cliques and computational experiments
PREAI
分享收藏
Incremental Maximal Clique Enumeration for Hybrid Edge Changes in Large Dynamic Graphs大型动态图中混合边变化的增量最大集团枚举
PREAI
分享收藏
查看更多内容