Efficient Maximum Relative Fair Clique Computation in Attributed Graphs

Cohesive subgraph mining is a fundamental problem in attributed graph analysis. However, the existing models on attributed graphs ignore the fairness of attributes. In this paper, we propose a novel model, called maximum relative fair clique, which integrates cohesiveness and fair resource allocation. Specifically, given an attributed graph G and a positive integer \(\delta \) , a relative fair clique is a clique where the number of vertices with the most common attribute minus the number of vertices with the least amount of the common attribute should be no more than \(\delta \) . We aim to find the maximum relative fair clique, which is the maximal one with the largest size. To solve this problem, we develop an algorithm, MRFCSearch, equipped with a novel heuristic algorithm and an efficient pruning technique. We evaluate the algorithm on four real-world graphs, demonstrating the performance of the proposed techniques.