K-shell (or k-core) graph decomposition methods were introduced as a tool for studying the structure of large graphs. K-shell decomposition methods have been recently proposed as a technique for identifying the most influential spreaders in a complex network. Such techniques apply to static networks, whereby the topology does not change over time. In this paper we address the problem of extending such a framework to dynamic networks, whose evolution over time can be characterized through a pattern of contacts among nodes. We propose two methods for ranking nodes, according to generalized k-shell indexes, and compare their ability to identify the most influential spreaders by emulating the diffusion of epidemics using both synthetic as well as real-world contact traces.
K-shell decomposition for dynamic complex networks
Daniele Miorandi;Francesco De Pellegrini
2010-01-01
Abstract
K-shell (or k-core) graph decomposition methods were introduced as a tool for studying the structure of large graphs. K-shell decomposition methods have been recently proposed as a technique for identifying the most influential spreaders in a complex network. Such techniques apply to static networks, whereby the topology does not change over time. In this paper we address the problem of extending such a framework to dynamic networks, whose evolution over time can be characterized through a pattern of contacts among nodes. We propose two methods for ranking nodes, according to generalized k-shell indexes, and compare their ability to identify the most influential spreaders by emulating the diffusion of epidemics using both synthetic as well as real-world contact traces.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
