Maximum Fairness-Aware (k, r)-Core Identification in Large Graphs

Cohesive subgraph mining is a fundamental problem in attributed graph analysis. The k-core model has been widely used in many studies to measure the cohesiveness of subgraphs. However, none of them considers the fairness of attributes in communities. To address this limitation, we propose a novel model, named fair (k, r)-core, to assess fairness equity within communities captured in attributed graphs. The model not only focuses on cohesive community structure but also eliminates vertices that contribute to unfairness. We prove that the problem of identifying the maximum fair (k, r)-core is NP-hard. To scale for large graphs, we introduce innovative pruning techniques and search methods. Comprehensive experiments are conducted on 6 real-world datasets to evaluate the efficiency and effectiveness of the proposed model and solutions.