Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistance

Georgina Curto, Adrián Arnaiz-Rodríguez, Nuria OliverarXiv 2023 · DOI · arXiv

Abstract

Social networks contribute to the distribution of social capital, defined as the relationships, norms of trust and reciprocity within a community or society that facilitate cooperation and collective action. Therefore, better positioned members in a social network benefit from faster access to diverse information and higher influence on information dissemination. A variety of methods have been proposed in the literature to measure social capital at an individual level. However, there is a lack of methods to quantify social capital at a group level, which is particularly important when the groups are defined on the grounds of protected attributes. To fill this gap, we propose to measure the social capital of a group of nodes by means of the effective resistance and emphasize the importance of considering the entire network topology. Grounded in spectral graph theory, we introduce three effective resistance-based measures of group social capital, namely group isolation, group diameter and group control, where the groups are defined according to the value of a protected attribute. We denote the social capital disparity among different groups in a network as structural group unfairness, and propose to mitigate it by means of a budgeted edge augmentation heuristic that systematically increases the social capital of the most disadvantaged group. In experiments on real-world networks, we uncover significant levels of structural group unfairness when using gender as the protected attribute, with females being the most disadvantaged group in comparison to males. We also illustrate how our proposed edge augmentation approach is able to not only effectively mitigate the structural group unfairness but also increase the social capital of all groups in the network.

Introduction

In the digital age, an individual's position within a social network significantly influences their "social capital"—the resources, information, and influence accessible through social ties. While individual centrality measures like PageRank are well-established, there is a critical gap in quantifying social capital at the group level, particularly for groups defined by protected attributes such as gender or race. This paper introduces a framework to measure and mitigate "structural group unfairness," defined as the disparity in social capital between demographic groups.

Measuring Group Social Capital

The authors propose using Effective Resistance ($R_{uv}$) as a foundational metric. By modeling a network as an electrical circuit where edges represent resistors, effective resistance accounts for all possible paths between nodes, capturing the importance of redundant connections and "weak ties" that shortest-path metrics often overlook.

Three group-level metrics are introduced:

  1. Group Isolation ($R_{tot}$): The average effective resistance from a group to the rest of the network.
  2. Group Diameter ($\mathcal{R}_{diam}$): The maximum effective resistance within a group, representing the "worst-case" internal connectivity.
  3. Group Control ($B_R$): A measure of the group's criticality in facilitating information flow across the network.
Visualization of effective resistance-based metrics: group isolation ($R_{tot}$), group diameter ($\mathcal{R}_{diam}$), and group control ($B_R$).

Empirical Evidence of Structural Unfairness

The researchers analyzed three real-world social networks—Facebook, UNC28, and Google+—using gender as the protected attribute. The results consistently revealed significant structural disadvantages for females across all metrics.

Structural group unfairness in real-world social networks using gender as the protected attribute. Bold values indicate the group with higher social capital (lower isolation/diameter, higher control).

As shown in the table, females exhibit higher isolation ($R_{tot}$) and lower control ($B_R$) compared to males in every dataset. This empirical evidence underscores the systemic nature of group-level network inequality.

To address these disparities, the authors developed ERG-Link, a budgeted edge augmentation heuristic. Unlike simple strategies that connect nodes to popular hubs, ERG-Link identifies pairs of nodes with the highest effective resistance—effectively building "bridges" across the network's widest gaps.

By leveraging the Woodbury Matrix Identity, the algorithm efficiently updates effective resistance calculations, making it feasible for medium-sized networks. A key finding is that improving the standing of the most disadvantaged group often reduces the total effective resistance of the entire graph, suggesting that fairness interventions can enhance overall network efficiency.

Results and Discussion

In comparative evaluations, ERG-Link significantly outperformed baselines such as random edge addition or neighborhood similarity. It achieved isolation disparity reductions of 75% on Facebook and 87% on Google+. Furthermore, the algorithm demonstrated rapid convergence, reaching fair states with fewer added edges than competing methods.

While effective, the current approach faces scalability challenges for massive networks and relies on a greedy optimization strategy. Future work may explore global optimization techniques and incorporate node features to ensure that suggested links are socially plausible.

Conclusion

This work provides a rigorous mathematical framework for quantifying and mitigating structural group unfairness. By moving beyond myopic shortest-path metrics to the holistic perspective of effective resistance, we can begin to design social networks that distribute social capital more equitably, benefiting both marginalized groups and the network as a whole.

Summary updated

Abstract

Social networks contribute to the distribution of social capital, defined as the relationships, norms of trust and reciprocity within a community or society that facilitate cooperation and collective action. Therefore, better positioned members in a social network benefit from faster access to diverse information and higher influence on information dissemination. A variety of methods have been proposed in the literature to measure social capital at an individual level. However, there is a lack of methods to quantify social capital at a group level, which is particularly important when the groups are defined on the grounds of protected attributes. To fill this gap, we propose to measure the social capital of a group of nodes by means of the effective resistance and emphasize the importance of considering the entire network topology. Grounded in spectral graph theory, we introduce three effective resistance-based measures of group social capital, namely group isolation, group diameter and group control, where the groups are defined according to the value of a protected attribute. We denote the social capital disparity among different groups in a network as structural group unfairness, and propose to mitigate it by means of a budgeted edge augmentation heuristic that systematically increases the social capital of the most disadvantaged group. In experiments on real-world networks, we uncover significant levels of structural group unfairness when using gender as the protected attribute, with females being the most disadvantaged group in comparison to males. We also illustrate how our proposed edge augmentation approach is able to not only effectively mitigate the structural group unfairness but also increase the social capital of all groups in the network.
BibTeX
@misc{curto2023structural,
  author = {Georgina Curto and Adrián Arnaiz-Rodríguez and Nuria Oliver},
  title = {{Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistance}},
  year = {2023},
  eprint = {2305.03223},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.03223},
}
Figure