Balancing Speed and Coverage by Sequential Seeding in Complex Networks

Abstract Information spreading in complex networks is often modeled as diffusing information with certain probability from nodes that possess it to their neighbors that do not. Information cascades are triggered when the activation of a set of initial nodes – seeds – results in diffusion to large nu...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jarosław Jankowski, Piotr Bródka, Przemysław Kazienko, Boleslaw K. Szymanski, Radosław Michalski, Tomasz Kajdanowicz
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/fc3132f200df4a5e816ba7bb88b8ea19
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:fc3132f200df4a5e816ba7bb88b8ea19
record_format	dspace
spelling	oai:doaj.org-article:fc3132f200df4a5e816ba7bb88b8ea192021-12-02T12:32:02ZBalancing Speed and Coverage by Sequential Seeding in Complex Networks10.1038/s41598-017-00937-82045-2322https://doaj.org/article/fc3132f200df4a5e816ba7bb88b8ea192017-04-01T00:00:00Zhttps://doi.org/10.1038/s41598-017-00937-8https://doaj.org/toc/2045-2322Abstract Information spreading in complex networks is often modeled as diffusing information with certain probability from nodes that possess it to their neighbors that do not. Information cascades are triggered when the activation of a set of initial nodes – seeds – results in diffusion to large number of nodes. Here, several novel approaches for seed initiation that replace the commonly used activation of all seeds at once with a sequence of initiation stages are introduced. Sequential strategies at later stages avoid seeding highly ranked nodes that are already activated by diffusion active between stages. The gain arises when a saved seed is allocated to a node difficult to reach via diffusion. Sequential seeding and a single stage approach are compared using various seed ranking methods and diffusion parameters on real complex networks. The experimental results indicate that, regardless of the seed ranking method used, sequential seeding strategies deliver better coverage than single stage seeding in about 90% of cases. Longer seeding sequences tend to activate more nodes but they also extend the duration of diffusion. Various variants of sequential seeding resolve the trade-off between the coverage and speed of diffusion differently.Jarosław JankowskiPiotr BródkaPrzemysław KazienkoBoleslaw K. SzymanskiRadosław MichalskiTomasz KajdanowiczNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 7, Iss 1, Pp 1-11 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Jarosław Jankowski Piotr Bródka Przemysław Kazienko Boleslaw K. Szymanski Radosław Michalski Tomasz Kajdanowicz Balancing Speed and Coverage by Sequential Seeding in Complex Networks
description	Abstract Information spreading in complex networks is often modeled as diffusing information with certain probability from nodes that possess it to their neighbors that do not. Information cascades are triggered when the activation of a set of initial nodes – seeds – results in diffusion to large number of nodes. Here, several novel approaches for seed initiation that replace the commonly used activation of all seeds at once with a sequence of initiation stages are introduced. Sequential strategies at later stages avoid seeding highly ranked nodes that are already activated by diffusion active between stages. The gain arises when a saved seed is allocated to a node difficult to reach via diffusion. Sequential seeding and a single stage approach are compared using various seed ranking methods and diffusion parameters on real complex networks. The experimental results indicate that, regardless of the seed ranking method used, sequential seeding strategies deliver better coverage than single stage seeding in about 90% of cases. Longer seeding sequences tend to activate more nodes but they also extend the duration of diffusion. Various variants of sequential seeding resolve the trade-off between the coverage and speed of diffusion differently.
format	article
author	Jarosław Jankowski Piotr Bródka Przemysław Kazienko Boleslaw K. Szymanski Radosław Michalski Tomasz Kajdanowicz
author_facet	Jarosław Jankowski Piotr Bródka Przemysław Kazienko Boleslaw K. Szymanski Radosław Michalski Tomasz Kajdanowicz
author_sort	Jarosław Jankowski
title	Balancing Speed and Coverage by Sequential Seeding in Complex Networks
title_short	Balancing Speed and Coverage by Sequential Seeding in Complex Networks
title_full	Balancing Speed and Coverage by Sequential Seeding in Complex Networks
title_fullStr	Balancing Speed and Coverage by Sequential Seeding in Complex Networks
title_full_unstemmed	Balancing Speed and Coverage by Sequential Seeding in Complex Networks
title_sort	balancing speed and coverage by sequential seeding in complex networks
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/fc3132f200df4a5e816ba7bb88b8ea19
work_keys_str_mv	AT jarosławjankowski balancingspeedandcoveragebysequentialseedingincomplexnetworks AT piotrbrodka balancingspeedandcoveragebysequentialseedingincomplexnetworks AT przemysławkazienko balancingspeedandcoveragebysequentialseedingincomplexnetworks AT boleslawkszymanski balancingspeedandcoveragebysequentialseedingincomplexnetworks AT radosławmichalski balancingspeedandcoveragebysequentialseedingincomplexnetworks AT tomaszkajdanowicz balancingspeedandcoveragebysequentialseedingincomplexnetworks
_version_	1718394195289309184

Balancing Speed and Coverage by Sequential Seeding in Complex Networks

Ejemplares similares