Bootstrapping Topological Properties and Systemic Risk of Complex Networks Using the Fitness Model

Musmeci, Nicolò; Battiston, Stefano; Caldarelli, Guido; Puliga, Michelangelo; Gabrielli, Andrea
May 2013
Journal of Statistical Physics;May2013, Vol. 151 Issue 3/4, p720
Academic Journal
In this paper we present a novel method to reconstruct global topological properties of a complex network starting from limited information. We assume to know for all the nodes a non-topological quantity that we interpret as fitness. In contrast, we assume to know the degree, i.e. the number of connections, only for a subset of the nodes in the network. We then use a fitness model, calibrated on the subset of nodes for which degrees are known, in order to generate ensembles of networks. Here, we focus on topological properties that are relevant for processes of contagion and distress propagation in networks, i.e. network density and k-core structure, and we study how well these properties can be estimated as a function of the size of the subset of nodes utilized for the calibration. Finally, we also study how well the resilience to distress propagation in the network can be estimated using our method. We perform a first test on ensembles of synthetic networks generated with the Exponential Random Graph model, which allows to apply common tools from statistical mechanics. We then perform a second test on empirical networks taken from economic and financial contexts. In both cases, we find that a subset as small as 10 % of nodes can be enough to estimate the properties of the network along with its resilience with an error of 5 %.


Related Articles

  • Bootstrap Percolation and Kinetically Constrained Models on Hyperbolic Lattices. Sausset, François; Toninelli, Cristina; Biroli, Giulio; Tarjus, Gilles // Journal of Statistical Physics;Feb2010, Vol. 138 Issue 1-3, p411 

    We study bootstrap percolation (BP) on hyperbolic lattices obtained by regular tilings of the hyperbolic plane. Our work is motivated by the connection between the BP transition and the dynamical transition of kinetically constrained models, which are in turn relevant for the study of glass and...

  • Minimal Contagious Sets in Random Regular Graphs. Guggiola, Alberto; Semerjian, Guilhem // Journal of Statistical Physics;Jan2015, Vol. 158 Issue 2, p300 

    The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of...

  • Bootstrap Percolation in Power-Law Random Graphs. Amini, Hamed; Fountoulakis, Nikolaos // Journal of Statistical Physics;Apr2014, Vol. 155 Issue 1, p72 

    A bootstrap percolation process on a graph $$G$$ is an 'infection' process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $$r$$ infected neighbours becomes infected and remains so forever. The parameter...

  • Bootstrapping on Undirected Binary Networks Via Statistical Mechanics. Fushing, Hsieh; Chen, Chen; Liu, Shan-Yu; Koehl, Patrice // Journal of Statistical Physics;Sep2014, Vol. 156 Issue 5, p823 

    We propose a new method inspired from statistical mechanics for extracting geometric information from undirected binary networks and generating random networks that conform to this geometry. In this method an undirected binary network is perceived as a thermodynamic system with a collection of...

  • Random Feynman Graphs. Söderberg, B. // AIP Conference Proceedings;2005, Vol. 776 Issue 1, p118 

    We investigate a class of random graph ensembles based on the Feynman graphs of multidimensional integrals, representing statistical-mechanical partition functions. We show that the resulting ensembles of random graphs strongly resemble those defined in random graphs with hidden color,...

  • Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs. Gaudilli�re, Alexandre; Scoppola, Benedetto; Scoppola, Elisabetta; Viale, Massimiliano // Journal of Statistical Physics;Dec2011, Vol. 145 Issue 5, p1127 

    We give a rigorous proof of two phase transitions for a disordered statistical mechanics system used to define an algorithm to find large cliques inside Erd�s random graphs. Such a system is a conservative probabilistic cellular automaton inspired by the cavity method originally introduced...

  • The Hopfield Model on a Sparse Erdös-Renyi Graph. Löwe, Matthias; Vermet, Franck // Journal of Statistical Physics;Apr2011, Vol. 143 Issue 1, p205 

    We analyze the storage capacity of the Hopfield model on a sparse G( N, p) random graph. We show that it is proportional to αpN in the entire regime where the corresponding random graph is asymptotically connected and for all value of α≤ α=0.03.

  • Connectivity of Soft Random Geometric Graphs over Annuli. Giles, Alexander; Dettmann, Carl; Georgiou, Orestis // Journal of Statistical Physics;Feb2016, Vol. 162 Issue 4, p1068 

    Nodes are randomly distributed within an annulus (and then a shell) to form a point pattern of communication terminals which are linked stochastically according to the Rayleigh fading of radio-frequency data signals. We then present analytic formulas for the connection probability of these...

  • Die Skoenlusmetode: 'n Kritiese oorsig. SWANEPOEL, J. W. H. // Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie;Sep2008 Supplement, Vol. 27 Issue 3, p23 

    Ever since its introduction, the bootstrap has provided both a powerful set of solutions for practical statisticians, and a rich source of theoretical and methodological solutions for problems in statistics. In this paper, a survey of some recent developments in the non-parametric bootstrap...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics