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

Adrian Arnaiz-Rodriguez<EMAIL_ADDRESS>ELLIS AlicanteSpain ,
Georgina Curto<EMAIL_ADDRESS>University of Notre DameNotre DameUSA and
Nuria Oliver<EMAIL_ADDRESS>ELLIS AlicanteSpain

(2024)

###### 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. Social capital
exists in the relations among individuals, such that 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. Furthermore, state-of-the-art approaches fail
to model the role of long-range interactions between nodes in the network and
their contributions to social capital. To fill this gap, we propose to measure
the social capital of a group of nodes by means of their information flow and
emphasize the importance of considering the whole 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.

††copyright: none††journalyear: 2024

##  1\. Introduction

Online social networks play an important role in defining and sustaining the
social fabric of human communities. With billions of users worldwide, they
allow individuals to connect, interact and share information with one another
over the internet. They have opened up new opportunities for personal and
professional networking, entertainment, learning and activism. However, the
formation of social networks —whether through organic growth or
recommendations— can create imbalances in network positions which condition
the access to resources and information (Ovadya and Thorburn, 2023). These
network inequalities have an impact on the social capital of its members,
which exists in the relations among individuals (Coleman, 1988). Better
positioned network members benefit from faster access to diverse information,
higher influence on information dissemination and more control of the
information flow (Burt, 2000, 2004; Granovetter, 1983; Gündoğdu et al., 2019;
Bashardoust et al., 2023). In practical terms, this means that individuals
with a strategic position in the network will have more influence over others,
and better access to information and opportunities regarding jobs, health,
education or finance.

Furthermore, link recommendation algorithms that pervade social media
platforms tend to connect similar users, contributing to the homophily and
clustering of the network (Zignani et al., 2014; Su et al., 2016). These
_filter bubbles_ limit the access to diverse individuals (Granovetter, 1983),
exacerbate the isolation and polarization of groups (Su et al., 2016;
Garimella et al., 2018; Del Vicario et al., 2016), reduce the opportunities of
innovation (Qiu and Hancock, 2007) and aggravate the perpetuation of societal
stereotypes (Iyer, 2021). In sum, the topology of the network can lead to a
vicious cycle where those who are disadvantaged accumulate fewer opportunities
to improve their social capital (Fish et al., 2019).

A variety of graph intervention methods have been proposed in the literature
to mitigate disparities in social capital at an individual level (Hohmann et
al., 2023; Bashardoust et al., 2023). However, there is a lack of methods that
consider such disparities at a group level, which is particularly relevant
when the groups correspond to socially vulnerable groups, i.e., those defined
on the grounds of sex, race, color, language, religion, political or other
opinion, national or social origin, association with a national minority,
property, birth or other (Council of Europe, 2010; United Nations, 1966).
Evaluating disparities at the group level provides a broader, systemic
perspective that allows for the identification of overarching structural
barriers or inequalities that may not be apparent when examining individual
experiences. Focusing on the group level also supports the development of
inclusive solutions at scale that benefit entire communities, promoting
equity, diversity and the inclusion of disadvantaged groups. We denote the
disparity in social capital among different groups in the network as
_structural group unfairness_.

Similar to Bashardoust et al. (2023), we consider a setting where each node in
the network is a source of unique information and, therefore, access to all
nodes is equally important. In this context, information flow is an integral
component of the social capital and a distance metric that quantifies total
information flow in the graph, considering high-order relations that expand
beyond the immediate neighbors, is of utmost importance. We propose using the
effective resistance to measure the overall information flow between pairs of
nodes, since it is a theoretically grounded continuous graph diffusion metric
that considers both _local_ and _global_ properties of the network’s topology
(Chung, 1997). In Section 3.1.2, we introduce three measures of group social
capital — _group isolation_ , _group diameter_ and _group control_ — based on
the effective resistance where the groups are defined according to the value
of their protected attribute of interest. Based on these measures of social
capital, we define three measures of structural group unfairness in Section
3.2, and frame the challenge of mitigating structural group unfairness as a
budgeted edge augmentation task in Section 3.3. This section also presents the
Effective Resistance Group Link (ERG-Link) algorithm, a greedy edge
augmentation algorithm that iteratively adds the edges to the graph to
increase the social capital of the most disadvantaged group. In experiments on
real-world networks, described in Section 4, we uncover significant levels of
structural group unfairness when using gender111Note that we follow the same
nomenclature for gender as that used in the analyzed datasets, which is a
binary variable with two values: male and female. as the protected attribute,
with females being the most disadvantaged group in comparison to males. We
also illustrate how our approach is able to not only mitigate structural group
unfairness, but also increase the social capital of all the groups in the
network.

In sum, the main contributions of our work are:
(1) We propose three effective resistance-based measures of group social
capital in social networks, namely _group isolation_ , _group diameter_ and
_group control_ ;
(2) We define _structural group unfairness_ as a disparity in the values of
such measures by different groups in the graph, where the groups are defined
according to the values of a protected attribute. This approach is
particularly relevant from a social perspective when the disadvantaged group
in the network corresponds to a vulnerable social group;
(3) We propose ERG-Link, an effective resistance-based greedy edge
augmentation algorithm that iteratively adds edges to the network to maximize
the social capital of the most disadvantaged _group_ ;
(4) In experiments on real-world networks, we uncover significant levels of
group structural unfairness when using gender as protected attribute, with
females being the most disadvantaged group in comparison to males. We also
illustrate how our approach is the most effective in reducing structural group
unfairness when compared to the baselines.

##  2\. Related Work

In this section, we provide an overview of the most relevant work in the
literature related to social capital, its measurement by means of
computational methods, fairness in graphs from the perspective of social
capital, and network interventions to mitigate unfairness.

##### Social capital

Social capital is as a multidimensional construct that has been extensively
studied in sociology, political science, economics, and more recently,
computational social science (Putnam, 2015). It is defined as the networks,
relationships, and norms of trust and reciprocity within a community or
society that facilitate cooperation and collective action (Coleman, 1988). In
simple terms, social capital is the value derived from connections between
people. It can be measured and analyzed both at an individual and collective
levels (Borgatti et al., 1998) and it has been characterized according to
different criteria. Some authors propose three main dimensions of social
capital, namely: structural, emphasizing the relationships among individuals,
organizations and communities; cognitive, focusing on the shared values, norms
and beliefs that bind members of a group or community; and relational,
highlighting the intensity and quality of relationships, including
reciprocity, trust and obligations among individuals (Nahapiet and Ghoshal,
1998). Others have proposed the distinction between bonding, bridging, and
linking social capital (Szreter and Woolcock, 2004). Bonding social capital
captures the aspects of “inward looking” communities that reinforce exclusive
identities and homogeneous groups (Coleman, 1988); bridging social capital
refers to “outward looking” networks across different groups that do not
necessarily share similar identities (Burt, 2004; Granovetter, 1983); and
linking social capital characterizes the trusting relationships and norms of
respect across power or authority gradients (Szreter, 2002; Woolcock et al.,
2001). The three forms are important for the well-being of individuals and
communities: bonding social capital contributes to social cohesion and
support; bridging social capital to mutual understanding, solidarity and
respect; and linking social capital to mobilize political resources and power.

##### Computational models of social capital

Network analysis offers a robust computational framework to examine and
quantify social capital (Wasserman and Faust, 1994; Burt, 2004; Coleman,
1988). We consider a setting where all the nodes in the network may be sources
of relevant information. As a consequence, access to all nodes —not just the
sources or seeds of information— is equally important. In this context,
_information flow_ is an integral component of the social capital, and a
variety of methods have been proposed to characterize it, mainly through two
concepts: centrality and criticality (Borgatti, 2005).

Centrality measures the relative importance or prominence of a node in the
network, quantifying its ability to reach the rest of nodes. Different
approaches have been proposed in the literature to measure centrality,
including the degree centrality, closeness, local clustering, the
assortativity coefficient (Newman, 2003; Borgatti et al., 2009), Katz
centrality (Katz, 1953) and PageRank (Page et al., 1998). Criticality reflects
the node’s level of influence or vulnerability within the network (Freeman,
1977; Tizghadam and Leon-Garcia, 2009). Nodes with high criticality are
essential, such that their failure or disruption can have significant
consequences, cascading effects or system-wide impact. Measures of criticality
include effective size (Burt, 2004), redundancy (Borgatti et al., 1998) and
shortest path betweenness (Jackson, 2019).

However, previously proposed methods are insufficient to accurately quantify
the overall information flow in the network for several reasons. First, they
model the distance between nodes as the shortest path distance (geodesic
distance (Newman, 2003)) which overlooks alternative routes and indirect
connections that may exist between distant nodes, thereby underestimating the
potential pathways for information diffusion, influence propagation
(Stephenson and Zelen, 1989; Bozzo and Franceschet, 2013) or resource
exchange. This myopic view can lead to oversimplified representations of
network dynamics, ignoring the interplay between weak ties, bridge nodes and
overlapping communities that facilitate connectivity and communication across
disparate components in the network. Second, most of the proposed approaches
only consider first-order —direct and local— relationships between nodes,
relying on small neighborhoods of the graph. As a result, they ignore higher-
order structural information (Agarwal et al., 2006), such as the global
properties of the network topology and long-range interactions between nodes,
which can lead to inaccurate insights on how information flows globally
(Rampášek et al., 2022). Third, popular approaches to model information flow
in a network, such as the Independent Cascade model (Kempe et al., 2003)
assume homogeneous, deterministic and instantaneous interactions between
neighboring nodes which might lead to inaccurate predictions, biased
estimations and misrepresentations of actual diffusion patterns observed in
complex networks (Tauch et al., 2015).

Conversely, graph diffusion metrics, such as the _effective resistance_
(Stephenson and Zelen, 1989; Klein and Randić, 1993), offer a principled
approach to quantifying distances and interactions between nodes within a
network, addressing the above limitations. The effective resistance accurately
captures not only short-range but also long-range relationships between nodes
(Chung, 1997) because it considers alternative pathways, including the network
dynamics, and quantifies connectivity between distant nodes. Therefore, it
constitutes a natural information distance metric between nodes in a graph
(Bozzo and Franceschet, 2013; Stephenson and Zelen, 1989). Previous work has
theoretically formulated measures of node centrality and criticality based on
effective resistances (Brandes and Fleischer, 2005; Tizghadam and Leon-Garcia,
2010; Bozzo and Franceschet, 2013; Newman, 2005), yet we are not aware of any
work that has modeled the social capital of a group of nodes by means of
effective resistance. From a practical perspective, the concept of effective
resistance has been used to measure polarization in social networks (Hohmann
et al., 2023) and to rank user-items relations in recommender systems (Fouss
et al., 2007). In this paper, we propose quantifying the social capital of a
group of nodes in the network by means of three measures derived from the
effective resistance: the group isolation, group diameter and group control,
explained in Section 3.1.2.

##### Fairness in graphs

Social status plays a role in defining the structure of a network (Campbell et
al., 1986; Ball and Newman, 2013) and a node’s position in a network is a form
of social capital (Burt, 2000; Coleman, 1988). Thus, there are structural
advantages in information flow depending on the position that a node occupies
in the network. In the field of social networks, prior work has stud fairness
from the perspective of disparities in access to information by differently
positioned nodes in the graph, particularly in the case of influence
maximization, i.e., when a single piece of information is spread in the
network (Wang et al., 2022; Saxena et al., 2022). However, there is a scarcity
of studies that model fairness considering that all the nodes are sources of
information and access to all the nodes is equally important (Bashardoust et
al., 2023). In this context and to the best of our knowledge, no previous
research has considered fairness in graphs from a group perspective, when the
groups are defined according to protected attributes —such as gender,
ethnicity, religion or socio-economic status. In this paper, we fill this gap
by defining, measuring and mitigating _structural group unfairness_ ,
understood as disparities in social capital between different groups and where
social capital is measured by information flow.

##### Network interventions to mitigate unfairness in graphs

Network interventions draw upon social network theory and structural analysis
to understand and address the underlying mechanisms of unfairness within
social networks. Interventions to mitigate structural unfairness in a network
may entail redesigning network structures (Santos et al., 2021; Hohmann et
al., 2023) or altering (adding and/or removing) edges (Tong et al., 2012;
Bashardoust et al., 2023) to eliminate discriminatory barriers, reduce
homophily, and foster diversity within the networks (Granovetter, 1983; Burt,
2004). These interventions aim to enhance connectivity, promote inclusivity,
and facilitate equitable access to resources, opportunities, and support
networks (Borgatti, 2005).

When aiming to improve the social capital in a network, edge augmentation
(i.e., adding edges) constitutes the natural intervention to mitigate
disparities (Bashardoust et al., 2023). Several edge augmentation strategies
have been proposed in the literature, such as connecting similar nodes to
improve bonding social capital (Zhang et al., 2011), linking nodes with the
highest product of eigenvector centralities (Tong et al., 2012) or creating
edges between the most disadvantaged nodes and the central node (Bashardoust
et al., 2023). However, these strategies are defined for individual notions of
social capital and they do not consider long-range interactions between nodes.
In our work, we focus on reducing the social capital disparities between
groups in the graph and we propose to measure the social capital by means of
the effective resistance, which is able to quantify both short- and long-range
interactions between nodes. We approach this objective by adding weak ties
(Granovetter, 1983) —i.e. ties that correspond to relationships that are not
within one node’s close-knit group (strong ties)— between the disadvantaged
group and the rest of the graph.

##  3\. Measuring structural group unfairness in a network

In this section, we first present the distance metric that quantifies the
information flow between pairs of nodes in a social network and provides the
theoretical basis for the proposed measures of group social capital. Next, we
introduce three measures to quantify the social capital of a group of nodes in
a graph and present the concept of structural group unfairness as the
disparity in the measures by different groups in the graph. Finally, we
describe a greedy graph intervention (edge augmentation) algorithm to mitigate
structural group unfairness.

###  3.1. Preliminaries

####  3.1.1. Effective resistance and social capital

We focus on the structural dimension of social capital, which emphasizes the
relationships among individuals, organizations and communities (Nahapiet and
Ghoshal, 1998), and propose to measure it as the information flow of a node in
the network. Such a measure is captured by the _effective resistance_ (Doyle
and Snell, 1984; Klein and Randić, 1993; Tetali, 1991) of the node. Given
nodes $u$ and $v$ in graph $G=\\{\mathcal{V,E}\\}$, where $\mathcal{V}$ is the
set of nodes,
${\mathcal{E}=\\{(u,v)\in\mathcal{V}\times\mathcal{V}:A_{uv}=1\\}}$ is the set
of edges and $\mathbf{A}$ is the graph’s adjacency matrix, the effective
resistance $R_{uv}$ between nodes $u$ and $v$ is a distance metric given by:

(1) $\displaystyle
R_{uv}=(\mathbf{e}_{u}-\mathbf{e}_{v})\mathbf{L}^{\dagger}(\mathbf{e}_{u}-\mathbf{e}_{v})^{\top},$

where $\mathbf{e}_{u}$ is the unit vector with a unit value at $u$-th index
and zero elsewhere;
$\mathbf{L}^{\dagger}=\sum_{i>1}\frac{1}{\lambda_{i}}\phi\phi^{\top}$ is the
pseudo-inverse of the graph’s Laplacian
$\mathbf{L}=\mathbf{D}-\mathbf{A}=\mathbf{\Phi\Lambda\Phi}^{\top}$, with
$\mathbf{D}$ the graph’s degree matrix, $D_{u,u}=\sum_{j\in V}A_{u,v}$ and 0
elsewhere; and $\lambda_{i}$ the $i$-th smallest eigenvalue of $\mathbf{L}$
corresponding to the $\phi_{i}$ eigenvector. The complete matrix of all
pairwise effective resistances in a graph, $\mathbf{R}$ is given by
$\mathbf{R}=\mathbf{1}\operatorname{diag}(\mathbf{L}^{\dagger})^{\top}+\operatorname{diag}(\mathbf{L}^{\dagger})\mathbf{1}^{\top}-2\mathbf{L}^{\dagger}$.

The effective resistance is a distance _metric_ since it satisfies the
symmetry, non-negativity and triangle inequality conditions (Ellens et al.,
2011). In addition, $R_{uv}$ is proportional to the commute times between $u$
and $v$, i.e., the expected number of steps in a random walk starting at $v$
to reach node $u$ and come back:
$R_{uv}\propto\mathbb{E}_{u}[v]+\mathbb{E}_{v}[u]$, where $\mathbb{E}_{u}[v]$,
$\mathbb{E}_{v}[u]$ are the expected number of steps that a random walker
takes to go from $u$ to $v$ and from $v$ to $u$, respectively (Chandra et al.,
1989; Tetali, 1991; Fouss et al., 2007, 2005; Qiu and Hancock, 2007). A high
value of $R_{uv}$ means that $u$ and $v$ generally struggle to visit each
other in a random walk, i.e., nodes with high effective resistance between
them are unlikely to exchange information. $R_{u,v}$ can be expressed as

$R_{u,v}=\sum_{i=0}^{\infty}\left(d_{u}^{-1}(\mathbf{A}^{i})_{uu}+d_{v}^{-1}(\mathbf{A}^{i})_{vv}-(d_{u}d_{v})^{-1/2}2(\mathbf{A}^{i})_{uu}\right),$

being $\mathbf{A}^{k}$ the matrix that defines the number paths of length $k$
between $u$ and $v$ (Black et al., 2023). Hence, it is able to capture both
short- and long-range interactions between nodes in the graph.

The effective resistance has been characterized as the _information distance_
in a network (Klein and Randić, 1993; Stephenson and Zelen, 1989; Bozzo and
Franceschet, 2013; Tetali, 1991) as it quantifies the amount of effort
(distance) required to transmit information between the nodes. The total
effective resistance $\operatorname{\mathsf{R_{tot}}}$ of a graph (Ellens et
al., 2011) – defined as the sum of all $R_{uv}$
($\operatorname{\mathsf{R_{tot}}}=\mathbf{1R}\mathbf{1}^{\top}$) – is
therefore inversely proportional to the expected ease of information flow in
the graph.

The total effective resistance of node $u$,
$\operatorname{\mathsf{R_{tot}}}(u)$, is given by
$\operatorname{\mathsf{R_{tot}}}(u)=\sum_{v\in\mathcal{V}}R_{uv}$, i.e., the
sum of all the effective resistances between node $u$ and the rest of nodes in
the network. Given that the effective resistance is an information distance,
the smaller the total effective resistance of a node, the larger its
information flow. In other words, the effective resistance allows to identify
which nodes in a graph have limited information flow (i.e., high effective
resistance) and thus low social capital (Ellens et al., 2011; Ghosh et al.,
2008). Equivalent terms to denote the effective resistance in the literature
include the current-flow closeness centrality (Brandes and Fleischer, 2005;
Newman, 2003) and the information centrality (Stephenson and Zelen, 1989).

From a computational perspective, calculating $R_{uv}$ does not require hyper-
parameter tuning and can be efficiently calculated, mitigating two significant
drawbacks of other diffusion or learnable graph distances (Perozzi et al.,
2014). An overview of the theoretical properties of $R_{uv}$ are provided in
Appendix B.

####  3.1.2. Effective-resistance-based measures of group social capital

Based on the definition of effective resistance above, we propose three
metrics that characterize the social capital of a group of nodes in a graph.
The metrics are computed based on pairwise effective resistances between the
nodes in the group and the rest of nodes the graph, which are then aggregated
to all members of the group to quantify its social capital. Each of the
proposed metrics is based on theoretical principles derived from effective
resistance, as explained in the previous section and in Section B.3. In the
following, we refer to a group of nodes $S_{i}$ in graph
$G=\\{\mathcal{V,E}\\}$ as a subset of $\mathcal{V}$, i.e.,
$S_{i}\subseteq\mathcal{V}$ with $|S_{i}|$ nodes.

##### 1\. Group Isolation

The isolation of a group $S_{i}$, $\operatorname{\mathsf{R_{tot}}}(S_{i})$, is
given by the average of the total effective resistances of all the nodes in
group. $\operatorname{\mathsf{R_{tot}}}(S_{i})$ is proportional to the
expected information distance when sampling one node from group $S_{i}$ and
another node at random. It can be interpreted as a proxy for the
marginalization of a group from the perspective of information flow, such that
the lower the $\operatorname{\mathsf{R_{tot}}}(S_{i})$, the less isolated the
group $S_{i}$ is in the network. Therefore, reducing this measure for group
$S_{i}$ would yield an increase in its social capital. It is given by:

(2) $\operatorname{\mathsf{R_{tot}}}(S_{i})=\mathbb{E}_{u\sim
S_{i}}[R_{tot}(u)]=\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\operatorname{\mathsf{R_{tot}}}(u)=|\mathcal{V}|\mathbb{E}_{u\sim
S_{i},v\sim\mathcal{V}}\left[R_{uv}\right]$

where $\operatorname{\mathsf{R_{tot}}}(u)=\sum_{v\in\mathcal{V}}R_{uv}$ is the
total effective resistance of node $u$, $\mathcal{V}$ is the set of all nodes
in the graph, and $S_{i}$ is group of interest. The normalization factor
enables comparing groups of different sizes. Note that adding links between
nodes with the highest $R_{uv}$ —irrespective of which group they belong to—
has been found to reduce the total effective resistance of a graph (Ghosh et
al., 2008; Black et al., 2023) and hence the isolation of all the graph’s
nodes.

##### 2\. Group Diameter

The group diameter, $\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})$,
measures the average of the maximum distance between any node in group $S_{i}$
and any node in the graph. A larger group diameter suggests that the nodes in
group $S_{i}$ are distant from the rest of the graph, indicating potential
challenges in information exchange with the nodes outside of $S_{i}$, and
hence it can be interpreted as another measure of social capital.

This measure is based on $\operatorname{\mathcal{R}_{\text{diam}}}(G)$, which
is the maximum effective resistance of the graph (Qiu and Hancock, 2007).

(3) $\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})=\mathbb{E}_{u\sim
S_{i}}[\operatorname{\mathcal{R}_{\text{diam}}}(u)]=\mathbb{E}_{u\sim
S_{i}}[\max_{v\in\mathcal{V}}R_{uv}]$

where
$\operatorname{\mathcal{R}_{\text{diam}}}(u)=\max_{v\in\mathcal{V}}R_{uv}$ is
the diameter of node $u$, i.e., the maximum $R_{uv}$ from $u$ to any other
node in the graph. $\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})$ gives an
indication of the information flow gap between the group $S_{i}$ and the rest
of the network (Fish et al., 2019). Therefore, the larger the
$\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})$, the lower the social
capital of group $S_{i}$.

##### 3\. Group Control

The aforementioned concepts measure the amount of information flow in a group
of nodes in the graph. Another relevant variable to assess is the criticality
of a node for the diffusion of information in the graph, which in the
literature has been measured as betweenness (Freeman, 1977), redundancy
(Borgatti et al., 1998) or effective size (Burt, 2004). Nodes with high levels
of control serve as important connectors in the network, facilitating the flow
of information and enabling communication between otherwise disconnected
groups of nodes (Burt, 2004).

The control of a node can be computed by restricting the summation of a node’s
total effective resistance to the nodes that are directly linked to it (i.e.,
its direct neighbors). Thus, it is expressed as
$\operatorname{\mathsf{B_{R}}}(u)=\sum_{v\in\mathcal{N}(u)}R_{uv}$, where
$\mathcal{N}(u)=\\{v:(u,v)\in\mathcal{E}\\}$ are the neighbors of $u$. The
larger the $\operatorname{\mathsf{B_{R}}}(u)$, the more control a node has in
the network’s information flow and hence the larger its social capital. The
node control of a node is bounded by
$1\leq\operatorname{\mathsf{B_{R}}}(u)\leq d_{u}$, being $d_{u}$ the number of
neighbors of node $u$ (see Theorem C.1). $\operatorname{\mathsf{B_{R}}}(u)$ is
theoretically related to the current-flow betweenness (Brandes and Fleischer,
2005; Tizghadam and Leon-Garcia, 2009, 2010; Newman, 2005), the node’s
information bottleneck (Arnaiz-Rodríguez et al., 2022), and the curvature of
the node (Devriendt and Lambiotte, 2022; Topping et al., 2022).

We define the group control or group betweenness
$\operatorname{\mathsf{B_{R}}}(S_{i})$ as the average of the controls of all
the nodes in $S_{i}$, _i.e._ :

(4) $\operatorname{\mathsf{B_{R}}}(S_{i})=\mathbb{E}_{u\sim
S_{i}}[\operatorname{\mathsf{B_{R}}}(u)]=\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\operatorname{\mathsf{B_{R}}}(u),$

and is bounded by
$1\leq\operatorname{\mathsf{B_{R}}}(S_{i})\leq\text{vol}(S_{i})/|S_{i}|$,
being $\text{vol}(S_{i})/|S_{i}|$ the average degree of the group $S_{i}$ (see
Theorem C.2). Note that the sum of all $R_{uv}$ for all nodes in a graph is
constant at $|\mathcal{V}|-1$ and it is independent of the number of edges
(Klein and Randić, 1993). If an edge is added, removed or modified in the
graph, all $R_{uv}$ are updated accordingly such that their sum remains
constant. The sum and the average control of all nodes in the graph are also
constant with values
$\sum_{u\in\mathcal{V}}\operatorname{\mathsf{B_{R}}}(u)=2|V|-2$ and
$\mathbb{E}_{u\sim\mathcal{V}}[\operatorname{\mathsf{B_{R}}}(u)]=2-\frac{2}{|\mathcal{V}|}$,
respectively, independently of the number of edges (see Section C.1.2 for more
details). Consequently, the control of a node or group of nodes is distributed
among the nodes in the network and cannot be optimized for every node/group in
the graph by adding more edges: if a node or group of nodes increase their
control over the information flow in the graph, they must do so at the cost of
reducing the control of other nodes.

###  3.2. Structural group unfairness

To study disparities in the distribution of social capital in the network, we
define the groups of nodes $S_{i}$ according to their values of a sensitive
attribute $i\in SA=\\{sa_{1},sa_{2},\dots,sa_{|SA|}\\}$, which is a
categorical variable with $|SA|$ possible values that refer to a socially
relevant concept, such as sex, age, gender, religion or race. We denote the
value of the sensitive attribute of a node $v$ as $SA(v)$. For instance, if
$SA$ is sex with three possible values, $SA$={male, female, non-binary}, the
groups $S_{\text{male}}$, $S_{\text{female}}$ and $S_{\text{non-binary}}$ are
the set of nodes whose sex is labeled as male, female and non-binary,
respectively.

We define the _structural group unfairness_ in a network as the disparity in
information flow between the nodes belonging to different groups in the
network. Since we have defined the groups in terms of protected attributes,
structural group unfairness becomes particularly relevant because it informs
about potential disparities in information flow (and hence social capital)
between a vulnerable group –e.g. females– and the rest of the network. We
present here three metrics to characterize the structural group unfairness,
namely isolation disparity, diameter disparity and control disparity.

##### 1\. Group Isolation Disparity

Ideally, every group in the network should have the same levels of information
flow and hence the same —and low— levels of group isolation, namely:

(5)
$\operatorname{\mathsf{R_{tot}}}(S_{i})=\operatorname{\mathsf{R_{tot}}}(S_{j}),\>\forall\>i,j\in
SA.$

Deviations from equality lead to isolation disparity
$\Delta\operatorname{\mathsf{R_{tot}}}$, which is defined as the maximum over
all groups in the graph of the differences in group isolation:
$\Delta\operatorname{\mathsf{R_{tot}}}=\max_{i,j\in
SA}(\operatorname{\mathsf{R_{tot}}}(S_{i})-\operatorname{\mathsf{R_{tot}}}(S_{j}))$.

Reducing the isolation disparity contributes to increasing the social capital
of the most disadvantaged group and equalizes the information flow between the
groups in the network.

##### 2\. Group Diameter Disparity

Ideally, every social group in the network should have the same –and low–
group diameter:

(6)
$\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})=\operatorname{\mathcal{R}_{\text{diam}}}(S_{j}),\>\forall\>i,j\in
SA.$

Any deviations from equality lead to diameter disparity,
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$, defined as the maximum over
all groups in the graph of the differences in group diameter:
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}=\max_{i,j\in
SA}(\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})-\operatorname{\mathcal{R}_{\text{diam}}}(S_{j}))$.

Achieving equal diameter entails equalizing the worst-case scenario in
information flowing to the entire network from the perspective of any group of
nodes in the graph. By promoting equal group diameter, we generate a fairer
information-sharing environment.

##### 3\. Group Control Disparity

By striving for equalized control in all groups in the network, no particular
group would dominate or be marginalized from the perspective of their control
of information in the network:

(7)
$\operatorname{\mathsf{B_{R}}}(S_{i})=\operatorname{\mathsf{B_{R}}}(S_{j})=2-\frac{2}{|\mathcal{V}|},\>\forall\>i,j\in
SA.$

Any deviations from equality lead to control disparity,
$\Delta\operatorname{\mathsf{B_{R}}}$, defined as the maximum over all groups
in the graph of the differences in group control:
$\Delta\operatorname{\mathsf{B_{R}}}=\max_{i,j\in
SA}(\operatorname{\mathsf{B_{R}}}(S_{i})-\operatorname{\mathsf{B_{R}}}(S_{j}))$.

As previously explained, control is a bounded resource to be distributed among
the groups of nodes in the graph with an expected value of
$2-\frac{2}{|\mathcal{V}|}$. Hence, reducing the control disparity entails a
redistribution of the control in all the groups in the graph converging to
$\operatorname{\mathsf{B_{R}}}(S_{i})=2-\frac{2}{|\mathcal{V}|},\>\forall\>i\in
SA$, leading to a more equitable allocation of the control that different
groups play regarding the information flow in the network.

###  3.3. Edge augmentation to mitigate structural group unfairness

##### Edge augmentation

Edge augmentation is the natural intervention to mitigate information flow
disparities in a network where all nodes are sources of unique pieces of
information (Burt, 2004; Bashardoust et al., 2023).

Regarding which structural group unfairness measure we should aim to optimize,
we argue that we should primarily focus on improving the isolation disparity
of the most isolated group in the graph. Note that mitigating isolation will
also yield an improvement in the diameter and control disparities, as
illustrated in our experiments. The reduction in isolation entails creating
edges between distant nodes, i.e., fostering the creation of weak ties.
Granovetter (1983)’s work provides evidence that information spreads more
effectively through weak ties than through strong ties: weak ties give
peripheral nodes more visibility in the network, which leads to a decrease in
group isolation and diameter. Adding weak ties reduces discontinuities in the
information flow, increases redundancies in the paths between nodes and
improves the control of peripheral nodes while reducing the control of
dominant ones (Burt, 2004).

Previous work has suggested connecting peripheral isolated nodes (with low
centrality and control) to salient nodes (with high centrality and control)
(Tong et al., 2012; Jackson, 2019; Bashardoust et al., 2023). However, these
solutions lead to a rich-get-richer phenomenon that benefits the best
connected nodes and potentially increases the disparities in information
access (Burt, 1999). Hence, we advocate for the creation of edges between the
most distant nodes in the network (weak ties) without necessarily connecting
them with a central node.

##### Problem definition

We consider a budgeted edge augmentation intervention: given a maximum number
$B$ of allowed new connections to be created in the graph, we aim to identify
the $B$ new edges $\mathcal{E}^{\prime}$ to be added to the graph $G$ that
would maximally reduce the group isolation disparity of the most disadvantaged
group in the graph. This leads to a new graph $G^{\prime}$ with lower levels
of structural group unfairness:

(8) $\displaystyle G^{\prime}=\min_{G^{\prime}=\mathcal{(V,E^{\prime})}}$
$\displaystyle\mathbb{E}_{u,v\thicksim V\times V}\left[R_{uv}\right]$ s.t.
$\displaystyle|\mathcal{E}^{\prime}\setminus\mathcal{E}|=B$
$\displaystyle\mathcal{E}\subset\mathcal{E}^{\prime}$

Figure 1. Illustration of the impact of adding one edge on the information
flow of $G$. The color denotes information distances (effective resistances)
w.r.t. to the star node. The histogram shows the change of all
$R_{u,v}^{\prime}s$ in $G$. Note how all $R_{u,v}^{\prime}s$ between the star
node and the rest of nodes in the network ($R_{\bigstar,v}$) decrease in
$G^{\prime}$ even if there is no change in the geodesic distance between them.

Illustration of the impact of adding one edge on the information flow of $G$.

##### Algorithm

To tackle the problem above, we introduce ERG-Link, a greedy algorithm that
adds edges between the nodes with the largest effective resistance between
them, where at least one of the nodes belongs to the most isolated group as
per Section 3.1.2, and groups in the graph are defined in the grounds of a
protected attribute. Note that this strategy also reduces the isolation (total
effective resistance) of the entire graph (Ghosh et al., 2008).

Algorithm 1 outlines the main steps of ERG-Link. Given a graph $G=(V,E)$, a
protected attribute $S$ and a total budget $B$ of new edges to add, the group
isolation $R_{tot}(S)$ is computed for each group according to $S$. The most
disadvantaged group $S_{d}$ is identified as the group with largest
$R_{tot}(S)$. Then, the $R_{uv}$ $\forall(u,v)\in\mathcal{V}\times\mathcal{V}$
is computed, and a ranking of all potential new edges in the graph is created
from the highest to the lowest values of effective resistance. In each
iteration, ERG-Link adds the new edge to the graph that yields the largest
improvement in the information flow of $S_{d}$, i.e., the edge that connects
the two nodes with largest effective resistance between them where at least
one of the nodes belongs to $S_{d}$. See Ghosh et al. (2008); Black et al.
(2023) for a proof that such an edge is the one that maximally improves the
information flow in the graph.

Data: Graph $G=(\mathcal{V},\mathcal{E})$, a protected attribute $SA$, budget
$B$ of total number of edges to add

Result: New Graph $G^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$
with $B$ new edges

1

2$\mathbf{L}=\mathbf{D}-\mathbf{A}$;

$S_{d}=\operatorname*{argmax}_{S_{i}\forall i\in
SA}\operatorname{\mathsf{R_{tot}}}(S_{i})$ ;

// Identify the most disadvantaged group

3

4Repeat

5
$\mathbf{L}^{\dagger}=\sum_{i>0}\frac{1}{\lambda_{i}}\phi_{i}\phi_{i}^{\top}=\left(\mathbf{L}+\frac{\mathbf{1}\mathbf{1}^{\top}}{n}\right)^{-1}-\frac{\mathbf{1}\mathbf{1}^{\top}}{n}$;

$\mathbf{R}=\mathbf{1}\operatorname{diag}(\mathbf{L}^{\dagger})^{\top}+\operatorname{diag}(\mathbf{L}^{\dagger})\mathbf{1}^{\top}-2\mathbf{L}^{\dagger}$
;

// Compute effective resistance

$C=\\{(u,v)\mid u\in S_{d}\text{ or }v\in
S_{d},(u,v)\notin\mathcal{E}^{\prime}\\}$ ;

// Select edge candidates

$\mathcal{E}^{\prime}=\mathcal{E}^{\prime}\cup\arg\max_{(u,v)\in C}R_{uv}$ ;

// Add edge with maximum effective resistance from $C$

$\mathbf{L}=\mathbf{L}+(\mathbf{e}_{u}-\mathbf{e}_{v})(\mathbf{e}_{u}-\mathbf{e}_{v})^{\top}$;

// Fast update of $\mathbf{L}$

6

7Until  _$|\mathcal{E^{\prime}}\setminus\mathcal{E}|=B$_ ;

8return $G^{\prime}$;

Algorithm 1 ERG-Link

ERG-Link leverages _Rayleigh’s monotonicity principle_ (Doyle and Snell, 1984;
Ellens et al., 2011), according to which the total effective resistance of a
graph can only decrease when new edges are added to it, as illustrated in Fig.
1. The new edges that most highly reduce both the graph’s total and maximum
effective resistances are those that connect the two nodes with the largest
effective resistance between them (Ghosh et al., 2008; Black et al., 2023; Qiu
and Hancock, 2007; Arnaiz-Rodríguez et al., 2022). Therefore, creating an edge
between nodes with maximum $R_{uv}$ not only improves the information flow
between the two nodes (increasing their social capital) but it also improves
the information flow of the entire graph.

Note that the addition of each new edge changes all the pairwise information
distances between nodes in the graph, requiring the re-computation of all
distances (effective resistances) in each iteration. Therefore, this type of
edge augmentation is not feasible by means of Independent Cascade distance
estimation (Bashardoust et al., 2023; Kempe et al., 2003), random-walk
embeddings (Perozzi et al., 2014) or graph neural networks (Kipf and Welling,
2016; Wu et al., 2022). These methods require training expensive neural
networks or running complex simulations for the estimation of the distances in
each iteration. In addition, they only capture short-range interactions
between nodes. Conversely, the effective resistance captures both short and
long-range interactions between nodes in the graph and it is efficient to
update. While it requires the computation of the Laplacian pseudo-inverse,
Woodbury’s formula (Black et al., 2023) can be used to avoid recomputing
$\mathbf{L}^{\dagger}$ in line 3 of Algorithm 1, as reflected in Algorithm 2.

##  4\. Experiments

###  4.1. Datasets and set-up

Table 1. Group social capital in the original graphs. Group with the largest social capital is highlighted in bold. $G$ | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}\uparrow$
---|---|---|---
Facebook (female) | 221.4 | 2.29 | 1.93
Facebook (male) | 179.8 | 2.25 | 2.03
UNC28 (female) | 608.6 | 2.11 | 1.99
4051 |  |  |
UNC28 (male) | 586.3 | 2.11 | 2.00
| 5.14 | 3767 |
Google+ (female) | 564.1 | 1.31 | 1.81
Google+ (male) | 287.7 | 1.24 | 2.32
Table 2. Structural group unfairness before and after the graph interventions.

(a) Facebook ($B$=50)

| $\Delta\operatorname{\mathsf{R_{tot}}}$ | $\Delta\operatorname{\mathcal{R}_{\text{diam}}}$ | $\Delta\operatorname{\mathsf{B_{R}}}$
---|---|---|---
$G$ (original) | 41.62 | 0.042 | 0.107
Random | 38.7 | 0.039 | 0.108
DW | 36.3 | 0.031 | 0.104
Cos | 28.7 | 0.029 | 0.120
ERG | 10.3 | 0.009 | 0.098
S-DW | 43.6 | 0.041 | 0.103
S-Cos | 41.4 | 0.042 | 0.105
S-ERG | 41.6 | 0.042 | 0.107

(b) UNC28 ($B$=5000)

| $\Delta\operatorname{\mathsf{R_{tot}}}$ | $\Delta\operatorname{\mathcal{R}_{\text{diam}}}$ | $\Delta\operatorname{\mathsf{B_{R}}}$
---|---|---|---
$G$ (original) | 22.4 | 0.006 | 0.009
Random | 19.8 | 0.005 | 0.014
DW | 22.2 | 0.006 | 0.004
Cos | 19.1 | 0.005 | 0.102
ERG | 8.8 | 0.002 | 0.003
S-DW | 20.6 | 0.006 | 0.008
S-Cos | 22.1 | 0.006 | 0.019
S-ERG | 22.3 | 0.006 | 0.004

(c) Google+ ($B$=5000)

| $\Delta\operatorname{\mathsf{R_{tot}}}$ | $\Delta\operatorname{\mathcal{R}_{\text{diam}}}$ | $\Delta\operatorname{\mathsf{B_{R}}}$
---|---|---|---
$G$ (original) | 276.4 | 0.078 | 0.51
Random | 129.4 | 0.037 | 0.47
DW | 274.1 | 0.078 | 0.51
Cos | 86.8 | 0.025 | 0.47
ERG | 37.1 | 0.011 | 0.29
S-DW | 272.5 | 0.078 | 0.49
S-Cos | 236.0 | 0.067 | 0.47
S-ERG | 276.4 | 0.079 | 0.52

To empirically evaluate ERG-Link, we tackle the challenge of mitigating
structural group unfairness in three real-world networks (school and online
social networks), where the nodes are users and the edges correspond to
connections between them, i.e., friendships. The three datasets are commonly
used in the graph fairness literature, namely:
(1) The Facebook dataset (Leskovec and Mcauley, 2012), a dense graph of 1,034
Facebook users ($|\mathcal{V}|$) and 26,749 edges ($|\mathcal{E}|$). It
corresponds to a large ego-network where nodes are connected if they are
friends in the social network;
(2) The UNC28 dataset (Red et al., 2011), consisting of a 2005 snapshot from
the Facebook network of the university of North Carolina
($|\mathcal{V}|$=3985, $|\mathcal{E}|$=65287);
(3) The Google+ dataset (Leskovec and Mcauley, 2012), an ego-network of G+,
the social network developed by Google, with 3,508 nodes ($|\mathcal{V}|$) and
25,3930 edges ($|\mathcal{E}|$).

Gender is the protected attribute in all networks with two possible values
$SA=${male, female}. We select the largest connected component for all the
datasets.

The original values of group social capital per gender are depicted in Table
1. As seen in the Table, our study unveils that the disadvantaged group
according to the three defined measures (group isolation, group diameter and
group control) corresponds to females in the three datasets. Hence,
${S_{d}=S_{female}}$.

In contrast, group extensions of traditional individual social capital metrics
fail to model long-range interactions between nodes and hence are unable to
uncover the extent of social capital disparities between groups. For example,
in the Google+ dataset, females are 49% more isolated than men according to
our proposed group isolation ($\operatorname{\mathsf{R_{tot}}}$) metric (564.1
vs 287.7 for females vs males). However, they are only 7% more isolated (8,073
vs 7,477 for females vs males) when using the geodesic distance and a
traditional farness centrality measure (Sabidussi, 1966). Furthermore,
according to the commonly used betweenness measure (number of shortest paths
through a node) (Freeman, 1977) on the UNC28 dataset, males —as opposed to
females— are the disadvantaged group with 7% less control than females (3,767
vs 4,051).

###  4.2. Baselines

We compare edge augmentation by means of ERG-Link with three baselines:
(1) Random: an algorithm that adds edges at random to the graph.
(2) DW: an algorithm that adds edges using the dot product similarity of
_DeepWalk_ (Perozzi et al., 2014) embeddings as a distance between nodes. It
is based on sampling random walks and training a BERT model to compute each
node’s embedding. Results correspond to the following hyper-parameters: 128
embedding dimension, 40 walk length, and 10 window size;
(3) Cos: a greedy algorithm that adds edges using the cosine similarity of the
rows of the adjacency matrix (Saxena et al., 2022) as a distance between
nodes. This is an example of a classic method based on neighborhood
similarity.

All the baselines correspond to an algorithm similar to Algorithm 1 (lines 2
and 6 remain the same) with one difference: instead of using the effective
resistances to quantify the distances between nodes, the baselines consider
cosine or DW distances. Note that we do not include any GNN-based method as a
baseline because they require training a neural network to estimate the
pairwise distances in the graph. This is computationally unfeasible in our
task as it would entail retraining the neural network every time a new edge is
added (Wu et al., 2022).

###  4.3. Experimental methodology

We set a budget $B$ of a maximum of 5,000 new links to be added to the the
UNC28 and Google+ datasets, which corresponds to approximately 0.05% of the
number of all potential edges in the graph. We also run experiments with a
maximum of 50 new edges for the Facebook dataset to showcase that even with an
extremely low budget, ERG-Link is able to significantly improve the social
capital of the disadvantaged group and reduce the structural unfairness in the
graph. We compute the social capital for each group (male and female) and the
structural group unfairness on both the original and the augmented graphs
(after all edges have been added) based on the defined measures. We also
compute them at each step of edge addition to shed light on the evolution of
the structural group unfairness as new edges are added.

(a) Facebook

(b) UNC28

(c) Google+

Figure 2. Pareto front of the structural group unfairness (X-axis) vs the sum
of the group social capital of all the groups (Y-axis) using
$\operatorname{\mathsf{R_{tot}}}$ on the top row and
$\operatorname{\mathcal{R}_{\text{diam}}}$ on the bottom row. From left to
right: Facebook, UNC28 and Google+ datasets.

Pareto front of the structural group unfairness (X-axis) vs the sum of the
group social capital of all the groups (Y-axis) using
$\operatorname{\mathsf{R_{tot}}}$ on the top row and
$\operatorname{\mathcal{R}_{\text{diam}}}$ on the bottom row.

###  4.4. Structural group unfairness mitigation

Table 2 depicts the three structural group unfairness measures on the original
graph $G$ and after adding 50 edges to the Facebook dataset and 5,000 edges to
the UNC28 and Google+ datasets. The groups are defined based on gender (male,
female) and the disadvantaged group are females according to the three
structural group unfairness measures, as depicted in Table 1 and top row of
Table 2. The disparities in social capital between males and females are
particularly large in the Google+ network with a
$\Delta\operatorname{\mathsf{R_{tot}}}$ of 276.4, meaning that females have
significantly lower levels of information flow than males in this network.
$\Delta\operatorname{\mathsf{B_{R}}}$ also shows a difference of 0.51 on the
control of the network, which is a large difference given that the values of
$\operatorname{\mathsf{B_{R}}}$ are in the range $[0,2-2/|\mathcal{V}|]$.

Regarding the results of the graph intervention algorithms, we observe how
edge augmentation via ERG-Link outperforms all the baseline methods on the
three datasets in terms of reducing structural group unfairness.
Interestingly, the larger the unfairness in the original graph, the larger the
improvement after the intervention with ERG-Link. For example, in the case of
isolation disparity, $\Delta\operatorname{\mathsf{R_{tot}}}$, the original
values of 22.4, 41.62 and 276.4 improve by 60%, 75% and 87% after ERG-Link’s
intervention in the UNC28, Facebook and Google+ networks, respectively. A
similar behavior is observed for the other structural group unfairness
measures.

For illustration purposes, we also report results of the three versions of
Algorithm 1 using the three distances (DeepWalk, cosine and effective
resistance) but where the added edges connect the nodes with the smallest
—instead of the largest— pairwise distance, similar to how link recommendation
algorithms work. We refer to these methods as the “Strong” version (for strong
ties) and hence denote them with an “S-” before the abbreviation. The bottom
part of Table 2 contains the results of edge augmentation with these
variations. As expected, edge augmentation in this case does not significantly
improve the structural group unfairness since such methods are not designed to
improve the information flow in the most isolated nodes in the graph, but to
connect nodes that are already structurally close to each other (foster strong
ties).

Note how the edge augmentations when using DW and Cos distances still yield
graphs with significant levels of structural group unfairness. Furthermore, in
the case of using DW distances, the improvement in performance worsens as the
graph gets larger (Google+). While using Cos distance for edge augmentation
improves $\Delta\operatorname{\mathsf{R_{tot}}}$ and
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$, it is unable to always
improve $\Delta\operatorname{\mathsf{B_{R}}}$ due to the inherently more
intricate nature of control disparity optimization. Unlike
$\Delta\operatorname{\mathsf{R_{tot}}}$ and
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$, minimizing
$\Delta\operatorname{\mathsf{B_{R}}}$ requires the precise identification of
network gaps which are difficult to detect using a cosine similarity distance.
For completeness, the social capital metrics for each group (males and
females) in the three data sets are shown in Table 4 in Section D.1. Note how
females always have lower values of social capital
($\operatorname{\mathsf{R_{tot}}}$, $\operatorname{\mathcal{R}_{\text{diam}}}$
and $\operatorname{\mathsf{B_{R}}}$) than males, even after the graph
interventions.

###  4.5. Overall social capital improvement

In this section, we illustrate how edge augmentation via ERG-Link is more
effective than the baseline methods not only to reduce the structural group
unfairness ($\Delta\operatorname{\mathsf{R_{tot}}}$ and
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$), but also to improve the
overall social capital measures of group isolation $R_{tot}(S_{i})$ and group
diameter $R_{diam}(S_{i})$ for all the groups in the graph. For each dataset,
the structural group unfairness metric
($\Delta\operatorname{\mathsf{R_{tot}}}$ or
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$) is shown on the x-axis and
the overall group isolation (sum of group isolation for all groups) or overall
group diameter (sum of diameters for all groups) on the y-axis. For both axes,
the lower the values, the better. Edge augmentation via ERG-Link clearly
outperforms any other graph intervention strategy, providing evidence that it
not only reduces inequalities in social capital between groups, but also
improves the social capital of all groups by reducing their group isolation.

###  4.6. Evolution of structural group unfairness throughout the
interventions

Figure 3. Evolution of the structural group unfairness metrics as the number
of added edges increases on the Google+ dataset with a total budget of 5,000
new edges.

Evolution of the structural group unfairness metrics as the number of added
edges increases on the Google+ dataset with a total budget of 5,000 new edges.

Fig. 3 illustrates the evolution of the structural group unfairness metrics
for the Google+ dataset as new edges are added to the network with a total
budget of 5,000 edges. As seen in the Figure, edge augmentation via ERG-Link
quickly mitigates the group isolation and diameter disparities, even after the
addition of a small number of edges. Furthermore, edge augmentation via ERG-
Link exhibits a smoother and more consistent reduction in control disparity
($\Delta\operatorname{\mathsf{B_{R}}}$), in contrast to the stair-step
behavior observed when adding edges using the baseline methods.

Note that $\operatorname{\mathsf{B_{R}}}$ is a finite resource to be allocated
among the groups and cannot be globally maximized. Hence, the right-most
graphs show how $\Delta\operatorname{\mathsf{B_{R}}}$ is improved by
decreasing $\operatorname{\mathsf{B_{R}}}$ of the group with highest initial
$\operatorname{\mathsf{B_{R}}}$ and increasing it otherwise (top-right). The
goal is to converge both controls to the optimal bound of $2-2/|\mathcal{V}|$
as indicated by the horizontal black line.

We also show in Section D.3 the evolution of the structural group unfairness
and group social capital metrics when the budget $B$ of edges to add is very
small (50 edges) and large (5,000 edges) to study the efficacy of the
interventions. Fig. 4 in Section D.3 depict the distribution of the social
capital metrics for the nodes in each of the groups in the original graph and
the resulting graphs after edge augmentation. The results are consistent: for
a fixed budget, edge augmentation via ERG-Link yields the best results both
for the mitigation of structural group unfairness and the increase in the
overall social capital of all the groups in the graph. Additionally, for a
fixed structural group unfairness mitigation goal, edge augmentation via ERG-
Link achieves it with a significantly smaller budget of added edges than any
of the baseline methods.

##  5\. Discussion, Conclusion and Future Work

In this paper, we have presented a novel method, based on the effective
resistance, to measure and mitigate structural unfairness in groups within a
social network, where the groups are defined according to the values of a
protected attribute. We have proposed a graph intervention approach rooted in
the literature of the philosophy of discrimination. We acknowledge that in the
literature there is not a single universal and absolute interpretation of
fairness (Curto and Comim, 2023). At present, the distributive paradigm of
fairness (Rawls, 1971) dominates the political and philosophical discussions
of social justice (Young, 1990). In social networks, this translates into the
pursuit of equal social capital for all individuals in the network.
Nevertheless, there are alternative interpretations of fairness (Coeckelbergh,
2022) that remain unexplored in social networks. For example, a sufficitarian
approach to fairness (Sen, 2001; Nussbaum, 2012) would entail guaranteeing a
minimum threshold of social capital for all network members, while a
prioritarian conception of fairness (Coeckelbergh, 2022) would give priority
to the individuals belonging to a vulnerable social group. Moreover, prominent
voices in social philosophy have long defended that fairness can be understood
not only as the redistribution of social capital among individuals, but also
as the social recognition of identity groups (Fraser and Honneth, 2003). In
this paper, we focus on group fairness in graphs and combine both a
prioritarian and a Rawlsian approach to fairness since our intervention aims
to mitigate the social capital gap for the most disadvantaged group while
increasing the social capital of all groups. Given the importance of social
networks in the definition of the social fabric, the ultimate goal of our work
is to spur a reflection on the potential use of social networks as reparative
tools for social inequality (Davis et al., 2021).

While one could argue that defining groups in terms of protected attributes
can be considered a form of discrimination, our approach does not aim to
systematically increase the social capital of a pre-defined vulnerable social
group, but to detect those that are structurally disadvantaged in the network
(i.e., those having the lowest levels of social capital) and implement a
mechanism at scale that benefits an entire community. This type of mitigation
of structural unfairness is particularly relevant since the potential
disadvantages suffered by groups in social networks can add up to already
existing social conditions that contribute to systemic injustice (Zalta and
Nodelman, 2011).

In terms of limitations, we have not validated the proposal with real users,
who could be reluctant to accept graph interventions that connect them with
nodes outside of their close-knit circle, despite the benefits that these
_weak ties_ bring as contributors to innovation (Rajkumar et al., 2022) and
social equity. Nonetheless, we envision our proposal as a complement to
existing graph interventions in a hybrid setup that combines the addition of
edges connecting nodes with both small (strong ties) and large (weak ties)
effective resistances. We leave for future work such a validation. Also, in
line with the body of work on intersectional bias mitigation which focuses on
demographic dimensions (Lalor et al., 2022), we have considered _gender_ as a
binary protected attribute in our experiments. We would have preferred to work
with a non-binary approach to gender, yet available social network datasets
only contain gender as a binary variable.

From a technical perspective, we plan to explore alternative edge augmentation
algorithms to mitigate structural group unfairness using our effective
resistance-based measures measures and we would like to incorporate additional
node features corresponding to the characteristics of the individuals in the
network. We also maintain ongoing discussions with several community
organizations to define a project with participants that arrive in another
country as refugees, for whom information access and connection with the local
population of the hosting country are key.

###### Acknowledgements.

This work was supported by the European Commission under Horizon Europe
Programme, grant number 101120237 - ELIAS, by Intel corporation, a nominal
grant received at the ELLIS Unit Alicante Foundation from the Regional
Government of Valencia in Spain (Convenio Singular signed with Generalitat
Valenciana, Conselleria de Innovación, Industria, Comercio y Turismo,
Dirección General de Innovación) and a grant by the Banc Sabadell Foundation.

## References

  * (1)
  * Agarwal et al. (2006) Sameer Agarwal, Kristin Branson, and Serge Belongie. 2006\.  Higher Order Learning with Graphs. In _Proceedings of the 23rd International Conference on Machine Learning_. Association for Computing Machinery, New York, NY, USA, 17–24.  https://doi.org/10.1145/1143844.1143847
  * Arnaiz-Rodríguez et al. (2022) Adrián Arnaiz-Rodríguez, Ahmed Begga, Francisco Escolano, and Nuria Oliver. 2022.  DiffWire: Inductive Graph Rewiring via the Lovász Bound. In _Proceedings of the First Learning on Graphs Conference_ _(Proceedings of Machine Learning Research, Vol. 198)_. PMLR, 15:1–15:27.  https://proceedings.mlr.press/v198/arnaiz-rodri-guez22a.html
  * Ball and Newman (2013) Brian Ball and Mark EJ Newman. 2013.  Friendship networks and social status.  _Network Science_ 1, 1 (2013), 16–30.
  * Banerjee et al. (2022) Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. 2022.  Oversquashing in GNNs through the lens of information contraction and graph expansion. In _2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 1–8.
  * Bashardoust et al. (2023) Ashkan Bashardoust, Sorelle A Friedler, Carlos E Scheidegger, Blair D Sullivan, and Suresh Venkatasubramanian. 2023.  Reducing Access Disparities in Networks using Edge Augmentation. In _Proceedings of the 2023 Conference on Fairness, Accountability, and Transparency_. ACM.
  * Black et al. (2023) Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. 2023\.  Understanding Oversquashing in GNNs through the Lens of Effective Resistance. In _Proceedings of the 40th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 202)_. PMLR, 2528–2547.
  * Borgatti (2005) Stephen P Borgatti. 2005\.  Centrality and network flow.  _Social networks_ 27, 1 (2005), 55–71.
  * Borgatti et al. (1998) Stephen P Borgatti, Candace Jones, and Martin G Everett. 1998\.  Network measures of social capital.  _Connections_ 21, 2 (1998), 27–36.
  * Borgatti et al. (2009) Stephen P Borgatti, Ajay Mehra, Daniel J Brass, and Giuseppe Labianca. 2009.  Network analysis in the social sciences.  _science_ 323, 5916 (2009), 892–895.
  * Bozzo and Franceschet (2013) Enrico Bozzo and Massimo Franceschet. 2013.  Resistance distance, closeness, and betweenness.  _Social Networks_ 35, 3 (2013), 460–469.
  * Brandes and Fleischer (2005) Ulrik Brandes and Daniel Fleischer. 2005.  Centrality measures based on current flow. In _Annual symposium on theoretical aspects of computer science_. Springer, 533–544.
  * Burt (1987) Ronald S Burt. 1987\.  Social contagion and innovation: Cohesion versus structural equivalence.  _American journal of Sociology_ 92, 6 (1987), 1287–1335.
  * Burt (1999) Ronald S Burt. 1999\.  The social capital of opinion leaders.  _The Annals of the American Academy of Political and Social Science_ 566, 1 (1999), 37–54.
  * Burt (2000) Ronald S Burt. 2000\.  The network structure of social capital.  _Research in organizational behavior_ 22 (2000), 345–423.
  * Burt (2004) Ronald S Burt. 2004\.  Structural holes and good ideas.  _American journal of sociology_ 110, 2 (2004), 349–399.
  * Campbell et al. (1986) Karen E Campbell, Peter V Marsden, and Jeanne S Hurlbert. 1986\.  Social resources and socioeconomic status.  _Social networks_ 8, 1 (1986), 97–117.
  * Chandra et al. (1989) Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, and Roman Smolensky. 1989.  The electrical resistance of a graph captures its commute and cover times. In _Proceedings of the twenty-first annual ACM symposium on Theory of computing_. 574–586.
  * Chung (1997) Fan RK Chung. 1997\.  _Spectral graph theory_. Vol. 92.  American Mathematical Soc.
  * Coeckelbergh (2022) Mark Coeckelbergh. 2022\.  _The Political Philosophy of AI_.  Polity.
  * Coifman et al. (2005) Ronald R Coifman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. 2005.  Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps.  _Proceedings of the National Academy of Sciences of the United States of America_ 102, 21 (2005), 7426–7431.
  * Coleman (1988) James S Coleman. 1988\.  Social capital in the creation of human capital.  _American journal of sociology_ 94 (1988), S95–S120.
  * Council of Europe (2010) Council of Europe. 2010\.  European Convention on Human Rights.  www.conventions.coe.int.
  * Curto and Comim (2023) Georgina Curto and Flavio Comim. 2023.  SAF: Stakeholder’s Agreement on Fairness in the Practice of Machine Learning Developent.  _Science and Engineering Ethics_ 29 (2023).
  * Davis et al. (2021) J.L. Davis, A. Williams, and M.W. Yang. 2021.  Algorithmic reparation.  _Big Data and Society_ 8, 2 (2021).
  * Del Vicario et al. (2016) Michela Del Vicario, Gianna Vivaldo, Alessandro Bessi, Fabiana Zollo, Antonio Scala, Guido Caldarelli, and Walter Quattrociocchi. 2016.  Echo chambers: Emotional contagion and group polarization on facebook.  _Scientific reports_ 6, 1 (2016), 37825.
  * Devriendt and Lambiotte (2022) Karel Devriendt and Renaud Lambiotte. 2022.  Discrete curvature on graphs from the effective resistance.  _Journal of Physics: Complexity_ 3, 2 (2022), 025008\.
  * Di Giovanni et al. (2023) Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael Bronstein. 2023.  On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. In _International Conference on Machine Learning_.
  * Doyle and Snell (1984) Peter G Doyle and J Laurie Snell. 1984.  _Random walks and electric networks_. Vol. 22.  American Mathematical Soc.
  * Ellens et al. (2011) Wendy Ellens, Floske M Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E Kooij. 2011\.  Effective graph resistance.  _Linear algebra and its applications_ 435, 10 (2011), 2491–2506.
  * Fish et al. (2019) Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. 2019\.  Gaps in information access in social networks?. In _The World Wide Web Conference_. 480–490.
  * Fouss et al. (2005) Francois Fouss, Stephane Faulkner, Manuel Kolp, Alain Pirotte, Marco Saerens, et al. 2005\.  Web Recommendation System Based on a Markov-Chainmodel.. In _ICEIS (4)_. 56–63.
  * Fouss et al. (2007) Francois Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. 2007.  Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation.  _IEEE Transactions on knowledge and data engineering_ 19, 3 (2007), 355–369.
  * Fraser and Honneth (2003) Nancy Fraser and Axel Honneth. 2003.  _Redistribution or recognition? A political -philosophical exchange_.  Verso Books.
  * Freeman (1977) Linton C Freeman. 1977\.  A set of measures of centrality based on betweenness.  _Sociometry_ (1977), 35–41.
  * Garimella et al. (2018) Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018.  Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship. In _Proceedings of the 2018 world wide web conference_. 913–922.
  * Ghosh et al. (2008) Arpita Ghosh, Stephen Boyd, and Amin Saberi. 2008.  Minimizing effective resistance of a graph.  _SIAM review_ 50, 1 (2008), 37–66.
  * Granovetter (1983) Mark Granovetter. 1983\.  The strength of weak ties: A network theory revisited.  _Sociological theory_ (1983), 201–233.
  * Gündoğdu et al. (2019) Didem Gündoğdu, Pietro Panzarasa, Nuria Oliver, and Bruno Lepri. 2019.  The bridging and bonding structures of place-centric networks: Evidence from a developing country.  _PloS one_ 14, 9 (2019), e0221148.
  * Hohmann et al. (2023) Marilena Hohmann, Karel Devriendt, and Michele Coscia. 2023\.  Quantifying ideological polarization on a network using generalized Euclidean distance.  _Science Advances_ 9, 9 (2023), eabq2044.  https://doi.org/10.1126/sciadv.abq2044 arXiv:https://www.science.org/doi/pdf/10.1126/sciadv.abq2044
  * Iyer (2021) Neema Iyer. 2021\.  _Alternate Realities, Alternate Internets: African Feminist Research for a Feminist Internet_.  Springer International Publishing, Cham, 93–113.  https://doi.org/10.1007/978-3-030-83734-1_6
  * Jackson (2019) Matthew O Jackson. 2019\.  _The human network: How your social position determines your power, beliefs, and behaviors_.  Vintage.
  * Katz (1953) Leo Katz. 1953.  A new status index derived from sociometric analysis.  _Psychometrika_ 18, 1 (1953), 39–43.
  * Kempe et al. (2003) David Kempe, Jon Kleinberg, and Éva Tardos. 2003\.  Maximizing the spread of influence through a social network. In _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_. 137–146.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Variational Graph Auto-Encoders. In _NeurIPS Workshop on Bayesian Deep Learning_.
  * Klein and Randić (1993) Douglas J Klein and Milan Randić. 1993.  Resistance distance.  _Journal of mathematical chemistry_ 12 (1993), 81–95.
  * Lalor et al. (2022) John P. Lalor, Yi Yang, Kendall Smith, Nicole Forsgren, and Ahmed Abbasi. 2022.  Benchmarking Intersectional Biases in NLP.  _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ (2022), 3598–3609.  https://doi.org/10.18653/V1/2022.NAACL-MAIN.263
  * Leskovec and Mcauley (2012) Jure Leskovec and Julian Mcauley. 2012.  Learning to discover social circles in ego networks.  _Advances in neural information processing systems_ 25 (2012).
  * Lipman et al. (2010) Yaron Lipman, Raif M Rustamov, and Thomas A Funkhouser. 2010\.  Biharmonic distance.  _ACM Transactions on Graphics (TOG)_ 29, 3 (2010), 1–11.
  * Lovász (1993) László Lovász. 1993\.  Random walks on graphs.  _Combinatorics, Paul erdos is eighty_ 2, 1-46 (1993), 4\.  https://web.cs.elte.hu/~lovasz/erdos.pdf
  * Nahapiet and Ghoshal (1998) Janine Nahapiet and Sumantra Ghoshal. 1998.  Social capital, intellectual capital, and the organizational advantage.  _Academy of management review_ 23, 2 (1998), 242–266.
  * Newman (2003) Mark EJ Newman. 2003\.  Mixing patterns in networks.  _Physical review E_ 67, 2 (2003), 026126.
  * Newman (2005) Mark EJ Newman. 2005\.  A measure of betweenness centrality based on random walks.  _Social networks_ 27, 1 (2005), 39–54.
  * Nussbaum (2012) Martha C Nussbaum. 2012\.  _Creating Capabilities_.  Harvard University Press, Cambridge, Massachusetts and London, England.
  * Ovadya and Thorburn (2023) Aviv Ovadya and Luke Thorburn. 2023.  Bridging Systems: Open Problems for Countering Destructive Divisiveness across Ranking, Recommenders, and Governance.  _arXiv preprint arXiv:2301.09976_ (2023).
  * Page et al. (1998) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998.  _The pagerank citation ranking: Bring order to the web_.  Technical Report. technical report, Stanford University.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 701–710.
  * Putnam (2015) Robert D Putnam. 2015\.  Bowling alone: America’s declining social capital.  In _The city reader_. Routledge, 188–196.
  * Qiu and Hancock (2007) Huaijun Qiu and Edwin R Hancock. 2007.  Clustering and embedding using commute times.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 29, 11 (2007), 1873–1890.
  * Rajkumar et al. (2022) Karthik Rajkumar, Guillaume Saint-Jacques, Iavor Bojinov, Erik Brynjolfsson, and Sinan Aral. 2022\.  A causal test of the strength of weak ties.  _Science (American Association for the Advancement of Science)_ 377, 6612 (2022), 1304–1310.  https://doi.org/10.1126/science.abl4476
  * Rampášek et al. (2022) Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022.  Recipe for a general, powerful, scalable graph transformer.  _Advances in Neural Information Processing Systems_ 35 (2022), 14501–14515.
  * Rawls (1971) J Rawls. 1971.  _A Theory of Justice_.  Oxford University Press, Oxford.
  * Red et al. (2011) Veronica Red, Eric D Kelsic, Peter J Mucha, and Mason A Porter. 2011.  Comparing community structure to characteristics in online collegiate social networks.  _SIAM review_ 53, 3 (2011), 526–543.
  * Sabidussi (1966) Gert Sabidussi. 1966\.  The centrality index of a graph.  _Psychometrika_ 31, 4 (1966), 581–603.
  * Santos et al. (2021) Fernando P Santos, Yphtach Lelkes, and Simon A Levin. 2021\.  Link recommendation algorithms and dynamics of polarization in online social networks.  _Proceedings of the National Academy of Sciences_ 118, 50 (2021), e2102141118.
  * Saxena et al. (2022) Akrati Saxena, George Fletcher, and Mykola Pechenizkiy. 2022\.  Fairsna: Algorithmic fairness in social network analysis.  _arXiv preprint arXiv:2209.01678_ (2022).
  * Sen (2001) Amartya Sen. 2001\.  _Development as freedom_.  Oxford University Press.
  * Spielman and Srivastava (2008) Daniel A Spielman and Nikhil Srivastava. 2008.  Graph sparsification by effective resistances. In _Proceedings of the fortieth annual ACM symposium on Theory of computing_. 563–568.
  * Stephenson and Zelen (1989) Karen Stephenson and Marvin Zelen. 1989.  Rethinking centrality: Methods and examples.  _Social networks_ 11, 1 (1989), 1–37.
  * Su et al. (2016) Jessica Su, Aneesh Sharma, and Sharad Goel. 2016\.  The effect of recommendations on network structure. In _Proceedings of the 25th international conference on World Wide Web_. 1157–1167.
  * Szreter (2002) Simon Szreter. 2002\.  The state of social capital: Bringing back in power, politics, and history.  _Theory and society_ 31, 5 (2002), 573–621.
  * Szreter and Woolcock (2004) Simon Szreter and Michael Woolcock. 2004.  Health by association? Social capital, social theory, and the political economy of public health.  _International journal of epidemiology_ 33, 4 (2004), 650–667.
  * Tauch et al. (2015) Sotharith Tauch, William Liu, and Russel Pears. 2015.  Measuring cascade effects in interdependent networks by using effective graph resistance. In _2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 683–688.
  * Tetali (1991) Prasad Tetali. 1991\.  Random walks and the effective resistance of networks.  _Journal of Theoretical Probability_ 4 (1991), 101–109.
  * Tizghadam and Leon-Garcia (2009) Ali Tizghadam and Alberto Leon-Garcia. 2009.  A graph theoretical approach to traffic engineering and network control problem. In _2009 21st International Teletraffic Congress_. IEEE, 1–8.
  * Tizghadam and Leon-Garcia (2010) Ali Tizghadam and Alberto Leon-Garcia. 2010.  Betweenness centrality and resistance distance in communication networks.  _IEEE Network_ 24, 6 (2010), 10–16.  https://doi.org/10.1109/MNET.2010.5634437
  * Tong et al. (2012) Hanghang Tong, B Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012\.  Gelling, and melting, large graphs by edge manipulation. In _Proceedings of the 21st ACM international conference on Information and knowledge management_. 245–254.
  * Topping et al. (2022) Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022.  Understanding over-squashing and bottlenecks on graphs via curvature. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=7UmjRGzp-A
  * United Nations (1966) United Nations. 1966\.  International Covenant on Civil and Political Rights.
  * Wang et al. (2022) Xindi Wang, Onur Varol, and Tina Eliassi-Rad. 2022.  Information access equality on generative models of complex networks.  _Applied Network Science_ 7, 1 (2022), 1–20.
  * Wasserman and Faust (1994) Stanley Wasserman and Katherine Faust. 1994.  Social network analysis: Methods and applications.  (1994).
  * Woolcock et al. (2001) Michael Woolcock et al. 2001\.  The place of social capital in understanding social and economic outcomes.  _Canadian journal of policy research_ 2, 1 (2001), 11–17.
  * Wu et al. (2022) Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. 2022.  Graph neural networks in recommender systems: a survey.  _Comput. Surveys_ 55, 5 (2022), 1–37.
  * Young (1990) I.M. Young. 1990\.  _Justice and the politics of difference_.  Princeton University Press, Princeton, N.J.
  * Zalta and Nodelman (2011) Edward N. Zalta and Uri Nodelman (Eds.). 2011.  _Stanford Encyclopedia of Philosophy_.  https://plato.stanford.edu/entries/discrimination/
  * Zhang et al. (2011) Saijun Zhang, Steven G Anderson, and Min Zhan. 2011\.  The differentiated impact of bridging and bonding social capital on economic well-being: An individual level perspective.  _J. Soc. & Soc. Welfare_ 38 (2011), 119.
  * Zignani et al. (2014) Matteo Zignani, Sabrina Gaito, Gian Paolo Rossi, Xiaohan Zhao, Haitao Zheng, and Ben Zhao. 2014\.  Link and triadic closure delay: Temporal metrics for social network dynamics. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 8. 564–573.

##  Appendix A Table of notation

Table 3. Table of Notation Symbol |  Description |  Definition
---|---|---
$G=\mathcal{(V,E)}$ |  Graph = (Nodes, Edges) |
$n=|\mathcal{V}|$ |  Number of nodes |
$\mathbf{A}$ |  Adjacency matrix: $\mathbf{A}\in\mathbb{R}^{n\times n}$ |  $A_{u,v}=1$ if $(u,v)\in\mathcal{E}$ and $0$ otherwise
$v$ or $u$ |  Node $v\in\mathcal{V}$ or $u\in\mathcal{V}$ |
$e$ |  Edge $e\in\mathcal{E}$ |
$d_{v}$ |  Degree of node, i.e., number of neighbors $v$ |  $d_{v}=\sum_{u\in V}A_{v,u}$
$\mathbf{D}$ |  Degree diagonal matrix where $d_{v}$ in $D_{vv}$ |  $\mathbf{D}=\text{diag}(d_{0},\ldots,d_{\mathcal{V}})$
$\text{vol}(G)$ |  Sum of the degrees of the graph |  $\text{vol}(G)=\sum_{u\in V}d_{u}=2|\mathcal{E}|=\text{Tr}[\textbf{D}]$
$\mathcal{N}(u)$ |  Neighbors of $u$ |  $\mathcal{N}(u)=\\{v:(u,v)\in\mathcal{E}\\}$
$S_{i}$ |  Subset of nodes |  $S\subseteq V$
$SA$ |  Set of sensitive attributes |  $SA=\\{sa_{1},sa_{2},\dots,sa_{|SA|}\\}$
$SA(v)$ |  Value of the sensitive attribute of the node $v$ |
$sa_{i}$ |  Specific value of a sensitive attribute, e.g., $sa_{i}$=female. |
$S_{i}$ |  Set of nodes defined by their sensitive attribute |  $S_{i}=\\{v\in V|SA(v)=sa_{i}\\}$
$S_{d}$ |  Set of nodes defined by their sensitive attribute with the highest level of isolation $\operatorname{\mathsf{R_{tot}}}(S_{i})$ |
$\mathbf{L}$ |  Graph Laplacian |  $\mathbf{L=D-A=\Phi\Lambda\Phi}^{\top}$
$\mathbf{\Lambda}$ |  Eigenvalue matrix of $\mathbf{L}$ |
$\Phi$ |  Matrix of eigenvectors of $\mathbf{L}$ |
$\lambda_{i}$ |  The $i$-th smallest eigenvalue of $\mathbf{L}$ |
$\mathbf{f}_{i}$ |  Eigenvector associated with the $i$-th smallest eigenvalue of $\mathbf{L}$ |
$\mathbf{L}^{+}$ |  The pseudo-inverse of $\mathbf{L}$ |  $\mathbf{L}^{+}=\sum_{i>1}\lambda_{i}^{-1}\phi\phi^{\top}$
$h_{G}$ |  Cheeger constant |  Eq. 9
$\mathbf{e}_{u}$ |  Unit vector with unit value at $u$ and 0 elsewhere |
$R_{uv}$ |  Effective resistance between nodes $u$ and $v$ |  $R_{uv}=(\mathbf{e}_{u}-\mathbf{e}_{v})\mathbf{L}^{+}(\mathbf{e}_{u}-\mathbf{e}_{v})$
$\mathbf{R}$ |  Effective resistance matrix where the $i,j$ entry corresponds to $R_{ij}$ |  $\mathbf{R}=\mathbf{1}\text{diag}(\mathbf{L}^{+})^{\top}+\text{diag}(\mathbf{L}^{+})\mathbf{1}^{\top}-2\mathbf{L}^{+}$
$\mathbf{Z}$ |  Commute Time Embedding matrix |  $\mathbf{Z}=\sqrt{vol(G)}\mathbf{\Lambda^{-1/2}}\mathbf{\Phi}^{\top}$
$\mathbf{z}_{u}$ |  Commute times embedding of node $Z_{u,:}$ |
$\operatorname{\mathsf{CT}}(u,v)$ |  Commute time |  $\operatorname{\mathsf{CT}}(u,v)=\text{vol}(G)R_{u.v}$
$\operatorname{\mathsf{R_{tot}}}$ |  Total Effective Resistance of $G$ |  $\operatorname{\mathsf{R_{tot}}}=\frac{1}{2}\mathbf{1}^{\top}\mathbf{R1}$
$\operatorname{\mathcal{R}_{\text{diam}}}$ |  Resistance Diameter of $G$ |  $\operatorname{\mathcal{R}_{\text{diam}}}=\max_{u,v\in\mathcal{V}}R_{u,v}$
$\operatorname{\mathsf{R_{tot}}}(u)$ |  Node Isolation or Total Effective Resistance |  $\operatorname{\mathsf{R_{tot}}}(u)=\sum_{v\in V}R_{uv}$
$\operatorname{\mathcal{R}_{\text{diam}}}(u)$ |  Node Resistance Diameter |  $\operatorname{\mathcal{R}_{\text{diam}}}(u)=\max_{v\in V}R_{uv}$
$\operatorname{\mathsf{B_{R}}}(u)$ |  Node Control or Resistance Betweenness |  $\operatorname{\mathsf{B_{R}}}(u)=\sum_{v\in\mathcal{N}(u)}R_{uv}$
$\operatorname{\mathsf{R_{tot}}}(S_{i})$ |  Group Isolation or Total Effective Resistance |  $\operatorname{\mathsf{R_{tot}}}(S_{i})=|S|^{-1}\sum_{u\in S}\operatorname{\mathsf{R_{tot}}}(u)$
$\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})$ |  Group Resistance Diameter |  $\operatorname{\mathcal{R}_{\text{diam}}}(S)=|S|^{-1}\sum_{u\in S}\operatorname{\mathcal{R}_{\text{diam}}}(u)$
$\operatorname{\mathsf{B_{R}}}(S_{i})$ |  Group Control or average Betweenness |  $\operatorname{\mathsf{B_{R}}}(S)=|S|^{-1}\sum_{u\in S}\operatorname{\mathsf{B_{R}}}(u)$

##  Appendix B Effective Resistance and information flow

In this section, we provide an overview of the graph diffusion concepts that
constitute the theoretical foundation of the effective resistance as a measure
of information flow in a graph.

###  B.1. Graph Diffusion Measures

##### Discrete information propagation

Information propagation in networks has been widely studied (Burt, 1987; Kempe
et al., 2003), prominently by means of graph diffusion and Random Walks
methods. A Random Walk (RW) on a graph is a Markov chain that starts at a
given node $i$, and moves randomly to another node from its neighborhood with
probability $1/D_{i,i}$. The RW transition probability matrix is given by
$\mathbf{P}=\mathbf{D}^{-1}\mathbf{A}$ and defines the discrete probability of
a random walker to move from node $u$ to node $v$. $\mathbf{P}^{k}$ is the
$k$-th power of the transition matrix $P$: the entry $(P^{k})_{ij}$ denotes
the probability of transitioning from node $i$ to node $j$ in exactly $k$
steps. The graph’s diffusion matrix is defined as
$\mathbf{T}=\sum_{k=0}^{\infty}\theta_{k}\mathbf{P}^{k}$, and it represents
the cumulative effect of multiple steps of a random walk on the graph. Each
entry $T_{ij}$ of $\mathbf{T}$ corresponds to the probability of transitioning
from node $i$ to node $j$ over an infinite number of steps. $\theta_{k}$ is
known as the teleport probability at step $k$ in the random walk. It
quantifies the likelihood that, at each step, the random walker will teleport
to a random node instead of following an edge. Thus, the sequence
$\\{\theta_{k}\\}$ is a series of teleport probabilities over the steps. The
resulting $T$ captures the cumulative probabilities of transitioning between
nodes over an infinite number of steps in the random walk, such that the
probability of co-occurrence of two nodes on a random walk corresponds to the
probability of information flowing between these two nodes.

However, this approach to assess information flow between nodes in a graph has
several limitations. First, it requires considering all the potential paths in
a graph, which might not be computationally feasible for large graphs. To
overcome this issue, a value of $k$ is typically chosen, which limits the
power of the method. Second, the teleport probabilities, $\theta_{k}$, need to
be defined for each $k$-hop. Several methods have studied how to approximate
it, such as Independent Cascade (Kempe et al., 2003), Katz (Katz, 1953), SIR
or PageRank (Page et al., 1998). Independent Cascade or SIR methods (Kempe et
al., 2003) are based on infection models, where they sample guided random
walks and, thus, usually rely on expensive Monte Carlo simulations leading to
a sub-optimal probability of transition, unable to consider the topology of
the entire graph.

##### Graph continuous diffusion metrics

Graph continuous diffusion metrics —such as the Heat kernel distance, (Coifman
et al., 2005), effective resistance (or _commute times_ distance) (Klein and
Randić, 1993; Fouss et al., 2007, 2005; Qiu and Hancock, 2007) or the bi-
harmonic distance (Lipman et al., 2010)— arise as a generalization of random
walk metrics. Their mathematical foundations allow for a better
characterization of the information flow and an intuitive interpretation of
the diffusion processes in a network.

Diffusion metrics define distances based on fine-grained nuances of the
topology of the graph that are not captured by simple geodesic distances. When
two nodes can be reached by many paths, they should be _closer_ than when they
can be reached only by few paths of equal length. When two nodes can be
reached by a set of edge-independent paths, they are _closer_ than when they
are reached by redundant paths. Similarly, when two nodes are separated by a
shorter path, they are _closer_ than when they are separated by a longer path
(Bozzo and Franceschet, 2013).

In addition, these metrics provide a node embedding, _i.e._ , a numerical
representation of each node in the graph that reflects its importance in the
process of information diffusion. These embeddings capture the global
structure of the network because they incorporate both the local and global
geometry of the graph.

The continuous diffusion metrics can be computed using the pseudo-inverse (or
Green’s function) of the combinatorial graph Laplacian
$\mathbf{L}=\mathbf{D}-\mathbf{A}$, or the normalized Laplacian
$\mathcal{L}=\mathbf{D}^{-1/2}\mathbf{L}\mathbf{D}^{-1/2}$ (Fouss et al.,
2007). The pseudo-inverse, denoted as $\mathbf{L}^{+}$ is computed using the
spectral decomposition: $\mathbf{L}^{+}=\sum_{i\geq
0}\lambda_{i}^{-1}\phi\phi^{\top}$ where
$\mathbf{L}=\mathbf{\Phi\Lambda\Phi}^{\top}$, where $\lambda_{i}$ is the
$i$-smallest eigenvalue of the Laplacian corresponding to the $\phi_{i}$
eigenvector.

In this paper, we use the effective resistance, which is a continuous
diffusion metric.

###  B.2. Effective Resistance and Commute Times

The Commute Time (CT) (Qiu and Hancock, 2007),
$\operatorname{\mathsf{CT}}(u,v)$, is the expected number of steps that a
random walker needs to go from node $u$ to $v$ and come back to $u$. The
Effective Resistance, $R_{uv}$, is the Commute Time divided by the volume of
the graph (Klein and Randić, 1993). In addition to providing a distance for
all pairs of nodes —whether connected or not— $R_{uv}$ may be viewed as an
indicator of the criticality or importance of the edges in the flow of
information throughout the network (Spielman and Srivastava, 2008).

Intuitively, this distance captures how structurally similar and connected are
two nodes in a graph. If two nodes are structurally similar to each other,
then the effective resistance between them will be small. Conversely, if two
nodes are weakly or not connected, then their effective resistance will be
large. In addition, we can define a commute time embedding (CTE,
$\mathbf{Z}=\sqrt{vol(G)}\mathbf{\Lambda^{-1/2}}\mathbf{\Phi}^{\top}$) of the
nodes in the graph —similar to the idea of the _node’s access signature_ in
Bashardoust et al. (2023)—, where the Euclidean distance in such an embedding
corresponds exactly to the commute times
$\operatorname{\mathsf{CT}}(u,v)=||Z_{u,:}-Z_{v,:}||^{2}=\mathbb{E}_{u}[v]+\mathbb{E}_{v}[u]=2|\mathcal{E}|R_{uv}$.
This distance is upper bounded by the geodesic distance, with equality in the
case of the graph being a tree.

Note that the effective resistance does not rely on any parameter and it is an
accurate metric to measure the graph’s information flow (Ghosh et al., 2008;
Arnaiz-Rodríguez et al., 2022; Chandra et al., 1989), as explained next.

##### Information flow in a graph

The graph’s information flow is given by the graph’s conductance, which is
measured leveraging the Cheeger Constant, $h_{G}$, of a graph (Chung, 1997):

(9) $h_{G}=\min_{H\subseteq V}\frac{|\\{e=(u,v):u\in
S,v\in\bar{H}\\}|}{\min(vol(H),vol(\bar{H}))}$

The larger $h_{G}$, the harder it is to disconnect the graph into separate
communities. Therefore, to increase the information flow in the network, one
could add edges to the original graph $G$, creating a new graph $G^{\prime}$,
such that $h_{G^{\prime}}>h_{G}$. In addition, by virtue of the Cheeger
Inequality, $h_{G}$ is bounded by the smallest non-zero eigenvalue of
$\mathbf{L}$ defined as $\lambda_{2}$:

(10) $2h_{G}\leq\lambda_{2}<\frac{h_{G}^{2}}{2}$

Finally, the $\operatorname{\mathsf{CT}}$ is bounded by $\lambda_{2}$ as per
the Lovász Bound (Lovász, 1993)

(11)
$\left|\frac{\operatorname{\mathsf{CT}}(u,v)}{\text{vol}(G)}-\left(\frac{1}{d_{u}}+\frac{1}{d_{v}}\right)\right|\leq\frac{1}{\lambda_{2}}\frac{2}{d_{min}}$

where vol($G$) is the volume of $G$, _i.e._ , the sum of the degrees of the
all nodes in the graph; $d_{u}$, $d_{v}$ are the degrees of nodes $u$ and $v$,
respectively; and $d_{min}$ is the minimum degree in the graph.

Therefore, a graph’s information flow is bounded by $\lambda_{2}$ which is
bounded by $h_{G}$. The intuition is that graphs with large
$\lambda_{2}\propto h_{G}$ have short $\operatorname{\mathsf{CT}}$ distances
and thus they have better information flow. Edge augmentation in a graph would
lead to a new graph $G^{\prime}$ where $h_{G^{\prime}}>h_{G}$, with smaller
$\operatorname{\mathsf{CT}}$ distances and therefore better information flow.

The effective resistance is also related to other ways of computing the
information flow between two nodes in a graph, such as the Jacobian (Topping
et al., 2022; Di Giovanni et al., 2023; Black et al., 2023).

###  B.3. Theoretical Metrics Derived from Effective Resistance

In this section, we introduce several measures that are derived from the
effective resistance. These measures have been proposed in previous work and
constitute the grounds for the group social capital metrics that we propose in
this paper (Sections 3.1.2 and 3.2).

##### Total effective resistance

$\operatorname{\mathsf{R_{tot}}}$ (Ellens et al., 2011) is the sum of all
effective distances in the graph. A lower value of
$\operatorname{\mathsf{R_{tot}}}$ indicates ease of signal propagation across
the entire network and hence larger information flow.
$\operatorname{\mathsf{R_{tot}}}$ is given by:

(12)
$\operatorname{\mathsf{R_{tot}}}=\operatorname{\mathsf{R_{tot}}}(\mathcal{V})=\frac{1}{2}\mathbf{1}^{\top}\mathbf{R1}=\frac{1}{2}\sum_{(v,u)\in
V}R_{uv}=n\sum_{2}^{n}\frac{1}{\lambda_{n}}=n\operatorname{Tr}(\mathbf{L}^{\dagger})$

The minimum $\operatorname{\mathsf{R_{tot}}}=|V|-1=n-1$ is achieved in a fully
connected graph. Conversely, the maximum $\operatorname{\mathsf{R_{tot}}}$ is
achieved on a path graph (or linear graph) and
$\operatorname{\mathsf{R_{tot}}}=\sum_{i}^{n-1}i=\frac{1}{2}(n(n-1))$.
Therefore, $\operatorname{\mathsf{R_{tot}}}$ is —for connected graphs— in the
range $[n-1,\frac{n(n-1)}{2}]$

Additionally, since the distance between $u$ and $v$ is the Euclidean distance
in the embedding $\mathbf{Z}$, $\operatorname{\mathsf{R_{tot}}}$ can be
obtained as follows (Ghosh et al., 2008):

(13) $\operatorname{\mathsf{R_{tot}}}=\sum_{(v,u)\in
V}||Z_{u:}-Z_{v:}||^{2}=n\sum_{u\in V}||Z_{u:}||^{2}$

Similarly to $R_{uv}$, $\operatorname{\mathsf{R_{tot}}}$ is theoretically
related to the connectivity of the graph defined by it smallest non-zero
eigenvalue. Ellens et al. (2011) demonstrated the relation between
$\operatorname{\mathsf{R_{tot}}}$ and $\lambda_{2}$:

(14)
$\frac{n}{\lambda_{2}}<\operatorname{\mathsf{R_{tot}}}\leq\frac{n(n-1)}{\lambda_{2}}.$

##### Resistance diameter

The proposed group resistance diameter is based on the resistance diameter of
a graph $\operatorname{\mathcal{R}_{\text{diam}}}$, which is the maximum
effective resistance on the graph (Chandra et al., 1989; Qiu and Hancock,
2007):

(15) $\operatorname{\mathcal{R}_{\text{diam}}}=\max_{u,v\in V}R_{uv}$

$\operatorname{\mathcal{R}_{\text{diam}}}\propto\lambda_{2}$ (Chung, 1997;
Chandra et al., 1989), since

(16)
$\frac{1}{n\lambda_{2}}\leq\operatorname{\mathcal{R}_{\text{diam}}}\leq\frac{2}{\lambda_{2}}$

and specifically (Qiu and Hancock, 2007; Arnaiz-Rodríguez et al., 2022):

(17)
$h_{G}\leq\frac{\alpha^{\epsilon}}{\sqrt{\operatorname{\mathcal{R}_{\text{diam}}}\cdot\epsilon}}vol(S)^{\epsilon-1/2},$

By (Qiu and Hancock, 2007) we know that

(18)
$\operatorname{\mathcal{R}_{\text{diam}}}\leq\frac{1}{\lambda_{2}}\>\>\text{and}\>\>\operatorname{\mathcal{R}_{\text{diam}}}\leq\frac{1}{h_{G}^{2}}$

In addition, $\operatorname{\mathcal{R}_{\text{diam}}}$ is related to the
_cover time_ of the graph, which is the expected time required for a random
walk to visit every node at least once, i.e., the expected time for a piece of
information to reach the entire network.
$\operatorname{\mathcal{R}_{\text{diam}}}$ can be used to estimate the cover
time of the graph, as per (Chandra et al., 1989):

(19) $m\operatorname{\mathcal{R}_{\text{diam}}}\leq\text{cover time}\leq
O(m\operatorname{\mathcal{R}_{\text{diam}}}\log n)$

##### Resistance betweenness and curvature

As the effective resistance is an information distance, this metric can be
used to propose alternative betweenness or criticality metrics to the shortest
path betweenness (Newman, 2005). In the literature, several effective
resistance-based measures have been proposed to determine a node’s
criticality, such as: the current flow betweenness (Tizghadam and Leon-Garcia,
2009, 2010; Bozzo and Franceschet, 2013; Brandes and Fleischer, 2005; Newman,
2005), the resistance curvature of a node (Topping et al., 2022; Devriendt and
Lambiotte, 2022), and the information bottleneck property of a node (Arnaiz-
Rodríguez et al., 2022; Black et al., 2023; Banerjee et al., 2022). Note that
the last two definitions are mathematically equivalent (Devriendt and
Lambiotte, 2022).

In this work, we focus on the resistance curvature of a node and the
information bottleneck, which have been shown to define how much information
is squeezed into a node when the information flows in the graph (Arnaiz-
Rodríguez et al., 2022; Banerjee et al., 2022). The resistance curvature of a
node is expressed as (Devriendt and Lambiotte, 2022):

(20) $p_{u}=1-\frac{1}{2}\sum_{v\in\mathcal{N}(u)}R_{uv}$

Therefore, it fulfills the following equality:

(21)
$p_{u}=1-\frac{1}{2}\sum_{v\in\mathcal{N}(u)}R_{uv}=1-\frac{1}{2}\operatorname{\mathsf{B_{R}}}(u)\rightarrow\operatorname{\mathsf{B_{R}}}(u)=-2(p_{u}-1).$

Although the definition of a node’s resistance curvature involves computing
the sum of the effective resistances between the node and its neighboring
nodes, the overall structure of the graph affects all $R_{uv}$’s and,
consequently, the value of $p_{i}$ and $\operatorname{\mathsf{B_{R}}}(u)$. The
curvature of a node is bounded by $1-d_{u}/2\leq p_{u}\leq 1/2$.

##  Appendix C Group Social Capital Metrics and Edge Augmentation Algorithm

In this section, we explore the properties and attributes of the proposed
group social capital metrics and present an efficient version of the greedy
edge augmentation algorithm described in the main paper.

###  C.1. Group Social Capital Metrics

####  C.1.1. Group Isolation and Isolation Disparity

Group Isolation is based on the previously explained notion of total effective
resistance of a graph and its close connection with the current flow closeness
centrality (Newman, 2005). We propose to define the isolation of a node as its
total effective resistance
$\operatorname{\mathsf{R_{tot}}}(u)=\sum_{v\in\mathcal{V}}R_{uv}$. The
proposed group isolation is obtained as the expectation in
$\operatorname{\mathsf{R_{tot}}}(u)$ for all the nodes in the group:

$\displaystyle\operatorname{\mathsf{R_{tot}}}(S_{i})=$
$\displaystyle\mathbb{E}_{u\sim
S_{i}}\left[\operatorname{\mathsf{R_{tot}}}(u)\right]$ $\displaystyle=$
$\displaystyle\left|\mathcal{V}\right|\mathbb{E}_{u\sim
S_{i}}\left[\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}R_{uv}\right]=|\mathcal{V}|\mathbb{E}_{u\sim
S_{i}}\left[\mathbb{E}_{v\sim\mathcal{V}}\left[R_{uv}\right]\right]$ (22)
$\displaystyle=$ $\displaystyle|\mathcal{V}|\mathbb{E}_{u\sim
S_{i},v\sim\mathcal{V}}\left[R_{uv}\right],$

and it is also proportional to the average $R_{uv}$ of the nodes in $S$ to all
other nodes in the graph, multiplied by the size of that group.

$\operatorname{\mathsf{R_{tot}}}(S_{i})$ is computed as the expectation of
$\operatorname{\mathsf{R_{tot}}}(u)$ for all nodes in group $S_{i}$:

(23) $\displaystyle\operatorname{\mathsf{R_{tot}}}(S_{i})=$
$\displaystyle|\mathcal{V}|\mathbb{E}_{u\sim
S_{i},v\sim\mathcal{V}}\left[R_{uv}\right]$ $\displaystyle=$
$\displaystyle|\mathcal{V}|\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}R_{uv}=\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\sum_{v\in\mathcal{V}}R_{uv}=\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\operatorname{\mathsf{R_{tot}}}(u)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{u\sim
S_{i}}\left[\operatorname{\mathsf{R_{tot}}}(u)\right]$

Finally, the cumulative group isolation across all groups in the graph
fulfills the following equality with the total effective resistance of the
graph.

$\displaystyle\frac{1}{2}\sum_{i\in
SA}\left|S_{i}\right|\operatorname{\mathsf{R_{tot}}}(S_{i})=\frac{1}{2}\sum_{i\in
SA}\left|S_{i}\right|\frac{1}{|S_{i}|}\sum_{u\in
S_{i}}\sum_{v\in\mathcal{V}}R_{uv}=\frac{1}{2}\sum_{v\in\mathcal{V}}\sum_{v\in\mathcal{V}}R_{uv}=\operatorname{\mathsf{R_{tot}}}=n\operatorname{Tr}(\mathbf{L}\dagger)$

Therefore, since $\operatorname{\mathsf{R_{tot}}}$ is related to the
information flow, $\operatorname{\mathsf{R_{tot}}}(S_{i})$ measures the ease
of information flow through group $S_{i}$ in the graph.

The optimal –yet extreme– scenario of maximum information flow in a graph is
such where all nodes in the graph are connected. Hence, $G$ will be a fully
connected graph. In this scenario, the total effective resistance of the graph
reaches its minimum $n-1$, where $n=|\mathcal{V}|$. The total effective
resistance of all existing edges in the graph is $n-1$, and given that we have
all connections, $\operatorname{\mathsf{R_{tot}}}$ also sums up to $n-1$.
Therefore, every pair of nodes will be separated by $R_{uv}=2/n$. In this
scenario, $\operatorname{\mathsf{R_{tot}}}(u)=(2/n)(n-1)=2-2/n$ for all nodes
in the graph. It leads to an group isolation of
$\operatorname{\mathsf{R_{tot}}}(S_{i})=2-2/n$ for all the different groups in
the graph and therefore a Isolation disparity
$\Delta\operatorname{\mathsf{R_{tot}}}=0$.

Regarding group isolation disparity, Eq. 5 can be redefined using Eq. 23. It
is equivalent to the equality for all groups of the mean $R_{uv}$ between of
the nodes in the group and all nodes in the graph:

$\displaystyle\operatorname{\mathsf{R_{tot}}}(S_{i})$
$\displaystyle=\operatorname{\mathsf{R_{tot}}}(S_{j}),\forall i,j\in SA$ (24)
$\displaystyle\mathbb{E}_{u\sim S_{i},v\sim\mathcal{V}}\left[R_{uv}\right]$
$\displaystyle=\mathbb{E}_{u\sim
S_{j},v\sim\mathcal{V}}\left[R_{uv}\right],\forall i,j\in SA\times SA$

####  C.1.2. Group Control and Control Disparity

In this section, we provide the proof for the bounds associated with the
proposed control metrics.

##### Bounds of $\operatorname{\mathsf{B_{R}}}(u)$ and
$\operatorname{\mathsf{B_{R}}}(S_{i})$

In this section, we show the proof of the bounds of the node and group
control.

###### Theorem C.1.

The control of a node is bounded by $1\leq\operatorname{\mathsf{B_{R}}}(u)\leq
d_{u}$, being $d_{u}$ the degree of node $u$. Equality on the upper bound
holds when all the edges are cut edges, _i.e.,_ edges that if removed the
graph would become disconnected.

###### Proof.

The resistance curvature of a node is known to be bounded by $1-d_{u}/2\leq
p_{u}\leq 1/2$ (Devriendt and Lambiotte, 2022), and the relation between the
curvature and group control is given by the equality
$p_{u}=1-\frac{1}{2}\operatorname{\mathsf{B_{R}}}(u)$. Therefore, we obtain
the bounds as

$\displaystyle 1-\frac{d_{u}}{2}$ $\displaystyle\leq
p_{u}\leq\frac{1}{2}\rightarrow$ $\displaystyle 1-\frac{d_{u}}{2}$
$\displaystyle\leq
1-\frac{1}{2}\operatorname{\mathsf{B_{R}}}(u)\leq-\frac{1}{2}\rightarrow$
$\displaystyle-d_{u}$
$\displaystyle\leq-\operatorname{\mathsf{B_{R}}}(u)\leq-1\rightarrow$
$\displaystyle 1$ $\displaystyle\leq\operatorname{\mathsf{B_{R}}}(u)\leq
d_{u}$

∎

###### Theorem C.2.

The control of a group is bounded by
$1\leq\operatorname{\mathsf{B_{R}}}(S_{i})\leq\frac{\text{vol}(S_{i})}{|S_{i}|}$,
being vol$(S_{i})$ the sum of the degrees of node $u$. Thus,
$\text{vol}(S_{i})/|S_{i}|$ is the average degree of all the nodes in $S_{i}$.
Equality on the upper bound holds when the subgraph with all nodes of $S_{i}$
and their neighbors is a tree graph, i.e., a connected acyclic undirected
graph.

###### Proof.

The control of a group is defined as
$\operatorname{\mathsf{B_{R}}}(S_{i})=\mathbb{E}_{u\thicksim
S_{i}}[\operatorname{\mathsf{B_{R}}}(u)]$ and using Theorem C.1, we derive the
bounds of $\operatorname{\mathsf{B_{R}}}(S_{i})$ as follows:

$\displaystyle 1$ $\displaystyle\leq\operatorname{\mathsf{B_{R}}}(u)\leq
d_{u}\rightarrow$ $\displaystyle 1$ $\displaystyle\leq\mathbb{E}_{u\thicksim
S_{i}}[\operatorname{\mathsf{B_{R}}}(u)]\leq\mathbb{E}_{u\thicksim
S_{i}}[d_{u}]\rightarrow$ $\displaystyle 1$
$\displaystyle\leq\operatorname{\mathsf{B_{R}}}(S_{i})\leq\frac{\text{vol}(S_{i})}{|S_{i}|}$

∎

##### Control as an allocation problem

Here we delve into the properties and behavior of the group control
($\operatorname{\mathsf{B_{R}}}(S_{i})$) as a limited resource to be
distributed in the network. The sum of $R_{uv}$ for every edge always equals
to $|\mathcal{V}|-1$ (Ellens et al., 2011):

$\sum_{(u,v)\in\mathcal{E}}R_{uv}=|V|-1.$

Therefore, the sum of the node controls in the graph is defined as

$\sum_{u\in\mathcal{V}}B_{R}(u)=\sum_{u\in\mathcal{V}}\sum_{v\in\mathcal{N}(u)}R_{uv}=2\times\sum_{(u,v)\in\mathcal{E}}R_{uv}=2|V|-2,$

and the expectation as:

$\mathbb{E}_{u\sim V}[B_{R}(u)]=2-\frac{2}{|V|}$

independently of the number of edges (density) of the graph.

As a consequence of the definition of group control (Eq. 4), the weighted sum
of group control for all groups in the graph and the weighted mean also remain
constant at:

$\sum_{S_{i}\in V}|S_{i}|\times
B_{R}(S_{i})=2|V|-2\>\>\quad\text{and}\>\>\quad\frac{1}{|V|}\sum_{S_{i}\in
V}|S_{i}|\times B_{R}(S_{i})=2-\frac{2}{|V|}.$

###  C.2. Efficient version of Algorithm

Algorithm 2 shows an efficient manner to update the pseudo-inverse of the
Laplacian after adding one edge to the graph. Therefore, we avoid the
computation of $\mathbf{L}^{\dagger}$ after every edge addition.
$\mathbf{L}^{\dagger}$ is easily updated using the Woodbury’s formula which is
based on the values of $\mathbf{L}^{\dagger}$ (see Black et al. (2023) for a
proof).

Data: Graph $G=(\mathcal{V},\mathcal{E})$, a protected attribute $SA$, budget
$B$ of total number of edges to add

Result: Interviened Graph
$G^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$

1

2$\mathbf{L}=\mathbf{D}-\mathbf{A}$;

$S_{d}=\operatorname*{argmax}_{S_{i}\forall i\in
SA}\operatorname{\mathsf{R_{tot}}}(S_{i})$ ;

// Identify the most disadvantaged group

$\mathbf{L}^{\dagger}=\sum_{i>0}\frac{1}{\lambda_{i}}\phi_{i}\phi_{i}^{\top}=\left(\mathbf{L}+\frac{\mathbf{1}\mathbf{1}^{\top}}{n}\right)^{-1}-\frac{\mathbf{1}\mathbf{1}^{\top}}{n}$
;

// Pre-computation of $\mathbf{L}^{\dagger}$

3

4Repeat

$\mathbf{R}=\mathbf{1}\operatorname{diag}(\mathbf{L}^{\dagger})^{\top}+\operatorname{diag}(\mathbf{L}^{\dagger})\mathbf{1}^{\top}-2\mathbf{L}^{\dagger}$
;

// Compute effective resistance

$C=\\{(u,v)\mid u\in S_{d}\text{ or }v\in S_{d},(u,v)\notin E\\}$ ;

// Select edge candidates

$\mathcal{E}^{\prime}=\mathcal{E}^{\prime}\cup\arg\max_{(u,v)\in C}R_{uv}$ ;

// Add edge with maximum effective resistance from $C$

5

// Fast update of $\mathbf{L}$ and $\mathbf{L}^{\dagger}$

6
$\mathbf{L}=\mathbf{L}+(\mathbf{e}_{u}-\mathbf{e}_{v})(\mathbf{e}_{u}-\mathbf{e}_{v})^{\top}$;

$\mathbf{L}^{\dagger}=\mathbf{L}^{\dagger}-\frac{1}{1+R_{uv}}\times(\mathbf{L}^{\dagger}_{u,:}-\mathbf{L}^{\dagger}_{v,:})\otimes(\mathbf{L}^{\dagger}_{u,:}-\mathbf{L}^{\dagger}_{v,:})$
;

// updated by Woodbury

7

8Until  _$|\mathcal{E^{\prime}}\setminus\mathcal{E}|=B$_ ;

9return $G^{\prime}$;

Algorithm 2 ERP-Link

##  Appendix D Additional experiments

In this section, we complement the experimental results reported in Section 4,
and we report results on additional experiments.

###  D.1. Group Social Capital Metrics

The experiments presented in the main paper illustrate how edge augmentation
via ERG-Link is able to (1) significantly mitigate the structural group
unfairness (Table 2); and (2) increase the social capital for all the groups
in the graph (Fig. 2). Table 4 depicts the group social capital for each group
after each intervention. Note that the optimal value of
$\operatorname{\mathsf{B_{R}}}$ is to get every group’s control equal to
$2-2/|\mathcal{V}|$.

Table 4. Group Social Capital after Edge Augmentation. The best values are
highlighted in bold. Note how edge augmentation via ERG-Link is able to not
only increase the social capital of the disadvantaged group (females) but also
of the rest of the groups (males).

(a) Facebook (50) Female | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 221.4 | 2.29 | 1.927
Random | 211.5 | 2.26 | 1.927
DW | 199.4 | 1.87 | 1.929
Cos | 190.4 | 1.64 | 1.918
ERG | 138.7 | 0.43 | 1.933

(b) UNC28 (5,000) Female | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 608.6 | 2.11 | 1.994
Random | 435.0 | 1.23 | 1.992
DW | 583.2 | 1.81 | 1.997
Cos | 429.6 | 0.42 | 1.940
ERG | 316.8 | 0.10 | 2.001

(c) Google+ (5,000) Female | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 564.1 | 1.31 | 1.807
Random | 305.1 | 1.07 | 1.824
DW | 558.7 | 1.31 | 1.806
Cos | 230.9 | 0.29 | 1.827
ERG | 145.5 | 0.07 | 1.889

(d) Facebook (50) Male | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 179.8 | 2.25 | 2.034
Random | 172.8 | 2.22 | 2.035
DW | 163.1 | 1.83 | 2.033
Cos | 161.8 | 1.61 | 2.039
ERG | 128.5 | 0.42 | 2.031

(e) UNC28 (5,000) Male | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 586.3 | 2.11 | 2.004
Random | 415.2 | 1.23 | 2.005
DW | 561.0 | 1.81 | 2.001
Cos | 410.6 | 0.41 | 2.043
ERG | 308.0 | 0.09 | 1.998

(f) Google+ (5,000) Male | $R_{tot}\downarrow$ | $\mathcal{R}_{diam}\downarrow$ | $\mathsf{B_{R}}$
---|---|---|---
$G$ | 287.7 | 1.24 | 2.321
Random | 175.7 | 1.03 | 2.293
DW | 284.6 | 1.24 | 2.323
Cos | 144.1 | 0.27 | 2.288
ERG | 108.5 | 0.06 | 2.185

###  D.2. Distribution of Social Capital by Group

For completeness, Fig. 4 illustrates the distributions of all effective
resistances $R_{uv}$ and the node’s social capital metrics
–$\operatorname{\mathsf{R_{tot}}}(u)$,
$\operatorname{\mathcal{R}_{\text{diam}}}(u)$ and
$\operatorname{\mathsf{B_{R}}}(u)$– in the graph before and after the edge
augmentation interventions for each of the groups.

The plots correspond to two different edge augmentation experiments on the
Facebook dataset, with budgets of B=50 and B=5,000 new edges. Edge
augmentation via ERG-Link is able to drastically reduce all effective
resistances of the graph, unlike the other methods and even for the small
budget. Note how there is still a long tail in the distribution of effective
resistances after edge augmentation with the baseline methods, which
illustrates that there are still nodes that struggle to exchange information
even after the intervention.

Regarding the node social capital metrics, edge augmentation via ERG-Link
reduces all $\operatorname{\mathsf{R_{tot}}}(u)$ and
$\operatorname{\mathcal{R}_{\text{diam}}}(u)$, which explains why
$\operatorname{\mathsf{R_{tot}}}(S_{i})$ and
$\operatorname{\mathsf{R_{tot}}}(S_{i})$ is improved for all groups in the
graph, and particularly for the disadvantaged group. Thus,
$\Delta\operatorname{\mathsf{R_{tot}}}$ and
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$ are significantly reduced.

Figure 4. Distribution of $R_{uv}$ and proposed social capital metrics on the
Facebook dataset and after different graph interventions, 50 links in the top
row and 5,000 in the bottom row. Columns show (left) distribution of all
$R_{u}v$ distances, (center-left) distribution of all
$\operatorname{\mathsf{R_{tot}}}(u)$, (center-right) distribution of all
$\operatorname{\mathcal{R}_{\text{diam}}}(u)$, (right) distribution of all
$\operatorname{\mathsf{B_{R}}}(u)$. The distributions for the node metrics are
shown for the two groups according to the protected attribute (gender).

###  D.3. Evolution of Group Social Capital During the Interventions

In this section, we provide additional results regarding the evolution of
group social capital metrics during the graph’s intervention, as initially
shown in Fig. 3. The goal is to analyze the effectiveness of the edge
augmentation methods on both small ($B=50$ edges) and large ($B=5,000$ edges)
budget scenarios. Figs. 5 and 6 show the evolution of both the group social
capital metrics for each group and the structural group unfairness metrics on
the Facebook dataset.

We observe in Fig. 5 how edge augmentation via ERG-Link is able to
significantly improve the group social capital for all groups and reduce all
structural unfairness metrics. In contrast, the baselines fail to do so.

Figure 5. Evolution of group social capital and disparity metrics for both
groups as the number of added edges increases on the Facebook dataset with a
budget of 50 new edges.

Fig. 6 depicts the evolution of group social capital and disparity metrics
when adding 5,000 edges to the Facebook dataset. The more edges we add to a
graph, the denser the graph becomes and therefore the better the information
flow. Thus, one can expect that after a large number of added edges, all
methods behave similarly.

However, we observe some differences. First, the convergence to minimal
isolation and diameter disparities is significantly faster when adding edges
via ERG-Link than any other method. Second, the decrease in
$\operatorname{\mathsf{R_{tot}}}(S_{i})$ is very significant for both groups
(males and females) even after just adding a small number of edges by means of
ERG-Link. Third, regarding group control and control disparity, edge
augmentation via ERG-Link systematically reduces
$\Delta\operatorname{\mathsf{B_{R}}}$ while converging each group control to
the optimal $\operatorname{\mathsf{B_{R}}}(S_{i})=2-2/|\mathcal{V}|$.

We also show in Fig. 7 the evolution of $\operatorname{\mathsf{B_{R}}}(S_{i})$
and $\Delta\operatorname{\mathsf{B_{R}}}$ on the UNC28 dataset with 1,000 edge
additions along with the distribution of node’s control
$\operatorname{\mathsf{B_{R}}}(u)$ after the intervention to showcase an
scenario where ERG-Link is able to reach the optimal control disparity in the
graph, allocating the same amount of control for each group,
$\operatorname{\mathsf{B_{R}}}(S_{i})\approx 2-2/|\mathcal{V}|\>\forall\>i\in
SA\rightarrow\Delta\operatorname{\mathsf{B_{R}}}\approx 0$.

Last but not least, the different baselines do not reach a better behavior
than the random method, neither on the group social capital metrics nor in
terms of structural unfairness. After 5,000 edge additions, the random method
significantly reduces the unfairness metrics
$\Delta\operatorname{\mathsf{R_{tot}}}$ and
$\Delta\operatorname{\mathcal{R}_{\text{diam}}}$ while also achieving decent
rated of $\operatorname{\mathsf{R_{tot}}}(S_{i})$ and
$\operatorname{\mathcal{R}_{\text{diam}}}(S_{i})$ since the budget is high
enough to improve the information flow with no strategy. However, all
baselines struggle to optimize $\Delta\operatorname{\mathsf{B_{R}}}(S_{i})$
and $\operatorname{\mathsf{B_{R}}}(S_{i})$. None of them is able to improve,
and the cosine similarity approach even increased the Control Disparity.

Figure 6. Evolution of group social capital metrics for both groups and
fairness metrics as the number of added links increases, on Facebook dataset
after adding 5,000 edges. Edge augmentation via ERG-Link exhibits a faster
rate of convergence to the optimal scenario than the baselines.

Figure 7. Behavior of node, group control and control disparity
($\operatorname{\mathsf{B_{R}}}(u),\operatorname{\mathsf{B_{R}}}(S_{i}),\Delta\operatorname{\mathsf{B_{R}}}$).
Illustration of the evolution of the group control (left,
$\operatorname{\mathsf{B_{R}}}(S_{i})$) and control disparity (middle,
$\Delta\operatorname{\mathsf{B_{R}}}$) through an edge augmentation with
$B=1,000$ edges on the UNC dataset. Right-most figure: distribution of the
nodes’ control ($\operatorname{\mathsf{B_{R}}}(u)$) for each group. Note how
edge augmentation via ERG-Link yields a control for all groups approaching
their optimal value of $2-2/|\mathcal{V}|$ by reducing the control of the
privileged group (males) while increasing the control of the disadvantaged
group (females).