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
(nodespecic) 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 counterintuitive
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 biasprone
procedure. Here we solve this problem by introducing
an analytical and unbiased maximumentropy method that
works in the shortest possible time and does not
require the explicit generation of reconstructed
samples. We consider several realworld applications
and show that, while the strengths alone give poor
results, the additional knowledge of the degrees
yields accurately reconstructed
networks. Informationtheoretic 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 higherorder patterns.
 
Downloads  


Back 