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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Mathematics

ISSN

2227-7390

e-ISSN

2227-7390

Svazek periodika

10

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

18

Strana od-do

nestrankovano

Kód UT WoS článku

000778250100001

EID výsledku v databázi Scopus

—