Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning

Yufeng Wang, Yiguang Bai, Tianqing Zhu, Ismail Ben Ayed, Jing Yuan · 2025

Read Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning by Yufeng Wang, Yiguang Bai, Tianqing Zhu, Ismail Ben Ayed, Jing Yuan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22684.txt.

Introduction

Splitting a network into communities usually means maximizing modularity, a score for how well knit each group is. Yufeng Wang and co-authors point out that the best-scoring split can shortchange protected groups, and they build fairness straight into the score. Their fairness-modularity measure rewards partitions that treat protected groups evenly, and they prove that minimizing a related cost yields naturally fair splits.

On top of the measure they design Fair Fast Newman, an algorithm that adapts a classic fast method to chase both quality and fairness at once. In experiments, especially on lopsided datasets, it produced partitions that were markedly fairer than rival methods while keeping community quality high.

Catalog record

CREATORYufeng Wang, Yiguang Bai, Tianqing Zhu, Ismail Ben Ayed, Jing Yuan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22684

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning Yufeng Wang, Yiguang Bai, Tianqing Zhu, Ismail Ben Ayed, Jing Yuan Abstract 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. 1 Introduction Community detection is a crucial scientific problem in network analysis, essential for understanding the structure and dynamics of complex networks. Related algorithms for community detection in a complex network are extensively utilized in various fields, including social networks, recommendation systems, bioinformatics, and traffic networks ( Fortunato, 2010 ) . Traditional algorithms primarily focus on maximizing community cohesiveness, often using modularity, a widely adopted metric introduced by Newman (2004) , as a measure to evaluate the quality of the resulting partitions given its close correspondence with the intrinsic structural properties observed in real-world networks ( Fortunato & Newman, 2022 ) . This has led to the development of numerous popular algorithms based on modularity optimization, including the Fast Newman algorithm ( Newman, 2004 ) , the Clauset-Newman-Moore algorithm ( Clauset et al., 2004 ) , the Louvain algorithm ( Blondel et al., 2008 ) , and the fast complex network clustering algorithm ( Jin et al., 2011 ) . Other approaches include the random walk ant colony algorithm ( Di et al., 2012 ) , the label propagation-based algorithm ( Raghavan et al., 2007 ) , the intuitive-based Girvan-Newman algorithm ( Newman & Girvan, 2004 ) , and information-based algorithm ( Rosvall & Bergstrom, 2007 ) . While these traditional modularity-based community partitioning algorithms have achieved significant results in community detection, a substantial limitation is that they often prioritize structural and cohesive community properties but omit fairness considerations. This can result in biased partitioning, especially when nodes are characterized by diverse attributes like gender, age, or race; such biases lead to overrepresentation or underrepresentation of specific groups within the detected communities. The concept of fairness in community partitioning promotes the constraint that the distribution of relevant attributes within each identified community should match the distribution observed in the global network. It is especially critical in sensitive application domains, such as social networks and criminal justice systems, where the deployment of biased algorithms has the potential to exacerbate existing societal inequalities. The COMPAS algorithm, employed in the U.S. criminal justice system, exemplifies this issue, having been shown to exhibit racial bias in sentencing decisions ( Khademi & Honavar, 2020 ) . Similar issues arise in other contexts; for example, biased power distribution may result in significant inequalities if regional needs are not addressed equitably, particularly during periods of resource scarcity. To address fairness in community partitioning, researchers have explored various approaches. Chierichetti et al. (2017) pioneered the concept of fair clustering, introducing "fairlets" to transform the problem into a more traditional clustering task and proposing approximation algorithms along with a "balance" metric for fairness. Ziko et al. (2021) used Kullback-Leibler (KL) divergence to measure community fairness, incorporating it as a penalty in objective functions for algorithms like K-Means, K-Medians, and Ncut. Pan et al. (2024) similarly studied fairness in K-Means, adding a penalty based on the difference between the protected group proportions within a community and the overall population. And then optimized it using coordinate descent. For spectral clustering, Kleindessner et al. (2019) used linear constraints based on the balance metric, and Wang et al. (2023) later proposed the s-FairSC algorithm to improve the computational efficiency of Kleindessner’s FairSC approach. Li et al. (2024) developed a fair multi-view clustering algorithm, using the degree of protected group nodes as a penalty within the Rcut framework. Zhou et al. (2025) achieved fair ensemble clustering through the vector rotation and the penalty term constructed by the Frobenius norm, which also ensured that the sizes of clusters are similar. Finally, Manolis & Pitoura (2024) connected fair community partitioning with the concept of "modularity fairness." A critical challenge of enforcing fairness in community partitioning is the potential trade-off between the effect of maximizing communities’ internal cohesion and the achievement of fairness in each community. This necessitates identifying a suitable balance among these competing objectives. While several studies introduced metrics for evaluating fairness in the context of modularity, no existing algorithm incorporates fairness directly within the modularity optimization procedure. This motivates the present study, which proposes an integrated approach to community partitioning by incorporating fairness considerations within the established framework of modularity-based methods, thereby providing a more comprehensive and elegant approach to the problem of fair community partitioning. Our main contributions to fair community partitioning in this study can be summarized as follows. Firstly, we introduce the concept of protected group network , which presents a novel perspective for analyzing fairness in community partitioning. This perspective facilitates a deeper understanding of community fairness, which lays the groundwork in theory for fair community detection and derives the novel fairness-modularity ( Q^{P} ) based on the modularity of the introduced protected group network. Particularly, we show that minimizing Q^{P} directly leads to fair community partitioning. Moreover, we propose a new modularity optimization algorithm, the so-called FairFN algorithm, to achieve efficient and effective fair community partitioning. It pioneers a way to integrate fairness directly into modularity optimization without significantly increasing computational complexity. The proposed FairFN algorithm outperforms state-of-the-art fair clustering algorithms in fairness while obtaining better community partitioning results, even on unbalanced datasets. It presents a novel groundbreaking solution for fair community detection in both theory and numerics. 2 Preliminaries Modularity of undirected graph: Let G=(V,E) be an undirected graph, with vertex set V=\{v_{1},v_{2},\cdots,v_{n}\} and edge set E , and let A=(A_{ij})\in R^{n\times n} denote the adjacency matrix of G . The objective of community partitioning is to divide G into a set \mathbb{C}=\{C_{1},C_{2},\cdots,C_{k}\} of k communities, where \bigcup_{u=1}^{k}C_{u}=V , C_{i}\cap C_{j}=\emptyset for any i and j , and all C_{u} are nonempty. Let k_{i} denote the degree of vertex i , and K=(k_{1},k_{2},\cdots,k_{n})^{T} the degree vector. m=(\sum_{i}k_{i})/2 is thus the total number of edges in G . The modularity Q to evaluate the effect of a community partitioning S=(S_{iu})\in R^{n\times k} is defined as ( Newman & Girvan, 2004 ) : Q=\frac{1}{2m}\sum_{ij}\sum_{u}\left[A_{ij}-\frac{k_{i}k_{j}}{2m}\right]S_{iu}S_{ju}, (1) where A=(A_{ij}) is the adjacency matrix of G and S_{iu}=\begin{cases}1,\,\,\text{if }v_{i}\in C_{u}\\ 0,\,\,\text{otherwise}\end{cases}, (2) for each i=1,2,\cdots,n and u=1,2,\cdots,k . It can also be rewritten as follows ( Newman, 2006 ) : Q=\frac{1}{2m}\Tr\left(S^{T}BS\right), (3) where B=A-\frac{1}{2m}KK^{T} . Clearly, the modularity metric ( 1 ) measures the quality of a community partition by comparing the observed edge density within the identified communities to the expected density in a randomized network configuration model. A higher modularity score indicates that the identified communities are more distinct, exhibiting a significantly

Read the complete text