King's College London

Research portal

Influence maximization in the presence of vulnerable nodes: A ratio perspective

Research output: Contribution to journalArticlepeer-review

Standard

Influence maximization in the presence of vulnerable nodes : A ratio perspective. / Chen, Huiping; Loukides, Grigorios; Pissis, Solon P.; Chan, Hau.

In: Theoretical Computer Science, Vol. 852, 08.01.2021, p. 84-103.

Research output: Contribution to journalArticlepeer-review

Harvard

Chen, H, Loukides, G, Pissis, SP & Chan, H 2021, 'Influence maximization in the presence of vulnerable nodes: A ratio perspective', Theoretical Computer Science, vol. 852, pp. 84-103. https://doi.org/10.1016/j.tcs.2020.11.020

APA

Chen, H., Loukides, G., Pissis, S. P., & Chan, H. (2021). Influence maximization in the presence of vulnerable nodes: A ratio perspective. Theoretical Computer Science, 852, 84-103. https://doi.org/10.1016/j.tcs.2020.11.020

Vancouver

Chen H, Loukides G, Pissis SP, Chan H. Influence maximization in the presence of vulnerable nodes: A ratio perspective. Theoretical Computer Science. 2021 Jan 8;852:84-103. https://doi.org/10.1016/j.tcs.2020.11.020

Author

Chen, Huiping ; Loukides, Grigorios ; Pissis, Solon P. ; Chan, Hau. / Influence maximization in the presence of vulnerable nodes : A ratio perspective. In: Theoretical Computer Science. 2021 ; Vol. 852. pp. 84-103.

Bibtex Download

@article{448d466851334abea87d3196546a963f,
title = "Influence maximization in the presence of vulnerable nodes: A ratio perspective",
abstract = "Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e.g., predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.",
keywords = "Influence maximization, Social networks, Vulnerable nodes",
author = "Huiping Chen and Grigorios Loukides and Pissis, {Solon P.} and Hau Chan",
year = "2021",
month = jan,
day = "8",
doi = "10.1016/j.tcs.2020.11.020",
language = "English",
volume = "852",
pages = "84--103",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS (suitable for import to EndNote) Download

TY - JOUR

T1 - Influence maximization in the presence of vulnerable nodes

T2 - A ratio perspective

AU - Chen, Huiping

AU - Loukides, Grigorios

AU - Pissis, Solon P.

AU - Chan, Hau

PY - 2021/1/8

Y1 - 2021/1/8

N2 - Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e.g., predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.

AB - Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e.g., predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.

KW - Influence maximization

KW - Social networks

KW - Vulnerable nodes

UR - http://www.scopus.com/inward/record.url?scp=85097068371&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.11.020

DO - 10.1016/j.tcs.2020.11.020

M3 - Article

AN - SCOPUS:85097068371

VL - 852

SP - 84

EP - 103

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454