Maximizing influence under influence loss constraint in social networks

Yifeng Zeng, Xuefeng Chen, Gao Cong, Shengchao Qin, Jing Tang, Yanping Xiang

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.

Original languageEnglish
Pages (from-to)255-267
Number of pages13
JournalExpert Systems with Applications
Volume55
DOIs
Publication statusPublished - 15 Aug 2016

Fingerprint

Simulated annealing
Marketing

Cite this

@article{e5a18335ca5c4b5697239633f02a6b63,
title = "Maximizing influence under influence loss constraint in social networks",
abstract = "Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.",
author = "Yifeng Zeng and Xuefeng Chen and Gao Cong and Shengchao Qin and Jing Tang and Yanping Xiang",
year = "2016",
month = "8",
day = "15",
doi = "10.1016/j.eswa.2016.01.008",
language = "English",
volume = "55",
pages = "255--267",
journal = "Expert Systems With Applications.",
issn = "0957-4174",
publisher = "Elsevier",

}

Maximizing influence under influence loss constraint in social networks. / Zeng, Yifeng; Chen, Xuefeng; Cong, Gao; Qin, Shengchao; Tang, Jing; Xiang, Yanping.

In: Expert Systems with Applications, Vol. 55, 15.08.2016, p. 255-267.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Maximizing influence under influence loss constraint in social networks

AU - Zeng, Yifeng

AU - Chen, Xuefeng

AU - Cong, Gao

AU - Qin, Shengchao

AU - Tang, Jing

AU - Xiang, Yanping

PY - 2016/8/15

Y1 - 2016/8/15

N2 - Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.

AB - Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.

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

U2 - 10.1016/j.eswa.2016.01.008

DO - 10.1016/j.eswa.2016.01.008

M3 - Article

VL - 55

SP - 255

EP - 267

JO - Expert Systems With Applications.

JF - Expert Systems With Applications.

SN - 0957-4174

ER -