2013/16 | LEM Working Paper Series | ||||||||||||||||
Enhanced network reconstruction from irreducible local information |
|||||||||||||||||
Rossana Mastrandrea, Tiziano Squartini, Giorgio Fagiolo, Diego Garlaschelli |
|||||||||||||||||
Keywords | |||||||||||||||||
Network reconstruction; Null models; Complex networks; Maximum entropy ensembles; Configuration model
|
|||||||||||||||||
JEL Classifications | |||||||||||||||||
|
|||||||||||||||||
Abstract | |||||||||||||||||
Network topology plays a key role in many phenomena, from the
spreading of diseases to that of nancial
crises. Whenever the whole structure of a network is
unknown, one must resort to reconstruction methods
that identify the least biased ensemble of networks
consistent with the partial information available. A
challenging case is when there is only local
(node-specic) information available. For binary
networks, the relevant ensemble is one where the
degree (number of links) of each node is constrained
to its observed value. However, for weighted networks
the problem is much more complicated. While the naive
approach prescribes to constrain the strengths (total
link weights) of all nodes, recent counter-intuitive
results suggest that in weighted networks the degrees
are often more informative than the strengths, and as
`fundamental' as the latter. This implies that the
reconstruction of weighted networks would be
signicantly enhanced by the specication of both
quantities, a computationally hard and bias-prone
procedure. Here we solve this problem by introducing
an analytical and unbiased maximum-entropy method that
works in the shortest possible time and does not
require the explicit generation of reconstructed
samples. We consider several real-world applications
and show that, while the strengths alone give poor
results, the additional knowledge of the degrees
yields accurately reconstructed
networks. Information-theoretic criteria rigorously
conrm that the binary information is irreducible to
the weighted one. Our results have strong implications
for the analysis of motifs and communities and
whenever the reconstructed ensemble is required as a
null model to detect higher-order patterns.
|
Downloads
|
|
| |
|
Back
|
|