Influence Maximization for Fixed Heterogeneous Thresholds

Abstract Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	P. D. Karampourniotis, B. K. Szymanski, G. Korniss
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2019
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/428f37a8d2814bffb499b912c2629cc1
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:428f37a8d2814bffb499b912c2629cc1
record_format	dspace
spelling	oai:doaj.org-article:428f37a8d2814bffb499b912c2629cc12021-12-02T15:09:13ZInfluence Maximization for Fixed Heterogeneous Thresholds10.1038/s41598-019-41822-w2045-2322https://doaj.org/article/428f37a8d2814bffb499b912c2629cc12019-04-01T00:00:00Zhttps://doi.org/10.1038/s41598-019-41822-whttps://doaj.org/toc/2045-2322Abstract Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.P. D. KarampourniotisB. K. SzymanskiG. KornissNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 9, Iss 1, Pp 1-12 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q P. D. Karampourniotis B. K. Szymanski G. Korniss Influence Maximization for Fixed Heterogeneous Thresholds
description	Abstract Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.
format	article
author	P. D. Karampourniotis B. K. Szymanski G. Korniss
author_facet	P. D. Karampourniotis B. K. Szymanski G. Korniss
author_sort	P. D. Karampourniotis
title	Influence Maximization for Fixed Heterogeneous Thresholds
title_short	Influence Maximization for Fixed Heterogeneous Thresholds
title_full	Influence Maximization for Fixed Heterogeneous Thresholds
title_fullStr	Influence Maximization for Fixed Heterogeneous Thresholds
title_full_unstemmed	Influence Maximization for Fixed Heterogeneous Thresholds
title_sort	influence maximization for fixed heterogeneous thresholds
publisher	Nature Portfolio
publishDate	2019
url	https://doaj.org/article/428f37a8d2814bffb499b912c2629cc1
work_keys_str_mv	AT pdkarampourniotis influencemaximizationforfixedheterogeneousthresholds AT bkszymanski influencemaximizationforfixedheterogeneousthresholds AT gkorniss influencemaximizationforfixedheterogeneousthresholds
_version_	1718387870248468480

Influence Maximization for Fixed Heterogeneous Thresholds

Ejemplares similares