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

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.
978-1-4244-7525-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11582/315521
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact