# Correlation distances in social networks

Pádraig MacCarron  MACSI, Department of Mathematics and Statistics, University
of Limerick, Limerick, Ireland  Centre for Social Issues Research, University
of Limerick, Limerick, Ireland  Shane Mannion  MACSI, Department of
Mathematics and Statistics, University of Limerick, Limerick, Ireland  Samuel
Unicomb  MACSI, Department of Mathematics and Statistics, University of
Limerick, Limerick, Ireland  Thierry Platini  Applied Mathematics Research
Centre, Coventry University, Coventry, England

###### Abstract

In this work we explore degree assortativity in complex networks, and extend
its usual definition beyond that of nearest neighbours. We apply this
definition to model networks, and describe a rewiring algorithm that induces
assortativity. We compare these results to real networks. Social networks in
particular tend to be assortatively mixed by degree in contrast to many other
types of complex networks. However, we show here that these positive
correlations diminish after one step and in most of the empirical networks
analysed. Properties besides degree support this, such as the number of papers
in scientific coauthorship networks, with no correlations beyond nearest
neighbours. Beyond next-nearest neighbours we also observe a diasassortative
tendency for nodes three steps away indicating that nodes at that distance are
more likely different than similar.

##  I Introduction

In recent decades, many quantities have been introduced to shed light on the
structural properties of complex networks. Of particular importance is degree
assortativity, which provides a measure of the correlations in the degree of
neighbouring nodes. Its importance was underlined due to it distinguishing the
structure of social networks, and other types of complex networks [1] (though
this is found to not always be the case for online social networks [2]).
Studies of assortativity have focused on nearest neighbour correlations, since
neighbours interact directly only with their nearest neighbours, by
construction.

By drawing parallels with spin systems, such as that described by the Ising
model, one can argue that system components may exert influence indirectly,
beyond their immediate neighbourhood. This is captured in the idea of
correlation length. In the Ising model, while an individual spin has no direct
interaction with more distant spins, a re-orientation of a spin can influence
its neighbours causing a disturbance to propagate over a large area of the
lattice, modelling the observed behaviour of ferromagnets. Regions separated
by more than this characteristic distance can be thought of as essentially
independent [3]. Here we examine whether degree correlations in complex
networks exist beyond those found between nearest neighbours.

In this work we study correlations on undirected, unweighted networks as a
function of network distance. The most elementary feature of a network node is
its degree, defined as the number of edges adjacent to that node. The network-
wide correlation between degrees of neighbouring nodes is commonly known as
assortativity [12]. A network with strong degree correlations between nodes is
called assortative, and with anti-correlations, disassortative. We use the
shortest path length between two nodes to represent the distance, when this is
greater than one we are moving beyond the traditional nearest neighbours.

In social networks, where node degree represents the number of friends that an
individual has, assortativity indicates that popular individuals tend to have
popular friends, and unpopular individuals unpopular friends. This notion is
related to that of homophily, whereby individuals associate with people
similar to themselves. This leads to a tendancy of individuals to associate
mostly with others of a similar race or ethnicity, age, religion or interest
[13].

Previous studies have suggested that nodes’ influence may extend beyond the
immediate neighbourhood in social networks (e.g. [9]). It has even been
claimed that individuals can have up to “three degrees of influence” on other
nodes in a network [10]; though serious questions have been raised about the
methods of these studies [11]. Here we use the assortativity at different
distances to test this. We use one co-authorship network in three time points,
if nodes are expected to influence each other at a distance, naïvely we might
expect the beyond nearest neighbour correlations to increase over time.

Related works have examined how correlations vary with distance, typically
using the length of the shortest path between two nodes as a measure of the
distance between them. In Ref. [14], the authors apply three different methods
to understand higher-order assortativity; a random-walk based approach, a
path-based approach and a degree-based path approach. Another theoretical
approach is taken in Ref. [15]. Here the authors look at several joint and
conditional probability distributions relating node degrees and the shortest
path lengths that separate them. These methods are more focused on the mean-
field scenario rather than correlations in empirical datasets as we are here.
In Ref. [16] the authors observe a critical value for the average degree of an
Erdős-Rényi random graph, above which negative long distance correlations
emerge. Finally, Ref. [17] studies three social networks using a slightly
different approach. They look at the average degrees of nodes at the end of
paths of a certain length from source nodes and plot this versus the source
node degree to view correlations. However, they only study correlation between
nodes separated by paths of length four or less on three social networks,
concluding that more research is necessary.

In this paper, we study path lengths up to the diameter of our graphs for 16
empirical social networks. In the following section we outline the theoretical
framework for our correlation measure, and introduce an expression to quantify
assortativity as a function of distance. We then apply this to 16 social
networks to observe correlation behaviour beyond nearest neighbours. We then
perform simulations on random graphs, configuration model variants of each
empirical network, as well as generated assortative networks, to attempt to
generalise the results we observe.

##  II Theory

In this section we define a number of quantities centered around the concept
of assortativity. We start by defining a graph or network as an ordered pair
$G=({\cal V},{\cal E})$, where ${\cal V}$ is the set of nodes and ${\cal E}$
is the set of edges. The number of nodes and edges in a network are written
$N=|{\cal V}|$ and $L=|{\cal E}|$, respectively. Denoting the adjacency matrix
by $A$, with elements $A_{ij}$, the degree $k_{i}$ of node $i$ is given by
$k_{i}=\sum_{j}A_{ij}$. The mean degree of the network is given by $\langle
k\rangle=\sum_{i}k_{i}/N$. Although our results may be extended to directed
graphs, for the purposes of this study, we focus solely on undirected
networks, meaning that $A_{ij}=A_{ji}$. It follows that
$2L=\sum_{i,j}A_{ij}=\sum_{i}k_{i}=\sum_{k}kp_{k},$ where $p_{k}$ is the
degree distribution so the final term is just $N$ times the mean degree of the
network.

The shortest path between nodes $i$ and $j$ is the path from $i$ to $j$ that
traverses the minimal number of edges. We define the length of this path by
$\lambda_{ij}$, noting that the path itself is often not unique. It is common
for networks to consist of disconnected components, or sets of nodes that are
mutually reachable by traversing edges. When this is the case, there exists no
path between nodes $i$ and $j$ belonging to distinct components and, by
convention, we then set $\lambda_{ij}=\infty$. To define the average path
length $\ell$ it is convenient to introduce $\Gamma$, the number of components
of a graph and to define $C_{m}$, with $m\in\\{1,2,\ldots,\Gamma\\})$, as the
$m^{\rm th}$ component, which contains $n_{m}$ nodes. Summing over all pairs
of a connected component, the average path length is given by

$\ell=\sum_{m=1}^{\Gamma}\frac{1}{n_{m}(n_{m}-1)}\sum_{ij\in{\cal
C}_{m}}\lambda_{ij}.$ (1)

The greatest shortest path length $\ell_{\rm{max}}$ is known as the diameter
of the network.

###  II.1 Assortativity

Consider the two nodes at the extremities of a randomly chosen edge. The
probability of one node having degree $k$ and the other degree $q$ is

$\Phi(k,q)=\dfrac{1}{2L}\sum_{i,j}A_{ij}\delta_{k_{i}k}\delta_{k_{j}q},$ (2)

where $\delta_{k_{i}k}$ is the Kronecker delta which is 1 when $k_{i}=k$ and 0
otherwise.

We denote the average degree of the node at the end of an edge by $E[k]$. We
stress that an average over edges is not the same as an average over nodes and
use the notation $\text{E}(k)$ to represent the average summing over the set
of edges. These quantities are, however, closely related. Further, note that
since we have undirected graphs, $\text{E}[q]=\text{E}[k]$. Summing over $q$,
the marginal probability is given by

$\phi(k)=\sum_{q}\Phi(k,q).$ (3)

Using this expression, it is possible to show that $\text{E}(k)$ and the mean
degree over the nodes of the network are related by

$\text{E}(k)=\sum_{k}k\phi(k)=\frac{\sum_{k}k^{2}p_{k}}{\sum_{k}kp_{k}}$ (4)

which is the degree variance divided by the mean (i.e. the second moment of
the degree distribution divided by the first moment). Note that any network
besides those whose nodes have identical degree has positive degree variance.
This implies that, except in the degree-regular case, $\text{E}(k)$ is greater
than the mean degree of the nodes of the network. This means that on average,
individuals are connected to those more popular than themselves. This
observation is commonly known as the friendship paradox.

Our starting point towards understanding degree correlations and assortativity
is the expected value of the product of the degrees of the nodes at the end of
an edge chosen uniformly at random, $\text{E}(kq)$, defined by

$\text{E}[kq]=\sum_{k,q}kq\Phi(k,q).$ (5)

For uncorrelated, undirected graphs the probability distribution $\Phi(k,q)$
can be factorized as $\Phi(k,q)=\phi(k)\phi(q)$. The latter relation
immediately implies

$\text{E}[kq]=\text{E}[k]\text{E}[q]=\text{E}[k]^{2}=\text{E}[q]^{2}.$ (6)

It follows that a network is said to have positive correlations when
$\text{E}[kq]>\text{E}[k]\text{E}[q]$,and negative correlations when
$\text{E}[kq]<\text{E}[k]\text{E}[q]$.We can now introduce the degree
assortativity $r$ as

$r=\frac{\text{E}[kq]-\text{E}[k]\text{E}[q]}{\sigma_{\kappa}^{2}},$ (7)

which is in form of the Pearson correlation coefficient [12], with
$\sigma_{\kappa}^{2}$ the variance of $\kappa$,

$\sigma_{k}^{2}=\text{E}[k^{2}]-\text{E}[k]^{2}$ (8)

Normalising by the variance ensures that $-1\leq r\leq 1$. If $r>0$ the
network is said to be assortative, while if $r<0$ it is said to be
disassortative. If $r=0$ the network is uncorrelated. Using eq. (5) and eq.
(2), the assortativity in eq. (7) can be written explicitly as

$r=\frac{1}{2L}\sum_{i,j}\frac{A_{ij}(k_{i}-\text{E}[k])(k_{j}-\text{E}[k])}{\sigma_{k}^{2}}.$
(9)

This expression highlights that assortativity as the measure of the
correlations between degree fluctuations (around the mean value) on two
neighbouring nodes. In particular, if $A_{ij}=1$, the product

$\displaystyle(k_{i}-\text{E}[k])(k_{j}-\text{E}[k]),$ (10)

shows that edges for which, at both extremities $k_{i}>\text{E}[k]$ and
$k_{j}>\text{E}[k]$ or, $k_{i}<\text{E}[k]$ and $k_{j}<\text{E}[k]$ contribute
positively to the assortativity. However, edges for which
$k_{i}<\text{E}[k]<k_{j}$ or $k_{j}<\text{E}[k]<k_{i}$ will contribute
negatively. Therefore, the assortativity expresses the weighted balance
between the number of edges for which both extremities have a degree under or
over the mean and the number of edges for which the mean sits between the
degree of each extremities.

We propose an alternative way to approach the assortativity and define the
probability $\Psi(K,\Delta)$, where, if $A_{ij}=1$, $K=k_{i}+k_{j}$ and
$\Delta=k_{i}-k_{j}$. This is the probability that the degrees of the nodes at
the end of a randomly chosen edge sum to $K$, and differ by $\Delta$. This is
given by

$\displaystyle\Psi(K,\Delta)=\frac{1}{2L}\sum_{ij}A_{ij}\delta_{k_{i}+k_{j},K}\delta_{k_{i}-k_{j},\Delta}.$
(11)

Naturally, the averages of any observable ${\cal O}(K,\Delta)$ is defined as
${\rm E}[{\cal O}(K,\Delta)]=\sum_{K,\Delta}\Psi(K,\Delta){\cal O}(K,\Delta)$.
We can show that the assortativity becomes

$\displaystyle
r=\frac{\sigma^{2}_{K}-\sigma^{2}_{\Delta}}{\sigma_{K}^{2}+\sigma_{\Delta}^{2}},$
(12)

where $\sigma^{2}_{K}$ and $\sigma^{2}_{\Delta}$ are defined as

$\displaystyle\sigma^{2}_{K}$ $\displaystyle=$ $\displaystyle{\rm
E}[K^{2}]-{\rm E}[K]^{2},$ (13) $\displaystyle\sigma^{2}_{\Delta}$
$\displaystyle=$ $\displaystyle{\rm E}[\Delta^{2}].$ (14)

With this picture we now see that the assortativity compares the variance of
the marginal distribution $\psi_{+}(K)$ and $\psi_{-}(\Delta)$,

$\displaystyle\psi_{+}(K)$ $\displaystyle=$
$\displaystyle\frac{1}{2L}\sum_{ij}A_{ij}\delta_{k_{i}+k_{j},K}.$ (15)
$\displaystyle\psi_{-}(\Delta)$ $\displaystyle=$
$\displaystyle\frac{1}{2L}\sum_{ij}A_{ij}\delta_{k_{i}-k_{j},\Delta}.$ (16)

Plotting this distribution allows one to visualise the behaviour of the
assortativity. Finally, note that the expected statistical error for the
assortativity can be calculated using either the jackknife method [24] or the
bootstrap method [25].

###  II.2 Generalisation

In this section, we provide a definition of assortativity beyond nearest
neighbours. We consider the simplest possible approach, by defining the matrix
$A(d)$ with elements being $1$ (respectively $0$) whenever there exist at
least one (respectively no) shortest path, of length $d$, between nodes $i$
and $j$. In other words $A_{ij}(d)=1$ if there is a path of length $d$ between
the two nodes and if $A_{ij}(l)=0$ for all $l<d$. This allows us to define
$\Phi(\kappa,\eta,d)$ as

$\displaystyle\Phi(\kappa,\eta,d)=\dfrac{1}{2L(d)}\sum_{ij}A_{i,j}(d)\delta_{k_{i}\kappa}\delta_{k_{j}\eta},$
(17)

with $2L(d)=\sum_{i,j}A_{ij}(d)$.

The assortativity at a distance $d$ is

$r(d)=\sum_{ij}\frac{A_{ij}(d)}{2L(d)}\frac{(k_{i}-\text{E}[k](d))(k_{j}-\text{E}[k](d))}{\sigma_{k}^{2}(d)},$
(18)

with $\sigma_{k}^{2}(d)=\text{E}[k^{2}](d)-\text{E}[k](d)^{2}$. This can be
extended to other properties of nodes other than degree as we will demonstrate
later (see fig. 3).

##  III Application

Table 1:  The number of nodes is given by $N$, $L$ is the number of edges, $\langle k\rangle$ is the mean degree, $k_{\text{max}}$ is the largest degree in the network, $\langle k^{2}\rangle$ is the mean of the square of the degree (related to the variance). The average path length is given by $\ell$ and the diameter by $\ell_{\text{max}}$. The assortativity is denoted by $r$ and the symbol * signals that the statistical error is larger than this value indicating there are no degree-degree correlations.  | $N$ | $L$ | $\langle k\rangle$ | $k_{\text{max}}$ | $\langle k^{2}\rangle$ | $\ell$ | $\ell_{\text{max}}$ | $r$
---|---|---|---|---|---|---|---|---
Faux Mesa high school | 147 | 202 | 2.75 | 13 | 11.70 | 6.81 | 16 | 0.12
Jazz Musicians | 198 | 2,742 | 27.70 | 100 | 1,070.24 | 2.24 | 6 | 0.02*
Infectious diseases | 410 | 2,765 | 13.49 | 50 | 252.43 | 3.63 | 9 | 0.23
Network Science | 1,461 | 2,742 | 3.75 | 34 | 26.05 | 5.82 | 17 | 0.46
Moreno - Health | 2,539 | 10,455 | 8.24 | 27 | 86.41 | 4.56 | 10 | 0.25
Petster | 2,426 | 16,631 | 13.71 | 273 | 582.93 | 3.59 | 10 | 0.05
PGP web of trust | 10,680 | 24,316 | 4.55 | 205 | 85.98 | 7.49 | 24 | 0.24
cond-mat arXiv | 16,726 | 47,594 | 5.69 | 107 | 73.57 | 6.63 | 18 | 0.19
Astrophysics | 18,771 | 198,050 | 21.10 | 504 | 1,379.51 | 4.19 | 14 | 0.21
Twitter | 23,370 | 32,831 | 2.81 | 238 | 108.17 | 6.30 | 15 | -0.48
Gplus | 23,628 | 39,194 | 3.32 | 2,761 | 1,250.88 | 4.03 | 8 | -0.39
Munmun | 30,398 | 86,312 | 5.68 | 285 | 159.74 | 4.67 | 12 | 0.01
Facebook Wall | 46,952 | 193,494 | 8.24 | 223 | 202.87 | 5.60 | 18 | 0.25
Facebook | 63,731 | 817,035 | 25.64 | 1,098 | 2,256.80 | 4.32 | 15 | 0.18
Slashdot | 79,116 | 467,731 | 11.82 | 2534 | 1,729.86 | 4.04 | 12 | -0.07
Enron email | 87,273 | 299,220 | 6.86 | 1,728 | 1,147.24 | 4.89 | 13 | -0.17

In this section we analyse the assortativity of 16 different social networks
of varying size. We focus on eq. (16) for these empirical networks, and then
calculate the assortativity as a distance for each network.

The datasets we use are (i) the students at Faux Mesa high school friendship
network [26, 27]; (ii) the American jazz musicians from 1912 to 1940 [28];
(iii) the face-to-face contact of participants at an infectious diseases
exhibition in Dublin’s Science Gallery [29]; (iv) a coauthorship network of
scientists working on network theory and experiment [30]; (v) a Friendship
network at Moreno high school [31, 32]; (vi) a Friendship network between
users of the petster website [33]; (vii) a key-sharing network from the PGP
(Pretty Good Privacy) web of trust [34]; (viii) collaboration networks of
authors on the condensed matter arXiv from 1995 to 2005 [35]; (ix) the
Astrophysics collaboration network [37, 36]; (x) a Twitter user network [39,
38]; (xi) a Google+ user network [39, 40]; (xii) a reply network for news site
digg [41, 42]; (xiii) a Facebook wall post network [43, 44] (xiv) a sample of
Facebook users in the New Orleans region [47]; (xv) a network of users of the
technology news site slashdot [48, 49]; and (xvi) the network of emails sent
at Enron [45, 46]. All datasets bar (ii), (iii), and (viii) can be found on
Konect.cc [50]. Konect is an open source library of network datasets taken
from a wide range of scientific areas.

Figure 1: Distributions $\psi_{+}(K)$ and $\psi_{-}(\Delta)$, as indicated, of the sum and difference in degrees of nodes at either extremity of an edge respectively. Panel (a) shows the Enron email network. This network is disassortative and there are numerous edges with a difference of degrees of $|\Delta|=1382$. In contrast the PGP web of trust $\psi_{-}(\Delta)$ distribution is shown in panel (b). This is assortative and has less noise in the tail of the $\psi_{-}(\Delta)$ distribution. Panel (c) displays the Facebook users network which is also assortative. Panel (d) however is for the online social network of slashdot users. This network is disassortative and contains a large number of fluctuations as $|\Delta|$ increases. Table 2: The number of pairs $n_{\rm{pairs}}(d)$ and their corresponding assortativity values $r(d)$ up to $d=3$ for each of the 12 networks. The value in parentheses after the assortativity is the error in the last digit calculated using the bootstrap method. For most networks, the assortativity goes to zero (or fluctuates around it) after a small number of steps. A notable exception is that of jazz musicians which becomes more disassortative as $d$ increases. | $n_{\rm{pairs}}(1)$ | $r(1)$ | $n_{\rm{pairs}}(2)$ | $r(2)$ | $n_{\rm{pairs}}(3)$ | $r(3)$
---|---|---|---|---|---|---
Faux Mesa high school | 202 | 0.12 (8) | 410 | -0.14 (5) | 561 | -0.05 (5)
Jazz Musicians | 2,742 | 0.02 (2) | 10,652 | -0.13 (1) | 5,067 | -0.31 (2)
Infectious diseases | 2,765 | 0.23 (2) | 13,150 | -0.00 (1) | 24,631 | -0.06 (1)
network science | 2,742 | 0.46 (3) | 3,980 | -0.03 (2) | 6,365 | -0.03 (2)
Moreno-Health | 10,455 | 0.25 | 71,624 | 0.09 | 365,757 | -0.00
Petster | 16,631 | 0.05 | 222,693 | -0.14 | 757,751 | -0.17
PGP web of trust | 24,316 | 0.24 (1) | 188,183 | 0.01 (1) | 932,993 | -0.09 (1)
cond-mat arXiv | 47,594 | 0.19 (1) | 275,120 | 0.07 (1) | 1,439,255 | -0.02 (1)
Astrophysics | 198,050 | 0.21 | 4,441,041 | -0.08 | 35,788,064 | -0.19
Twitter | 32,831 | -0.48 | 1,110,048 | 0.12 | 2,534,785 | -0.11
Gplus | 39,194 | -0.39 | 12,928,409 | 0.00 | 4,494,516 | -0.01
Munmun-Digg | 86,312 | 0.01 | 2,169,143 | -0.06 | 33,925,631 | -0.14
Facebook Wall | 193,494 | 0.25 | 3,149,984 | 0.06 | 32,678,260 | -0.10
Facebook | 817,035 | 0.18 | 31,073,418 | -0.04 | 357,008,740 | -0.14
Slashdot | 467,731 | -0.07 | 47,324,811 | -0.08 | 696,650,899 | -0.11
Enron email | 299,220 | -0.17 | 27,781,955 | -0.05 | 282,174,082 | -0.07
Figure 2: The degree-degree correlations $r(d)$ plotted versus the distance
$d$. Panel (a) shows as $d$ increases for the PGP and Facebook networks, they
lose their correlations. Panel (b) shows the correlations for three time
periods on the condensed matter arXiv, which after $d=2$ become anti-
correlated. Error bars are calculated using the bootstrap method (they become
more prominent at the end due to a significantly smaller number of pairs
separated for large $d$). Figure 3: Correlations in the number of papers $p$
per author in the scientific coauthorship network dervied from the condensed
matter arXiv. Networks are the result of aggregation from the year 1995 to
that indicated.

Some basic properties of these networks are listed in table 1. In Refs. [12,
1], it is observed that social networks tend to be assortative while non-
social networks are not. Here, four of these social networks are found to be
disassortative, and one is almost zero (with the error being larger than the
value). The disassortativity in the network of Marvel Universe characters is
described as being one of the reasons it is dissimilar to real social networks
in Ref. [51]. The Twitter and Google+ networks show the same disassortative
behaviour of other large online social networks [2]. The slashdot network also
contains ‘hostile’ or ‘negative’ edges. As shown in Refs. [52, 53], hostile
edges contribute towards disassortativity. To examine this further, in the
Enron email network we plot the $\psi_{+}(K)$ and $\psi_{-}(\Delta)$
distributions from eq. (15) and eq. (16) in Fig. 1, and compare them to two
assortative networks.

In Fig. 1 (a), the distributions $\psi_{+}(K)$ and $\psi_{-}(\Delta)$ are
shown for the Enron email network. In the tail of the $\psi_{-}(\Delta)$
distribution in particular, we observe a high fraction of edges with
$|\Delta|=1382$. Hence the node with the highest degree interacts with
multiple nodes which interact with no other nodes in the network. This
strongly contributes towards the disassortativity. The PGP web of trust
network on the other hand has a relatively low maximum degree, and low degree
variance. It is assortative, and we observe in Fig. 1 (b) that there are
comparatively few fluctuations in $\Delta$.

In Fig. 1 (c-d) the $\psi_{+}(K)$ and $\psi_{-}(\Delta)$ distributions are
shown for the Facebook and slashdot networks respectively. The Facebook
network is assortatively mixed by degree while the slashdot one is not. There
are large fluctuations around $|\Delta|\approx 1500$ and $|\Delta|\approx
2500$ for the slashdot users which drives the disassortativity. However the
distribution for Facebook users decays with fewer fluctuations.

###  III.1 Influence

We turn our attention to correlations at a distance for these 16 social
networks. In table 2 the correlations for pairs of nodes separated up to an
edge distance of $d=3$ are displayed. For $d=1$, the number of pairs of nodes
$n_{\rm{pairs}}(d)$, and $r(d)$, simply correspond to the number of edges and
the traditional assortativity of the network, respectively. As $d$ increases,
the number of pairs increases rapidly. For most networks, $r(d)$ decreases
beyond a distance of $d=1$, and tends to fluctuate about $r(d)=0$ for values
of $d$ near the average path length $\ell$. None of the networks have positive
correlations at $d=3$, and only two networks have $r(2)>0$.

In Fig. 2 (a), $r(d)$ is plotted as a function of $d$ for two of the larger
assortative networks, namely the PGP web of trust and Facebook networks. In
each case, the networks are assortative at $d=1$, with $r_{k}$ decreasing
until $d=4$, by which point they are disassortative. Beyond $d=4$, values of
$r_{k}$ plateau below zero. In these networks, users distance $d=3$ apart are
unlikely to have similar degrees. This is not an unexpected result; as shown
in Ref. [54], an individual’s friends are not representative of a social
network, instead they are a biased population. Similarly, that reference shows
high degree nodes have a disproportionately large effect on networks at a
distance of $d=2$. This effect seems to increase with $d$, implying that as
distances increase, people become more dissimilar.

This method is quite different to the degrees of influence observed by Refs.
[9, 10]. There, the authors study social networks evolving in time, and focus
on correlations between node attributes besides degree, such as obesity and
happiness. In contrast, we focus on degree correlations, on networks that have
either been aggregated in time, or extracted at a snapshot in time. One
exception, however, is the condensed matter arXiv network, which we examine
over multiple time periods; 1995-1999, 1995-2003 and 1995-2005 [35]. Fig. 2
(b) shows the degree-correlations $r$ as a function of distance $d$ for these
time periods. They each have positive values of $r$ for $d=1$, which become
negative as as $d$ increases. Note that we have adopted the subscript $k$ to
distinguish degree correlations from correlations in the number of scientific
papers, which we study in the next figure.

Although our focus is on degree correlations, one may study correlations as a
function of distance for arbitrary node attributes. The scientific
coauthorship network, for instance, details the number of papers $p_{i}$ that
author $i$ has published. Studying correlations in this quantity provides a
measure of the output assortativity of the collaboration network. These
results are shown in Fig. 3, where we plot output correlation $r_{p}$ as a
function of distance $d$. These are correlated initially among nearest
neighbours, implying productive authors have productive coauthors, and
unproductive authors have unproductive coauthors. Small but nonzero
correlations exist at $d=2$ in the first two time-periods but are decorrelated
for the final time point. For $d>2$, there are no positive correlations
present. Therefore, on average, two authors three steps away from one another
in this coauthorship network are unlikely to have a similar number of
publications and this seems to become less similar as time goes on. At higher
$d$ values then, authors are more likely to have a different number of
publications to their distant neighbours.

##  IV Simulations

Having studied the behaviour of the assortativity for increasing $d$ in
empirical networks, we turn our attention to simulated networks. Here we will
examine three types of simulated network; Erdős-Rényi graphs, Erdős-Rényi
graphs that we have made assortative by rewiring, and configuration model
graphs corresponding to each of the empirical networks in table 1.

###  IV.1 Erdős-Rényi graphs

Here we generate Erdős-Rényi graphs and calculate $r(d)$ for all values of $d$
such that $1\leq d\leq l_{\text{max}}$, where $l_{\text{max}}$ is the diameter
of the graph. This is repeated 1000 times each for Erdős-Rényi graphs of size
$N=1000$, with average degree $\langle k\rangle=5$, 10, and 15. We then repeat
this 1,000 times each for graphs of size $N=10000$, again with $\langle
k\rangle=5$, 10, and 15. The results of these calculations are shown below in
Fig. 4.

As we can see, there are no positive correlations between the degrees of nodes
at any value of $d$. Negative correlations begin to emerge in all cases at or
beyond the average path lengths of the graphs, indicated as dashed vertical
lines. This finding is in line with the work of Mayo et al. [17], who find
negative correlations emerge when the average degree is greater than one.
While high-degree nodes are exponentially suppressed in Erdős-Rényi graphs,
negative correlations still emerge due to the finite size of the simulations.
That is, paths of higher values of $d$ still connect central nodes to nodes at
the periphery of the graph. It is reasonable to expect that the degrees of
such pairs of nodes would be dissimilar, thus reducing the assortativity at
these $d$ values.

Figure 4: Results for Erdős-Rényi graphs with 1,000 nodes (top), and 10,000
nodes (bottom). Points are average values for 1,000 instances of each size and
average degree, error bars are 95 percent coverage bars for the assortativity
values observed. Vertical dashed lines represent the mean average path length
of each set of 1,000 graphs. As we can see in all cases the networks became
anticorrelated as $d$ increases.

###  IV.2 Configuration models networks

We now examine the assortativity as a function of $d$ for configuration model
variants of the networks Infectious disease through Munmun-Digg in table 1.
For each network, 100 instances of the corresponding configuration model
network were created, and the assortativity calculated for all $d$ values up
to the diameter of each graph. Results for the network science coauthorship,
PGP web of trust, and Munmun-Digg networks can be seen in Fig. 5. These
results are representative of the remaining networks not shown.

In all cases we find that the assortativity rapidly decreases before beginning
to increase and approach zero for higher values of $d$. In the three cases
shown here we also see large fluctuations at the largest value of $d$ for each
network. These fluctuations are due to the fact that at these large $d$
values, there are very few pairs separated by a shortest path of that length
$d$.

One possible explanation for the decrease in assortativity is that the
quantity reaches its minimum when the influence of hubs in the network is at
its maximum. For example, high-degree nodes will be connected to many other
nodes by shortest paths of lengths 2 and 3, and these nodes will have degrees
that are dissimilar to that of the hub node, thus reducing the assortativity.
As $d$ increases further,the number of pairs of nodes separated by shortest
paths of length $d$ increases. Many of these pairs then will be positively
assortative, which counteracts the effect of the hub nodes.

To illustrate this further, we plot the number of pairs at each distance $d$
in Fig. 6. Here we see after the average path length (dashed vertical line),
these is a sharp drop in the number of pairs. Beyond this point, the hubs have
probably reached every periphery node, but nodes at different ends of the
network still have not been used. As the hub is likely to be at a different
side of $E(k)$ to a periphery node in Eq. (9), their influence will contribute
negatively to the assortativity. This difference in degree for neighbours can
be seen in Fig. 1, these spikes will only increase as the number of paths
increase.

Figure 5: Degree assortativity $r$ as a function of shortest paths length $d$,
for configuration model variants of the network science coauthorship network,
the PGP security network, and the Munmun-Digg network. Error bars are 95 per
cent coverage bars for the assortativity values.

Figure 6: The number of pairs for each shortest path length $d$ for the
Network Science coauthors (top) and PGP web of trust (bottom). The dashed
vertical line represents the average path length of the original network.

###  IV.3 Modified Erdős-Rényi graphs

Here we start with Erdős-Rényi graphs of size $N=1000$ and average degree
$\langle k\rangle=5$, 10, and 15. We run a rewiring algorithm on 1000
instances of each graph and calculate the assortativity for all values of $d$
up to the diameter of the rewired graph. The algorithm works by randomly
removing edges that decrease the assortativity, and replacing them with edges
that increase the assortativity, as per eq. 9. This process is repeated until
the desired value of first-neighbour assortativity is reached, choosing
$r=0.4$ for graphs size $N=1000$ and $r=0.25$ for graphs of size $N=10000$.
The results for this process are shown in Fig. 7. This approach is then
repeated $500$ times for Erdős-Rényi graphs of size $N=10000$ and average
degrees $\langle k\rangle=5$ and 10, and 250 times for Erdős-Rényi graphs of
size $N=10000$ and average degree $\langle k\rangle=15$. The reduced number of
iterations here is due to the increased computational cost of rewiring larger
graphs. As the number of nodes and edges increases, the contribution that each
edge makes to the overall assortativity decreases and so many more iterations
of the rewiring algorithm are required to reach the desired assortativity
value.

As we can see, all of the graphs started out assortative at $d=1$ due to the
rewiring algorithm, but these positive correlations quickly disappear as $d$
increases, and beyond the average path lengths, the results are very similar
to those seen for the Erdős-Rényi graphs in fig 4. This is not a great
surprise, but serves to highlight that the degree distribution plays a role
the behaviour of the decay of the assortativity as the value of $d$ increases.

Figure 7: Correlations between the degrees of nodes separated by shortest
paths of length $d$ for Erdős-Rényi graphs of size 1000 nodes (top, 1,000
instances for each value of $k$), and 10,000 nodes (bottom, 500 instances each
for $k=5$ and $k=10$, 250 instances for $k=15$) that have been rewired to be
assortative. Vertical dashed lines represent the mean average path length of
each set of 1,000 graphs. The error bars are 95 per cent coverage bars for the
assortativity values.

##  V Conclusions

Social networks are generally found to be assortatively mixed by degree, a
property separating them from other complex networks. Here we extend this to
go beyond nearest neighbours in order to test if they remain assortative or if
this changes as the distance increases. We find that for all cases, as the
edge distance between nodes increases, degree-degree correlations vanish. In
some cases, they become anti-correlated before becoming decorrelated. In all
16 social networks, nodes three steps away from each other are more likely to
have dissimilar degrees. That is, nodes three steps away from each other are
more likely to have degrees on either side of the average value $\text{E}(k)$.
The same is true of number of papers in the condensed matter arXiv
coauthorship network, and in that dataset, over time, both quantities become
less correlated as time increases.

We performed simulations on three different types of network to test this.
With Erdős-Rényi random graphs, correlations remain close to zero as expected
from mean-field arguments for distances $d$ up to the average path length.
Beyond this, while correlations become negative, there are fewer pairs
corresponding to these distances, and fluctuations are large as a result.
Further, this seems to be a reflection of the finite size of the simulations,
with pairs of distant nodes tending to consist of one high-degree node, and
one peripheral node at the end of a chain. In contrast, configuration model
variants of real-world networks, correlations quickly become negative as a
function of $d$. Finally in Erdős-Rényi graphs rewired for assortativity,
correlations become negative for distance beyond the average path length, as
before. This is due to their similarity to Erdős-Rényi random graphs, despite
rewiring.

We attribute the decreasing degree correlations to the right-skewed
distributions of the empirical datasets and, hence, the influence of hubs in
these networks. Hubs are nodes with large degrees, and due to the initial
assortativity in social networks, they are in general more likely to connect
to nodes with a similar degree. However, they will have quite different
degrees to others as the distance increases. With the calculation for the
assortativity, if the degrees are on either side of the average degree at the
end of an edge this contributes negatively towards the assortativity value.
Therefore, as the distance increases, a pair is more likely to contain a well
connected node and one at the periphery. As the number of pairs increases
significantly at each step, these high degree nodes interact more and more
with low degree nodes. However, by a distance around the average path length,
a hub may be connected to every node in the graph. Beyond this distance then,
the influence of hubs on the assortativity value is diminished.

To investigate this further, we next aim to explore the role of the degree
distribution with beyond nearest-neighbour correlations and identify how much
influence hubs play on this. We also aim to explore more of the behaviour of
disassortative networks, both in empirical data and simulations. Finally the
assortativity at a distance here is calculated from the point of view of one
shortest path between a pair, this could be weighted by the number of shortest
paths, this is another extension we intend to explore.

In Ref. [17], using an average degree approach for three social networks it
was also shown that the assortativity decreases as the distance increases.
Here we show that for more social networks, as well as simulated networks,
this is always the case. Similarly on a network at different time points, both
assortativity and a further property become negative at distances above 2.
These anti-correlations get stronger as time increases. This result is the
opposite of what the “three degrees of influence” work would suggest. Our work
instead implies, that in a social network, the more distant you are from
someone, the more likely you are different to them. This is related to the
idea of the “friendship paradox” – that your friends, on average, have more
friends than you – and is also likely because social networks are right-
skewed.

This again implies that our observations of the correlations between nodes
separated by distances greater than one here are tied to the degree
distributions of the graphs, and the future work outlined above will help to
explain this connection.

## Funding

SM and SU are funded by the Science Foundation Ireland under Grant numbers
18/CRT/6049 and 16/IA/4470 respectively.

## Acknowledgment

The authors would like to thank Ralph Kenna for ideas on assortativity and
conceptual discussions.

## References

  * [1] Newman M.E.J. and Park J., Phys. Rev. E 68, 036122 (2003).
  * [2] Hu H.B., & Wang X.F. EPL (Europhysics Letters), 86(1), 18003 (2009).
  * [3] Wilson K.G., Sci. Am. 241, 158-179 (1979).
  * [4] Stauffer D., arXiv:1109.2475.
  * [5] Galam S., J. of Stat. Phys. 61, 943-951 (1990).
  * [6] Sznajd-Weron K., Acta Physica Polonica B, 36, no. 8 (2005).
  * [7] Li, Chengcheng, Fengming Liu, and Pu Li. Discrete Dynamics in Nature and Society 2018 (2018).
  * [8] da F. Costa L. et al., Advances in Physics, V. 60(3) 329-412 (2011).
  * [9] Christakis N. and Fowler J., The New England Journal of Medicine 357, 370-379 (2007).
  * [10] Christakis N. and Fowler J., Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives. Little Brown, New York (2009).
  * [11] Lyons R, Statistics, Politics, and Policy 2(1), Article 2 (2011).
  * [12] Newman M.E.J., Phys. Rev. Lett. 89, 208701 (2002).
  * [13] McPherson M., Smith-Lovin L., and Cook J. M., Annual Review of Sociology 27, 415-444 (2001).
  * [14] Arcagni, A., Grassi, R., Stefani, S., & Torriero, A. . European Journal of Operational Research, 262(2), 708-719 (2017).
  * [15] Fujiki, Y., Takaguchi, T., & Yakubo, K. Physical Review E, 97(6), 062308 (2018).
  * [16] Mizutaka, S., & Hasegawa, T. Journal of Physics: Complexity, 1(3), 035007 (2020).
  * [17] Mayo, M., Abdelzaher, A., & Ghosh, P. Computational Social Networks, 2(1), 1-13 (2015).
  * [18] Albert R. and Barabási A.-L., Rev. Mod. Phys. 74, 47 (2002).
  * [19] Newman M.E.J., SIAM Review 45, 167-256 (2003).
  * [20] Watts D.J. and Strogatz S.H., Nature 393, 440-442 (1998).
  * [21] Kaiser M., New Journal of Physics 10, 083042 (2008).
  * [22] Brandes U. & Erlebach T., Springer, Heidelberg (2005).
  * [23] Latapy M, Theoretical Computer Science, 407 no.1-3, 458-473, (2008)
  * [24] Efron B., SIAM Review 21, 460-480 (1979).
  * [25] Efron B. and Tibshirani R., Statistical science, 54-75 (1986).
  * [26] Resnick, M. D. et al. JAMA, 278(10), 823-832 (1997).
  * [27] Hunter, D. R., Goodreau, S. M., and Handcock, M. S.. Journal of the American Statistical Association, 103(481) (2008).
  * [28] Gleiser, P. M., and Danon, L. Advances in complex systems, 6(04), 565-573 (2003).
  * [29] Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J. F., and Van den Broeck, W. Journal of theoretical biology, 271(1), 166-180 (2011).
  * [30] Newman, M.E.J. Physical review E, 74(3), 036104 (2006).
  * [31] KONECT, http://konect.cc/networks/moreno_health/
  * [32] J. Moody. In Soc. Netw., 23(4): (pp. 261–283). 2001
  * [33] KONECT, http://konect.cc/networks/petster-hamster/
  * [34] Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A., and Arenas, A. Physical review E, 70(5), 056122 (2004).
  * [35] Newman, M.E.J. Proceedings of the National Academy of Sciences, 98(2), 404-409 (2001).
  * [36] KONECT, http://konect.cc/networks/ca-AstroPh/
  * [37] J. Leskovec, J. Kleinberg, and C. Faloutsos. ACM Trans. Knowl. Discov. from Data, 1(1), 1-40 (2007).
  * [38] KONECT, http://konect.cc/networks/ego-twitter/
  * [39] J. McAuley and J. Leskovec In Adv. in Neural Inf. Process. Syst., 548–556 (2012).
  * [40] KONECT, http://konect.cc/networks/ego-gplus/
  * [41] M. De Choudhury, H. Sundaram, A. John, and D. D. Seligmann. In Conf. on Comput. Science and Engineering, 151-158 (2009).
  * [42] KONECT, http://konect.cc/networks/munmun_digg_reply/
  * [43] B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi. In  On the evolution of user interaction in Facebook., 37-42 (2009).
  * [44] KONECT, http://konect.cc/networks/facebook-wosn-wall/
  * [45] Klimt, B., and Yang, Y. In Machine learning: ECML 2004 (pp. 217-226). Springer Berlin Heidelberg (2004).
  * [46] Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M.W.
  * [47] Viswanath, B., Mislove, A., Cha, M., and Gummadi, K. P. In Proceedings of the 2nd ACM workshop on Online social networks (pp. 37-42). ACM (2009, August).
  * [48] Kunegis, J., Lommatzsch, A., and Bauckhage, C. In Proceedings of the 18th international conference on World wide web (pp. 741-750). ACM (2009, April).
  * [49] KONECT, http://konect.uni-koblenz.de/networks/slashdot-zoo (2013, August).
  * [50] Kunegis, J. Proceedings of the 22nd international conference on world wide web, 2013: 1343–1350.
  * [51] Gleiser, P. M. Journal of Statistical Mechanics: Theory and Experiment, 2007(09), P09020 (2007).
  * [52] Szell, M., and Thurner, S. Social networks, 32(4), 313-329 (2010).
  * [53] Mac Carron, P., and Kenna, R. EPL (Europhysics Letters), 99(2), 28002 (2012).
  * [54] Newman, M.E.J. Social Networks, 25(1), 83-95 (2003).
  * [55] Barabási A.-L. & Albert R., Science 286, 509 (1999).