Multiple Benefit Thresholds Problem in Online Social Networks: An Algorithmic Approach

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F22%3A10251956" target="_blank" >RIV/61989100:27240/22:10251956 - isvavai.cz</a>

Result on the web

<a href="https://www.mdpi.com/2227-7390/10/6/876" target="_blank" >https://www.mdpi.com/2227-7390/10/6/876</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/math10060876" target="_blank" >10.3390/math10060876</a>

Result language

angličtina

Original language name

Multiple Benefit Thresholds Problem in Online Social Networks: An Algorithmic Approach

Original language description

An important problem in the context of viral marketing in social networks is the Influence Threshold (IT) problem, which aims at finding some users (referred to as a seed set) to begin the process of disseminating their product&apos;s information so that the benefit gained exceeds a predetermined threshold. Even though, marketing strategies exhibit different in several realistic scenarios due to market dependence or budget constraints. As a consequence, picking a seed set for a specific threshold is not enough to come up with an effective solution. To address the disadvantages of previous works with a new approach, we study the Multiple Benefit Thresholds (MBT), a generalized version of the IT problem, as a result of this phenomenon. Given a social network that is subjected to information distribution and a set of thresholds, T = {T-1, T-2, ..., T-k}, Ti &gt; 0, the issue aims to seek the seed sets S-1, S-2, ..., Sk with the lowest possible cost so that the benefit achieved from the influence process is at the very least T-1, T-2, ..., T-k, respectively. The main challenges of this problem are a #NP-hard problem and the estimation of the objective function #P-Hard under traditional information propagation models. In addition, adapting the exist algorithms many times to different thresholds can lead to large computational costs. To address the abovementioned challenges, we introduced Efficient Sampling for Selecting Multiple Seed Sets, an efficient technique with theoretical guarantees (ESSM). At the core of our algorithm, we developed a novel algorithmic framework that (1) can use the solution to a smaller threshold to find that of larger ones and (2) can leverage existing samples with the current solution to find that of larger ones. The extensive experiments on several real social networks were conducted in order to show the effectiveness and performance of our algorithm compared with current ones. The results indicated that our algorithm outperformed other state-of-the-art ones in terms of both the total cost and running time.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Volume of the periodical

10

Issue of the periodical within the volume

6

Country of publishing house

CH - SWITZERLAND

Number of pages

18

Pages from-to

nestrankovano

UT code for WoS article

000778250100001

EID of the result in the Scopus database

—