# A robust method for Fitting degree distributions of complex networks

Shane Mannion  MACSI, Department of Mathematics and Statistics, University of
Limerick, Limerick, V94 T9PX, Ireland  Pádraig MacCarron  MACSI, Department of
Mathematics and Statistics, University of Limerick, Limerick, V94 T9PX,
Ireland

###### Abstract

This work introduces a method for fitting to the degree distributions of
complex network datasets, such that the most appropriate distribution from a
set of candidate distributions is chosen while maximizing the portion of the
distribution to which the model is fit. Current methods for fitting to degree
distributions in the literature are inconsistent and often assume a priori
what distribution the data are drawn from. Much focus is given to fitting to
the tail of the distribution, while a large portion of the distribution below
the tail is ignored. It is important to account for these low degree nodes, as
they play crucial roles in processes such as percolation. Here we address
these issues, using maximum likelihood estimators to fit to the entire
dataset, or close to it. This methodology is applicable to any network dataset
(or discrete empirical dataset), and we test it on over 25 network datasets
from a wide range of sources, achieving good fits in all but a few cases. We
also demonstrate that numerical maximization of the likelihood performs better
than commonly used analytical approximations. In addition, we have made
available a Python package which can be used to apply this methodology.

##  I Introduction

Although complex networks have been studied for around a quarter of a century,
there is still a lack of consistency in determining one of their core
properties – namely, the degree distribution. One of the early observations
about complex networks was that their degree distributions differed from those
of the random graph models which had been studied for many years before.
Specifically it was observed that complex networks had right-skewed
distributions, and Barabási and Albert claim that these right tails often
followed power-law distributions [1]. Their work appears to show that
different types of networks have different power-law exponents and these
exponents are often in the range $2\leq\gamma\leq 3$.

However, Amaral et al. [2] argue that power-law distributions are not so
common and suggest that for social networks other distributions are sometimes
more appropriate. In addition they define three classes of small-world
networks: power-law or ‘scale-free’ networks, ‘broad-scale’ networks (power-
law distributions with sharp cut-offs), and ‘single-scale’ networks, which
have distributions that decay quickly, such as exponential or Gaussian
distributions. The distribution of the network determines which of these
classes it belongs to.

More recently, Broido & Clauset [3] argue that scale-free networks are rare.
They introduce a strict procedure for identifying power-laws as well as
several weaker regimes. This method, however, tends to be more focused on the
tail of the distribution, as even the strongest criteria they outline only
requires a power-law to be a good fit to the 50 highest-degree nodes and the
method requires comparing to many simulated graphs which are generated under
strict conditions. It is more concerned with whether or not evidence can be
found to support or rule out a power-law distribution than being able to
robustly identify the most appropriate distribution.

Knowing the distribution of a graph is important as it allows us to model and
estimate other properties of the network structure. Similarly, it allows us to
build general models for the formation of complex networks such as the
preferential-attachment model [1]. The preferential-attachment model is still
one of the most popular complex network formation models, though it requires
the degree distribution to follow a power law, or at least with slight
deviations from it.

The question of what distribution a given network’s degree distribution
follows remains a heavily researched topic (see [4, 3]). In addition, some
controversy exists around the prevalence of power-law distributions in
empirical networks [3, 5, 6].

Despite this, current methods for fitting degree distributions are
inconsistent. Often still, the method of least squares is used to determine
the parameter of a distribution, despite work highlighting the issues with
this approach [7]. The method of least squares has several drawbacks, for
example, in the case of a power-law distribution, one would plot the
distribution on a log-log scale and use least squares to determine the slope
of the relatively straight line through the data. This assumes a priori that
the data is a power-law however, and data appearing as a relatively straight
line on a log-log scale is not a sufficient condition to rule out other
possibilities. Additionally, it is not applicable to data that is less easy to
linearize.

A better method is described in the work of Clauset et al. [8]. This uses the
method of maximum likelihood to estimate the parameters of the distribution.
This method is intended for general empirical datasets. A problem with using
it to specifically fit degree distributions is that it focuses on fitting to
the tail of the distribution, and in doing so can ignore huge amounts of the
data available, as we will discuss in Section III. Nodes with a low degree are
important for percolation processes [9] and community identity in social
networks [10], choosing a high degree cut-off will miss these.

In this paper we build on the method of Clauset et al. [8] in order to
identify the most appropriate distribution for the degree distribution of a
network from a set of candidate distributions and apply this methodology to a
variety of network datasets. We do this while taking minimal approximations
(for example using a minimum value of $k_{\rm min}$), which are discussed in
more detail throughout this paper. The methods are applicable to any network
dataset and do not rely on choosing things such as $k_{\rm min}$ or the
distribution by eye.

The rest of this paper proceeds as follows. In the next section we cover
important background information concerning some basics of network science. In
Section III we cover power-law distributions, methods of estimating power-law
exponents and maximum likelihood estimators. Section IV compares the estimates
for the power-law exponent covered in the previous section. In Section V we
introduce the distributions which we use in our methodology before discussing
model selection and goodness of fit in Section VI. Section VII describes in
detail exactly how our methodology works. An in-depth analysis of the results
we obtain and discussion around them are found in Sections VIII and IX.

A Python package for the implementation of these methods is included in
Appendix A.

##  II Background

A network is defined as an ordered set of $N$ nodes and $M$ edges between
them. In this work we are concerned with unweighted and undirected networks,
however the methods described can be easily applied to weighted degree
distributions and directed networks. Nodes and edges can represent many things
in different networks. For example, nodes may represent people in a social
network and the edges represent friendship ties between them.

The degree of a node is the number of edges connected to it. The distribution
of the degrees in a network gives some important characteristics related to
its structure. The degree distribution $p_{k}$ is the fraction of vertices in
a network with degree $k$,

$p_{k}=\frac{1}{N}\sum_{i=1}^{N}\delta_{k_{i}k},$ (1)

where $k_{i}$ is the degree of node $i$ and $\delta_{k_{i},k}$ is the
Kronecker delta function which is one if $k_{i}=k$ and zero otherwise. We are
assuming there are no nodes of degree zero in the network. We use $p_{k}$ to
denote probability mass functions (for discrete distributions) and $p(k)$ to
denote probability density functions (for continuous distributions).

For complex networks, degree distributions are often found to have a positive
or right skew [11], which is also referred to as being heavy-tailed. These
heavy tails are frequently due to a small number of vertices having very large
degrees. Such highly connected nodes are often referred to as hubs. In
contrast, Erdős-Rényi graphs tend to lack hubs due to having a small standard
deviation in their degree when compared to complex networks.

In Figure 1 we display the degree distribution for protein interactions in
yeast, data taken from [12]. The distribution has a noisy tail due to many
instances of only one vertex with a specific (large) degree. To reduce the
noise in the tail we often consider instead the complementary cumulative
distribution function (CCDF) for the dataset [11]. This is the probability
that a node has a degree greater than or equal to $k$ and is denoted $P_{k}$:

$P_{k}=\sum_{j=0}^{\infty}p_{k+j}=\sum_{q=k}^{\infty}p_{q}.$ (2)

Figure 1: Degree distribution for yeast protein interactions on a log-log
scale (a) and the complementary cumulative degree distribution, again on a
log-log scale.

##  III Power-Law distributions

One of the most common and thoroughly studied distributions observed in
complex networks is the power-law distribution [13, 14]. A power-law
distribution has the form

$p_{k}\sim k^{-\gamma},$ (3)

where the exponent of the power-law, $\gamma\geq 1$. This is the most basic
definition of a power-law, though the criteria for what is classified as a
power-law is a much debated topic in network science (see [3] for a summary of
different definitions). As discussed in Section I, this behaviour is usually
found only in the tail of the distribution beginning at some value $k_{\rm
min}$. If we take logarithm of Equation (3),

$\log p_{k}\sim\log{k^{-\gamma}\sim-\gamma\log{k}},$ (4)

we can see that the relationship between the log of $p_{k}$ and the log of $k$
is linear. Hence, when a power-law is displayed on a log-log scale, it will
appear linear.

Therefore, one way in which we can obtain an estimate for the exponent
$\gamma$ is by performing a least squares regression on Equation (4). In this
section we look at this and other methods of estimating the power-law
exponents. First, we must normalize Equation (3). We start with

$\sum_{k=1}^{k_{\rm min}-1}\rho_{k}+\sum_{k=k_{\rm min}}^{k_{\rm
max}}p_{k}=1,$ (5)

where $\rho_{k}$ is the distribution below $k_{\rm min}$. Our equation
therefore becomes

$p_{k}=\frac{(1-\Delta)}{\zeta(\gamma,k_{\rm min})}k^{-\gamma},$ (6)

where

$\Delta\equiv\sum_{k=0}^{k_{\rm min}-1}\rho_{k}\;\;{\rm
and}\;\;\zeta(\gamma,k_{\rm min})\equiv\sum_{n=0}^{\infty}(k_{\rm
min}+n)^{-\gamma}.$

Here, $\zeta(\gamma,k_{\rm min})$ is the Hurwitz-zeta function. In the case
where the entire distribution follows a power-law and $k_{\rm min}=1$, the
denominator is just the Riemann zeta function $\zeta(\gamma)$. The
complementary cumulative distribution function for the full degree
distribution is given by

$P_{k}=\sum_{q=k}^{\infty}p_{q}=(1-\Delta)\frac{\zeta(\gamma,k)}{\zeta(\gamma,k_{\rm
min})}.$ (7)

### Continuous Approach

Often when fitting, the approximation is made that the distribution is
continuous instead of made up of discrete integers. We now consider the
continuous regime to introduce an approximation for the exponent of a power-
law before returning to the discrete case. In the continuous case, Equation
(3) can be normalized by

$\int_{0}^{k_{\rm min}}\rho(k)\,dk+\int_{k_{\rm min}}^{\infty}p(k)\,dk=1,$

where $\rho(k)$ is some unknown distribution below $k_{\rm min}$. The
normalized distribution is then

$p(k)=(1-\delta)\frac{\gamma-1}{k_{\rm min}}\left(\frac{k}{k_{\rm
min}}\right)^{-\gamma},$ (8)

where $\delta\equiv\int_{0}^{k_{\rm min}}\rho(k)\,dk$ is treated as constant.
We can then integrate Equation (8) to determine the cumulative distribution
function,

$P(k)=\int_{k_{\rm min}}^{\infty}p(q)\,dq=(1-\delta)\left(\frac{k}{k_{\rm
min}}\right)^{-\gamma+1}.$

We can see from this that the cumulative distribution function also follows a
power-law but with an exponent differing by one to the original. As with
Equation (4), a least squares fit to the cumulative distribution can be used
to determine an estimate for the exponent. This estimate will usually provide
a better fit than a fit to the probability density function as the cumulative
distribution is less noisy in the tail [11].

### Moments of The Distribution

If we make the assumption that the distribution can be used for the entire
data (i.e., set $k_{\rm min}=1$) and thus $\delta\rightarrow 0$, the
probability density function Equation (8) is

$p(k)=(\gamma-1)k^{-\gamma}.$ (9)

Since the probability that $k=1$ is bounded by unity, we must have $\gamma<2$.
The first moment of Equation (9) is

$\langle
k\rangle=(\gamma-1)\frac{1}{2-\gamma}\left[k^{2-\gamma}\right]^{\infty}_{1}.$
(10)

If $\gamma\leq 2$, then $\langle k\rangle$ will diverge when we evaluate this
integral (for the discrete case it will be a large finite value). As a result,
we should use $k_{\rm min}>1$ to remain consistent with $k=1$ implying
$\gamma<2$. Empirically in complex networks we often observe that the mean
degree is often low compared to the size of the network. Hence, choosing a
high value of $k_{\rm min}$ could lead to the distribution only being fitted
to a small number of nodes. Indeed, in the case of 1,000 simulated true power-
law distributions with $\gamma=2.5$, 918 of these have an average degree less
than three.

It may be also worth considering the using the modal degree as the value for
$k_{\rm min}$ as the distribution likely decays beyond this point. Clauset et.
al [8] provide various methods for estimating $k_{\rm min}$, however, they
assume large values of $N$, and so these methods may not be applicable to
smaller datasets. We aim to provide a methodology to fit to datasets of any
size. Methods for choosing $k_{\rm min}$ will be discussed in section VI. For
now we continue in the continuous regime. If $\gamma>2$ in Equation (10) then
we can obtain an estimate for $\gamma$ from the mean,

$\langle k\rangle=\frac{\gamma-1}{\gamma-2}\implies\gamma=\frac{2\langle
k\rangle-1}{\langle k\rangle-1}.$ (11)

We will use this as one of the estimates for the exponent. The same procedure
can be repeated for the second moment and we obtain

$\langle k^{2}\rangle=\int_{K_{\rm
min}}^{N-1}k^{2}p(k)\,dk\sim\frac{1}{3-\gamma}\left[k^{3-\gamma}\right]_{k_{\rm
min}}^{N}.$

As $N$ goes to infinity, one observes that the second moment diverges when
$\gamma\leq 3$. Therefore, if the degree distributions follow a power-law with
$\gamma\leq 3$, they would be expected to have a large value of $\langle
k^{2}\rangle$.

### Maximum Likelihood Estimators

From the continuous regime, we have three estimates for the exponent, 1) a
least squares fit to the log-log probability mass function, 2) a least squares
fit to the log-log complementary cumulative distribution function (exponent
will be different by one) and 3) an estimate from the first moment of the
degree distribution. We now turn our attention to the main focus of this paper
which is using maximum likelihood estimators to obtain estimates for
distribution parameters.

In general, the likelihood $\cal L$ is the probability that an independent and
identically distributed dataset of $N$ observations were drawn from a model
$p_{k}$ with parameter $\theta$,

${\cal L}(\theta|k)=\prod_{i}^{N}p_{\theta}(k_{i}).$ (12)

Here $k_{i}$ is the degree of node $i$ and $N$ is the number of nodes in the
network. As mentioned above, the complementary cumulative distribution in
Equation (2) is often used to reduce noise in the tail of the probability
distribution. Fits are then often made to the cumulative distribution $P_{k}$
rather than the original distribution $p_{k}$. It has been suggested that
applying the method of least squares to cumulative distributions is unsuitable
for empirical data [8, 15]. This is in part due to the data being discrete and
therefore the continuous approach to the complementary cumulative distribution
may not be appropriate (particularly for small datasets). Network data will
always contain dependencies between the observations, violating one of the
assumptions underlying maximum likelihood estimation [16]. Despite this, MLE
still shows good results as we see below and shown in Ref. [3].

Furthermore, the estimates for the parameters obtained using a least squares
fit can be inaccurate, and the error in the parameter value can be difficult
to estimate [8]. Instead, maximum likelihood estimators (MLEs) are said to
provide better measurements for the parameters as no estimator has lower
asymptotic error in the large sample size as the MLE [8].

Sticking with the continuous regime for now, the likelihood corresponding to
the power-law from Equation (8) is

${\cal L}(\gamma|k)=\prod_{i=1}^{N}(1-\Delta)\frac{\gamma-1}{k_{\rm
min}}\left(\frac{k_{i}}{k_{\rm min}}\right)^{-\gamma}.$ (13)

Taking the logarithm we obtain

$\ln{\cal L}=N\ln(1-\Delta)+N\ln(\gamma-1)-N\ln{k_{\rm
min}}-\gamma\sum_{i=1}^{N}\ln{\frac{k_{i}}{K_{\rm min}}}.$

We can obtain a value for $\Delta$ from the data. This does not affect the
maximisation, however, it is important to have an estimate for $\Delta$ when
displaying the fit to the distribution. Typically, $\Delta$ or
$\sum_{k=1}^{k_{\rm min}-1}\rho_{k}$ as in Equation (5), is ignored in works
such as ref. [8] or any other methodology that focuses on the tail of the
distribution. Here we aim to account for it as fully as possible, though it
does not affect the maximization.

We set $\partial(\ln{\cal L}/\partial\gamma)=0$ and solve analytically for an
estimate for the power-law exponent. We obtain

$\hat{\gamma}=1+N\left[\sum_{i=1}^{N}\ln\frac{k_{i}}{k_{\rm
min}}\right]^{-1},$ (14)

where $\hat{\gamma}$ denotes an estimate from the data rather than the true
value. If a power-law is a good model for the data then
$\hat{\gamma}\approx\gamma$. Our tests show however, that this estimate
performs relatively poorly and this will be discussed in the next section (see
Tables 1, 2, 3).

In addition, complex network data, even when relatively large, is rarely a
complete set of integers and there may be large gaps between consecutive
degrees. It is therefore much more accurate to look at the discrete case from
Equation (6). Taking the log likelihood of this we get

$\ln{\cal{L}}=N\,\ln(1-\Delta)-N\,\ln{\zeta(\gamma,k_{\rm
min})}-\gamma\,\sum_{i=1}^{N}\ln{k_{i}}.$ (15)

This can be numerically maximized to obtain an estimate for $\gamma$.
Additionally, Clauset et al. [8] find an approximation for the log likelihood
in Equation (15) as

$\hat{\gamma}=1+N\left[\sum_{i=1}^{N}\ln{\frac{k_{i}}{k_{\rm
min}-\frac{1}{2}}}\right]^{-1}.$ (16)

However, the convenience of this estimate comes at the cost of accuracy for
smaller networks, particularly with small $k_{\rm min}$ as we show later. We
compare all of these estimates in Section IV.

##  IV Comparison of Estimates

In the previous section we outlined four ways of obtaining estimates for the
power-law estimate $\gamma$. In this section we will compare these four
estimates along with estimates obtained by performing least squares on the
log-transformed PDF and CCDF of the data.

We denote as $\gamma_{\rm c}$ the estimate obtained from the continuous
version of the distribution as in Equation (14), $\gamma_{\rm mle}$ as the
maximisation of the discrete discrete log likelihood in Equation (15), and
$\gamma_{\rm d}$ as the discrete approximation from Equation (16).

Additionally we define $\gamma_{\rm pdf}$ to be the value obtained by
performing least squares regression on log-log plot of the probability density
function, and $\gamma_{\rm ccdf}$ to be the value obtained by performing least
squares regression on the log-log plot of the complementary cumulative
distribution. Lastly, $\gamma_{\langle k\rangle}$ is the estimate calculated
from the first moment of the distribution as described by Equation (11).

For this we generated synthetic power-law distributions of varying sizes, all
with a parameter $\gamma=2.5$. We generate these using the NumPy package’s
built-in random number generators. For each value of $N$, we generated 1,000
distributions and calculated each estimate. The average estimates as well as
their standard distributions for $N=1,000$ are shown below in Table 1.
Additional tables for graphs of size $N=100$ and $N=10,000$ can be found in
Appendix B. We see that in this case, with small $k_{\rm min}$, the numerical
maximisation $\gamma_{\rm mle}$ performs best when compared to other
estimates.

In Ref. [8], the authors say that the continuous estimate, $\gamma_{\rm c}$ is
less accurate than the discrete estimate and no easier to calculate and so it
should not be used. Our results here agree with this statement as we can see
the continuous estimate is inaccurate even at large values of $k_{\rm min}$.
Instead, they suggest using the discrete approximation, however, we observe
here that the numerically maximized discrete MLE performs better than the
approximation.

As we can see here the least squares fit to the CCDF, $\gamma_{\rm ccdf}$, is
highly consistent under variation of $k_{\rm min}$, however, Clauset et al.
[8] also point out flaws with this method, such as the underlying assumptions
being invalid. The fit to the PDF, $\gamma_{\rm pdf}$, is always less accurate
than that to the CCDF, on account of the PDF having a noisier tail [17]. In
addition, as mentioned in Sections I and III, there are drawbacks and
limitations to applying the method of least squares to cumulative
distributions.

The discrete estimate, $\gamma_{\rm d}$, that Clauset et al. [8] recommend
using is accurate at $k_{\rm min}=3$ and above, however, at this point already
over 90% of the points will be missed. In Ref. [8], it is stated that this
method works well only for $k_{\rm min}\gtrapprox 6$. With this we would run
into a more extreme version of this problem, and our tests show that it begins
to become less accurate at this point.

The method calculated using the first moment of the distribution,
$\gamma_{\langle k\rangle}$ performs poorly for all values of $k_{\rm min}$
and we recommend that it should not be used.

We can see from Table 1 that in the case of small $k_{\rm min}$, the numerical
maximisation of the log likelihood $\gamma_{d}$ performs best of all the
estimates compared here. This is not surprising, given that all other methods
are approximations, however, we believe the increased accuracy of maximum
likelihood estimators justifies the relative increase in difficulty of their
implementation. There are several other advantages that MLEs have over the
other estimates as well, as mentioned in Section III.

Furthermore, none of the other estimators here are applicable to any
distribution in the way that MLEs are, as the estimates $\gamma_{\rm c}$ and
$\gamma_{\rm d}$ are unique to power-laws, and least squares regression is
only applicable if the data can be easily linearized. The method of moments
can be applied to some other distributions (e.g. exponential), however, its
performance is still poor. Finally, all of these other estimates assume the
distribution a priori, whereas MLEs allow for easy comparison of multiple
distributions using information criteria. For these reasons, we argue that
maximum likelihood estimators should be the standard approach for fitting
distributions to network data.

Indeed, this is a clarification needed when discussing the work of Clauset et
al. [8]; the methodology they discuss is applied to empirical data, but not
necessarily network distributional data, which are often small and incomplete,
especially in the case of poor sampling. It should be noted as well that the
above paper is more concerned with determining if a power-law distribution is
an appropriate fit for data than it is with testing many distributions to find
the most appropriate fit. In the succeeding sections we will show all of the
common distributions that one should consider when fitting a distribution to
network data as well as equations for the log likelihood to be maximized, and
some of the pitfalls that should be avoided in plotting these distributions
against empirical data to ensure correct fitting.

Table 1: Values for each power-law exponent estimate discussed in section IV obtained on 1,000 datasets each of size $N=1,000$ with true parameter value $\gamma=2.5$. Values shown are means with standard deviations in brackets. $\hat{\gamma}_{c}$ is the continuous estimator for the exponent from eq. (14), $\gamma_{\rm pdf}$ and $\gamma_{\rm ccdf}$ are the values obtained by least squares regression of the pdf and ccdf respectively. $\gamma_{\rm d}$ is the value obtained by the discrete approximation eq. 16, $\gamma_{\langle k\rangle}$ is the value obtained by the method of moments and $\gamma_{\rm mle}$ is the value obtained by maximum likelihood estimation. Best estimates for each value of $k_{\rm min}$ are highlighted in bold. $k_{\rm min}$ |  $\gamma_{\rm c}$ |  $\gamma_{\rm pdf}$ |  $\gamma_{\rm ccdf}$ |  $\gamma_{\rm d}$ |  $\gamma_{\langle k\rangle}$ |  $\gamma_{\rm mle}$
---|---|---|---|---|---|---
1 |  4.47 (0.23) |  2.57 (0.28) |  2.53 (0.23) |  2.02 (0.02) |  3.15 (0.23) |  2.50 (0.05)
2 |  3.28 (0.21) |  2.34 (0.29) |  2.45 (0.26) |  2.38 (0.07) |  2.29 (0.06) |  2.50 (0.10)
3 |  3.00 (0.24) |  2.18 (0.30) |  2.43 (0.30) |  2.46 (0.13) |  2.17 (0.04) |  2.52 (0.14)
4 |  2.88 (0.29) |  2.04 (0.32) |  2.43 (0.34) |  2.50 (0.18) |  2.12 (0.03) |  2.53 (0.19)
5 |  2.81 (0.32) |  1.89 (0.30) |  2.41 (0.36) |  2.51 (0.22) |  2.09 (0.02) |  2.53 (0.23)
6 |  2.77 (0.35) |  1.74 (0.28) |  2.37 (0.38) |  2.53 (0.26) |  2.07 (0.02) |  2.54 (0.26)
7 |  2.75 (0.38) |  1.62 (0.25) |  2.37 (0.39) |  2.54 (0.29) |  2.06 (0.02) |  2.56 (0.29)
8 |  2.74 (0.42) |  1.52 (0.25) |  2.37 (0.43) |  2.55 (0.33) |  2.06 (0.02) |  2.56 (0.34)
9 |  2.73 (0.48) |  1.42 (0.27) |  2.35 (0.48) |  2.57 (0.38) |  2.05 (0.02) |  2.57 (0.37)
10 |  2.76 (0.54) |  1.37 (0.27) |  2.37 (0.50) |  2.60 (0.44) |  2.05 (0.01) |  2.60 (0.42)

##  V Other Distributions

Additionally we looked at the following distributions; (a) truncated power-law
distributions, (b) exponential distributions, (c) stretched exponential
distributions, (d) Weibull distributions, (e) Poisson distributions, (f)
normal (Gaussian) distributions and (g) lognormal distributions. Most of these
distributions are for continuous variables, but here we discretize and
normalize them in order to obtain their corresponding log likelihoods. We
choose these as they are common in formation processes and the complex network
literature, e.g. [2, 8, 18].

### Truncated Power-Law Distributions

The second class of network described by Amaral et al. [2] contains a power-
law regime followed by a sharp cut-off. Albert & Barabási [14] provide a list
of exponents and cut-offs for a range of complex networks. A truncated power-
law, or a power-law with exponential cut-off has the form

$p_{k}\sim k^{-\gamma}{\rm e}^{-k/\kappa}.$ (17)

A truncated power-law is shown for the collaboration network of the condensed
matter arXiv from 1995-1999 in Ref. [19]. The log likelihood then is

$\ln{\cal L}=N\ln(1-\Delta)+\frac{Nk_{\rm min}}{\kappa}-N\ln{Z(k_{\rm
min})}-\sum_{i=1}^{N}\left(\gamma\ln{k_{i}}+\frac{k_{i}}{\kappa}\right),$ (18)

where $Z(k_{\rm min})\equiv\sum_{m=0}^{\infty}(x+m)^{-\gamma}{\rm
e}^{-m/\kappa}$. We then maximize this numerically. Details of obtaining
Equation (18) from Equation (17) are shown in Appendix A.

### Exponential and Weibull Distributions

The final class of network described by Amaral et al. are so-called single-
scale networks characterized by fast-decaying tails. Although they are rarely
used, these classifications provide a useful ordering by complexity of the
different types of distributions.

We first look at the exponential distribution which is given by

$p_{k}\sim{\rm e}^{-k/\kappa}.$ (19)

Its log likelihood is

$\ln{\cal L}=N\ln(1-\Delta)+N\,\ln\left(1-{\rm
e}^{-1/\kappa}\right)-\frac{1}{\kappa}\,\sum_{i=1}^{N}(k_{i}-k_{\rm min}).$
(20)

The exponential distribution can be generalized to a stretched exponential
distribution which has been found to be a good fit for some empirical
datasets, such as the jazz band network in Ref. [20], however, the stretched
exponential & Weibull distributions are related with the stretched exponential
being the CCDF of the Weibull distribution. Hence we only include the Weibull
here.

The Weibull distribution is given by

$p_{k}\sim\left(\frac{k}{\kappa}\right)^{\beta-1}{\rm
e}^{(k/\kappa)^{\beta}}.$ (21)

As we can see when $\beta=1$, the Weibull simplifies to the exponential
distribution. When $\beta=2$, it is closely related to the normal distribution
(below). Its log likelihood is

$\ln{\cal L}=N\ln(1-\Delta)-N\ln\left(\sum_{m=k_{\rm
min}}^{\infty}\left(\frac{k}{\kappa}\right)^{\beta-1}{\rm
e}^{(-k/\kappa)^{\beta}}\right)\\\
+N\ln\left((k/\kappa)^{\beta-1}\right)+N\ln\left({\rm
e}^{(k/\kappa)^{\beta}}\right).$ (22)

Details of this calculation can once again be found in Appendix A.

### Normal & Lognormal Distributions

The normal distribution (or Gaussian) is given by

$p_{k}\sim{\rm e}^{-\frac{(k-\mu)^{2}}{2\sigma^{2}}},$ (23)

where $\mu$ is the mean and $\sigma^{2}$ is the variance. This distribution is
included here as it is found to fit some social networks [2], however, given
the skewed nature of network degree sequences it is unlikely to be chosen in
most cases. The log likelihood is given by

$\ln{\cal L}=N\ln(1-\Delta)-N\ln\left(\sum_{m=k_{\rm{min}}}^{\infty}{\rm
e}^{-\frac{(m-\mu)^{2}}{2\sigma^{2}}}\right)-\sum_{i=1}^{N}\frac{(k_{i}-\mu)^{2}}{2\sigma^{2}}.$
(24)

The lognormal distribution then is given by

$p_{k}\sim\frac{1}{k}{\rm e}^{-\frac{(\ln k-\mu)^{2}}{2\sigma^{2}}}.$ (25)

The log likelihood is given by

$\ln{\cal L}=N\ln(1-\Delta)-N\ln\left(\sum_{m=k_{\rm
min}}^{\infty}\frac{1}{m}{\rm
e}^{-\frac{(\ln(m)-\mu)^{2}}{2\sigma^{2}}}\right)\\\ -\sum_{k=k_{\rm
min}}^{N}\ln(k)-\sum_{k=k_{\rm min}}^{N}\frac{(\ln(k)-\mu)^{2}}{2\sigma^{2}}.$
(26)

### Poisson Distribution

The last distribution we test for these network datasets is the Poisson
distribution. It is given by

$p_{k}=\frac{\lambda^{k}}{k!}{\rm e}^{-\lambda}.$ (27)

The log likelihood then is

$\ln{\cal L}=N\ln(1-\Delta)-\ln\left(1-{\rm e}^{-\lambda}\sum_{m=0}^{k_{\rm
min}-1}\frac{\lambda^{m}}{m!}\right)\\\
-N\lambda+\ln{\lambda}\sum_{i=1}^{N}k_{i}-\sum_{i=1}^{N}\ln(k_{i}!).$ (28)

Again, details of obtaining this equation as well as those for the normal and
lognormal distributions can be found in Appendix A. As with the normal
distribution, a Poisson is an unlikely candidate for most network datasets
given their skewed nature, however, both are included here for completeness
given their ubiquity in other empirical datasets and scientific settings [21,
22].

##  VI Model selection, Choosing $k_{\rm min}$ , and Goodness of Fit

As discussed in Section IV, there are several advantages to using maximum
likelihood estimation. Most importantly is the ability to compare the
likelihoods of different distributions in order to choose the best
distribution for a given dataset. In order to compare different models we use
the Akaike information criterion with correction for finite sample sizes
(${\rm AIC_{c}}$) [23, 24] and the Bayesian information criterion (BIC) [25].
The ${\rm AIC_{c}}$ is given by

${\rm AIC_{c}}=-2\ln{\cal
L}(\theta|k_{i})+2n_{\theta}+\frac{2n_{\theta}(n_{\theta}+1)}{N-n_{\theta}-1},$
(29)

and the BIC is given by

${\rm BIC}=-2\ln{\cal L}(\theta|k_{i})+n_{\theta}\ln N.$ (30)

In each equation $n_{\theta}$ is the number of parameters in the model, and
$N$ is the sample size. This ${\rm AIC_{c}}$ gives greater penalty for number
of parameters, and the penalty is diminished with a larger sample size.
Anderson & Burnham [24] recommend always using the ${\rm AIC_{c}}$ instead of
the regular AIC (which is the same as Equation 29 but without the last term)
as in the case of large $N$ the correction tends to zero.

We also make use of AIC weights. For a given set of $m$ models for a given
dataset, the AIC weights are given by

$W_{i}=\frac{{\rm e}^{-\Delta_{i}/2}}{\sum_{1}^{m}{{\rm e}^{-\Delta_{i}/2}}},$
(31)

where $\Delta_{i}={\rm AIC_{c}}_{i}-{\rm min}({\rm AIC_{c}})$. These values
represent the relative likelihood of the models and allow us to determine if
there is support for more than one model. The values of the weights will sum
to 1, and the closer a value is to one the more support for that model there
is. Usually the weights are accompanied by some cut-off, below which we say a
model is not supported.

Since the ${\rm AIC}_{c}$ and the BIC both depend on $N$, we can only compare
two distributions that start at the same value of $k_{\rm min}$. For this
reason, the model and $k_{\rm min}$ must be chosen in tandem. It is important
to remember that to capture the true distribution of a dataset, it should be a
priority that $k_{\rm min}$ be minimized. How exactly we achieve this is
discussed in Sections VII and VIII.

Goodness-of-fit tests for this type of analysis leave much to be desired. Two
common means of assessing goodness-of-fit are (i) Kolmogorov-Smirnov tests,
and (ii) Q-Q plots, both of which have their drawbacks. Descriptions of how
these tests work can be found in Refs. [26] and [27] respectively.

First, with network datasets, we are often dealing with sample sizes of the
order of 10,000 nodes or more. These sample sizes are in contrast to the work
done by Goldstein et al. [7], who find success using the KS test on sample
sizes of the order of 1,000 nodes. The critical value for a KS test at a 5%
level of significance in the limit of large $n$ is given by $1.36/\sqrt{n}$,
where $n$ is the sample size or in our case the number of nodes. Our tests
find that the KS test is simply too restrictive, and will tell the user that
even the best of our fits are poor.

Quantile-quantile or Q-Q plots (shown in Figure 4) are useful in many cases
but since they require visual interpretation, they are not suitable in a
situation where automation is desired. Furthermore they are sensitive to
outliers or extreme values, which are common across all of our datasets.

##  VII Fitting

Here we outline the methodology used to choose distributions for datasets
based on the methods discussed already. The datasets to which this methodology
was applied can be found in Table 4. For a given degree sequence, the
methodology works as follows:

(i) Beginning with $k_{\rm min}=1,$ we find the parameter values that maximize
the log likelihood functions of each of the distributions discussed above.

(ii) The ${\rm AIC}_{c}$ and AIC weights for each distribution are calculated.
The user may choose to use the ${\rm AIC}_{c}$ or the BIC to choose the best
distribution or both.

(iii) We increase $k_{\rm min}$ by one and repeat steps (i) and (ii). Once the
same distribution is chosen for three consecutive $k_{\rm min}$ values we
choose this distribution for the dataset. In the case of small datasets (here
chosen to be fewer than 2,500 nodes), the same distribution need only be
chosen for two consecutive $k_{\rm min}$ values. The value 2,500 was chosen
based on our datasets; below this value, requiring the same distribution to be
chosen three times simply resulted in cutting off too much of the data below
$k_{\rm min}$.

(iv) We use the determined distribution and parameters to fit a curve to the
CCDF of the degree sequence for visual purposes. At this point, both the CCDF
and the PDF should be inspected, as we find that looking at just the CCDF is
insufficient to determine if we have obtained a good fit or not. Other
goodness-of-fit metrics such as a Q-Q plots can be used. If one determines
that the fit obtained is poor, then $k_{\rm min}$ should be increased and the
algorithm repeated. We find that we can best determine the degree distribution
when using all available information. We will explore this further in the
results section.

(v) We then bootstrap the dataset 1,000 times and fit the same distribution to
our bootstrapped samples in order to obtain means, standard deviations, and
other desired summary statistics for the parameters of our fitted
distributions. These summary statistics are shown in Table 5.

When fitting we must account for data below $k_{\rm min}$. This is done using
our empirical CCDF. If, for example, we have $k_{\rm min}=3$, then we multiply
the values in our fitted CCDF by $\sum_{k=0}^{3}p(k)\equiv P(3)$. This ensures
that the fitted curve begins at the correct point.

There are some limitations for what can be done given a network dataset. Many
networks are poorly sampled or not a complete sample. Consider the Enron email
dataset [28], here emails between employees were recorded but not emails to
external addresses, i.e., contacts outside of the organisation would not add
to an individual’s degree. Therefore, we do not have the actual degrees of
nodes, and so conclusions from the dataset about the degree distribution
cannot be extended to the network as a whole. In this case we may just want to
fit to the tail and not the full distribution so a high value of
$k_{\rm{min}}$ may be appropriate.

In contrast to this is the power-grid network studied in Ref. [29]. Here, the
degree is the number of physical connections to a generator, a transformer, or
a substation and so the degree of a node is correct to the underlying network.
In this case, a high $k_{\rm{min}}$ may result in a different distribution
being chosen for the tail and not be representative of the full network.

Keeping these limitations in mind, this methodology can be applied to any
distribution of discrete integers. In the following section we will see how it
performs on a wide variety of network types.

##  VIII Results

Figure 2: Results for a selection of the networks whose degree distributions
we fitted. As we can see in most cases, we manage to obtain excellent fits
with low $k_{\rm min}$ values in all cases. Notable exceptions are Gene Fusion
and Google+, which are discussed in turn in Section VIII.

We now look at some of the results obtained by using the above described
methodology on a collection of network datasets, some of our own, one sexual
contact network taken from Ref. [4], and many taken from the Konect database.
Konect stands for the Koblenz Network Collection [30]; an open-access online
database of network datasets from various areas of science. A full list of the
datasets we applied the methodology to as well as a description of each
dataset can be seen in Table 4 in Appendix B. A summary of some basic
properties of these networks can be found in Table 5 in Appendix B.

For most networks that we looked at, we obtain good estimates for the
parameters of the chosen distributions, as can be seen from the closely
fitting curves to the datapoints. Note as well that in the majority of these
cases we begin at $k_{\rm min}$ values of one and two, in line with our
priority of minimizing $k_{\rm min}$.

The results shown in Figure 2 are representative of the results as a whole
(results for all other datasets can be seen in Figures 7 and 8). In fact,
based on its CCDF the Google+ (Figure 2 (h)) dataset appears to be the worst
fit of any dataset displayed. One possible reason for this relatively poor fit
is the very noisy tail of the distribution, which can be seen in the PDF of
this distribution in Figure 6. This noisy tail is caused by many hubs of
different degrees, i.e., there are many points with different degrees but
equal probabilities, hence the long horizontal line of points in Figure 6 (b).
This is in contrast to the more ‘well-behaved’ PDF of the astrophysics dataset
in Figure 6 (a). Even in this case, looking at the PDF, we can see that there
is not that much room for improvement in the fit.

According to the CCDF in Figure 5 (b) for the Linux dataset we appear to
obtain a bad fit here too. However, looking at the PDF (Figure 5 (a)) we see
we actually have quite a good fit. In this case, the sharp drop off in CCDF
values may have been caused by finite size effects, cumulative errors in
individual probability values, or something else. The lesson here is that we
cannot judge fit based solely on the CCDF.

A counter example to this is the Twitter dataset whose CCDF and PDF can be
seen in Figures 7 (v) and 8 (v) respectively. Here, we see a poor fit to both
the PDF and CCDF, highlighting the need to look at both before determining if
a distribution is a good fit or not.

In Figure 2 (g) we have the Gene Fusion dataset. Overall this fits the data
well however the dataset only contains approximately 250 nodes, hence we have
large distances between the predicted and observed probabilities. As mentioned
in step (iii) of the algorithm, in the case of such small datasets, the
methodology is altered slightly so that only two votes for the same
distribution are required for the distribution to be chosen, as we found that
a larger value results in too large a portion of the data being excluded.

We can see that in cases such as the Facebook dataset in Figure 2 (c), we
obtain a good fit for the entire distribution. In the work of Clauset et. al
[8], it would be reasonable to choose a $k_{\rm min}$ value even as high as
$k_{\rm min}\approx 110$. In doing so all of the data below this point would
be ignored, which equates to over 99% of the values, and with our methodology
we have fit to the entire dataset. Other methodologies would similarly ignore
the bulk of the data and fit a power-law to the tail, using one of the
estimators shown in Table 1 based on it appearing as a straight line when
plotted on a log-log scale.

Some fits may be poor while prioritizing a low value of $k_{\rm min}$, but in
this situation we would increase $k_{\rm min}$ to see if we can obtain a
better fit. Examples of this can be seen in the Internet (CAIDA), Internet AS
2, and Internet Topology datasets, for which we get a very poor fit for low
values of $k_{\rm min}$ but see improvement when we increase $k_{\rm min}$.
This is in contrast to the Twitter dataset, for which we find that even larger
values of $k_{\rm min}$ struggle to obtain a good fit. In this case, perhaps
some less common distribution which we have not covered here would provide a
better fit.

In the case of the RIP Ireland dataset, we see that the chosen distribution is
a Weibull with parameters $\kappa=183.14$, $\beta=0.99$. Since $\beta$ is so
close to one this is essentially an exponential distribution. However, since
an exponential distribution is a special case of a Weibull distribution, and
one can always achieve a higher likelihood by adding more parameters [8], the
likelihood of an exponential will always be less than that of a Weibull. In
this case, we rely on the information criteria to sufficiently penalize the
distribution with more parameters. If using the Bayesian information criteria
with $k_{\rm min}=1$, we obtain an exponential fit for this distribution,
though not for $k_{\rm min}=2$ or greater. With the advantage of a lower
$k_{\rm min}$ and a simpler distribution, an exponential distribution is
likely the better choice here. Results for this daataset shown in Table 5 are
for a Weibull distribution to illustrate our point.

In all other cases, we find that choosing BIC instead of AIC has no effect on
what distribution is chosen.

Figure 3: Weibull distribution and a lognormal distribution fit to the Petster
dataset at different $k_{\rm min}$ values as described in Section VIII.

Lastly, we focus on the Petstser dataset, which is a more ambiguous example.
Initially we fit using the steps outlined in the previous section, which tells
us that the data follow a Weibull distribution for $k\geq 3$. This fit is
shown in Figure 3.

Suppose we feel that based on the CCDF we could improve the fit to the tail of
the distribution. We increase $k_{\rm min}$ to four and repeat the algorithm,
which gives the lognormal again shown in Figure 3.

This distribution arguably fits better in the tail of the distribution, so how
do we choose between the two options? Looking at the PDF for both
distributions we see there is very little appreciable difference, aside from
the different $k_{\rm min}$ values. We then look at the Q-Q plots for each
distribution, shown in Figure 4. As we can see here the Weibull appears to be
a better fit for the distribution, as the data follows the diagonal more
closely (both begin to deviate at the tail which is to be expected when
dealing with extreme values).

When the choice between two distributions is so close, we must look at the AIC
weights. At $k_{\rm min}=3$, the weights for the Weibull and lognormal
distributions were 0.99 and 0.01 respectively. At $k_{\rm min}=5$, these
values were 0.3 and 0.7. Because of this, at $k_{\rm min}=3$ we can rule out a
lognormal distribution. However, at $k_{\rm min}=5$, there is still some
support for a Weibull distribution.

Combining all of this information, along with our priority of minimizing
$k_{\rm min}$ we conclude that the Weibull distribution is the better fit for
the data. In the case of more ambiguous fits, or wanting to improve the fit to
a distribution we recommend this approach of looking at all available
information.

All in all, we can see that the methodology described in this paper performs
well in a variety of scenarios, and only does poorly in a few cases. This may
be improved upon by testing other distributions, as here we have only tested a
handful of commonly found distributions.

Figure 4: Q-Q plots of a Weibull distribution (left) and a lognormal
distribution (right) fit to the Petster dataset as described in Section VIII.

Figure 5: PDF and CCDF of fits to the Linux dataset. As we can see, both the
PDF and CCDF should be accounted for when assessing the fit.

Figure 6: Probability density functions for the Astrophysics dataset (left)
and Google+ dataset (right). As we can see the Google+ data is far noisier in
the tail, making the distribution more difficult to fit to.

##  IX Discussion

For the majority of the time that the field of complex networks has been
studied, questions around the degree distributions of networks have persisted
to be left without satisfying answers. Here we have built upon the work of
Clauset et al. [8] to provide a methodology that introduces more rigour to the
process of determining the degree distribution of a network dataset. We have
three key differences to their method.

Firstly, we suggest taking a low value of $k_{\rm{min}}$ to consider as many
of the nodes as possible. Depending on the network’s distribution, even a
value of 3 or larger could end up fitting to less than 10% of the network.
This is only desirable when a network is poorly sampled and we are just
interested in the tail. If we suspect the network is well sampled, then a high
value of $k_{\rm{min}}$ will miss the majority of the network. These often-
ignored low degree nodes are important in many contexts [31], playing crucial
roles in processes such as percolation [9], as well community detection in
social networks [10].

Secondly, we show that the parameter estimate obtained through numerical
maximisation of Equation 15 is superior to the estimate given by Equation 16,
especially for low values of $k_{\rm{min}}$. Taking the approximation for
smaller networks with low values of $k_{\rm{min}}$ will give poor results and
possibly rule out a power-law even if that is the true distribution.

Thirdly, we use information criteria to choose the model rather than
constructing a $p$-value from the Kolmogorov-Smirnov tests. These methods do
not tell us about the goodness of fit but allow us to choose the most
appropriate of the candidate models for this dataset.

As we can see from the results in Section VIII, using maximum likelihood
estimation to determine the most appropriate fit from a set of candidate
models performs well on a variety of network datasets with complex
distributions. This work improves the standard of distribution fitting, with
most if not all of the data being fit to in all cases, through minimisation of
$k_{\rm min}$. This process is not entirely automated and we believe this
should be the case. In some cases Q-Q plots may be necessary to interpret the
results and one may need to check both the CCDF and PDF. These are noisy
empirical datasets so caution must be taken and an automated process could
easily miss these subtleties.

After checking many different distributions, one may wonder why we are so
interested in the specific distribution a complex network has. Networks have
different underlying formation processes. For example, if we know the degree
distribution follows a Poisson or binomial distribution, then we know this
network if formed by purely a random process. If we know nodes prefer to
connect to high degree nodes, we know it’s a preferential attachment process.
Hence, if we know the underlying distribution, we can come up with a theory
that will give rise to that distribution.

This is one of the reasons why the power-law is so popular, not only is it
instrumental in many statistical physics theories, and required for the
epidemic threshold in disease transmission models, but it is the distribution
underlying the preferential attachment model. It is also a single parameter
distribution making it quite desirable for fitting with low statistical
complexity. In our results, we find support for power-laws in many internet-
based networks. However, this does not seem like a good mechanism for many of
the social networks we analyse.

Power-laws suggest some nodes will have an extremely high degree, often
approaching the system size, something not realistic for social systems. In
the social networks here for example, they are better fitted by Weibull or
log-normal distributions. In fact the RIP Ireland data is well fitted by a
Weibull with $\beta\approx 1$ – i.e. an exponential. With the exception of two
outliers (people known in the media) no one has a lifetime degree even close
to 2,000 (for a system size $>4$ million). Therefore, preferential attachment
seems like a poor mechanism for social networks in particular with their fast
decaying tails.

Many other processes for social networks have been suggested even in the early
years of complex networks, for example Ebel et al. [18] propose a mechanism
which will give rise to a stretched exponential. This is closer to the results
that we observe. We aim to test this further going forward to identify an
appropriate mechanism for social networks.

The foundation presented here performs well and can be extended to improve its
performance further. In the future, we aim to extend the analysis both to more
datasets and to test more parametric distributions. Another avenue for the
extension of this work that we aim to explore is allowing for fitting of more
than one distribution function to distributions in which we feel the tail
behaves differently to the body of the distribution, i.e., splitting the
distribution at some value $k^{*}$ and fitting two different distributions to
the data above and below this value.

We believe that this widely applicable and user-friendly approach provides
much needed rigour in answering a fundamental question about the properties of
a network.

## Acknowledgements

This publication has emanated from research conducted with the financial
support of Science Foundation Ireland under Grant number 18/CRT/6049. The
authors would like to thank David O’Sullivan, Samuel Unicomb and James Gleeson
for their suggestions and comments on the manuscript.

## References

  * Barabási and Albert [1999] A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  * Amaral et al. [2000] L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, Proceedings of the National Academy of Sciences 97, 11149 (2000).
  * Broido and Clauset [2019] A. D. Broido and A. Clauset, Nature Communications 10, 1 (2019).
  * Ito et al. [2019] H. Ito, K. Tamura, T. Wada, T. Yamamoto, and S. Morita, PloS One 14, e0221520 (2019).
  * Voitalov et al. [2019] I. Voitalov, P. van der Hoorn, R. van der Hofstad, and D. Krioukov, Physical Review Research 1, 033034 (2019).
  * Holme [2019] P. Holme, Nature Communications 10, 1 (2019).
  * Goldstein et al. [2004] M. L. Goldstein, S. A. Morris, and G. G. Yen, The European Physical Journal B-Condensed Matter and Complex Systems 41, 255 (2004).
  * Clauset et al. [2009] A. Clauset, C. R. Shalizi, and M. E. Newman, SIAM Review 51, 661 (2009).
  * Newman et al. [2001] M. E. Newman, S. H. Strogatz, and D. J. Watts, Physical review E 64, 026118 (2001).
  * Mehrabi et al. [2019] N. Mehrabi, F. Morstatter, N. Peng, and A. Galstyan, in 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (IEEE, 2019) pp. 509–512.
  * Newman [2003] M. E. Newman, SIAM Review 45, 167 (2003).
  * Jeong et al. [2001] H. Jeong, S. P. Mason, A.-L. Barabási, and Z. N. Oltvai, Nature 411, 41 (2001).
  * Strogatz [2001] S. H. Strogatz, Nature 410, 268 (2001).
  * Albert and Barabási [2002] R. Albert and A.-L. Barabási, Reviews of Modern Physics 74, 47 (2002).
  * Edwards et al. [2007] A. M. Edwards, R. A. Phillips, N. W. Watkins, M. P. Freeman, E. J. Murphy, V. Afanasyev, S. V. Buldyrev, M. G. da Luz, E. P. Raposo, H. E. Stanley, et al., Nature 449, 1044 (2007).
  * Gerlach and Altmann [2019] M. Gerlach and E. G. Altmann, Physical Review Letters 122, 168301 (2019).
  * Newman [2005] M. E. Newman, Contemporary Physics 46, 323 (2005).
  * Ebel et al. [2002] H. Ebel, J. Davidsen, and S. Bornholdt, Complexity 8, 24 (2002).
  * Newman [2001] M. E. Newman, Proceedings of the National Academy of Sciences 98, 404 (2001).
  * Gleiser and Danon [2003] P. M. Gleiser and L. Danon, Advances in Complex Systems 6, 565 (2003).
  * Lyon [2014] A. Lyon, The British Journal for the Philosophy of Science (2014).
  * Johnson et al. [2005] N. L. Johnson, S. Kotz, and A. W. Kemp, Univariate discrete distributions (John Wiley & Sons, 2005).
  * Akaike [1974] H. Akaike, IEEE Transactions on Automatic Control 19, 716 (1974).
  * Anderson and Burnham [2004] D. Anderson and K. Burnham, Second. NY: Springer-Verlag 63, 10 (2004).
  * Schwarz [1978] G. Schwarz, The Annals of Statistics , 461 (1978).
  * Massey Jr [1951] F. J. Massey Jr, Journal of the American Statistical Association 46, 68 (1951).
  * Kratz and Resnick [1996] M. Kratz and S. I. Resnick, Stochastic Models 12, 699 (1996).
  * Klimt and Yang [2004] B. Klimt and Y. Yang, in European conference on machine learning (Springer, 2004) pp. 217–226.
  * Watts and Strogatz [1998] D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998).
  * Kunegis [2013a] J. Kunegis, in Proceedings of the 22nd international conference on world wide web (2013) pp. 1343–1350, http://konect.cc/.
  * Tanaka et al. [2012] G. Tanaka, K. Morino, and K. Aihara, Scientific reports 2, 1 (2012).
  * Höglund et al. [2006] M. Höglund, A. Frigyesi, and F. Mitelman, Oncogene 25, 2674 (2006).
  * Mac Carron and Kenna [2013] P. Mac Carron and R. Kenna, The European Physical Journal B 86, 1 (2013).
  * Isella et al. [2011] L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J.-F. Pinton, and W. Van den Broeck, Journal of Theoretical Biology 271, 166 (2011).
  * Newman [2006] M. E. Newman, Physical Review E 74, 036104 (2006).
  * Gessey-Jones et al. [2020] T. Gessey-Jones, C. Connaughton, R. Dunbar, R. Kenna, P. MacCarron, C. O’Conchobhair, and J. Yose, Proceedings of the National Academy of Sciences 117, 28582 (2020).
  * Kunegis [2013b] J. Kunegis, Konect (2013b), http://konect.cc/networks/petster-hamster/.
  * Moody [2001] J. Moody, Social Networks 23, 261 (2001).
  * Rual et al. [2005] J.-F. Rual, K. Venkatesan, T. Hao, T. Hirozane-Kishikawa, A. Dricot, N. Li, G. F. Berriz, F. D. Gibbons, M. Dreze, N. Ayivi-Guedehoussou, et al., Nature 437, 1173 (2005).
  * Šubelj and Bajec [2012] L. Šubelj and M. Bajec, in Proceedings of the First International Workshop on Software Mining (2012) pp. 9–16.
  * Joshi-Tope et al. [2005] G. Joshi-Tope, M. Gillespie, I. Vastrik, P. D’Eustachio, E. Schmidt, B. de Bono, B. Jassal, G. Gopinath, G. Wu, L. Matthews, et al., Nucleic Acids Research 33, D428 (2005).
  * Kunegis [2013c] J. Kunegis, Konect (2013c), http://konect.cc/networks/dimacs10-as-22july06/.
  * Boguná et al. [2004] M. Boguná, R. Pastor-Satorras, A. Díaz-Guilera, and A. Arenas, Physical Review E 70, 056122 (2004).
  * Dempsey et al. [2020] R. Dempsey, A. Parnell, P. McCarron, and G. McCarthy, Irish Geography , 163 (2020).
  * Leskovec et al. [2007] J. Leskovec, J. Kleinberg, and C. Faloutsos, ACM transactions on Knowledge Discovery from Data (TKDD) 1, 2 (2007).
  * Leskovec and Mcauley [2012] J. Leskovec and J. Mcauley, Advances in Neural Information Processing Systems 25 (2012).
  * De Choudhury et al. [2009] M. De Choudhury, H. Sundaram, A. John, and D. D. Seligmann, in 2009 International conference on computational science and engineering, Vol. 4 (IEEE, 2009) pp. 151–158.
  * Kunegis [2013d] J. Kunegis, Konect (2013d), http://konect.cc/networks/linux/.
  * Zhang et al. [2005] B. Zhang, R. Liu, D. Massey, and L. Zhang, ACM SIGCOMM Computer Communication Review 35, 53 (2005).
  * Viswanath et al. [2009] B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, in Proceedings of the 2nd ACM workshop on Online social networks (2009) pp. 37–42.
  * Gómez et al. [2008] V. Gómez, A. Kaltenbrunner, and V. López, in Proceedings of the 17th international conference on World Wide Web (2008) pp. 645–654.

##  Appendix A Code & Other Distributions

### Code

A documented package with which the results in this paper were produced is
available at https://github.com/Shaneul/MLE.

### Truncated Power-Law Distribution

Normalizing the truncated power-law from Equation (17) yields

$p_{k}=(1-\Delta)\frac{{\rm e}^{k_{\rm min}/\kappa}}{Z(k_{\rm
min})}k^{-\gamma}{\rm e}^{-k/\kappa},$ (32)

where $Z(x)=\Sigma_{m=0}^{\infty}(x+m)^{-\gamma}{\rm e}^{-m/\kappa}.$ The log
likelihood then is straightforward to obtain from this and shown in Equation
(18).

### Exponential Distribution

Starting with Equation (19), we expand like so

$1-\Delta=C\,\sum_{k=k_{\rm min}}^{k_{\rm max}}{\rm
e}^{-{{k}/{\kappa}}}=C\left({\rm e}^{{-k_{\rm min}}/{\kappa}}+{\rm
e}^{{-k_{\rm min}+1}/{\kappa}}+...\right).$

To normalize the distribution we multiply the summation here above and below
by $1-{\rm e}^{-1/\kappa}$ like so

$C\,\frac{1}{1-{\rm e}^{-1/\kappa}}\,\left(1-{\rm
e}^{-1/\kappa}\right)\,\left({\rm e}^{{-k_{\rm min}}/{\kappa}}+{\rm
e}^{{-k_{\rm min}+1}/{\kappa}}+...\right)$ $=\frac{C}{1-{\rm
e}^{-1/\kappa}}\bigl{(}{\rm e}^{{-k_{\rm min}}/{\kappa}}+{\rm e}^{{-k_{\rm
min}+1}/{\kappa}}+\\\ ...-{\rm e}^{{-\left(k_{\rm
min}+1\right)}/{\kappa}}-{\rm e}^{-\left(k_{\rm
max}+1\right)/\kappa}\bigl{)}.$

All but the first and last terms here cancel, leaving us with

$\frac{C}{1-{\rm e}^{-1/\kappa}}\left({\rm e}^{-k_{\rm min}/\kappa}-{\rm
e}^{-\left(k_{\rm max}+1\right)/\kappa}\right),$

and so

$C=(1-\Delta)\,\frac{1-{\rm e}^{-1/\kappa}}{{\rm e}^{{-k_{\rm
min}}/\kappa}-{\rm e}^{-\left(k_{\rm max}+1\right)/\kappa}}.$

If $k_{\rm max}\rightarrow\infty$ then we get

$C=(1-\Delta)\frac{1-{\rm e}^{-1/\kappa}}{{\rm e}^{-k_{\rm min}/\kappa}},$

and this leads to the normalized exponential distribution

$p(k)=(1-\Delta)\left(\frac{1-{\rm e}^{-1/\kappa}}{{\rm e}^{-k_{\rm
min}/\kappa}}\right){\rm e}^{-k/\kappa},$ (33)

from which the log likelihood Equation (20) is obtained.

### Weibull Distribution

Starting with Equation (21), we first define the constant to normalize the
distribution.

$(1-\Delta)=C\sum_{i=k_{\rm
min}}^{\infty}(k/\kappa)^{\beta-1}e^{-(k/\kappa)^{\beta}}.$

This gives

$C=\frac{(1-\Delta)}{\sum_{i=k_{\rm
min}}^{\infty}(k/\kappa)^{\beta-1}e^{-(k/\kappa)^{\beta}}},$

and with $C$ defined as above, we have

$p(k)=C(k/\kappa)^{\beta-1}{\rm e}^{-(\lambda k)^{\beta}}.$

The likelihood then is given by

${\cal{L}}=\prod^{N}\frac{(1-\Delta)}{\sum_{m=k_{\rm
min}}^{\infty}(m/\kappa)^{\beta-1}{\rm
e}^{-(m/\kappa)^{\beta}}}(k/\kappa)^{\beta-1}{\rm e}^{-(k/\kappa)^{\beta}},$

from which the log likelihood Equation (22) is obtained

### Poisson Distribution

Starting with Equation (27), we normalize like so

$1-\Delta=C\sum_{k=k_{\rm min}}^{\infty}\frac{\lambda^{k}}{k!}{\rm
e}^{-\lambda}.$

Adding and subtracting the same term from the above equation leads to

$\begin{split}1-\Delta&=C\left[\sum_{k=k_{\rm
min}}^{\infty}\frac{\lambda^{k}}{k!}{\rm e}^{-\lambda}+\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}{\rm e}^{-\lambda}-\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}{\rm e}^{-\lambda}\right]\\\ &=C{\rm
e}^{-\lambda}\left(\sum_{k=0}^{\infty}\frac{\lambda^{k}}{k!}-\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}\right)\\\ &=C{\rm e}^{-\lambda}\left({\rm
e}^{\lambda}-\sum_{k=0}^{k_{\rm min}-1}\frac{\lambda^{k}}{k!}\right)\\\
&=C\left(1-{\rm e}^{-\lambda}\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}\right).\\\ \end{split}$

This gives

$C=(1-\Delta)\left(1-{\rm e}^{-\lambda}\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}\right)^{-1}.$

Equation 27 then becomes

$p(k)=(1-\Delta)\left(1-{\rm e}^{-\lambda}\sum_{k=0}^{k_{\rm
min}-1}\frac{\lambda^{k}}{k!}{\rm
e}^{-\lambda}\right)^{-1}\frac{\lambda^{k}}{k!}{\rm e}^{-\lambda},$

and our log likelihood is as shown in Equation (28).

### Lognormal Distribution

Starting with Equation (25) we normalize in the usual way

$1-\Delta=C\sum_{k=k_{\rm min}}^{\infty}\frac{1}{k_{i}}{\rm
e}^{-\frac{(\ln{k_{i}}-\mu)^{2}}{2\sigma^{2}}}.$

This gives

$C=(1-\Delta)\left(\sum_{k=k_{\rm min}}^{\infty}\frac{1}{k}{\rm
e}^{-\frac{(\ln{k}-\mu)^{2}}{2\sigma^{2}}}\right)^{-1}.$

Equation (25) then becomes

$p(k)=(1-\Delta)\left(\sum_{k=k_{\rm min}}^{\infty}\frac{1}{k}{\rm
e}^{-\frac{(\ln{k}-\mu)^{2}}{2\sigma^{2}}}\right)^{-1}\frac{1}{k}{\rm
e}^{-\frac{(\ln{k}-\mu)^{2}}{2\sigma^{2}}},$

and the log likelihood Equation (26) is obtained from this.

##  Appendix B Additional Tables & Figures

Below are a collection of supporting tables and figures referenced throughout
the paper.

Table 2:  Values for each power-law exponent estimate discussed in section IV obtained on 1,000 datasets each of size $N=100$ with true parameter value $\gamma=2.5$. Values shown are means with standard deviations in brackets. $\hat{\gamma}_{c}$ is the continuous estimator for the exponent from eq. (14), $\gamma_{\rm pdf}$ and $\gamma_{\rm ccdf}$ are the values obtained by least squares regression of the pdf and ccdf respectively. $\gamma_{\rm d}$ is the value obtained by the discrete approximation eq. 16, $\gamma_{\langle k\rangle}$ is the value obtained by the method of moments and $\gamma_{\rm mle}$ is the value obtained by maximum likelihood estimation. Best estimates for each value of $k_{\rm min}$ are highlighted in bold. $k_{\rm min}$ |  $\gamma_{\rm c}$ |  $\gamma_{\rm pdf}$ |  $\gamma_{\rm ccdf}$ |  $\gamma_{\rm d}$ |  $\gamma_{\langle k\rangle}$ |  $\gamma_{\rm mle}$
---|---|---|---|---|---|---
1 |  4.49 (0.19) |  2.76 (0.23) |  2.72 (0.21) |  2.02 (0.02) |  3.31 (0.13) |  2.51 (0.04)
2 |  3.23 (0.21) |  2.24 (0.28) |  2.37 (0.24) |  2.35 (0.08) |  2.27 (0.06) |  2.48 (0.10)
3 |  2.98 (0.20) |  2.20 (0.24) |  2.46 (0.22) |  2.45 (0.11) |  2.17 (0.02) |  2.51 (0.12)
4 |  2.90 (0.27) |  2.09 (0.37) |  2.48 (0.36) |  2.51 (0.17) |  2.12 (0.02) |  2.55 (0.18)
5 |  2.58 (0.20) |  1.71 (0.17) |  2.20 (0.21) |  2.36 (0.14) |  2.08 (0.02) |  2.37 (0.15)
6 |  2.77 (0.25) |  1.75 (0.26) |  2.40 (0.33) |  2.53 (0.19) |  2.08 (0.02) |  2.54 (0.19)
7 |  2.75 (0.43) |  1.59 (0.29) |  2.29 (0.44) |  2.54 (0.34) |  2.06 (0.02) |  2.55 (0.34)
8 |  2.63 (0.43) |  1.45 (0.22) |  2.27 (0.32) |  2.46 (0.35) |  2.05 (0.02) |  2.47 (0.36)
9 |  2.91 (0.58) |  1.44 (0.24) |  2.47 (0.34) |  2.71 (0.46) |  2.06 (0.01) |  2.72 (0.47)
10 |  2.59 (0.49) |  1.27 (0.18) |  2.33 (0.61) |  2.46 (0.41) |  2.04 (0.02) |  2.46 (0.42)
Table 3:  Values for each power-law exponent estimate discussed in section IV obtained on 1,000 datasets each of size $N=10,000$ with true parameter value $\gamma=2.5$. Values shown are means with standard deviations in brackets. $\hat{\gamma}_{c}$ is the continuous estimator for the exponent from eq. (14), $\gamma_{\rm pdf}$ and $\gamma_{\rm ccdf}$ are the values obtained by least squares regression of the pdf and ccdf respectively. $\gamma_{\rm d}$ is the value obtained by the discrete approximation eq. 16, $\gamma_{\langle k\rangle}$ is the value obtained by the method of moments and $\gamma_{\rm mle}$ is the value obtained by maximum likelihood estimation. Best estimates for each value of $k_{\rm min}$ are highlighted in bold. $k_{\rm min}$ |  $\gamma_{\rm c}$ |  $\gamma_{\rm pdf}$ |  $\gamma_{\rm ccdf}$ |  $\gamma_{\rm d}$ |  $\gamma_{\langle k\rangle}$ |  $\gamma_{\rm mle}$
---|---|---|---|---|---|---
1 |  4.46 (0.07) |  2.60 (0.19) |  2.51 (0.14) |  2.02 (0.01) |  3.08 (0.13) |  2.50 (0.02)
2 |  3.27 (0.06) |  2.48 (0.20) |  2.48 (0.16) |  2.37 (0.02) |  2.27 (0.03) |  2.50 (0.03)
3 |  2.96 (0.07) |  2.39 (0.19) |  2.47 (0.16) |  2.45 (0.04) |  2.16 (0.02) |  2.50 (0.04)
4 |  2.83 (0.08) |  2.31 (0.20) |  2.46 (0.17) |  2.47 (0.05) |  2.11 (0.01) |  2.50 (0.05)
5 |  2.76 (0.09) |  2.22 (0.20) |  2.44 (0.18) |  2.49 (0.07) |  2.08 (0.01) |  2.50 (0.07)
6 |  2.72 (0.10) |  2.17 (0.20) |  2.45 (0.19) |  2.49 (0.07) |  2.07 (0.01) |  2.50 (0.08)
7 |  2.68 (0.11) |  2.09 (0.20) |  2.43 (0.20) |  2.50 (0.09) |  2.06 (0.01) |  2.50 (0.09)
8 |  2.66 (0.12) |  2.02 (0.19) |  2.43 (0.20) |  2.50 (0.10) |  2.05 (0.01) |  2.51 (0.10)
9 |  2.65 (0.13) |  1.95 (0.19) |  2.42 (0.22) |  2.50 (0.11) |  2.04 (0.01) |  2.51 (0.11)
10 |  2.63 (0.14) |  1.91 (0.19) |  2.43 (0.22) |  2.51 (0.12) |  2.04 (0.01) |  2.51 (0.12)
Table 4:  List of network datasets and a brief explanation of their sources. All datasets can be found on the Konect website [30] Network | Description | Source
---|---|---
Gene Fusion |  | Nodes represent genes, edges represent that two have fused in the
---
emergence of cancer.
[32]
Laxdaela |  | Character interaction network from Laxdaella
---
\- one of the Icelandic sagas.
[33]
Infectious Disease | Nodes represent people, edges represent face-to-face contact. | [34]
Network Science | Collaboration network of network scientists. | [35]
ASoIaF | Charcter interaction network from the fantasy series A Song of Ice and Fire. | [36]
Yeast | Nodes represent proteins, edges represent interactions. | [12]
Petster | Friendship network between users of the Petster website. | [37]
Moreno Health | Friendship network at Moreno high school. | [38]
Human Proteins | Nodes represent proteins, edges represent interactions. | [39]
US powergrid |  | Nodes represent substations, transformators, or generators,
---
edges represent connections between them.
[29]
Sexual Contact | Sexual contact network in Japan. | [4]
Java Classes |  | Nodes represent Java classes, edges represent dependency between
---
two classes.
[40]
Reactome | Nodes represent proteins, edges represent interactions. | [41]
Internet of AS 1 |  | Nodes represent autonomous systems, edges represent connections
---
between them.
[42]
PGP |  | Key-sharing network from the PGP (Pretty Good Privacy) web of
---
trust.
[43]
RIP Ireland |  | Online book of condolences for deaths in Ireland. Number of signatures
---
corresponds to node degree.
[44]
Astrophysics | Collaboration network of astrophysicists. | [19]
Internet AS 2 |  | Nodes represent autonomous systems, edges represent
---
communication between them.
[45]
Twitter | Twitter user network. | [46]
Gplus | Google+ user network. | [46]
Internet (CAIDA) |  | Nodes represent autonomous systems from the CAIDA project and
---
edges represent communication.
[45]
Munmun Digg | Reply network on the news site Digg. | [47]
Linux |  | Nodes represent files, edges represent that they contain each
---
other.
[48]
Internet Topology |  | Nodes represent autonomous systems, edges represent connections
---
between them.
[49]
Facebook | Users of Facebook in the New Orleans region. | [50]
Facebook wall | Facebook wall post network. | [50]
Slashdot | User network of technology news site Slashdot. | [51]
Enron |  | Network of emails sent at Enron. Nodes represent employees,
---
edges represent emails sent between them.
[28]
Table 5: Quantities for each of our studied networks. $N$ is number of nodes, $L$ is number of edges, $\langle k\rangle$ is the mean degree and $k_{\rm max}$ is the maximum degree. Name | $N$ | $L$ | $\langle k\rangle$ | $k_{\rm max}$
---|---|---|---|---
Gene Fusion |  291 |  279 |  1.92 |  34
Laxdaela |  338 |  894 |  5.29 |  45
Infectious Disease |  410 |  2,765 |  13.49 |  50
Network Science |  1,461 |  2,742 |  3.75 |  34
ASoIaF |  1,786 |  14,478 |  16.21 |  215
Yeast |  1,870 |  2,277 |  2.44 |  56
Petster |  2,426 |  16,631 |  13.71 |  273
Moreno Health |  2,539 |  10,455 |  8.24 |  27
Human Proteins |  3,133 |  6,726 |  4.29 |  129
US Powergrid |  4,941 |  6,594 |  2.67 |  19
Sexual Contact |  4,999 |  23,979 |  9.59 |  985
Java Classes |  6,120 |  50,290 |  16.43 |  5,655
Reactome |  6,327 |  147,547 |  46.64 |  855
Internet AS 1 |  6,474 |  13,895 |  4.29 |  1,460
PGP |  10,680 |  24,316 |  4.55 |  205
RIP Ireland |  15,310 |  1,410,272 |  184.23 |  4,235
Astrophysics |  18,771 |  198,050 |  21.10 |  504
Internet AS 2 |  22,963 |  48,436 |  4.22 |  2,390
Twitter |  23,370 |  32,831 |  2.81 |  238
Gplus |  23,628 |  39,194 |  3.32 |  2,761
Internet (CAIDA) |  26,475 |  53,381 |  4.03 |  2,628
Munmun Digg |  30,398 |  86,312 |  5.68 |  285
Linux |  30,837 |  213,747 |  13.86 |  9,340
Internet Topology |  34,761 |  107,720 |  6.20 |  2,760
Facebook Wall |  46,952 |  193,494 |  8.24 |  223
Facebook |  63,731 |  817,035 |  25.64 |  1,098
Slashdot |  79,116 |  467,731 |  11.82 |  2,534
Enron |  87,273 |  299,220 |  6.86 |  1,728
Table 6: Network datasets and their corresponding distributions, all figures rounded to two decimal places. $x_{1}$ is the first parameter for a distribution, $\bar{x}_{1}$ is the mean parameter obtained from fitting this distribution to bootstrapped samples. $\sigma_{x_{1}}$ is the standard deviation for this parameter. $P_{2.5}(x_{1})$ and $P_{97.5}(x_{1})$ are the 2.5th and 97.5th percentiles of the parameters respectively. These values are then repeated for $x_{2}$ in the case of two-parameter distributions. Network | Distribution |  $k_{\rm min}$ |  $x_{1}$ |  $\bar{x}_{1}$ |  $\sigma_{x_{1}}$ |  $P_{2.5}(x_{1})$ |  $P_{97.5}(x_{1})$ |  $x_{2}$ |  $\bar{x}_{2}$ |  $\sigma_{x_{2}}$ |  $P_{2.5}(x_{2})$ |  $P_{97.5}(x_{2})$
---|---|---|---|---|---|---|---|---|---|---|---|---
Gene Fusion | Powerlaw |  1 |  2.50 |  2.51 |  0.11 |  2.32 |  2.72 |  |  |  |  |
Laxdaela | Lognormal |  1 |  1.27 |  1.28 |  0.05 |  1.17 |  1.37 |  0.90 |  0.92 |  0.05 |  0.83 |  1.02
Infectious Disease | Weibull |  1 |  14.99 |  15.04 |  0.50 |  14.08 |  16.07 |  1.62 |  1.60 |  0.08 |  1.45 |  1.76
Network Science | Lognormal |  1 |  1.02 |  1.02 |  0.02 |  0.98 |  1.06 |  0.77 |  0.78 |  0.02 |  0.74 |  0.82
ASoIaF | Weibull |  1 |  12.68 |  12.69 |  0.49 |  11.73 |  13.62 |  0.75 |  0.75 |  0.02 |  0.71 |  0.80
Yeast Proteins | Lognormal |  2 |  0.01 |  0.24 |  0.85 |  0.00 |  4.17 |  1.11 |  1.06 |  0.21 |  0.01 |  1.17
Petster | Weibull |  3 |  7.40 |  7.31 |  0.65 |  6.06 |  8.69 |  0.62 |  0.62 |  0.03 |  0.57 |  0.67
Moreno Health | Lognormal |  2 |  0.0082 |  0.26 |  0.92 |  0.00 |  4.31 |  1.11 |  1.05 |  0.23 |  0.01 |  1.17
Human Proteins | Lognormal |  1 |  0.64 |  0.66 |  0.52 |  0.21 |  0.72 |  1.16 |  1.17 |  0.12 |  1.11 |  1.41
US Powergrid | Lognormal |  1 |  0.82 |  0.82 |  0.01 |  0.80 |  0.84 |  0.59 |  0.59 |  0.01 |  0.58 |  0.60
Sexual Contact | Lognormal |  1 |  1.31 |  1.31 |  0.28 |  1.24 |  1.36 |  1.30 |  1.30 |  0.07 |  1.25 |  1.37
Java Classes | Lognormal |  1 |  2.05 |  2.05 |  0.01 |  2.04 |  2.07 |  0.84 |  0.84 |  0.01 |  0.81 |  0.87
Reactome | Weibull |  1 |  25.60 |  25.40 |  1.79 |  23.88 |  27.14 |  0.56 |  0.55 |  0.11 |  0.52 |  0.56
Internet AS 1 | Powerlaw |  2 |  2.30 |  2.30 |  0.02 |  2.26 |  2.34 |  |  |  |  |
PGP | Weibull |  2 |  0.17 |  0.14 |  0.05 |  0.07 |  0.25 |  0.33 |  0.32 |  0.07 |  0.29 |  0.36
RIP Ireland | Weibull |  1 |  183.14 |  183.20 |  1.60 |  180.16 |  186.45 |  0.99 |  0.99 |  0.01 |  0.97 |  1.00
Astrophysics | Weibull |  2 |  10.87 |  10.82 |  0.26 |  10.30 |  11.31 |  0.59 |  0.59 |  0.01 |  0.57 |  0.60
Internet AS 2 | Powerlaw |  5 |  2.71 |  2.71 |  0.02 |  2.68 |  2.75 |  |  |  |  |
Twitter | Powerlaw |  1 |  2.47 |  2.47 |  0.01 |  2.44 |  2.49 |  |  |  |  |
Gplus | Powerlaw |  1 |  2.38 |  2.38 |  0.01 |  2.36 |  2.40 |  |  |  |  |
Internet (CAIDA) | Powerlaw |  5 |  2.70 |  2.70 |  0.02 |  2.67 |  2.73 |  |  |  |  |
Munmun Digg | Weibull |  1 |  0.48 |  0.47 |  0.03 |  0.41 |  0.54 |  0.37 |  0.37 |  0.01 |  0.36 |  0.38
Linux | Lognormal |  1 |  1.85 |  1.85 |  0.01 |  1.84 |  1.86 |  1.02 |  1.02 |  0.01 |  1.01 |  1.03
Internet topology | Powerlaw |  5 |  2.39 |  2.40 |  0.01 |  2.37 |  2.42 |  |  |  |  |
Facebook wall | Weibull |  1 |  4.29 |  4.29 |  0.06 |  4.18 |  4.40 |  0.61 |  0.61 |  0.00 |  0.61 |  0.62
Facebook | Weibull |  1 |  14.00 |  14.01 |  0.15 |  13.72 |  14.30 |  0.58 |  0.58 |  0.00 |  0.57 |  0.58
Slashdot | Weibull |  1 |  0.05 |  2.34 |  4.67 |  0.05 |  12.02 |  0.23 |  1.54 |  1.66 |  0.18 |  4.00
Enron | Weibull |  3 |  0.05 |  0.05 |  0.00 |  0.05 |  0.05 |  0.22 |  0.26 |  0.39 |  0.22 |  0.22

Figure 7: Empirical and fitted CCDFs for all studied networks listed in table
4. When assessing fit both PDFs and CCDFs should be considered.

Figure 8: Empirical and fitted PDFs for all studied networks listed in table
4. When assessing fit both PDFs and CCDFs should be considered.