Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning
This addresses fairness issues in network analysis for real-world applications, representing a novel method for a known bottleneck rather than incremental.
The paper tackles the problem of fairness in community partitioning by introducing a fairness-modularity metric and proving that minimizing it yields fair partitions for protected groups, with experiments showing FairFN achieves significantly improved fairness and high-quality partitions compared to state-of-the-art methods.
Community partitioning is crucial in network analysis, with modularity optimization being the prevailing technique. However, traditional modularity-based methods often overlook fairness, a critical aspect in real-world applications. To address this, we introduce protected group networks and propose a novel fairness-modularity metric. This metric extends traditional modularity by explicitly incorporating fairness, and we prove that minimizing it yields naturally fair partitions for protected groups while maintaining theoretical soundness. We develop a general optimization framework for fairness partitioning and design the efficient Fair Fast Newman (FairFN) algorithm, enhancing the Fast Newman (FN) method to optimize both modularity and fairness. Experiments show FairFN achieves significantly improved fairness and high-quality partitions compared to state-of-the-art methods, especially on unbalanced datasets.