We live in a connected world where networks be it, social, communication, interaction, or collaboration networks, play an important role. In this paper, we focus on how power is distributed among the nodes of such networks. Specifically, we look at the structural importance of the nodes in a network as measured by the pagerank algorithm. Given two groups of nodes, we say that a network is fair, if the nodes of the two groups hold equally central positions in the network. First, we investigate whether real networks are fair and the conditions that may cause unfairness. Then, we present modifications of the pagerank algorithm such that the computed node importance is both fair and also as accurate as possible. Finally, we propose recommending connections whose additions in the network will improve fairness.
Networks ofer a generic data structure for representing entities and the relationships and
interactions between them. For example, in a social network, nodes correspond to people and
edges to connections between them. In this paper, we look into network fairness. We adopt a
group-based approach [
One measure of node centrality is the degree of the node, i.e, the number of its neighbors.
For example, in a social network degree centrality considers the number of followers. A more
elaborate measure of centrality is provided by the celebrated pagerank algorithm ( ). In
defining the centrality of a node, takes into account the centrality of its neighbors
[
The pagerank algorithm assigns a weight P() to each node that indicates the significance of in the network, with the sum of the weights assigned to all nodes being equal to 1. We assume two groups, the protected group, that we call the red group and the privileged group, that we call the blue group . We will use P() and P() to denote the total weight that assigns to the nodes in the red and blue group respectively. Clearly, P() = 1 − P(). For simplicity, we call P() red pagerank and P() blue pagerank.
We say that there is (pagerank) fairness, if the red pagerank is equal to , i.e., P() = ,
where is a parameter whose value depends on the fairness policy. For example, by setting
= 0.5, we ask that both groups are equally important. As another example, let be he fraction
of nodes that belong to , that is, || = × , where is the total number of nodes. By
setting = , we ask that the red nodes have a share in the weights proportional to their share
in the population, a property also known as demographic parity [
Besides pagerank, we also consider personalized pagerank, where each node assigns a weight P() to each node in the network. P() indicates the significance that node has for node and can be seen as a measure of proximity between source node and node . Again, we use P() and P() to denote the weight that node allocates to the red and blue groups respectively and ask that P() is equal to . Intuitively, fairness of P implies that node weights the red and blue groups fairly. Overall, we can think of P() as a measure of how a specific node weights the red group, while P() captures the weight that the network as a whole places on the red group.
In the following, we address briefly the following research questions: RQ1 Are networks fair and what are the conditions that may cause unfairness? RQ2 Can we modify the pagerank algorithm to produce weights that are both fair and as accurate as possible? RQ3 Can we intervene in the evolution of a network through link recommendations so as to improve fairness?
Previous research has shown that size imbalance between groups, and homophily (here the
tendency to connect with nodes of the same color) may lead to degree unfairness [
To address this question, we generate synthetic networks using the biased preferential
attachment model [
We plot in Figures 1(a) and 2(a) the red pagerank. Note that demographic parity corresponds to the identity line, i.e., P() = . Values above the identity line indicate unfairness towards the blue group, while values below the line unfairness towards the red group. We also plot the red personalized in Figures 1(b)-(d) and 2(b)-(d). We plot two distributions, one for the () of the red nodes (i.e., ∈ ) and one for () of the blue nodes ( ∈ ). Distributions are 00..78 BRleude rkeegd an0.6 Pa0.5 R0.4 0.3 00..67 BRleude rkeedg an0.5 Pa0.4 R0.3 0.2 0.1H0eteroph0i.l3y0 N0e.u5t0ral 0.7H0omophi0ly.90 (c) = 0.3 0. 90 0. 70 0. 50 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
r (a) P() kan000...789 000... 759000 r00.. 1300 re0.6 ag0.5 P d0.4 eR0.3 0.2 0.1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
r (a) P() 00..54 BRleude kPaengR ra0.3 ed0.2 0.1 0.1H0eteroph0i.l3y0 N0e.u5t0ral 0.7H0omophi0ly.90 (b) = 0.1 0.1H0eteroph0i.l3y0 N0e.u5t0ral 0.7H0omophi0ly.90 (c) = 0.3 0.1H0eteroph0i.l3y0 N0e.u5t0ral 0.7H0omophi0ly.90 (d) = 0.5 plotted in the form of violin plots. Demographic parity corresponds to the case in which the two distributions overlap, with their mean on value .
Symmetric case. In case of homophily, ( = 0.7, 0.9), nodes tend to form two clusters, one with red nodes and one with blue nodes sparsely connected to each other. This leads to almost pagerank fair networks (with a very slight unfairness towards the smaller group), but the nodes are personalized pagerank unfair. In case of heterophily ( = 0.1, 0.3), there are no clusters, nodes tend to connect with nodes of the opposite color, and the larger group favors the smaller one. There is pagerank unfairness towards the larger group, and both blue and red nodes are personalized pagerank unfair towards the larger group. This is especially evident when there is large size imbalance (small ).
Asymmetric case. When the red nodes are homophilic ( = 0.7, 0.9), the red group keeps the pagerank to itself. As a result there is both pagerank and personalized pagerank unfairness towards the blue (that is, the neutral) group. When the red nodes are heterophilic ( = 0.1, 0.3), the red group favors the blue group, and as a result, there is both pagerank and personalized pagerank unfairness towards the red (that is, the heterophilic) group.
The only case when there is both pagerank and personalized pagerank fairness is when both groups are neutral ( = 0.5 for both groups) and of similar sizes (r = 0.5) (middle violin plots in Figures 1(d), and 2(d)).
We would like to modify the pagerank algorithm so that the produced weights are fair
independently of whether the network is fair or not. Furthermore, we would like these weights to
be as accurate as possible, that is, as close as possible to the weights assigned by the original
pagerank algorithm. It was shown that the only way to produce both global and personalized
fair weights is by the family of locally fair PR algorithms [
In the simplest form of the locally fair PR
algorithm, called neighbor-based locally fair
PR, when at node , the walk moves with
probability to a red neighbor of , and
with probability 1 − to a blue neighbor of
[
Instead of modifying the PR algorithm to produce fair weights, a more efective intervention
would be to “correct” the network so that the original PR algorithm produces fair weights. The
growth of many real-world networks is afected by link recommendations [
It was shown that the most important edges in terms of fairness are edges that connect nodes whose neighborhoods are of a “diferent color”. It was also shown that in general the characteristics of the target node of the recommended link have a stronger correlation with fairness than the characteristics of the source node. Among these characteristics, the most relevant ones are the group (i.e., color) and the personalized PR of the target node.
In this short paper, we have summarized our previous work on centrality fairness. An
important research question is to study how centrality unfairness is reflected on the fairness of
downstream ML tasks. For example, is pagerank unfairness reflected in graph embeddings or in
GNN models? Along this line, the efect of unfairness on network processes such as difusion
[
It is also important to view fairness in networks from an interdisciplinary perspective.
Understanding the confounding social and psychological factors that lead to network unfairness
would help in designing more relevant link recommendation algorithms. Furthermore, studying
both the short term and long term efect that network unfairness may have in the lives of
individuals would be instrumental [
The author was supported by the “ARCHIMEDES Unit: Research in Artificial Intelligence, Data Science and Algorithms” OPS code 5154714 within the framework of the National Recovery and Resilience Plan “Greece 2.0” with funding from the European Union – NextGenerationEU.