# Statistical Analysis of Weighted Networks

Authors: I. E. Antoniou; E. T. Tsompa
Journal: Discrete Dynamics in Nature and Society
 (2008)

---

## Abstract

The purpose of this paper is to assess the statistical characterization of weighted networks in terms of the generalization of the relevant parameters, namely, average path length, degree distribution, and clustering coefficient. Although the degree distribution and the average path length admit straightforward generalizations, for the clustering coefficient several different definitions have been proposed in the literature. We examined the different definitions and identified the similarities and differences between them. In order to elucidate the significance of different definitions of the weighted clustering coefficient, we studied their dependence on the weights of the connections. For this purpose, we introduce the relative perturbation norm of the weights as an index to assess the weight distribution. This study revealed new interesting statistical regularities in terms of the relative perturbation norm useful for the statistical characterization of weighted graphs.


---

## Body

## 1. Introduction

Complex systems may also [1] emerge from a large
number of interdependent and interacting elements. Networks have proven to be effective
models of natural or man-made complex systems, where the elements are
represented by the nodes and their interactions by the links. Typical well-known
examples include communication and transportation networks, social networks, and
biological networks [2–5].Although the statistical analysis of the underlying
topological structure has been very fruitful [2–5], it was limited due
to the fact that in real networks the links may have different capacities or
intensities or flows of information or strengths. For example, weighted links
can be used for the Internet to represent the amount of data exchanged between
two hosts in the network. For scientific collaboration networks, the weight
depends on the number of coauthored papers between two authors. For airport
networks, it is either the number of available seats on direct flight
connections between airports i and j or the actual number of passengers that
travel from airport i to j. For neural networks, the weight is the number of
junctions between neurons and for transportation networks it is the Euclidean
distance between two destinations.The diversification of the links is described in terms
of weights on the links. Therefore, the statistical analysis has to be extended
from graphs to weighted complex networks. If all links are of equal weight, the
statistical parameters used for unweighted graphs are sufficient for the
statistical characterization of the network. Therefore, the statistical
parameters of the weighted graphs should reduce to the corresponding parameters
of the conventional graphs if all weights are put equal to unity.Complex graphs are characterized by three main
statistical parameters, namely, the degree distribution, the average path
length, and the clustering coefficient. We will briefly mention the definitions
for clarity and for a better understanding of the proposed extensions of these
parameters for weighted graphs.The structure of a network withN nodes is represented
by an N×N binary matrix A={aij},
known as adjacency matrix, whose element aij equals 1, when
there is a link joining node i to node j and 0 otherwise (i,j=1,2,…,N).In the case of undirected networks with no self-links (links
connecting a node to itself), the adjacency matrix is symmetric (aij=aji) and all elements of the main diagonal equal 0 (aii=0).The degreeki of a node i is
defined as the number of its neighbors, that is, the number of links incident
to node i:(1.1)ki=∑j∈Π(i)aij, where aij the elements of the adjacency matrix A and Π(i) the neighborhood
of node i.The degree
distribution is the
probability that some node hask connections to other nodes. Many real complex
networks have been found to be described by a power law degree, P(k)~k−γ, with 2≤γ≤3.The characteristic
path length of a network is defined as the average of the shortest path
lengths between any two nodes:(1.2)L=2N(N−1)∑i,jdij, where dij is the shortest path length between i and j,
defined as the minimum number of links traversed to get from node i to node j.In many real networks,
it is found that the existence of a link between nodesi and j and between
nodes i and k enhances the probability that node j will also be connected to
node k. This tendency of the
neighbors of any node i to connect to each
other is called clustering and is quantified by the clustering coefficient Ci,
which is the fraction of triangles in which node i participates, to the maximum
possible number of such triangles:(1.3)Ci=niki(ki−1)=∑j,kaijajkakiki(ki−1),ki≠0,1, where (1/2)ni=(1/2)∑j,kaijajkaki is the actual number of triangles in which
node i participates, that is, the actual number of links between the neighbors of
node i, and ki(ki−1)/2 is the maximum possible number of links, when
the subgraph of neighbors of node i is completely connected.The clustering
coefficientCi equals 1 if node i is the center of a fully
interconnected cluster, and equals 0 if the neighbors of
node i are not connected to each other.In order to characterize the network as a whole, we usually consider the average
clustering coefficientC over all the nodes. We may also consider the average
clustering coefficient C(k) over the node degree k.Studies of real complex networks have shown that their
connection topology is neither completely random nor completely regular, but
lies between these extreme cases. Many real networks share features of both
extreme cases. For example, the short average path length, typical of random
networks, comes along with large clustering coefficient, typical of regular
lattices. The coexistence of these attributes defines a distinct class of
networks, interpolating between regular lattices and random networks, known
today as small world networks [3–6]. Another class of networks emerges
when the degree distribution is a power law (scale free) distribution, which
signifies the presence of a nonnegligible number of highly connected nodes,
known as hubs. These nodes, with very large degree k compared to the average
degree 〈k〉, are critical for the network’s robustness and
vulnerability. These networks are known today as scale-free networks [2–4, 7].The purpose of this paper is to assess the statistical
characterization of weighted networks in terms of proper generalizations of the
relevant parameters, namely, average path length, degree distribution, and
clustering coefficient. After reviewing the definitions of the weighted average
path length, weighted degree distribution and weighted clustering coefficient
in Section2, we compare them in Section 3. Although the degree distribution and the average path length admit straightforward
generalizations, for the clustering coefficient several different definitions
have been proposed. In order to elucidate the significance of different
definitions of the weighted clustering coefficient, we studied their dependence
on the weights of the connections in Section 4, where we introduce the relative
perturbation norm as an index to assess the weight distribution. This study
revealed new interesting statistical regularities in terms of the relative
perturbation norm useful for the statistical characterization of weighted
graphs.


## 2. Statistical Parameters of Weighted Networks

The weights of the links between nodes are described by anN×N matrix W={wij}. The weight wij is 0 if the nodes i and j are not linked. We
will consider the case of symmetric positive weights (wij=wji≥0), with no
self-links (wii=0).In order to compare different networks or different
kinds of weights, we usually normalize the weights in the interval [0,1], by
dividing all weights by the maximum weight. The normalized weights are wij/max(wij).The statistical parameters for weighted networks are
defined as follows.The node degreeki=∑j∈Π(i)aij, which is the number of links attached to node i, is
extended directly to the strength or
weighted degree, which is the sum of the weights of all links attached
to node i:(2.1)si=∑j∈Π(i)wij. The strength of a
node takes into account both the connectivity as well as the weights of the
links.The degree distribution is also extended for the weighted
networks to the strength distributionP(s), which is the probability that
some node’s strength equals s. Recent studies indicate power law P(s)~s−a [8–10].There are two
different generalizations of the characteristic path length in the literature,
applicable to transportation and communication networks. In the case of
transportation networks, the weighted
shortest path lengthdij between the nodes i and j is defined as the smallest sum of
the weights of the links throughout all possible paths from node i to node j [11, 12]:(2.2)dijtr=minγ(i,j)∈Γ(i,j)[∑m,n∈γ(i,j)wmn], where γ(i,j) is a path from
node i to node j and Γ(i,j) is the class of
paths from i to j.The weight  describes
physical distances and/or cost usually involved in transportation networks. The
capacity, intensity, strength, or efficiency of the connection is
inversely proportional to the weight.However, this
definition is not suitable for communication networks, where the efficiency of
the communication channel between two nodes is proportional to the weight. The
shortest path length in case of communication networks is defined as the
smallest sum of the inverse weights of the links throughout all possible paths
from nodei to node j:(2.3)dijcom=minγ(i,j)∈Γ(i,j)[∑m,n∈γ(i,j)1wmn]. The weighted
characteristic path length for both cases is the average of all shortest path
lengths and it is calculated by formula (1.2).We found in the literature seven proposals for the
definitions of the weighted clustering
coefficient, which  we will  review.(i) Zhang and Horvath’s [13] definition is as follows:
(2.4)Cw,iZ=∑j∑kwijwjkwki(∑jwij)2−∑jwij2. The weights in this definition are normalized. The
idea of the generalization is the substitution of the elements of the adjacency
matrix by the weights in the nominator of formula (1.3); as for the denominator,
the upper limit of the nominator is obtained in order to normalize the
coefficient between 0 and 1. The definition originated from gene coexpression
networks.As shown by Kalna and Higham [14], an alternative formula
that may apply for this definition is (2.5)Cw,iK=∑j∑kwijwjkwki∑j∑k≠jwijwik.(ii) Lopez-Fernandez et al.’s  [15] definition is
(2.6)Cw,iL=∑j,k∈Π(i)wjkki(ki−1). The weights in this
definition are not normalized. The idea of the generalization is the
substitution of the number of links that exist between the neighbors of node i in formula (1.3) by the weight of the link between the neighbors j and k. The
definition originated from an affiliation network for committers (or
modules) of free, open source software projects.(iii) Onnela et al.’s [16]
definition is
(2.7)Cw,iO=∑j,k(wijwjkwki)1/3ki(ki−1). The weights in this definition are normalized. The
quantity I(g)=(wijwjkwki)1/3 is called
“intensity” of the triangle ijk. The concept for this generalization is to
substitute the total number of the triangles in which node i participates by
the intensity of the triangle, which is geometric mean of the links’ weights.(iv) Barrat et al.’s  [8] definition is
(2.8)Cw,iB=1si(ki−1)∑j,kwij+wik2aijajkaki. The weights in this
definition are not normalized. The idea of the generalization is the
substitution of the elements of the adjacency matrix in formula (1.3), by the average
of the weights of the links between node i and its neighbors j and k with
respect to normalization factor si(ki−1) which ensures
that 0≤Cw,iB≤1. This definition was used for airport and scientific
collaboration networks.(v) Serrano et al.’s  [17] definition is
(2.9)Cw,iS=∑j∑kwijwikakjsi2(1−Yi), where Yi=∑j(wij/si)2 has been named “disparity.”The weights in this definition are not normalized.
This formula is used for the generalization of the average clustering
coefficient with degreek, which has a probabilistic interpretation just as the
unweighted clustering coefficient.(vi) Holme et al.’s  [18] definition is
(2.10)Cw,iH=∑j∑kwijwjkwkimax(wij)∑j∑k≠jwijwik. The only difference between formulas (2.4) and (2.10) is
that (2.10) is divided by max(wij).We will not discuss this definition in the comparison
because the essence of the comparison is already addressed by definition (2.4).(vii) Li et al.’s [19] definition of the weighted clustering
coefficient is another version of the Lopez-Fernandez proposal (2.6).


## 3. The Relation between the Different Weighted Clustering Coefficients

(1) All definitions reduce to the clustering coefficient (1.3), when the
weights wij are replaced by
the adjacency matrix elements.(2) All weighted clustering coefficients reduce to 0 when there are no links
between the neighbors of nodei, that is, when ajk=wjk=0.(3) In the other extreme, all weighted clustering coefficients take the value
1 when all neighbors of nodei are connected to each other. Formulas (2.4) and
(2.6) take the value 1 if the weights between the neighbors of the node i are 1,
independently of the weights of the other links. Formula (2.7) takes the value 1,
if and only if all the weights are equal to 1. Formulas (2.8) and (2.9) take the
value 1 for all fully connected graphs, independently of all the weights.These calculations are presented in Appendix1.(4) We calculated the values of the weighted clustering coefficients of nodei participating in a fully connected triangle. Formulas (2.4) and (2.6) take the
value wjk of the weight of the link between neighbors j and k of node i. Formula (2.7) becomes equal to the intensity of the triangle Cw,iO=(wijwjkwki)1/3 for all nodes
of the triangle. Formulas (2.8) and (2.9) take the value 1 for all fully
connected graphs, independently of all weights.These calculations
are presented in Appendix2.


## 4. The Dependence of the Weighted Clustering Coefficients on the Weights

In order to understand the meaning of the different
proposals or definitions
(2.4), (2.6), (2.7), (2.8), and (2.9) of the weighted clustering coefficient, we will examine
their dependence on the weights, without alteration of the topology of the
graph. We simply examine the values of these definitions for different
distributions of weights, substituting the nonzero elements of the adjacency
matrix A by weights normalized between 0 and 1.A way to distinguish and compare different weight
distributions over the same graph is in terms of the relative perturbation norm∥A−W∥/∥A∥, which gives
the percentage of the perturbation of
the adjacency matrix introduced by the weights. For simplicity, we considered
the L2 norm.Although the weight  distributions of certain real
weighted networks have been found to be inhomogeneous like the exponential [8–10, 12, 19], we will examine the dependence of the weighted clustering
coefficient with respect to the relative perturbation norms for the exponential
as well as for the uniform and normal distributions, for different graphs.We have examined many networks from 20 up to 300 nodes
with different topologies that were generated by the networks software PAJEK [20].
The weights examined are randomly generated numbers following uniform, normal, or
exponential distributions with several parameter values, so that the
percentages of the perturbations scale from 0–90% increasing by
10% at each perturbation. All simulations gave rise to the same results, Figures
3 and 4, representing the typical trends of random and scale free networks, Figures
1 and 2. The related statistical trend analysis is reported in Appendix 3.Figure 1
The random network (Erdos-Renyi model)
examined consists of 100 nodes and was generated by the networks software PAJEK
[20]. The clustering coefficient for the unweighted network is 0.3615.Figure 2
The scale-free network (Barabasi-Albert
extended model) examined consists of 100 nodes and was generated by the
networks software PAJEK [20]. The clustering coefficient for the unweighted
network is 0.6561.The values of all five weighted clustering
coefficients Zhang and HorvathCw,iZ(★), Lopez-Fernandez et al. Cw,iL(▪), Onnela et al. Cw,iO(▴), Barrat et al. Cw,iB(⧫), and Serrano et al. Cw,iS(□), in terms of the relative perturbation norm for the
random network (Erdos-Renyi model) with 100 nodes. (a) The weights are
randomly generated numbers following the uniform distribution; (b) the weights are randomly generated numbers
following the normal distribution; (c) the weights are randomly generated
numbers following the exponential distribution.
(a)(b)(c)The values of all five weighted clustering
coefficients Zhang and HorvathCw,iZ(★), Lopez-Fernandez et al. Cw,iL(▪), Onnela et al. Cw,iO(▴), Barrat et al. Cw,iB(⧫), and Serrano et al. Cw,iS(□), in terms of the relative perturbation norm for the
scale-free network (Barabasi-Albert extended model) with 100 nodes. (a) The
weights are randomly generated numbers following the uniform distribution; (b) the
weights are randomly generated numbers following the normal distribution; (c) the
weights are randomly generated numbers following the exponential distribution.
(a)(b)(c)Observations on the dependence of the weighted
clustering coefficients on the relative perturbation norm are defined as follows.(1) For the weighted clustering coefficients (2.4), (2.6), and
(2.7), there is a clear linear dependence of their values, in terms of the
relative perturbation norm of the weighted network. It is remarkable that no
dependence is observed on the values of weights on specific links. The Zhang and Horvath (2.4), Lopez-Fernandez et al. (2.6), and Onnela et al. (2.7) weighted clustering
coefficients follow the same trend, decaying smoothly as the relative
perturbation norm increases. More specifically the trends of Zhang and Horvath (2.4)
and Lopez-Fernandez et al. (2.6) almost coincide, as expected (Section 3), while
the trend of Onnela et al. (2.8) varies slightly from the other two.(2) The resulting linear models indicate that the
values of the weighted clustering coefficients decrease by 10% of the value of
the unweighted clustering coefficient, as the relative perturbation norm
increases by 10%.(3) The dependence of the weighted clustering coefficients
(2.8) and (2.9) on the weights is not significant. The weighted clustering
coefficients of Barrat et al. (2.8) and Serrano et al. (2.9) do not change
(variations appear after the first two decimal digits), regardless of the size
of the network or the distribution of the weights. As mentioned in Section 3,
these coefficients are independent of the weights when the graph is completely
connected. We observe here that the weighted clustering coefficients (2.8) and
(2.9) are independent of the weights for graphs that are not completely
connected. We conjecture therefore that this is a general fact.


## 5. Concluding Remarks

(1) From the observed dependence of the values of all five weighted clustering coefficients on the relative perturbation norm, we conjecture that the proposed
relative perturbation norm is a reliable index of the weight distribution. The
meaning of the decaying trend of weighted clustering coefficients defined by
Zhang and Horvath (2.4), Lopez-Fernandez et al. (2.6), and Onnela et al. (2.7), with
respect to the increase of the relative perturbation norm, is quite natural.
The clustering decreases almost linearly as the weights “decrease.”(2) We presented in Appendices1 and 2 the calculations demonstrating that all definitions
reduce to the clustering coefficient (1.3), when the weights wij are replaced by
the adjacency matrix elements. The values of the weighted clustering
coefficients of node i participating in a fully connected triangle are
presented for completeness because we did not found them in  the literature.Table 1
A comparison between random network and scale-free network (NM: network model, WD: weight distribution, WCC: weighted clustering coefficient,R2: squared correlation coefficient, F∣sig: F-ratio and corresponding significance, b0, b1: Estimated parameters of the linear model (constant and coefficient of the predictor variable relative perturbation norm) with corresponding t∣sig (p-value)).
NMWDWCCR2F∣sigb0t∣sigb1t∣sigRandomNetwork Erdos-Renyi modelUniform
(Figure3(a))Zhang0.9941290.026∣0.0000.37269.092∣0.000−0.362−35.917∣0.000Lopez-Fernandez0.9941364.860∣0.0000.37171.072∣0.000−0.362−36.944∣0.000Onnela0.9972975.038∣0.0000.370100.354∣0.000−0.376−54.544∣0.000Barrat0.0130.101∣0.7580.362657.630∣0.0000.000−0.318∣0.758Serrano0.0000.001∣0.9720.362301.844∣0.0000.000−0.036∣0.972Normal (Figure3(b))Zhang0.99913629.467∣0.0000.364219.958∣0.000−0.362−116.745∣0.000Lopez-Fernandez0.99913711.182∣0.0000.364220.768∣0.000−0.362−117.094∣0.000Onnela135769.842∣0.0000.363352.133∣0.000−0.366−189.129∣0.000Barrat0.0010.011∣0.9200.3611763.897∣0.0000.000−0.104∣0.920Serrano0.0270.224∣0.6490.362888.635∣0.0000.000−0.473∣0.649Exponential
(Figure3(c))Zhang1102303.279∣0.0000.362599.496∣0.000−0.362−319.849∣0.000Lopez-Fernandez1109645.313∣0.0000.362619.969∣0.000−0.362−331.127∣0.000Onnela124935.117∣0.0000.363291.250∣0.000−0.369−157.909∣0.000Barrat0.4416.305∣0.0360.361903.747∣0.0000.0022.511∣0.036Serrano0.59211.622∣0.0090.361700.433∣0.0000.0033.409∣0.009Scale free Network Barabasi Albert Extended modelUniform (Figure4(a))Zhang0.982425.202∣0.0000.67940.511∣0.000−0.647−20.620∣0.000Lopez-Fernandez0.982427.643∣0.0000.68040.421∣0.000−0.651−20.680∣0.000Onnela0.9962269.81∣0.0000.67287.611∣0.000−0.685−47.643∣0.000Barrat0.1060.945∣0.3600.655356.437∣0.0000.0030.972∣0.360Serrano0.0960.854∣0.3820.655162.161∣0.0000.0070.924∣0.382Normal
(Figure4(b))Zhang0.9983375.047∣0.0000.652109.145∣0.000−0.650−58.095∣0.000Lopez-Fernandez0.9983510.742∣0.0000.652111.183∣0.000−0.651−59.252∣0.000Onnela125056.870∣0.0000.656296.796∣0.000−0.655−158.294∣0.000Barrat0.0160.129∣0.7290.655368.559∣0.0000.0010.359∣0.729Serrano0.0180.150∣0.7090.655170.560∣0.0000.0030.387∣0.709Exponential (Figure4(c))Zhang0.99913635.348∣0.0000.656215.181∣0.000−0.667−116.770∣0.000Lopez-Fernandez0.99913883.081∣0.0000.656216.885∣0.000−0.668−117.826∣0.000Onnela121450.540∣0.0000.658269.459∣0.000−0.670−146.460∣0.000Barrat0.1191.077∣0.3300.656745.786∣0.0000.0021.038∣0.330Serrano0.0880.771∣0.4050.655388.730∣0.0000.0030.878∣0.405



---

*Source: 375452-2008-05-06.xml*