Information Technology Reference
In-Depth Information
vertex chosen uniformly at random has weight =
s
. A plot of
R
(
s
) for any network
can be constructed by making a histogram of the vertices' strength. This
histogram represents the strength distribution of the graph and allows a better
understanding of the strength allocation in the system. In particular, when dealing
with directed graphs, the strength distribution has to be split in order to consider
in a separated way the contribution of the incoming and outgoing flows.
10.3.4.
Link Reciprocity
In a directed network, the analysis of
link reciprocity
reflects the tendency of
vertex pairs to form mutual connections between each other [44]. Here we
computed the correlation coefficient index
ρ
proposed by Garlaschelli and
Loffredo, which measures whether double links (with opposite directions) occur
between vertex pairs more or less often than expected by chance. The correlation
coefficient can be written as follows:
r
(
A
)
−
k
(
A
)
w
ρ
(
A
)
=
(10.16)
1
−
k
(
A
)
w
In this formula,
r
is the ratio between the number of links pointing in both
directions and the total number of links, while
k
w
is the connection density that
equals the average probability of finding a reciprocal link between two connected
vertices in a random network. As a measure of reciprocity,
ρ
is an absolute
quantity that directly allows one to distinguish between reciprocal (
ρ
> 0) and
anti-reciprocal (
ρ
< 0) networks, with mutual links occurring more and less often
than random, respectively. The neutral or areciprocal case corresponds to
ρ
= 0.
Note that if all links occur in reciprocal pairs one has
ρ
= 1, as expected.
10.3.5.
Motifs
By motif it is usually meant a small connected graph of M vertices and a set of
edges forming a subgraph of a larger network with N > M nodes. For each N,
there are a limited number of distinct motifs. For N = 3, 4, and 5, the
corresponding numbers of directed motifs is 13, 199, and 9364. In this work, we
focus on directed motifs with N = 3. The 13 different 3-node directed motifs are
shown in Fig. 10.3. Counting how many times a motif appears in a given network
yields a frequency spectrum that contains important information on the network
basic building blocks. Eventually, one can looks at those motifs within the
considered network that occur at a frequency significantly higher than in random
graphs.
