Targeted Influence Minimization in Social Networks

Xinjue Wang, Ke Deng, Jianxin Li, Jeffery Xu Yu, Christian Søndergaard Jensen, Xiaochun Yang

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

5 Citations (Scopus)

Abstract

An online social network can be used for the diffusion of malicious information like derogatory rumors, disinformation, hate speech, revenge pornography, etc. This motivates the study of influence minimization that aim to prevent the spread of malicious information. Unlike previous influence minimization work, this study considers the influence minimization in relation to a particular group of social network users, called targeted influence minimization. Thus, the objective is to protect a set of users, called target nodes, from malicious information originating from another set of users, called active nodes. This study also addresses two fundamental, but largely ignored, issues in different influence minimization problems: (i) the impact of a budget on the solution; (ii) robust sampling. To this end, two scenarios are investigated, namely unconstrained and constrained budget. Given an unconstrained budget, we provide an optimal solution; Given a constrained budget, we show the problem is NP-hard and develop a greedy algorithm with an (1−1/e) -approximation. More importantly, in order to solve the influence minimization problem in large, real-world social networks, we propose a robust sampling-based solution with a desirable theoretic bound. Extensive experiments using real social network datasets offer insight into the effectiveness and efficiency of the proposed solutions.
Original languageEnglish
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings
EditorsGeoffrey I. Webb, Dinh Phung, Mohadeseh Ganji, Lida Rashidi, Vincent S. Tseng, Bao Ho
Number of pages12
PublisherSpringer
Publication date2018
Pages689-700
ISBN (Print)978-3-319-93039-8
DOIs
Publication statusPublished - 2018
Externally publishedYes
Event22nd Pacific-Asia Conference - Melbourne, Australia
Duration: 3 Jun 20186 Jun 2018

Conference

Conference22nd Pacific-Asia Conference
CountryAustralia
CityMelbourne
Period03/06/201806/06/2018
SeriesLecture Notes in Computer Science
Volume10939
ISSN0302-9743

Fingerprint

Sampling
Computational complexity
Experiments

Cite this

Wang, X., Deng, K., Li, J., Xu Yu, J., Jensen, C. S., & Yang, X. (2018). Targeted Influence Minimization in Social Networks. In G. I. Webb, D. Phung, M. Ganji, L. Rashidi, V. S. Tseng, & B. Ho (Eds.), Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings (pp. 689-700). Springer. Lecture Notes in Computer Science, Vol.. 10939 https://doi.org/10.1007/978-3-319-93040-4_54
Wang, Xinjue ; Deng, Ke ; Li, Jianxin ; Xu Yu, Jeffery ; Jensen, Christian Søndergaard ; Yang, Xiaochun. / Targeted Influence Minimization in Social Networks. Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. editor / Geoffrey I. Webb ; Dinh Phung ; Mohadeseh Ganji ; Lida Rashidi ; Vincent S. Tseng ; Bao Ho. Springer, 2018. pp. 689-700 (Lecture Notes in Computer Science, Vol. 10939).
@inproceedings{85f88ff02f50450aad6f8ea96a8cd519,
title = "Targeted Influence Minimization in Social Networks",
abstract = "An online social network can be used for the diffusion of malicious information like derogatory rumors, disinformation, hate speech, revenge pornography, etc. This motivates the study of influence minimization that aim to prevent the spread of malicious information. Unlike previous influence minimization work, this study considers the influence minimization in relation to a particular group of social network users, called targeted influence minimization. Thus, the objective is to protect a set of users, called target nodes, from malicious information originating from another set of users, called active nodes. This study also addresses two fundamental, but largely ignored, issues in different influence minimization problems: (i) the impact of a budget on the solution; (ii) robust sampling. To this end, two scenarios are investigated, namely unconstrained and constrained budget. Given an unconstrained budget, we provide an optimal solution; Given a constrained budget, we show the problem is NP-hard and develop a greedy algorithm with an (1−1/e) -approximation. More importantly, in order to solve the influence minimization problem in large, real-world social networks, we propose a robust sampling-based solution with a desirable theoretic bound. Extensive experiments using real social network datasets offer insight into the effectiveness and efficiency of the proposed solutions.",
author = "Xinjue Wang and Ke Deng and Jianxin Li and {Xu Yu}, Jeffery and Jensen, {Christian S{\o}ndergaard} and Xiaochun Yang",
year = "2018",
doi = "10.1007/978-3-319-93040-4_54",
language = "English",
isbn = "978-3-319-93039-8",
pages = "689--700",
editor = "Webb, {Geoffrey I.} and Dinh Phung and Mohadeseh Ganji and Lida Rashidi and Tseng, {Vincent S.} and Bao Ho",
booktitle = "Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings",
publisher = "Springer",
address = "Germany",

}

Wang, X, Deng, K, Li, J, Xu Yu, J, Jensen, CS & Yang, X 2018, Targeted Influence Minimization in Social Networks. in GI Webb, D Phung, M Ganji, L Rashidi, VS Tseng & B Ho (eds), Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. Springer, Lecture Notes in Computer Science, vol. 10939, pp. 689-700, Melbourne, Australia, 03/06/2018. https://doi.org/10.1007/978-3-319-93040-4_54

Targeted Influence Minimization in Social Networks. / Wang, Xinjue; Deng, Ke; Li, Jianxin; Xu Yu, Jeffery; Jensen, Christian Søndergaard; Yang, Xiaochun.

Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. ed. / Geoffrey I. Webb; Dinh Phung; Mohadeseh Ganji; Lida Rashidi; Vincent S. Tseng; Bao Ho. Springer, 2018. p. 689-700.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Targeted Influence Minimization in Social Networks

AU - Wang, Xinjue

AU - Deng, Ke

AU - Li, Jianxin

AU - Xu Yu, Jeffery

AU - Jensen, Christian Søndergaard

AU - Yang, Xiaochun

PY - 2018

Y1 - 2018

N2 - An online social network can be used for the diffusion of malicious information like derogatory rumors, disinformation, hate speech, revenge pornography, etc. This motivates the study of influence minimization that aim to prevent the spread of malicious information. Unlike previous influence minimization work, this study considers the influence minimization in relation to a particular group of social network users, called targeted influence minimization. Thus, the objective is to protect a set of users, called target nodes, from malicious information originating from another set of users, called active nodes. This study also addresses two fundamental, but largely ignored, issues in different influence minimization problems: (i) the impact of a budget on the solution; (ii) robust sampling. To this end, two scenarios are investigated, namely unconstrained and constrained budget. Given an unconstrained budget, we provide an optimal solution; Given a constrained budget, we show the problem is NP-hard and develop a greedy algorithm with an (1−1/e) -approximation. More importantly, in order to solve the influence minimization problem in large, real-world social networks, we propose a robust sampling-based solution with a desirable theoretic bound. Extensive experiments using real social network datasets offer insight into the effectiveness and efficiency of the proposed solutions.

AB - An online social network can be used for the diffusion of malicious information like derogatory rumors, disinformation, hate speech, revenge pornography, etc. This motivates the study of influence minimization that aim to prevent the spread of malicious information. Unlike previous influence minimization work, this study considers the influence minimization in relation to a particular group of social network users, called targeted influence minimization. Thus, the objective is to protect a set of users, called target nodes, from malicious information originating from another set of users, called active nodes. This study also addresses two fundamental, but largely ignored, issues in different influence minimization problems: (i) the impact of a budget on the solution; (ii) robust sampling. To this end, two scenarios are investigated, namely unconstrained and constrained budget. Given an unconstrained budget, we provide an optimal solution; Given a constrained budget, we show the problem is NP-hard and develop a greedy algorithm with an (1−1/e) -approximation. More importantly, in order to solve the influence minimization problem in large, real-world social networks, we propose a robust sampling-based solution with a desirable theoretic bound. Extensive experiments using real social network datasets offer insight into the effectiveness and efficiency of the proposed solutions.

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

U2 - 10.1007/978-3-319-93040-4_54

DO - 10.1007/978-3-319-93040-4_54

M3 - Article in proceeding

SN - 978-3-319-93039-8

SP - 689

EP - 700

BT - Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings

A2 - Webb, Geoffrey I.

A2 - Phung, Dinh

A2 - Ganji, Mohadeseh

A2 - Rashidi, Lida

A2 - Tseng, Vincent S.

A2 - Ho, Bao

PB - Springer

ER -

Wang X, Deng K, Li J, Xu Yu J, Jensen CS, Yang X. Targeted Influence Minimization in Social Networks. In Webb GI, Phung D, Ganji M, Rashidi L, Tseng VS, Ho B, editors, Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings. Springer. 2018. p. 689-700. (Lecture Notes in Computer Science, Vol. 10939). https://doi.org/10.1007/978-3-319-93040-4_54