# Inequality and Inequity in Network-based Ranking and Recommendation
Algorithms

Lisette Espín-Noboa  GESIS – Leibniz-Institute for the Social Sciences,
Cologne, Germany  University of Koblenz-Landau, Koblenz, Germany  Central
European University, Vienna, Austria  Claudia Wagner  GESIS – Leibniz-
Institute for the Social Sciences, Cologne, Germany  HumTec Institute, RWTH
Aachen University, Aachen, Germany  Markus Strohmaier  GESIS – Leibniz-
Institute for the Social Sciences, Cologne, Germany  HumTec Institute, RWTH
Aachen University, Aachen, Germany  Fariba Karimi  Complexity Science Hub,
Vienna, Austria<EMAIL_ADDRESS>
###### Abstract

Though algorithms promise many benefits including efficiency, objectivity and
accuracy, they may also introduce or amplify biases. Here we study two well-
known algorithms, namely PageRank and Who-to-Follow (WTF), and show under
which circumstances their ranks produce inequality and inequity when applied
to directed social networks. To this end, we propose a directed network model
with preferential attachment and homophily (DPAH) and demonstrate the
influence of network structure on the rank distributions of these algorithms.
Our main findings suggest that (i) inequality is positively correlated with
inequity, (ii) inequality is driven by the interplay between preferential
attachment, homophily, node activity and edge density, and (iii) inequity is
mainly driven by homophily. In particular, these two algorithms amplify,
replicate and reduce inequity in top ranks when majorities are homophilic,
neutral and heterophilic, respectively. Moreover, when inequity is amplified,
minorities may improve their visibility in the rank by connecting
strategically in the network. For instance, by increasing their homophily when
majorities are also homophilic. These findings shed light on social and
algorithmic mechanisms that hinder equality and equity in network-based
ranking and recommendation algorithms.

###### keywords:

Preferential Attachment, Homophily, Directed Networks, PageRank, Who-To-
Follow, Rank inequality, Visibility of minorities in top ranks

## Introduction

Online social networks and information networks have become integral parts of
our everyday life. However, the opportunities offered by such networks are
often constrained not only by our previous interactions [1, 2, 3, 4, 5], but
also by algorithms. For instance, algorithms could make some people or content
more visible than others via ranking or recommendations [6]. In this regard,
search engines and recommender systems are increasingly used for various
applications such as whom to follow, whom to cite, or whom to hire. Typically,
these applications use algorithms to order items (e.g., people and academic
papers) based on “importance” or “relevance”, and may therefore produce social
inequalities by discriminating certain individuals or groups of people in top
ranks. In fact, it has been shown that recommender systems such as Who-to-
Follow (WTF) [7] tend to increase the popularity of users who are already
popular [8, 9, 6]. A similar effect has been found in PageRank [10], where
nodes in high ranks stabilize their position and give little opportunity to
other nodes to occupy higher positions [11]. This tendency towards the
“popular” arises because these algorithms harness structural information, in
particular the in- and out-degree of nodes.

However, social networks are complex systems and many other structural
properties may also alter the distribution of nodes and groups in the ranking.
For example, previous studies have shown that homophily affects the visibility
of minorities in degree rankings [12] and people recommender systems [13].
Consequently, it can reinforce societal issues such as the glass ceiling
effect [14, 15, 16] and the invisibility syndrome [17]. Despite these
findings, little is known about the extent to which the combination of
multiple structural properties can alter the visibility of minorities in top
ranks from ranking and recommendation algorithms. A further complication is
that debiasing ranking outcomes and making them fair is very challenging.
First, fairness is an essentially contested construct that has different
theoretical understandings in different contexts [18]. Second, data can be
biased due to missing data [19], selective exposure [20], historical
prejudices or implicit bias [21, 22]. Third, biases in ranking can be
mitigated in different ways [23]: by intervening on the score distribution of
candidates [24], on the ranking algorithm [25], or on the ranked outcome [26].
While most of these studies tackle fairness in ranking, they do not explore
the effects of networked data in ranking. This paper is a step towards this
goal. Since such algorithms are so deeply involved in social, economic and
political processes, we need to first understand how our connections affect
them to then apply appropriate interventions towards fair results.

To this end, we propose DPAH, a network model that generates directed scale-
free networks with binary-attributed nodes. It encodes two main mechanisms of
edge formation found in social networks: homophily and preferential attachment
[27, 28, 29]. Moreover, it allows to control for the fraction of minorities,
edge density, and the skewness of the out-degree distribution. By using this
model we systematically study how these structural properties of social
networks impact the ranking of nodes in PageRank and WTF. In particular, we
investigate two ranking issues, inequality and inequity, and show how they get
affected by the ranking algorithm together with the type of network. We
measure inequality by quantifying the skewness of the rank distribution of
nodes that PageRank and WTF produce, and inequity as how well-represented the
minorities are in the top of the rank compared to the proportion of minorities
in the network. In this work we study both ranking issues and measure their
correlation. Furthermore, we quantify them globally using the whole rank
distribution, and locally within each top-k% rank. The goal is to identify
both the overall inequality and inequity trend that these algorithms produce,
and the tipping points where minorities start gaining visibility in the top of
the rank.

As an example, consider the directed networks shown in Figure 1. Every column
represents a network with two types of nodes, minority (orange) and majority
(blue), and different levels of homophily within groups. Homophily $h$, is a
parameter ranging from 0 to 1 and determines the tendency of two nodes of the
same color to be connected. $h_{MM}$ and $h_{mm}$ represent homophily within
majorities and minorities, respectively. When nodes are ranked using PageRank
(second row), the position of the minorities in the rank varies
systematically. For instance, when majorities are heterophilic ($h_{MM}=0.2$,
columns a and b), minorities often appear at the top (+). In contrast, when
majorities are homophilic ($h_{MM}=0.8$, columns d and e), minorities tend to
appear at the tail of the rank (-). Next, we explain this systematic ranking
behavior in top ranks by further varying the structure of the network.

Figure 1: Inequality and inequity: Every column represents a network with
certain level of homophily. All networks contain $20$ nodes: 20% belong to the
minority group (orange), and 80% to the majority group (blue). Edges follow a
preferential attachment with homophily mechanism. The top row shows the graph
and the level of homophily within groups ($MM$: majorities and $mm$:
minorities). The second row shows all nodes in descending order (from + to -)
based on their PageRank scores. The third row represents the rank inequality:
Gini coefficients of the rank distribution for every top$-k\%$ (black line).
Giniglobal refers to the Gini coefficient of the entire rank distribution
(i.e., at top-$100\%$). We see that the lower the $k$, the lower the Gini of
the rank distribution. The bottom row represents the rank inequity: Percentage
of minorities found in each top-$k\%$ of the rank distribution (orange line).
$ME$ is the mean error of these percentages compared to a fair baseline or
diversity constraint (i.e., how much the orange line deviates from the dotted
line across all top-k’s). Here we see three main patterns: (a,b) When the
majority group is heterophilic, minorities are on average over-represented,
$ME>0.02$. (d,e) When majorities are homophilic, minorities are on average
under-represented, $ME<-0.02$. (c) When both groups are neutral, the observed
fraction of minorities is almost as expected, $ME\approx 0$.

## Results

### Inequality and inequity in ranking

Inequality refers to the dispersion or distribution of importance among
individuals. This importance is the ranking score assigned to every node by
the algorithm. We compute the Gini coefficient of the rank distribution to
measure how far the ranking scores of individuals deviate from a totally equal
distribution. As shown in Figure 2, a very low Gini score ($\text{Gini}<0.3$)
means that all individuals in the network (or in the top-k% for local
inequality) are very similar with respect to their ranking scores. If the Gini
score is extremely high ($\text{Gini}\geq 0.6$), it means that only a few
individuals capture most of the rank. In other words, the rank distribution is
very skewed. Values in between ($0.3\leq\text{Gini}<0.6$) represent moderate
skewed distributions. From our example in Figure 1, we see that PageRank on
average generates moderate skewed ranking distributions for all the depicted
networks ($Gini_{global}\approx 0.5$). However, for very small top-k%’s, the
Gini is very low. This means that the top individuals possess very similar
ranking scores.

Inequity refers to group fairness. In particular, it measures the error
distance between the fraction of minorities in the top-k% and a given fair
baseline (e.g., a diversity constraint or quota). This baseline may be
adjusted depending on the context of the application [30, 31, 23]. Here, a
ranking is fair when its top-k% preserves the proportional representation of
groups in the network (i.e., disparate impact fairness or realistic overview
[32]). Therefore, the error represents the local inequity per top-k%, and $ME$
the mean of these errors across all top-k% ranks or global inequity. As shown
in Figure 1 last row, we measure the local inequity in two steps. First, we
compute the fraction of minorities that appear in each top-k% rank (orange
line). Second, we compute the error between the observed fraction of
minorities in each top-k% rank and a fair baseline (e.g., the actual fraction
of minorities in the network, in this example $20\%$). Then, we average these
error scores across all top-k% ranks to determine the global inequity score
($ME$ values). As shown in Figure 2, a fair ranking is such that $-\beta\leq
ME\leq\beta$ (green region). The value of $\beta$ is arbitrary, and allows for
a smooth definition of “low mean error” or fairness. We set $\beta=0.05$. If
$ME>\beta$, then minorities are over-represented (blue region) in the top-k%.
If $ME<-\beta$, then they are under-represented (red region), otherwise the
ranking is representing very well the minorities in the top of the rank.
Alternatively, we can say that the top rank (i) replicates the levels of
inequity from the network when $ME$ is very low, (ii) amplifies or worsens
inequity and harms the minority group when $ME<-\beta$, and (iii) reduces
inequity by increasing the visibility of minorities when $ME>\beta$.

Finally, we refer to the relationship between inequality and inequity as
disparity. For example, if a ranking distribution achieves $Gini=0.65$ and
$ME=0.5$, we say that the disparity lies in the region $III$ (dark blue),
i.e., high inequality and high inequity, see Figure 2.

Figure 2: Regions of disparity. We measure inequality (y-axis) as the skewness
of the rank distribution, and inequity (x-axis) as the mean differences
between the proportional representation of groups in top-k% ranks and the
network. Highly skewed distributions lie in regions I to III (darker colors),
and fair rankings, where minorities are well represented in the top ranks, lie
in regions II, V, VIII (green). We set $\beta=0.05$ which is arbitrary and
allows for a flexible region of group fairness.

### Growth network model with homophily and directed links

In order to examine the effect of homophily on the ranking of minorities in
social networks, first we need to develop realistic network models that
capture not only a variety of group mixing, but also the directionality of
links. Many online social networks are directed networks in their nature,
including the follower-followee structure on Twitter and the hyperlink
structure of the Web. Directed links are the key components of many algorithms
such as PageRank and Who-to-Follow.

To this end, we propose a directed network model with adjustable homophily and
minority size, and we refer to it as DPAH (directed preferential attachment
with homophily network growth model). We generate these networks by adjusting
the fraction of minorities $f_{m}\in\\{0.1,0.2,0.3,0.4,0.5\\}$, and the in-
class or group homophily $h_{MM},h_{mm}\in\\{0.0,0.1,...,1.0\\}$. We refer to
the minority group as $m$, and to the majority group as $M$. Additionally, we
assign an activity score to every node. This score is drawn from a power-law
distribution and determines with what probability the existing node becomes
active and creates additional links to other nodes. This means that more
active nodes possess higher out-degree (see Methods for more details).

Figure 3 (a) illustrates the DPAH model. At time $t$, a source node $p$ is
selected with a probability proportional to its activity. Then, $p$ connects
to an existing node $j$ with a probability related to their pair-wise
homophily $h_{pj}$ and preferential attachment that is based on $k^{in}_{j}$,
the in-degree of node $j$. By this process, we ensure that the out-degree and
in-degree distribution of nodes follow a seemingly power-law distribution that
have been observed in many large social networks [33]. The algorithm stops
once the network reaches an expected density. Note that source nodes can be
either new nodes joining the network for the first time (e.g., node $p$ at
time $t$) or existing nodes (e.g., node $l$ at time $t+1$). Once a source node
connects to a target node successfully, the source node becomes available in
the next rounds to become a target candidate. This means that in the beginning
the model faces a cold start problem since there are no existing (target)
nodes to connect to. Thus, the first 1% of new edges are between a source node
(drawn from the activity distribution) and any other node with probability as
in Equation 3.

Figure 3: DPAH model and ranking of nodes. a) Illustration of the directed
network model with preferential attachment and homophily (DPAH). At time $t$,
a source node $p$ is drawn from a power-law (activity) distribution and joins
the network for the first time. Then, a target node $j$ is drawn based on the
in-degree distribution and the pair-wise homophily $h_{pj}$. At time $t+1$, a
new edge is added between already existing nodes $l\rightarrow o$ based on the
same mechanism. The algorithm repeats until a desired edge density is
fulfilled. b) The PageRank score of each node is shown under $PR$. Nodes in
each top-k% of the rank are grouped based on the unique PageRank scores. In
this example, the top-60% of nodes concentrate most of the PageRank and their
scores are somewhat similar (i.e., low Gini). Also, the ranking is fair from
top-80% onwards, since they capture the same fraction of minorities as in the
population, 25%. Local values are measured per top-k%, and global values are
measured using the whole distribution for inequality (Gini), and the average
across all top-k% ranks for inequity (mean error).

### How do homophily and directional links influence the ranking of minorities
globally and locally?

##### Global disparity.

We corroborate that the Gini coefficient of the rank distributions is large,
$Gini\geq 0.6$ (regions I, II and III; dark colors) for both PageRank (see
Figure 4) and WTF (see Figure S1 in the supplementary material). Moreover, we
find that on average: (i) Balanced networks ($f_{m}=0.5$) can get a fair
ranking (green) when both groups possess the same homophily scores
($h_{MM}=h_{mm}$). The same applies for neutral networks ($h_{MM}=h_{mm}=0.5$)
regardless of their fraction of minorities ($f_{m}\leq 0.5$). (ii) When the
fraction of minorities decreases ($f_{m}<0.5$), groups can be fairly
represented in the rank in two regimes: First, when both groups are
homophilic, homophily within minorities must be higher than homophily within
majorities ($h_{mm}>h_{MM}>0.5$). Second, when both groups are heterophilic,
homophily within majorities must be higher than homophily within minorities
($h_{mm}<h_{MM}<0.5$) to balance the importance of groups.

Figure 4: The effects of homophily and fraction of minorities in the global
disparity of PageRank. Columns represent the fraction of minorities in the
network, x-axis indicates the homophily within minorities, and y-axis the
homophily within majorities. Colors denote the region where the disparity lies
in according to our interpretation in Figure 2. First, we see that, on
average, there is never low global inequality (i.e., regions IV to IX —lighter
colors— do not appear). This makes sense because these are scale-free
networks. Second, depending on the level of homophily within groups,
minorities on average can be under-represented (region I, red), or over-
represented (region III, blue), or well-represented (region II, green). For
example, in the balanced case $f_{m}=0.5$, minorities are on average under-
represented when $h_{MM}>h_{mm}\geq 0.3$.

##### Local disparity.

We also compute inequality and inequity within each top-k% rank in order to
see to what extent they change when k% increases. In the case of PageRank, we
see in Figure 5 that inequality varies (i.e., from light to dark colors) in
different regimes mainly due to the size of $k$ (x-axis), and inequity due to
the interplay between homophily within groups, $h_{MM}$ and $h_{mm}$. In
particular: (i) Only at the top-5% of the rank we see a few cases of low
inequality (regions VII, VIII and IX; very light colors), this means that
nodes at the very top possess very similar ranking scores, but they are very
far from the rest of the population, i.e., the larger the top-k%, the higher
the Gini. This holds in WTF up to roughly the top-30% (see Figure S2 in the
supplementary material). Overall, PageRank converges to high inequality faster
than WTF. (ii) Inequity (regions: red, blue, green) is consistent across all
top-k% ranks for both algorithms. In other words, if the ranking algorithm
favors or harms one group in the top-5%, it will continue to do so until
converging to the fair regime (regions II, V, VIII; green). With a few
exceptions, this fair regime is only reached when $k$ is very large. For
example, if a minority group is under-represented at the top-5%, it will
remain under-represented at the top-80% (see $h_{mm}=0.1$ and $h_{MM}\geq 0.7$
in Figure 5 for PageRank, and Figure S2 in the supplementary material for
WTF). (iii) Minorities are often over-represented when majorities are
heterophilic $h_{MM}<0.5$; (regions III, VI, IX; blue). In contrast,
minorities are often under-represented when majorities are homophilic
$h_{MM}>0.5$ (regions I, IV, VII; red). This is consistent up to $\approx$
top-$80\%$ for both algorithms.

In summary, our results suggest that the size of $k$ does not have an
influence on inequity. This means that if the algorithm amplifies inequity at
the top-5%, it will also amplify inequity at larger top-k%’s. Therefore,
increasing the selection pool (larger k) does not improve the representation
of minorities. This can be explained by the fact that the preferential
attachment mechanism disproportionately affects nodes ranking [11].

Figure 5: The effects of homophily and fraction of minorities in the local
disparity of PageRank. Columns represent the fraction of minorities (10%, 30%
and 50%) and rows show homophily within minorities (from top to bottom:
heterophilic, neutral and homophilic). The x-axis denotes the top-k% rank and
the y-axis shows homophily within majorities. Colors refer to the regions of
disparity introduced in Figure 2. One can see that the minority suffers most
(red) when the majority is homophilic and the minority is either heterophilic
or neutral. Moreover, inequality is lowest (very light colors) only for a few
cases at top-5%. This means that the top best ranked nodes are very similar
and their ranks are far from the majority of nodes (i.e., due to preferential
attachment). Moreover, inequity remains mostly consistent regardless of
top-$k$%. In other words, if the ranking algorithm favors one group in the
top-5% (e.g., red or blue), it will continue to do so until entering the fair
regime (green).

##### Correlation and feature importance.

We compute the Spearman correlation between inequality and inequity, and
conduct a random forest regression to measure the importance of each network
property on both inequality and inequity values. Results are shown in Table 1
for PageRank and Table S1 (in the supplementary material) for WTF.

We find that inequality and inequity are positively correlated in both global
and local regimes. In other words, the skewer the rank distribution (i.e.,
high Gini), the more unfair with either group (i.e., mean error far from
zero), and vice versa. This correlation is stronger and more significant in
PageRank than in WTF.

Global inequality ($gini$) is mainly explained by both homophily values,
whereas global inequity ($me$) is mainly driven by homophily within
majorities. Local inequality ($gini_{k}$), on the other hand, is mainly
explained by the top-$k\%$ rank, and local inequity ($me_{k}$) is mainly
explained by the homophily within the majority group.

Table 1: 10-fold cross-validation for PageRank: We use a Random Forest Regressor to assess model performance and feature importance. $R^{2}$ values are averages (and standard deviations) across all networks. Features are ranked in descending order based on their mean importance (from left to right) and highlighted if their importance represents more than 50% of the total importance. Corr shows the Spearman correlation between inequality and inequity scores (p-values $\approx 0$). Type | Outcome | Corr | $R^{2}$ | Feature importance
---|---|---|---|---
Global | $gini$ | 0.41 | 0.92 (0.009) | $\boldsymbol{h_{MM}}\rightarrow\boldsymbol{h_{mm}}\rightarrow f_{m}$
$me$ | 0.99 (0.001) | $\boldsymbol{h_{MM}}\rightarrow h_{mm}\rightarrow f_{m}$
Local | $gini_{k}$ | 0.21 | 0.95 (0.002) | $\boldsymbol{k}\rightarrow h_{MM}\rightarrow h_{mm}\rightarrow f_{m}$
$me_{k}$ | 0.99 (0.001) | $\boldsymbol{h_{MM}}\rightarrow h_{mm}\rightarrow k\rightarrow f_{m}$

These results are in agreement with what we see in previous figures; Even
though majority nodes produce most of the inequality and inequity in the rank,
their interplay with minority nodes can change or intensify the direction of
bias. In fact, both homophily values can explain $75\%$ (49%) of $gini$, the
global inequality in PageRank (WTF), $92\%$ (88%) of $me$, the global
inequity, and $78\%$ (74%) of $me_{k}$, the local inequity. However, the
top-k% rank together with the homophily within majority nodes explain $84\%$
(86%) of $gini_{k}$, the local inequality.

### How do different social mechanisms of edge formation contribute to
disparity?

So far, we show that PageRank and WTF on our network model produce high
inequality and a wide-range of possible inequity outcomes. How much of that
inequality or inequity was a product of homophily or preferential attachment?
To see the effects of these two mechanisms alone, we generate new networks by
turning on and off the homophily and preferential attachment features (see
Methods for the details of the models).

Figure 6 shows the inequality and inequity produced by PageRank on a variety
of models: DPA (Directed Preferential Attachment), DH (Directed Homophily),
Random, and DPAH (see Figure S3 in the supplementary material for WTF).
Results from both algorithms show that networks whose nodes connect through
preferential attachment (DPA) produce on average higher inequality compared to
DH and Random. However, when preferential attachment is combined with
homophily (DPAH), this inequality increases even further. Additionally, we see
that WTF produces higher inequality compared to PageRank (see section A.3 in
the supplementary material for more details). Inequity, on the other hand, is
mainly driven by homophily. This means that, homophily (DPAH and DH)
influences both, inequality and inequity in both algorithms.

Figure 6: The effects of homophily and preferential attachment in the global
disparity of PageRank. We generated directed networks using four different
models of edge formation. DPA: only preferential attachment. DH: only
homophily. DPAH: our proposed model that combines DPA and DH. Random: a
baseline where nodes are connected randomly. We see the following patterns:
(i) Homophily (DH) produces a moderate-to-high level of inequality
($0.3<Gini<0.8$), while preferential attachment (DPA) produces a consistent
moderate inequality ($Gini\approx 0.5$). When both mechanisms are combined
(DPAH), the rank inequality increases even further ($0.7<Gini<0.9$). (ii)
Random and Preferential attachment (DPA) are always fair ($ME=0$), while in
the cases where homophily is involved (DH and DPAH) inequity is often high
($|ME|>\epsilon$). Thus, in general preferential attachment is the main driver
of inequality, while homophily influences both inequality and inequity.

Note that in Figure 6, we fixed the activity of nodes to
$\gamma_{M}=\gamma_{m}=3.0$. However, when we set these parameters to
$\gamma_{M}=\gamma_{m}<3.0$ (lower values), inequality decreases, see Figure
S4 in the supplementary material. Additionally, in Figure S5 in the
supplementary material, we see that edge density also plays a role in the
inequality produced by PageRank and WTF. This means that, by further adjusting
these two parameters (node activity and edge density), we would expect changes
only to inequality since inequity is mainly affected by homophily as we saw
before.

### Strategies towards a fair ranking

Results from both algorithms show that while the homophily within majorities
is the main driver for inequality and inequity, minorities may overcome unfair
rankings by connecting strategically in the network. In general, when
majorities are homophilic $h_{MM}>0.5$, minorities should increase their
homophily such that $h_{mm}>h_{MM}$. When majorities are (somewhat) neutral
($h_{MM}=0.5\pm 0.1$), minorities may connect arbitrarily with any group
without being too homophilic, otherwise they will become over-represented in
the rank. Finally, when majorities are heterophilic $h_{MM}<0.5$, one solution
to achieve a fair rank is to increase the size of the minority group, and make
sure that both groups behave similarly in terms of homophily ($h_{MM}\approx
h_{mm}$). Otherwise, minorities will be over-represented regardless of their
in-group homophily. Note that these “strategies” without algorithmic
intervention may work in scenarios such as a citation or collaboration
networks, but they might not work in other scenarios. In such cases, we need
additional recommender systems to help under-represented groups discover those
“strategic” links that will help them climb to higher ranks.

## Discussion and Future Work

In this work we have proposed a systematic study to measure the inequality and
inequity produced by PageRank and Who-To-Follow (WTF). Our approach
disentangles the effect of network structure on the rank distributions of
these two algorithms by using synthetic networks. By doing so, we control for
the properties of the network and measure how these changes affect the
rankings. In particular, we studied six prominent structural properties of
social networks: homophily, preferential attachment, fraction of minorities,
edge density, node activity and the directionality of links.

Consequently, our systematic study makes PageRank and Who-To-Follow
interpretable and explainable. Our results show that the systemic bias
produced by these algorithms in the rank—in particular inequity—is mainly due
to homophily imbalance ($h_{MM}\gg h_{mm}$ or $h_{mm}\gg h_{MM}$). A potential
avenue to reduce inequity is to create synthetic connections during the
ranking process as it is done for correcting the class imbalance problem in
supervised learning [34]. Additionally, our results show the necessary
conditions to achieve a fair rank. These conditions can be implemented in
ranking and recommendation algorithms to strategically adjust the importance
of connections in a given network. In certain applications such as citation or
collaboration networks, these strategies can be recommended through additional
recommendation algorithms. For instance, recommender systems could suggest
relevant articles not only based on popularity and (keyword) similarity but
also based on fairness by fulfilling diversity constraints. Finally, further
research can investigate other social mechanisms of edge formation that have
been seen in social networks such as clustering [35], transitivity [36], and
reciprocity [37]. Similarly, other structural properties such as monophily
[38] and second order homophily [39] can be studied to measure their influence
on ranking.

## Conclusions

In this work we have investigated under which conditions PageRank and Who-To-
Follow (WTF) replicate, amplify or reduce inequality and inequity in top
ranks. In particular, given the rank distribution produced by these
algorithms, we computed inequality as the dispersion among individuals in
terms of ranking scores, and inequity as whether minorities are over-, under-
or well-represented in top ranks compared to their representation in the
network. We studied these two metrics separately and in combination to better
understand the mechanisms that can explain them.

To that end, we proposed DPAH, a growth network model that allows to generate
realistic scale-free directed networks with different levels of homophily,
fraction of minorities, node activity, and edge density. In these networks, we
found that both inequality and inequity are positively correlated and mainly
driven by the homophily within majorities. This means that, when the majority
group is highly homophilic, the minority group is under-represented in top
ranks. Also, when the majority is highly heterophilic, the minority benefits
tremendously since it is over-represented in the top-k%. However, minorities
can overcome these disparities by connecting strategically with others. Thus,
equity in ranking is a trade-off between homophily and the fraction of
minorities.

Our systematic study makes PageRank and Who-to-Follow explainable and
interpretable to help data scientists understand and estimate the disparity
that these algorithms produce given the structure of networks, which is key
for proposing targeted interventions. We hope our results create awareness
among majority and minority groups about these disparities since they may
replicate and even amplify the biases found in social networks.

## Data and Methods

### Synthetic networks

We propose DPAH, a directed preferential attachment with homophily network
growth model, and generate networks with $n=2000$ number of nodes, edge
density of $d=0.0015$, and adjust five network properties: fraction of
minorities $f_{m}\in\\{0.1,0.2,0.3,0.4,0.5\\}$, in-class or group homophily
$h_{MM},h_{mm}\in\\{0.0,0.1,...,1.0\\}$, and the power-law exponents of the
activity distributions $\gamma_{M}=\gamma_{m}=3.0$. Each combination of
network structure is generated $10$ times, nodes are ranked using PageRank and
WTF separately, and inequality and inequity scores are computed and averaged
accordingly for each algorithm.

#### Directed network

We define a directed network as: Let $G=(V,E,C)$ be a node-attributed
unweighted graph with $V=\\{v_{1},...,v_{n}\\}$ being a set of $n$ nodes,
$E\subseteq V\times V$ a set of $e$ directed edges, and
$C=\\{c_{1},...,c_{n}\\}$ a list of binary class labels where each element
$c_{i}$ represents the class membership of node $v_{i}$. The fraction of
minorities $f_{m}$ captures the relative size of the minority class—with
respect to $C$—in the network. We refer to the minority group as $m$, and to
the majority group as $M$. A network is _balanced_ when all class labels have
the same number of nodes ($f_{m}=0.5$), otherwise it is _unbalanced_
($f_{m}<0.5$).

In order to generate directed links, inspired by the activity-driven network
model [40], we assign an activity score to each node that determines with what
probability the existing node becomes active and creates additional links to
other nodes. It has been shown that in empirical networks the activity of the
nodes follows a power-law distribution [40]. Therefore, we assign an activity
to each node drawn from a power-law distribution. Note that each group possess
its own activity distribution and they are defined by its power-law exponent
$\gamma_{M}$ and $\gamma_{m}$ for majority and minority nodes, respectively.

Then, the probability of connecting a source (active) node $v_{i}$ to a target
node $v_{j}$ (or in other words the probability of connecting to $v_{j}$ given
the source node $v_{i}$) is explained by any of the following three mechanisms
of edge formation.

#### Preferential Attachment (DPA)

Also known as the rich-get-richer effect or cumulative advantage in social
networks [41, 29]. It indicates that nodes tend to connect to popular nodes.
We define popularity as the in-degree of the node. Therefore, the probability
that a source node $v_{i}$ connects to a target node $v_{j}$ is proportional
to the in-degree of the target node $v_{j}$.

$P(i\to j)=P(j|i)=\frac{k^{in}_{j}}{\sum_{l}k^{in}_{l}}$ (1)

#### Homophily (DH)

It is the tendency of individuals to connect (or interact) with similar others
[28, 42]. Thus, the probability that a source node $v_{i}$ connects to a
target node $v_{j}$ is driven by the homophily between their classes $c_{i}$
and $c_{j}$. We assign a homophily value to each dyad based on pre-defined
homophily parameters within majorities and minorities, $h_{MM}$ and $h_{mm}$,
respectively. Homophily values range from $0.0$ to $1.0$. If the homophily
value is high, that means that nodes of the same class are attracted to each
other more often than nodes of different attributes. Nodes of the same class
with homophily $h_{aa}=0.5$ are referred to as _neutral_ (i.e., they connect
randomly to either class), otherwise they are _heterophilic_ if $h_{aa}<0.5$
(i.e., more likely to connect to the other class), or _homophilic_ when
$h_{aa}>0.5$ (i.e., more likely to connect to the same class).

$P(i\to j)=P(j|i)=\frac{h_{ij}}{\sum_{l}h_{il}}$ (2)

#### Preferential Attachment with Homophily (DPAH)

We propose DPAH111DPAH stands for: Directed network with Preferential
Attachment and Homophily., a directed growth network model with adjustable
homophily and fraction of minorities. This mechanism combines DPA and DH, and
is an extension of the BA-Homophily model [12].

$P(i\to j)=P(j|i)=\frac{h_{ij}k^{in}_{j}}{\sum_{l}h_{il}k^{in}_{l}}$ (3)

Note that DPA and DH are especial cases of DPAH where only the in-degree
mechanism varies. This means that, the out-degree distribution remains the
same as in DPAH: it is driven by the activity model. Additionally, we include
a random model where both source and target nodes are chosen at random (i.e.,
Erdős-Rényi model). Table 2 shows the parameters adjusted in each model.
Number of nodes $n$ and edge density $d$ are arbitrary in the sense that they
are not part of the edge formation mechanism. Thus, we fix them to make a fair
comparison across all models.

Table 2: Model parameters: Check marks denote that a given model (column) requires a particular parameter (row): number of nodes $n$, fraction of minorities $f_{m}$, edge density $d$, in-group homophily $h_{aa}$, and the power-law exponent of the activity distribution $\gamma$. Sub-indices $M$ and $m$ refer to the majority and minority groups, respectively. The difference between DH and DPAH is the preferential attachment (in-degree) mechanism. All models produce directed networks. | Random | DPA | DH | DPAH
---|---|---|---|---
$n$ | ✓ | ✓ | ✓ | ✓
$f_{m}$ | ✓ | ✓ | ✓ | ✓
$d$ | ✓ | ✓ | ✓ | ✓
$h_{MM}$ | - | - | ✓ | ✓
$h_{mm}$ | - | - | ✓ | ✓
$\gamma_{M}$ | - | ✓ | ✓ | ✓
$\gamma_{m}$ | - | ✓ | ✓ | ✓

### Ranking and Recommendation algorithms

There exist a variety of ranking and recommendation algorithms that follow
different strategies depending on the nature of the problem. For instance, in
information systems, items such as content, Web pages, and products are ranked
to recommend users what to read or buy [43]. In social networks, however,
people are ranked to identify their hierarchy or importance [44, 45, 46], and
recommended to other users in order to establish new connections [47, 48, 49,
50]. These rankings and recommendations are based on algorithms that often
rely on whom we are already connected with. In this work, we focus on two such
algorithms widely used in practice [51]: PageRank [10] and Who-to-Follow (WTF)
[7]. While PageRank determines the global ranking of nodes in comparison with
all other nodes, WTF deals with ranking nodes in a node level and thus remains
a local measure. For that reason, we focus on these two algorithms to capture
both dimensions.

#### PageRank

It was invented to rank all web pages in the Web [10], and has been used in
several applications [51]. For example, to study citation and co-authorship
networks [52, 53, 54]. PageRank assigns an importance score to every single
node in a network. This score takes into account the number and quality of
incoming links of each node. The PageRank of node $i$ is defined as follows:

$PR(i)=(1-\alpha)+\alpha\sum_{j\in N_{i}}\frac{PR(j)}{k^{out}_{j}}$ (4)

where $i\in G$, $N_{i}$ represents all neighbors of $i$ (e.g., all nodes $i$
points to), and $k^{out}_{j}$ the out-degree of node $j$. The damping factor
$\alpha$, or probability of following links using a Random Walker, is set to
$0.85$ as suggested by Brin and Page [55]. We use the fast-pagerank [56]
python package to compute the PageRank score of all nodes using sparse
adjacency matrices.

#### Who-To-Follow (WTF)

This recommendation algorithm was created and used by Twitter to suggest new
people to follow [7]. It is based on SALSA [57] which in turn is based on
Personalized PageRank [58]. In a nutshell, for each user $u$, the algorithm
looks for its circle of trust, which is the result of an egocentric random
walk (similar to personalized PageRank) [7]. Then, based on this circle-of-
trust, the algorithm ranks all users that are not yet friends with $u$ but are
connected through the circle of trust. Then, we take the top-k of these
(recommended) users, and add up the counter of being selected as a
recommendation to each of them. This is done for every node $u$ in the
network. At the end, the rank of each node encodes the number of times a user
was suggested as a recommendation across all nodes in the network. Thus, the
WTF score for each node is defined as follows:

$WTF(i)=\sum_{j\in V}\mathds{1}_{SALSA(j)}(i)$ (5)

where $SALSA(j)$ refers to the top-k users the SALSA algorithm recommends to
node $j$. In this work we select the top-$10$ users as recommendations.
$\mathds{1}_{A}(x)$ denotes the indicator function or boolean predicate
function to test set inclusion (i.e., whether $x\in A$).

## References

  * [1] Burt, R. S.  Positions in networks.  _Social forces_ 55, 93–122 (1976).
  * [2] Coleman, J. S.  Social capital in the creation of human capital.  _American journal of sociology_ 94, S95–S120 (1988).
  * [3] Burt, R. S.  The social structure of competition.  _Networks in the knowledge economy_ 13, 57–91 (2003).
  * [4] Morselli, C.  Career opportunities and network-based privileges in the cosa nostra.  _Crime, Law and Social Change_ 39, 383–418 (2003).
  * [5] Bottero, W. & Crossley, N.  Worlds, fields and networks: Becker, bourdieu and the structures of social relations.  _Cultural sociology_ 5, 99–119 (2011).
  * [6] Abdollahpouri, H., Mansoury, M., Burke, R. & Mobasher, B.  The unfairness of popularity bias in recommendation.  _arXiv preprint arXiv:1907.13286_ 2440 (2019).  [Online; accessed 02-June-2021].
  * [7] Gupta, P. _et al._ Wtf: The who to follow service at twitter.  In _Proceedings of the 22nd international conference on World Wide Web_ , 505–514 (2013).
  * [8] Su, J., Sharma, A. & Goel, S.  The effect of recommendations on network structure.  In _Proceedings of the 25th international conference on World Wide Web_ , 1157–1167 (2016).
  * [9] Bellogín, A., Castells, P. & Cantador, I.  Statistical biases in information retrieval metrics for recommender systems.  _Information Retrieval Journal_ 20, 606–634 (2017).
  * [10] Page, L., Brin, S., Motwani, R. & Winograd, T.  The pagerank citation ranking: Bringing order to the web.  Tech. Rep., Stanford InfoLab (1999).
  * [11] Ghoshal, G. & Barabási, A.-L.  Ranking stability and super-stable nodes in complex networks.  _Nature communications_ 2, 394 (2011).
  * [12] Karimi, F., Génois, M., Wagner, C., Singer, P. & Strohmaier, M.  Homophily influences ranking of minorities in social networks.  _Scientific reports_ 8 (2018).
  * [13] Fabbri, F., Bonchi, F., Boratto, L. & Castillo, C.  The effect of homophily on disparate visibility of minorities in people recommender systems.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , vol. 14, 165–175 (2020).
  * [14] Cotter, D. A., Hermsen, J. M., Ovadia, S. & Vanneman, R.  The glass ceiling effect.  _Social Forces_ 80, 655–681, DOI: 10.1353/sof.2001.0091 (2001).  https://academic.oup.com/sf/article-pdf/80/2/655/6519837/80-2-655.pdf.
  * [15] Avin, C. _et al._ Homophily and the glass ceiling effect in social networks.  In _Proceedings of the 2015 conference on innovations in theoretical computer science_ , 41–50 (2015).
  * [16] Stoica, A.-A., Riederer, C. & Chaintreau, A.  Algorithmic glass ceiling in social networks: The effects of social recommendations on network diversity.  In _Proceedings of the 2018 World Wide Web Conference_ , 923–932 (2018).
  * [17] Franklin, A. J. & Boyd-Franklin, N.  Invisibility syndrome: A clinical model of the effects of racism on african-american males.  _American Journal of Orthopsychiatry_ 70, 33–41 (2000).
  * [18] Jacobs, A. Z. & Wallach, H.  Measurement and fairness.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 375–385 (2021).
  * [19] Little, R. J. & Rubin, D. B.  _Statistical analysis with missing data_ , vol. 793 (John Wiley & Sons, 2019).
  * [20] Freedman, J. L. & Sears, D. O.  Selective exposure.  In _Advances in experimental social psychology_ , vol. 2, 57–97 (Elsevier, 1965).
  * [21] Lum, K. & Isaac, W.  To predict and serve?  _Significance_ 13, 14–19 (2016).
  * [22] Brownstein, M.  Implicit Bias.  In Zalta, E. N. (ed.) _The Stanford Encyclopedia of Philosophy_ (Metaphysics Research Lab, Stanford University, 2019), Winter 2019 edn.
  * [23] Zehlike, M., Yang, K. & Stoyanovich, J.  Fairness in ranking: A survey.  _arXiv preprint arXiv:2103.14000_ (2021).
  * [24] Kleinberg, J. & Raghavan, M.  Selection problems in the presence of implicit bias.  _arXiv preprint arXiv:1801.03533_ (2018).
  * [25] Asudeh, A., Jagadish, H., Stoyanovich, J. & Das, G.  Designing fair ranking schemes.  In _Proceedings of the 2019 International Conference on Management of Data_ , 1259–1276 (2019).
  * [26] Yang, K. & Stoyanovich, J.  Measuring fairness in ranked outputs.  In _Proceedings of the 29th International Conference on Scientific and Statistical Database Management_ , 22 (ACM, 2017).
  * [27] Borgatti, S. P., Everett, M. G. & Johnson, J. C.  _Analyzing social networks_ (Sage, 2018).
  * [28] McPherson, M., Smith-Lovin, L. & Cook, J. M.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ 27, 415–444 (2001).
  * [29] Barabási, A.-L. & Albert, R.  Emergence of scaling in random networks.  _science_ 286, 509–512 (1999).
  * [30] Drosou, M., Jagadish, H., Pitoura, E. & Stoyanovich, J.  Diversity in big data: A review.  _Big data_ 5, 73–84 (2017).
  * [31] Singh, A. & Joachims, T.  Fairness of exposure in rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2219–2228 (ACM, 2018).
  * [32] Gao, R. & Shah, C.  Toward creating a fairer ranking in search engine results.  _Information Processing & Management_ 57, 102138 (2020).
  * [33] Voitalov, I., van der Hoorn, P., van der Hofstad, R. & Krioukov, D.  Scale-free networks well done.  _Physical Review Research_ 1, 033034 (2019).
  * [34] Chawla, N. V., Bowyer, K. W., Hall, L. O. & Kegelmeyer, W. P.  Smote: synthetic minority over-sampling technique.  _Journal of artificial intelligence research_ 16, 321–357 (2002).
  * [35] Davis, J. A.  Clustering and hierarchy in interpersonal relations: Testing two graph theoretical models on 742 sociomatrices.  _American Sociological Review_ 843–851 (1970).
  * [36] Block, P.  Reciprocity, transitivity, and the mysterious three-cycle.  _Social Networks_ 40, 163–173 (2015).
  * [37] Dufwenberg, M. & Patel, A.  Reciprocity networks and the participation problem.  _Games and Economic Behavior_ 101, 260–272 (2017).
  * [38] Altenburger, K. M. & Ugander, J.  Monophily in social networks introduces similarity among friends-of-friends.  _Nature human behaviour_ 2, 284–290 (2018).
  * [39] Evtushenko, A. & Kleinberg, J.  The paradox of second-order homophily in networks.  _Scientific Reports_ 11, DOI: 0.1038/s41598-021-92719-6 (2021).
  * [40] Perra, N., Gonçalves, B., Pastor-Satorras, R. & Vespignani, A.  Activity driven modeling of time varying networks.  _Scientific reports_ 2, 469 (2012).
  * [41] Merton, R. K.  The matthew effect in science, ii: Cumulative advantage and the symbolism of intellectual property.  _isis_ 79, 606–623 (1988).
  * [42] Newman, M. E.  The structure and function of complex networks.  _SIAM review_ 45, 167–256 (2003).
  * [43] Lofgren, P., Banerjee, S. & Goel, A.  Personalized pagerank estimation and search: A bidirectional approach.  In _Proceedings of the Ninth ACM International Conference on Web Search and Data Mining_ , 163–172 (2016).
  * [44] Ding, Y., Yan, E., Frazho, A. & Caverlee, J.  Pagerank for ranking authors in co-citation networks.  _Journal of the American Society for Information Science and Technology_ 60, 2229–2243 (2009).
  * [45] Gollapalli, S. D., Mitra, P. & Giles, C. L.  Ranking authors in digital libraries.  In _Proceedings of the 11th annual international ACM/IEEE joint conference on Digital libraries_ , 251–254 (2011).
  * [46] Senanayake, U., Piraveenan, M. & Zomaya, A.  The pagerank-index: Going beyond citation counts in quantifying scientific impact of researchers.  _PloS one_ 10, e0134794 (2015).
  * [47] Barbieri, N., Bonchi, F. & Manco, G.  Who to follow and why: link prediction with explanations.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 1266–1275 (2014).
  * [48] Yu, Y. & Wang, X.  Link prediction in directed network and its application in microblog.  _Mathematical Problems in Engineering_ 2014 (2014).
  * [49] Morone, F. & Makse, H. A.  Influence maximization in complex networks through optimal percolation.  _Nature_ 524, 65–68 (2015).
  * [50] Zhang, J.-X., Chen, D.-B., Dong, Q. & Zhao, Z.-D.  Identifying a set of influential spreaders in complex networks.  _Scientific reports_ 6, 27823 (2016).
  * [51] Gleich, D. F.  Pagerank beyond the web.  _SIAM Review_ 57, 321–363 (2015).
  * [52] Liu, X., Bollen, J., Nelson, M. L. & Van de Sompel, H.  Co-authorship networks in the digital library research community.  _Information processing & management_ 41, 1462–1480 (2005).
  * [53] Jezek, K., Fiala, D. & Steinberger, J.  Exploration and evaluation of citation networks.  In _ELPUB_ , 351–362 (2008).
  * [54] Fiala, D., Rousselot, F. & Ježek, K.  Pagerank for bibliographic networks.  _Scientometrics_ 76, 135–158 (2008).
  * [55] Brin, S. & Page, L.  The anatomy of a large-scale hypertextual web search engine.  _Computer networks and ISDN systems_ 30, 107–117 (1998).
  * [56] Sajadi, A.  Fast personalized pagerank implementation.  https://github.com/asajadi/fast-pagerank (2019).  Accessed: 2021-03-30.
  * [57] Lempel, R. & Moran, S.  Salsa: the stochastic approach for link-structure analysis.  _ACM Transactions on Information Systems (TOIS)_ 19, 131–160 (2001).
  * [58] Jeh, G. & Widom, J.  Scaling personalized web search.  In _Proceedings of the 12th international conference on World Wide Web_ , 271–279 (2003).
  * [59] Fortunato, S., Boguñá, M., Flammini, A. & Menczer, F.  Approximating pagerank from in-degree.  In _International workshop on algorithms and models for the web-graph_ , 59–71 (Springer, 2006).
  * [60] Goswami, S., Murthy, C. & Das, A. K.  Sparsity measure of a network graph: Gini index.  _Information Sciences_ 462, 16–39 (2018).

## Acknowledgements

We would like to thank Nicola Perra, Indira Sen, Mattia Samori, and Reinhard
Munz who have helped improving this paper. Special thanks to the
LXAI@ICML2020, NetSci2020, and WiDS Guayaquil@ESPOL communities for their
fruitful discussions around this paper.

## Author contributions statement

L.E.N., F.K., C.W. and M.S. devised the research project. L.E.N. conceived the
experiments and analyzed the datasets. F.K. performed analytical derivations.
L.E.N., F.K., C.W., and M.S. wrote the paper. All authors reviewed the
manuscript.

## Additional information

### Competing Interests

The author(s) declare no competing interests.

### Availability of materials and data

The code and datasets generated during and/or analyzed during the current
study are available in the GitHub repository,
https://github.com/gesiscss/Homophilic_Directed_ScaleFree_Networks.

## Supplementary Material

##  Appendix A Analytics

###  A.1 Derivation of the probability of having an internal link

Let $K^{in}_{a}(t)$ and $K^{out}_{a}(t)$ be the sum of the in- and out-degrees
of nodes from group $a$ at time $t$. The overall growth of the network follows
a DPAH process. Thus, the evolution of in-degree and out-degree follows:

$\left\\{\begin{array}[]{l}K_{a}^{in}(t)+K_{b}^{in}(t)=K^{in}(t)=m\times t\\\
K_{a}^{out}(t)+K_{b}^{out}(t)=K^{out}(t)=m\times t\end{array}\right.$ (1)

where $m$ is the number of new links in the network at each time step $t$. In
each time step, a node $v_{i}$ is chosen. That results in $m$ new out-going
links from $v_{i}$ and $m$ new incoming links to node $v_{j}$. We set $m=1$.
Thus, in each time step only one edge is created.

Let us denote the relative fraction of group size for each group as $f_{a}$
and $f_{b}$, and the activation probability as $\eta$. The activation
probability is independent of the node attribute. Thus, the behavior of the
network is similar to what we have shown before [12]; only the total number of
links is different. We can show that in the limit of $\Delta t\rightarrow 0$,
for each group, the in-degree growth function follows the following:

$\dfrac{dK_{a}^{in}}{dt}=(m\times\eta)\left(f_{a}\left(1+\dfrac{h_{aa}K^{in}_{a}(t)}{h_{aa}K^{in}_{a}(t)+h_{ab}K^{in}_{b}(t)}\right)+f_{b}\left(\dfrac{h_{ba}K^{in}_{a}(t)}{h_{bb}K^{in}_{b}(t)+h_{ba}K^{in}_{a}(t)}\right)\right)\\\
$ (2)
$\dfrac{dK_{b}^{in}}{dt}=(m\times\eta)\left(f_{b}\left(1+\dfrac{h_{bb}K^{in}_{b}(t)}{h_{bb}K^{in}_{b}(t)+h_{ba}K^{in}_{a}(t)}\right)+f_{a}\left(\dfrac{h_{ab}K^{in}_{b}(t)}{h_{aa}K^{in}_{a}(t)+h_{ab}K^{in}_{b}(t)}\right)\right)\\\
$ (3)

We focus on the case of links within group $a$. The same analysis applies for
group $b$.

Let $p_{aa}$ be the probability to establish a link between two nodes of group
$a$. The probability for an incoming or existing node from group $a$ to link
to a node of the same group is given by:

$p_{aa}(t)=f_{a}\dfrac{h_{aa}K_{a}^{in}(t)}{h_{aa}K_{a}^{in}(t)+h_{ab}K_{b}^{in}(t)}$
(4)

In the simple network growth model, the total degree of the groups increases
linearly over time.

$\left\\{\begin{array}[]{l}K_{a}^{in}(t)=C\times(m\times\eta)\times t\\\
K_{b}^{in}(t)=(2-C)\times(m\times\eta)\times t\\\
K_{a}^{out}(t)=(m\times\eta)\times t\\\ K_{b}^{out}(t)=(m\times\eta)\times
t\\\ \end{array}\right.$ (5)

Denoting $C$ as the in-degree growth factor of the minority group.

###  A.2 Calculating Homophily from empirical network

We can calculate homophily in empirical networks using the information about
in-group links. First, the total number of edges in a directed network
follows:

$e=e_{aa}+e_{ab}+e_{ba}+e_{bb}$ (6)

To calculate $e_{aa}$, the number of links within class $a$, we can simply
argue that it depends on $p_{aa}$, the probability of connecting two nodes
belonging to class $a$, multiplied by the probability of the arrival or source
node to be of class $a$, denoted by $f_{a}$, the fraction of nodes in class
$a$, as shown in Equation 4.

Our network model grows linearly in time. That means, the in-degree growth for
each group is linear. Let us assume that the in-degree growth rate of group
$a$ is denoted by $C_{a}$:

$K^{in}_{a}(t)=C_{a}K^{in}(t)$ (7)

Since the in-degree growth remains constant over time, we can calculate
$C_{a}$ in the empirical network by summing all in-degrees of the group

$C_{a}(empirical)=\frac{K^{in}_{a}}{K^{in}}$ (8)

Equation 4 can be rewritten as

$p_{aa}=f_{a}\dfrac{h_{aa}C_{a}}{h_{aa}C_{a}+h_{ab}(1-C_{a})}$ (9)

In empirical networks, $p_{aa}$ represents the probability of a directed edge
from class $a$ to class $a$. This probability is proportional to the number of
edges from $a$ to $a$, normalized by the total number of directed edges that
start from $a$:

$p_{aa}=\frac{e_{aa}}{e_{aa}+e_{ab}}$ (10)

We can then calculate Equation 10 in the empirical network. Finally we use
maximum-likelihood estimate to find the best values for $h_{aa}$ and $h_{bb}$
in Equation 9.

Note that in-degree growth rate $C$ has an sub-linear relationship to the
exponent of the in-degree distribution $\sigma$ and the exponent of the in-
degree growth $\theta$ [12]. Thus, another method to retrieve empirical
homophily is to fist estimate the exponents of the in-degree distributions for
minority and majorities ($\sigma_{a}$ and $\sigma_{b}$) and plug that into the
equation.

$p_{aa}=\frac{f_{a}^{2}h_{aa}(1-\theta_{b})}{f_{a}h_{aa}(1-\theta_{b})+f_{b}h_{ab}(1-\theta_{a})}$
(11)

$p_{bb}=\frac{f_{b}^{2}h_{bb}(1-\theta_{a})}{f_{b}h_{bb}(1-\theta_{a})+f_{a}h_{ba}(1-\theta_{b})}$
(12)

where $\sigma_{a}=-(\frac{1}{\theta_{a}}+1)$ and
$\sigma_{b}=-(\frac{1}{\theta_{b}}+1)$.

###  A.3 WTF produces higher inequality compared to PageRank

In the main manuscript we see that WTF produces skewer rank distributions
compared to PageRank. To understand this behavior, we need to first understand
how the algorithms work. PageRank scores reflect the global importance of
nodes in the network, and this global importance is mostly determined by in-
degree [59]. On the other hand, the WTF score of a node is the number of times
the node appears in the top-10 recommendation across all nodes in the network.
This top-10 is determined by the circle-of-trust of each node, similar to a
Personalized PageRank. This means that this top-10 contains the most visited
nodes by a random walker that always starts at the node who is getting the
recommendation. Thus, that (local) top-10 will be highly influenced by in-
degree too. However, since the WTF score counts the number of times a node
appears as a recommendation, it is likely that the highest WTF scores refer to
high degree nodes due to preferential attachment. Therefore, the high
inequality produced by WTF can be explained by the fact that WTF combines a
local random walk with a global count.

##  Appendix B Additional Tables and Figures

Table S1: 10-fold cross-validation for WTF: We use a Random Forest Regressor to assess model performance and feature importance. $R^{2}$ values are averages (and standard deviations) across all networks. Features are ranked based on their mean importance (from left to right) and highlighted if their importance represents more than 50% of the total importance. Features with a mark (*) are less important than random. Corr shows the disparity as the Spearman correlation between inequality and inequity scores (p-values $\approx 0$). Type | Outcome | Corr. | $R^{2}$ | Feature importance
---|---|---|---|---
Global | $gini$ | 0.29 | 0.35 (0.03) | $h_{MM}^{*}\rightarrow h_{mm}^{*}\rightarrow f_{m}^{*}$
$me$ | 0.92 (0.01) | $\boldsymbol{h_{MM}}\rightarrow h_{mm}\rightarrow f_{m}$
Local | $gini_{k}$ | 0.06 | 0.86 (0.00) | $\boldsymbol{k}\rightarrow h_{MM}^{*}\rightarrow h_{mm}^{*}\rightarrow f_{m}^{*}$
$me_{k}$ | 0.85 (0.01) | $\boldsymbol{h_{MM}}\rightarrow\boldsymbol{h_{mm}}\rightarrow k\rightarrow f_{m}^{*}$
Figure S1: The effects of homophily and fraction of minorities in the global
disparity of WTF Columns represent the fraction of minorities in the network,
x-axis indicates the homophily within minorities, and y-axis the homophily
within majorities. Colors denote the region where the disparity lies in
according to our interpretation (see Figure 8 in main article). As in the case
of PageRank (cf. Figure 4 in main article), we see that, on average, there is
never low global inequality. Also, depending on the level of homophily within
groups, minorities on average can be under-represented (region I, red), or
over-represented (region III, blue). Note that the fair case (region II,
green) rarely occurs.  Figure S2: The effects of homophily and fraction of
minorities in the local disparity of WTF. Columns represent the fraction of
minorities (10%, 30% and 50%) and rows show homophily within minorities (from
top to bottom: heterophilic, neutral and homophilic). The x-axis denotes the
top-k% rank and the y-axis shows homophily within majorities. Colors refer to
the regions of disparity (see Figure 8 in main article). As in the case of
PageRank (cf. Figure 5 in main article), we see that the minority suffers most
(red) when the majority is homophilic and the minority is either heterophilic
or neutral. Also, inequity remains mostly consistent regardless of top-$k$%.
In contrast to PageRank (up to top-5%), WTF manages to capture nodes with very
similar ranking scores (roughly) up to the top-30% (i.e., Gini is low, regions
VII, VIII, IX). Figure S3: The effects of homophily and preferential
attachment in the global disparity of WTF We generated directed networks using
four different models of edge formation. DPA: only preferential attachment.
DH: only homophily. DPAH: our proposed model that combines DPA and DH. Random:
a baseline where nodes are connected randomly. Compared to PageRank (cf.
Figure 2 in main article), all models generate higher inequality (y-axis),
whereas inequity remains similar.  Figure S4: The effects of node activity in
the global disparity of PageRank. We generate DPAH networks by varying
$f_{m}$, $h_{MM}$, $h_{mm}$, and fixing edge density $d=0.0015$ and $10$
epochs. Each color represents the activity of nodes as the out-degree
exponents of the networks $\gamma_{M}=\gamma_{m}\in\\{1.5,2.0,2.5,3.0,3.5\\}$.
We see that by reducing the out-degree exponent in the DPAH networks (from
$\gamma=3.5$ to $\gamma=1.5$), we reduce inequality (vertical axis), and
inequity remains stable. Figure S5: Global inequality on Random networks as a
function of edge density. We generate directed Erdős-Rényi networks to
demonstrate how the global inequality (y-axis) varies with respect to the edge
density (x-axis) of the network. For each density value we generate networks
with different fractions of minorities and $10$ epochs. Note that $d=0.0015$
corresponds to the Random networks used in the main experiments. Inequality
computed on the PageRank distribution is shown in red, while the inequality on
WTF is shown in blue. We see different trends for each algorithm. First, the
inequality (Gini coefficient) of PageRank is very low when the edge density is
extreme (i.e., either too low or too high). This means that in these regimes
most nodes are similarly important regardless of the magnitude of their
degrees. Second, the inequality of WTF is in general negatively correlated
with density (i.e., the lower the density, the higher the inequality [60]).
However, in the extreme case of denser networks (i.e., $d=0.1$), inequality
raises. Recall that ranking inequity is very close to zero ($ME\approx 0$) in
random networks. Further studies are required to analytically understand the
limits of inequality with respect to density.


# A quantum bound on the $1/f$ noise in semiconductors with a conical energy-
momentum dispersion

Kirill A. Kazakov  Department of Theoretical Physics, Physics Faculty,
Moscow State University, $119991$, Moscow, Russian Federation

###### Abstract

The quantum indeterminacy caused by non-commutativity of observables at
different times sets a lower bound on the voltage noise power spectrum in any
conducting material. This bound is calculated explicitly in the case of
semiconductors with a conical energy-momentum dispersion of charge carriers.
It possesses all characteristic properties of $1/f$ noise. Its momentum
decomposition is found to be singular at zero particle momentum, a measurable
consequence being a sharp peak in the noise magnitude at small charge carrier
density. In application to monolayer graphene, this peak becomes M-shaped on
account of a continuous transition from the electron to hole conductivity. A
comparison with experimental data is made which demonstrates that the
calculated power spectrum is close in magnitude and congruent to the observed.

1/f noise, quantum bound, conical dispersion, Schwinger-Keldysh formalism,
graphene

###### pacs:

42.50.Lc, 72.70.+m

##  I Introduction

It is well known that the spectra of voltage fluctuations in materials
possessing free-like charge carriers are to a large degree universal at low
frequencies: the power spectral density of fluctuations $S(f)\sim
1/f^{\gamma},$ where the frequency exponent $\gamma$ is around unity johnson ;
buckingham ; bell1980 ; raychaudhuri . This so-called $1/f$ noise has been
detected down to frequencies as low as $f=10^{-6.3}$ Hz rollin1953 ;
caloyannides , with no sign of a low-frequency cutoff. There are many physical
processes in conducting media which affect electrical conductivity at random
and thereby produce voltage noise: charge carrier trapping, temperature
fluctuations, generation-recombination of carriers in semiconductors, impurity
migration, etc. The corresponding noise spectra are well understood, and their
detection is a means to identify the underlying processes in specific
materials. An eventual flattening at low frequencies and comparatively narrow
frequency spans (three decades at most) are two most common features of these
conventional spectra. As regards to $1/f$ noise, despite the lack of a
conductance-fluctuation model that would explain altogether its amazing
ubiquity, the absence of a low-frequency cutoff and the observed magnitudes of
$1/f$ spectra, it is currently widely accepted that this noise, too, is
generated by fluctuations in electrical conductance. On the other hand, it was
shown recently that the quantum nature of charge carrier interaction with
photons sets a lower bound on the spectral power of voltage fluctuations, and
moreover, that this bound possesses all characteristic features of the
observed $1/f$ noise kazakov1 ; kazakov2 . This bound was calculated
explicitly in the case of charge carriers with a parabolic energy-momentum
dispersion, and a comparison with $1/f$-noise in InGaAs quantum wells and
high-temperature superconductors was made which led to the conclusion that the
measured noise levels are only a few times as high as the bound established.
The purpose of this Letter is to obtain a similar bound in another important
case – a conical energy-momentum dispersion. This case is of special interest
in view of the fact that the bound found in Refs. kazakov1 ; kazakov2  is
inversely proportional to the charge carrier mass, whereas the conical
dispersion implies that the particles are massless.

To recapitulate main points of the new approach, a lower bound on the power
spectral density (power spectrum) of voltage fluctuations arises from the
quantum indeterminacy caused by non-commutativity of observables at different
times. This indeterminacy obstructs applicability of the Wiener-Khinchin
theorem, which otherwise leads to a divergent total noise power whenever
$S(f)\sim 1/f^{\gamma}$ with $\gamma\geqslant 1.$ It is by this reason that
the quantum bound involves no low-frequency cutoff. In fact, it applies
equally well at all frequencies of interest in $1/f$-noise studies. Consider a
(semi)conducting sample with a constant electric current through it, and let
the voltage across the sample be measured by means of two voltage probes which
may or may not coincide with the current leads. For simplicity, the probes are
assumed pointlike, $\bm{x}_{1},\bm{x}_{2}$ denoting their position. A voltage
between them measured at time $t$ is the sum of a constant bias
$U_{0}(\bm{x}_{1},\bm{x}_{2})$ and a fluctuation, or noise, $\Delta
U(t,\bm{x}_{1},\bm{x}_{2}).$ The results of Ref. kazakov1  can be summarized
as a recipe for calculating the lower bound, $S_{F}(f),$ of the voltage power
spectrum, as follows. The voltage fluctuation $\Delta
U(t,\bm{x}_{1},\bm{x}_{2})$ is an observable to which there corresponds a
Hermitian (Heisenberg) operator $\widehat{\Delta U}(t)$ (for brevity, the
arguments $\bm{x}_{1},\bm{x}_{2}$ in $\widehat{\Delta U}$ are henceforth
omitted). Define a correlation of the fluctuations,
$S(t-t^{\prime})=\left\langle\widehat{\Delta U}(t)\widehat{\Delta
U}(t^{\prime})\right\rangle,$ where angular brackets denote the quantum-
mechanical average over a fixed state of the system “conducting sample plus
electromagnetic field.” $S_{F}(f)$ is determined by the part of
$S(t-t^{\prime})$ which is antisymmetric under the interchange
$t\leftrightarrow t^{\prime}$ ($\omega=2\pi f$):

$\displaystyle
S_{F}(f)=\left|\lim\limits_{t_{m}\to\infty}\left\\{\int_{-t_{m}}^{t_{m}}{\rm
d}\tau S(\tau)\sin(\omega\tau)-\frac{1}{t_{m}}\int_{-t_{m}}^{t_{m}}{\rm
d}\tau|\tau|S(\tau)\sin(\omega\tau)\right\\}\right|.$ (1)

As was demonstrated in Refs. kazakov1 ; kazakov2 , the antisymmetric part of
$S(t-t^{\prime})$ admits a Fourier decomposition despite the presence of
$1/f$-term in the power spectrum, and the limit under the modulus sign in Eq.
(1) may exist even if $S(\tau)$ does not vanish for $\tau\to\infty,$ as is the
case when $S(f)\sim 1/f$ at low frequencies.

The expectation value $\left\langle\widehat{\Delta U}(t)\widehat{\Delta
U}(t^{\prime})\right\rangle$ can be computed using the Schwinger-Keldysh
technique schwinger ; keldysh , according to which it is written as

$\displaystyle\left\langle\widehat{\Delta U}(t)\widehat{\Delta
U}(t^{\prime})\right\rangle={\rm
tr}\left(\hat{\rho}\,\mathcal{T}_{C}\widehat{\Delta u}^{(2)}(t)\widehat{\Delta
u}^{(1)}(t^{\prime})\exp\left\\{-{\rm i}\int_{C}{\rm
d}t\,\hat{w}(t)\right\\}\right),$ (2)

where $\widehat{\Delta
u}(t)=\hat{a}_{0}(t,\bm{x}_{1})-\hat{a}_{0}(t,\bm{x}_{2})-U_{0},$ with
$\hat{a}_{0}$ the scalar electromagnetic potential, $\hat{\rho}$ is the system
density matrix, $\hat{w}$ is the interaction Hamiltonian, and the lowercase
letters denote operators in the interaction picture; the so-called Schwinger-
Keldysh time contour $C$ runs from $t=-\infty$ to $t=+\infty$, and then back
to $t=-\infty,$ with all time instants on the forward branch [designated with
a superscript $(1)$] treated as being in the past with respect to any time
instant on the backward branch [designated with a superscript $(2)$];
$\mathcal{T}_{C}$ denotes operator ordering along this contour.

Our goal is to determine how $S_{F}(f)$ is changed by switching from a
parabolic to a conical energy-momentum dispersion of the charge carriers.
Therefore, the right hand side of Eq. (2) will be evaluated under conditions
otherwise identical to those of Ref. kazakov1 , namely, the charge carriers
will be assumed non-relativistic unpolarized fermions, with all spin indices
accordingly suppressed, and the finite-temperature effects due to photon heat
bath neglected. Thus, the charge carrier energy $\varepsilon$ is related to
its momentum $\bm{q}$ as

$\displaystyle\varepsilon(\bm{q})=v_{F}|\bm{q}|,$ (3)

where $v_{F}$ is the Fermi velocity. The assumption that the charge carriers
are non-relativistic means that $v_{F}\ll c,$ the speed of light in vacuum.
The charge carrier Hamiltonian is taken in the simplest form obtained by
replacing the ordinary derivatives with covariant ones. The interaction
Hamiltonian thus reads

$\displaystyle\hat{w}(t)=\int{\rm
d}^{3}\bm{x}\hat{\phi}^{\dagger}(x)\left[\varepsilon\left(-{\rm
i}\hbar\bm{\nabla}-\frac{e}{c}\bm{a}\right)-\varepsilon\left(-{\rm
i}\hbar\bm{\nabla}\right)+e\hat{a}_{0}(x)\right]\hat{\phi}(x),\quad
x=(ct,\bm{x}),$ (4)

where $\hat{\phi}(x)$ is the fermionic field, and

${\bm{a}}={\rm i}c\bm{E}\frac{{\rm e}^{{\rm i\lambda
t}}-1}{\lambda}\,,\quad\lambda\to 0,$

is the vector potential of the electric field $\bm{E}$ established in the
sample. The lowest-order contribution to the correlation function is quadratic
with respect to $\bm{E}.$ Therefore, the relevant interaction vertices
generated by $\hat{w}(t)$ include, in momentum space, a linear vertex

$\hat{w}_{1}(t)=-\frac{v_{F}e}{c}\int\frac{{\rm
d}^{3}\bm{q}}{(2\pi)^{3}}(\bm{v},\bm{a})\hat{\phi}^{\dagger}(\bm{q})\hat{\phi}(\bm{q}),$

where $\bm{v}=\partial\varepsilon(\bm{q})/\partial\bm{q}$ is the charge
carrier velocity, and a vertex quadratic in $\bm{E},$

$\hat{w}_{2}(t)=\frac{v_{F}e^{2}}{2c^{2}}\int\frac{{\rm
d}^{3}\bm{q}}{(2\pi)^{3}}\frac{[\bm{q},\bm{a}]^{2}}{|\bm{q}|^{3}}\hat{\phi}^{\dagger}(\bm{q})\hat{\phi}(\bm{q}),$

$(\cdot,\cdot)$ and $[\cdot,\cdot]$ denoting the scalar and vector product,
respectively.

Figure 1: Generic $O(\bm{E}^{2})$-graphs representing the right hand side of
Eq. (2). Solid straight and wavy lines depict respectively the charge carrier
and photon propagators, dashed line – the charge carrier density matrix.
Circles on the solid line with one or two dotted lines attached designate
vertices $w_{1}$ and $w_{2},$ respectively.

The lowest-order contribution to the correlation function is represented by
two generic graphs in Fig. 1, while Fig. 2 is the set of nonvanishing
Schwinger-Keldysh diagrams for the graph in Fig. 1(a). The sum of these
diagrams reads, in relativistic units $\hbar=c=1,$

$\displaystyle S(\tau)=\frac{{\rm i}v_{F}(4\pi
e^{2})^{2}}{2}\frac{\partial^{2}}{\partial\lambda\partial\lambda^{\prime}}\int\frac{{\rm
d}^{4}k}{(2\pi)^{4}}\frac{{\rm d}^{3}\bm{q}}{(2\pi)^{3}}\frac{{\rm
d}^{3}\bm{q}^{\prime}}{(2\pi)^{3}}\varrho(\bm{q},\bm{q}^{\prime})\left[{\rm
e}^{{\rm i}\bm{k}\cdot(\bm{x}_{1}-\bm{x}_{2})}-1\right]{\rm e}^{{\rm
i}(\bm{q}-\bm{q}^{\prime})\cdot\bm{x}_{1}}$
$\displaystyle\times\left\\{\left[{\rm e}^{-{\rm i}k^{0}\tau-{\rm i}k^{\prime
0}t}G^{(11)}(q-q^{\prime}+k+k^{\prime})D^{(11)}(q+k+k^{\prime})D^{(11)}(q+k)G^{(12)}(k)\right.\right.$
$\displaystyle\left.\left.-{\rm e}^{{\rm i}k^{0}\tau-{\rm i}k^{\prime
0}t^{\prime}}G^{(22)}(q-q^{\prime}+k+k^{\prime})D^{(22)}(q+k+k^{\prime})D^{(22)}(q+k)G^{(21)}(k)\right]\frac{[\bm{q},\bm{E}]^{2}}{|\bm{q}|^{3}}\right.$
$\displaystyle\left.+\left[{\rm e}^{-{\rm i}k^{0}\tau-{\rm i}k^{\prime
0}t}G^{(12)}(k)D^{(11)}(q^{\prime}-k)D^{(11)}(q^{\prime}-k-k^{\prime})G^{(11)}(q-q^{\prime}+k+k^{\prime})\right.\right.$
$\displaystyle\left.\left.-{\rm e}^{{\rm i}k^{0}\tau-{\rm i}k^{\prime
0}t^{\prime}}G^{(21)}(k)D^{(22)}(q^{\prime}-k)D^{(22)}(q^{\prime}-k-k^{\prime})G^{(22)}(q-q^{\prime}+k+k^{\prime})\right]\left.\frac{[\bm{q}^{\prime},\bm{E}]^{2}}{|\bm{q}^{\prime}|^{3}}\right\\}\right|_{\lambda=\lambda^{\prime}=0}$
$\displaystyle+(\bm{x}_{1}\leftrightarrow\bm{x}_{2}),$ (5)

where $k^{\prime}=(\lambda+\lambda^{\prime},\bm{0}),$ $G$ and $D$ are the
momentum-space Schwinger-Keldysh propagators of temporal photons and charge
carriers, respectively,

$\displaystyle G^{(11)}(k)$ $\displaystyle=$ $\displaystyle\frac{{\rm
i}}{k^{2}+{\rm i}0}=[G^{(22)}(k)]^{*},\quad
G^{(12)}(k)=2\pi\theta(-k^{0})\delta(k^{2}),\quad
G^{(21)}(k)=2\pi\theta(k^{0})\delta(k^{2}),$ $\displaystyle D^{(11)}(q)$
$\displaystyle=$ $\displaystyle\frac{{\rm i}}{q^{0}-\varepsilon(\bm{q})+{\rm
i}0}=[D^{(22)}(q)]^{*},\quad k=(k^{0},\bm{k}),\quad
q=(\varepsilon(\bm{q}),\bm{q}),$ (6)

and the step function $\theta(k^{0})=0$ for $k^{0}\leqslant 0$,
$\theta(k^{0})=0$ for $k^{0}>0$; the photon momentum $\bm{k}$ is negligible
compared to the charge carrier momenta $\bm{q},\bm{q}^{\prime},$ and as such
it is explicitly omitted in the vertex factors; since the photon heat bath
effects are neglected, $G$’s are purely vacuum; accordingly, the system
density matrix $\hat{\rho}$ is reduced to that of the charge carriers,
$\varrho(\bm{q},\bm{q}^{\prime})$ denoting its momentum-space representation;
the latter is normalized by

$\int\frac{{\rm d}^{3}\bm{q}}{(2\pi)^{3}}\varrho(\bm{q},\bm{q})=1.$

At last, “$+(\bm{x}_{1}\leftrightarrow\bm{x}_{2})$” means that the preceding
expression is to be added with $\bm{x}_{1}$ and $\bm{x}_{2}$ interchanged.

Figure 2: Nonvanishing diagrams representing the graph Fig. 1(b) in the
Schwinger-Keldysh formalism. The arrows on the lines show the energy-momentum
flow.

At low photon frequencies $k^{0},$ the charge carrier propagators are near
their poles, and therefore, the leading low-frequency term results from
$\lambda$-differentiations of the factors $D^{(11)}(q+k+k^{\prime}),$
$D^{(11)}(q^{\prime}-k-k^{\prime}),$ etc. To extract this term, we expand
$\varepsilon(\bm{q+k})\approx\varepsilon(\bm{q})+(\bm{v},\bm{k})$ in the
denominators and recall that $|\bm{v}|\ll 1,$ $|\bm{k}|=|k^{0}|,$ hence
$|(\bm{v},\bm{k})|\ll|k^{0}|.$ The propagators are thus simplified as

$\displaystyle D^{(11)}(q+k+k^{\prime})$ $\displaystyle=$
$\displaystyle\frac{{\rm
i}}{q^{0}+k^{0}+\lambda+\lambda^{\prime}-\varepsilon(\bm{q+k})}\approx\frac{{\rm
i}}{k^{0}+\lambda+\lambda^{\prime}},$ $\displaystyle
D^{(11)}(q^{\prime}-k-k^{\prime})$ $\displaystyle\approx$
$\displaystyle-\frac{{\rm i}}{k^{0}+\lambda+\lambda^{\prime}},$ (7)

etc. Substituting these expressions into Eq. (I) readily shows that the four
diagrams give rise to pairwise equal contributions to the leading term (the
pairs are enclosed in square brackets). Expanding also ${\rm e}^{{\rm
i}\bm{k}\cdot(\bm{x}_{1}-\bm{x}_{2})}$ to the second order, and performing
integration over $\bm{k}$ yields

$\displaystyle S(\tau)=$
$\displaystyle\frac{8v_{F}e^{4}(\bm{x}_{1}-\bm{x}_{2})^{2}}{3}\int_{0}^{\infty}{\rm
d}k^{0}\frac{{\rm e}^{{\rm i}k^{0}\tau}}{k^{0}}\int\frac{{\rm
d}^{3}\bm{q}}{(2\pi)^{3}}\frac{{\rm d}^{3}\bm{q}^{\prime}}{(2\pi)^{3}}$ (8)
$\displaystyle\times\varrho(\bm{q},\bm{q}^{\prime})\left(\frac{[\bm{q},\bm{E}]^{2}}{|\bm{q}|^{3}}+\frac{[\bm{q}^{\prime},\bm{E}]^{2}}{|\bm{q}^{\prime}|^{3}}\right)\frac{{\rm
e}^{{\rm i}(\bm{q}-\bm{q}^{\prime})\cdot\bm{x}_{1}}+{\rm e}^{{\rm
i}(\bm{q}-\bm{q}^{\prime})\cdot\bm{x}_{2}}}{(\bm{q}-\bm{q}^{\prime})^{2}}\,.$

It is now easy to see that similar transformations of the Schwinger-Keldysh
diagrams representing the graph in Fig. 1(b) yield expressions which pairwise
cancel each other (this is because these diagrams involve an odd number of the
charge carriers propagators, which makes the sign of their contributions
alternate). The leading low-frequency term of the spectral density of
$S(\tau)$ is thus linear with respect to the Fermi velocity, but its
dependence on the charge carrier momentum turns out to be more complicated
than in the case of massive particles. To evaluate this dependence, it is
convenient to express the charge carrier density matrix via the mixed
position-momentum distribution function $R(\bm{r},\bm{Q}),$

$\displaystyle\varrho\left(\bm{Q}-\frac{\bm{p}}{2},\bm{Q}+\frac{\bm{p}}{2}\right)=\frac{1}{\Omega}\int_{\Omega}{\rm
d}^{3}\bm{r}{\rm e}^{{\rm i}\bm{p}\cdot\bm{r}}R(\bm{r},\bm{Q}),$ (9)

where $\Omega$ is the sample volume. $R(\bm{r},\bm{Q})$ vanishes for $\bm{r}$
outside of the sample. It follows that $(\bm{q}^{\prime}-\bm{q})=\bm{p}$ is of
the order of the inverse linear sample size which in practice is much larger
than the lattice constant. Therefore, $|\bm{p}|\ll|\bm{q}|$ for all relevant
charge carrier momenta, and so one can set
$\bm{q}^{\prime}\approx\bm{q}\approx\bm{Q}$ in the vertex factors. The
integral over $\bm{p}$ in Eq. (8) is then just a Fourier decomposition of the
Coulomb potential. Finally, the power spectrum of voltage fluctuations is
found by substituting an odd in $\tau$ part of $S(\tau)$ into Eq. (1).
Restoring ordinary units, we obtain

$\displaystyle S_{F}(f)=$
$\displaystyle\frac{2v_{F}e^{4}\Delta\bm{x}^{2}}{3\pi\hbar
c^{3}|f|}\frac{1}{\Omega}\int_{\Omega}{\rm
d}^{3}\bm{r}\left(\frac{1}{|\bm{r}-\bm{x}_{1}|}+\frac{1}{|\bm{r}-\bm{x}_{2}|}\right)\int\frac{{\rm
d}^{3}\bm{Q}}{(2\pi)^{3}}R(\bm{r},\bm{Q})\frac{[\bm{Q},\bm{E}]^{2}}{|\bm{Q}|^{3}}\,,$
(10)

where $\Delta\bm{x}\equiv\bm{x}_{1}-\bm{x}_{2}.$ In the practically important
case of macroscopically homogeneous sample, $R(\bm{r},\bm{Q})=R(\bm{Q}),$ this
expression further factorizes:

$\displaystyle S_{F}(f)=\frac{2v_{F}e^{4}\Delta\bm{x}^{2}}{\pi\hbar
c^{3}|f|}g\int\frac{{\rm
d}^{3}\bm{Q}}{(2\pi)^{3}}R(\bm{Q})\frac{[\bm{Q},\bm{E}]^{2}}{|\bm{Q}|^{3}}\,,$
(11)

where

$g=\frac{1}{3\Omega}\int_{\Omega}{\rm
d}^{3}\bm{r}\left(\frac{1}{|\bm{r}-\bm{x}_{1}|}+\frac{1}{|\bm{r}-\bm{x}_{2}|}\right)$

is a purely geometric factor (it is defined here as in the massive case).

It is seen that the power spectrum essentially depends on the momentum
distribution of massless charge carriers, in contrast to the case of parabolic
energy-momentum dispersion where it is independent of $R(\bm{Q}).$ Most
notably, the integrand in Eq. (11) turns out to be singular for $\bm{Q}\to 0$:
the factor $[\bm{Q},\bm{E}]^{2}/|\bm{Q}|^{3}=O(1/|\bm{Q}|).$ Possible
observational consequences of this singularity are naturally expected to be
especially pronounced in low-dimensional systems and/or at small charge
carrier densities, $n,$ wherein the characteristic charge carrier momentum is
also small. This suggests consideration of $S_{F}$ as a function of $n.$

Let the sample be a thin semiconducting layer deposited on a dielectric
substrate that allows controlling the charge carrier density in the sample.
The sample thickness is supposed to be so small as to admit a two-dimensional
treatment of the charge carrier motion. Assuming that the distribution of
charge carrier momentum is isotropic in the sample plane, and that the voltage
probes are aligned parallel to the electric field (as is usually the case in
$1/f$ experiments), so that $\bm{E}^{2}\Delta\bm{x}^{2}=U^{2}_{0},$ Eq. (11)
takes the form

$\displaystyle S_{F}(f)=\frac{\varkappa
U^{2}_{0}}{|f|}\,,\quad\varkappa=\frac{v_{F}e^{4}g}{\pi\hbar
c^{3}}\int\frac{{\rm
d}^{2}\bm{Q}}{(2\pi\hbar)^{2}}\frac{R(\bm{Q})}{|\bm{Q}|}\,.$ (12)

As defined by Eq. (9), $R(\bm{Q})$ is normalized in the two-dimensional case
according to

$\displaystyle\int\frac{{\rm d}^{2}\bm{Q}}{(2\pi\hbar)^{2}}R(\bm{Q})=1.$ (13)

Therefore, on neglecting the effect of particle interactions on $R(\bm{Q})$,
it can be written as $R(\bm{Q})=2N(\varepsilon(\bm{Q}))/n,$ where
$N(\varepsilon)=[\exp(\varepsilon-\mu)/T+1]^{-1}$ is the Fermi–Dirac
distribution, and $n$ has the meaning of surface density of charge carriers
(the factor of two counts the electron spin states). Substitution of this
relation in Eqs. (12), (13) yields the reduced power spectrum $\varkappa$ and
$n$ as functions of the chemical potential $\mu$:

$\displaystyle\varkappa=\frac{2v_{F}e^{4}g}{\pi\hbar c^{3}n}\int\frac{{\rm
d}^{2}\bm{Q}}{(2\pi\hbar)^{2}}\frac{N(\varepsilon(\bm{Q}))}{|\bm{Q}|}\,,\quad
n=2\int\frac{{\rm d}^{2}\bm{Q}}{(2\pi\hbar)^{2}}N(\varepsilon(\bm{Q})).$ (14)

Figure 3: Reduced power spectrum ($\varkappa$) versus charge carrier density
($n$) as given by Eq. (14) in a square sample with $g\approx 1.6\times
10^{4}\,$cm${}^{-1}.$ $T=100\,$K, $v_{F}=10^{8}\,$cm/s. Inset: log-log plot of
the same function for a fixed $T=100\,$K and various $v_{F}=10^{7}\,$cm/s
(dotted line), $5\times 10^{7}\,$cm/s (dashed) and $10^{8}\,$cm/s (solid).

Figure 3 is a parametric plot of the function $\varkappa(n),$ $\mu$ being the
parameter, in the case of a square $1\times 1\,$$\mu$m2-sized sample, with the
voltage probes placed in the middle of its opposite sides. We see that the
singularity at $\bm{Q}=0$ in the momentum decomposition of $\varkappa$ shows
itself as a sharp increase of the noise magnitude at small charge carrier
density. As the inset demonstrates, $\varkappa$ tends to a finite limit as
$n\to 0,$ which is readily found to be

$\displaystyle\varkappa|_{n=0}=\frac{v^{2}_{F}e^{4}g}{\pi\hbar c^{3}T}\,.$
(15)

An asymptotic of $\varkappa(n)$ in the opposite case of large $n$ is also easy
to determine analytically. For $n$ so large that $\mu\gg T,$ one has

$n\simeq\frac{\mu^{2}}{2\pi\hbar^{2}}\,,\quad\varkappa\simeq\frac{v_{F}e^{4}g\mu}{\pi^{2}\hbar^{3}c^{3}n}\,,$

and therefore,

$\varkappa\simeq\frac{v_{F}e^{4}g}{\pi^{3/2}\hbar^{2}c^{3}}\sqrt{\frac{2}{n}}\,.$

This asymptotic is thus independent of temperature, and in fact, of the
particular structure of $N(\varepsilon)$ at $\varepsilon\sim\mu.$

In essence, the considered physical conditions are realized in the field-
effect transistors based on single-layer graphene. The sample in this case is
a planar monolayer of carbon atoms arranged in a hexagonal lattice geim2009 .
The energy-momentum dispersion is mainly determined by the electron hopping
between the two triangular sublattices, and is conical near the so-called
Dirac points which are two corners of the graphene Brillouin zone wallace1947
. Near these points, the energy spectrum is symmetric with respect to zero
energy, $\varepsilon(\bm{q})=\pm v_{F}|\bm{q}|,$ Dirac point being at
$\bm{q}=0,$ though the symmetry is broken away the point by the next-to-
nearest electron hopping. Thus, the charge carriers are two copies of
electrons ($\varepsilon>0$) and holes ($\varepsilon<0$), all characterized by
the same value of $v_{F}\approx 10^{8}\,$cm/s. The approximations made above
imply disregard of the effects related to the electron spin (except for the
number of states counting) and to the pseudo-spin (except for the energy-
momentum dispersion). In view of this, Eq. (14) is to be considered only as an
order-of-magnitude estimate of the quantum bound on $1/f$-noise in graphene.
On the other hand, there is another, more general source of inaccuracy that
makes exactness of calculations hard to improve. The point is that there is a
natural interplay between the power spectrum magnitude and the value of the
frequency exponent, $\gamma.$ As $\gamma$ deviates from unity, $\varkappa$ in
Eq. (14) becomes dimensional, $\varkappa\to\varkappa(f_{*})^{\delta},$ where
$\delta\equiv\gamma-1$ and $f_{*}$ is a frequency parameter which is on the
order of the inverse characteristic time of the physical process responsible
for the deviation. One such process is the charge carrier–phonon interaction,
wherein $f_{*}$ is the ratio of the sound speed to the lattice constant
kazakov2 . This parameter is a large number when measured in hertz,
$f_{*}\approx 10^{13},$ so that even a comparatively small deviation of
$\gamma$ can noticeably change the magnitude of $S(f).$ The available
experimental data suggest that $\gamma$ is close to unity in graphene, but it
is difficult to both calculate and measure accurately. The measurement error
depends largely on the frequency span, and for $2-2.5$ decades commonly found
in the $1/f$-studies in graphene, it is not less than $0.05.$ This error in
$\gamma$ brings in a factor of $10^{13\cdot 0.05}\approx 5$ in $\varkappa.$

Still, this ambiguity in the magnitude does not hinder comparison with the
experimental data of the trends predicted by Eq. (14), in particular, the
dependence of power spectrum on the charge carrier density. To this end, we
use the results of Ref. pal2011  where this dependence was measured in various
graphene devices including graphene monolayer flakes deposited on SiO2
substrates. Figure 4(a) compares the reduced power spectrum measured in a
sample of size $3.5\times 4.5\,$$\mu$m2 (marks, as read off from figure 1(d)
of Ref. pal2011 ) with the calculated according to Eq. (14) wherein $n$ is
doubled to account for the two Dirac points (solid line). The positive and
negative $n$s correspond, respectively, to the electron and hole doping.
Dashed curve is obtained by a vertical shift of the solid curve to match the
experimental data. The right (left) wing of the curve is shifted by
multiplying the theoretical $\varkappa$ for $\gamma=1$ with a factor of $15$
($10$). Should this factor be a result of deviation of the frequency exponent
from unity, the two numbers would correspond to $\delta=0.09$ and
$\delta=0.08$ (unfortunately, the comparison cannot be pursued in this
direction, as Ref. pal2011  does not specify values of $\gamma$).

Figure 4: (a) Reduced power spectrum versus charge carrier density as measured
in Ref. pal2011  in a field-effect device SLG1 (marks), and calculated
according to Eq. (14) (solid line). Dashed line is a vertical shift of the
solid. (b) Same in a suspended graphene flake at $T=300\,$K (solid line,
circles), and at $T=200\,$K (dashed line, diamonds). $n>0$ ($n<0$) is the
electron (hole) doping.

Strictly speaking, the peak value (15) is practically unattainable because of
fluctuations in $n$ caused by disorder and charged impurities in the
substrate. The corresponding characteristic density fluctuation in graphene,
$\delta n\sim 10^{11}\,$cm-2. But since $\varkappa$ slowly varies for
$n\lesssim 10^{11}$ (Cf. Fig. 3), $\varkappa|_{n=0}$ may well serve as an
estimate of the $\varkappa$ maximum. There is also another important scale of
electron density, $n_{\rm i},$ below which it becomes inhomogeneous because of
occurrence of hole “puddles” within the sample, which grow and coalesce with
decreasing electron density until they fill up the whole sample at $n=-n_{\rm
i}$ hwang2007 . $n\in(-n_{\rm i},n_{\rm i})$ is thus a region of mixed
electron-hole conductivity, the average electron (hole) density vanishing at
its left (right) end. Under such circumstances, $R(\bm{r},\bm{Q})$ in Eq. (10)
does depend on $\bm{r}$ within the sample, but if the puddles are distributed
approximately uniformly throughout, Eq. (14) is still valid. Then, to take
into account the vanishing of average electron/hole density at $n=-/+n_{\rm
i},$ the right (left) wing of the curve $\varkappa(n)$ is to be shifted to the
left (to the right) by the amount of $n_{\rm i};$ density fluctuations are
allowed for by smearing the result on the scale $\delta n.$ This produces a
curve with an M-shaped peak as drawn by a solid line in Fig. 4(b), and this
structure should be possible to experimentally resolve in samples with not-to-
large $\delta n.$ On the other hand, M-shaped $\varkappa$s in graphene have
been reported by a number of experimental studies lin2008 ; pal2009 ;
heller2010 ; zhang2011 ; pal2011 ; kaverzin2012 ; in particular, the authors
of Ref. pal2011  observed it in a device having the graphene flake partially
suspended. This suspension reduces the disorder induced by the substrate,
damping thereby fluctuations in the charge carrier density. The calculated
dependence $\varkappa(n)$ is compared with the experimental result pal2011  in
Fig. 4(b). The theoretical curves are drawn using the value $n_{\rm i}=5\times
10^{10}\,$cm-2 as estimated in Ref. pal2011 , and $\delta n$ on the order of
$10^{11}\,$cm-2 chosen so as to obtain best fits to the experimental data (the
latter is read off from figure 2(c3) of Ref. pal2011  where the sets of marks
for different temperatures were separated by shifting them vertically;
unfortunately, the authors of Ref. pal2011  were unable to specify the
shifts,111A.N. Pal, private communication. which does not allow accurate
comparison of the theoretical and observed noise magnitudes, and in
particular, determination of $\delta$). Yet, the similarity of theoretical and
experimental shapes of $\varkappa(n),$ evident in Fig. 4, is quite revealing.
Namely, in conjunction with their order-of-magnitude closeness and the
possibility to attribute the magnitude difference to $\delta\neq 0,$ it
suggests that what is observed in the experiment is actually a manifestation
of the quantum indeterminacy, rather than a result of conductance
fluctuations. In the absence of consistent theory of conductance $1/f$-noise
that would describe both the frequency profile and the noise magnitude, to
decide which contribution dominates calls for comprehensive measurements which
would allow a sufficiently accurate determination of the frequency exponent to
verify the trends predicted by Eq. (14).

To summarize, the quantum bound on $1/f$ voltage power spectrum in materials
with a conical energy-momentum dispersion of charge carriers is finite despite
an apparent zero-mass singularity of the bound in the case of parabolic
dispersion kazakov1 . Rather, the masslessness of charge carriers shows itself
as a singularity of the momentum decomposition of the reduced power spectrum
at zero particle momentum. This singularity has a directly measurable
consequence, namely, it gives rise to a sharp peak in the power spectrum
versus charge carrier density at small values thereof. In application to
monolayer graphene, this peak becomes M-shaped on account of a continuous
transition from the electron to hole conductivity, and this M-shape turns out
to be congruent with the experimentally observed.

## References

  * (1) J. B. Johnson, Phys. Rev. 26(1), 71 (1925).
  * (2) M. Buckingham, Noise in Electronic Devices and Systems (Ellis Horwood, Chichester, 1983).
  * (3) D. A. Bell, J. Phys. C: Solid St. Phys. 13, 4425 (1980).
  * (4) A.K. Raychaudhuri, Curr. Opin. Solid State Mater. Sci. 60, 67 (2002).
  * (5) B. V. Rollin and I. M. Templeton, Proc. Phys. Soc. B 66, 259 (1953).
  * (6) M. F. Caloyannides, J. Appl. Phys. 45, 307 (1974).
  * (7) J.F. Stephany, J. Phys.: Condens. Matter 12, 2469 (2000).
  * (8) K.A. Kazakov, Phys. Lett. A384, 126812 (2020).
  * (9) K.A. Kazakov, “Quantum theory of flicker noise: the $1/f$ law as a lower bound on the voltage power spectrum,” arXiv:2007.14481 (2020).
  * (10) J. Schwinger, J. Math. Phys. 2, 407 (1961).
  * (11) L. V. Keldysh, Zh. Eksp. Teor. Fiz. 47, 1515 (1964) [Sov. Phys. JETP 20, 1018 (1965)].
  * (12) G. D. Mahan, Many-Particle Physics (Kluwer Academic/Plenum Publishers, New York, 2000).
  * (13) A. H. Castro Neto, F. Guinea, N. M. R. Peres, K. S. Novoselov, and A. K. Geim, Rev. Mod. Phys. 81, 109 (2009).
  * (14) P. R. Wallace, Phys. Rev. 71, 622 (1947).
  * (15) E. H. Hwang, S. Adam, and S. Das Sarma, Phys. Rev. Lett. 98, 186806 (2007).
  * (16) Y.-M. Lin and P. Avouris, Nano Lett. 8, 2119 (2008).
  * (17) A. N. Pal and A. Ghosh, Phys. Rev. Lett. 102, 126805 (2009).
  * (18) I. Heller, S. Chatoor, J. M$\ddot{\rm a}$nnik, M. A. G. Zevenbergen, J. B. Oostinga, A. F. Morpurgo, C. Dekker, and S. G. Lemay, Nano Lett. 10, 1563 (2010).
  * (19) Y. Zhang, E. E. Mendez, and X. Du, ACS Nano 5, 8124 (2011).
  * (20) A. N. Pal, S. Ghatak, V. Kochat, E. Sneha, A. Sampathkumar, S. Raghavan, A. Ghosh, ACS Nano 5, 2075 (2011).
  * (21) A. A. Kaverzin, A. S. Mayorov, A. Shytov, and D. W. Horsell, Phys. Rev. B85, 075435 (2012).