Influence Maximization under Fairness Budget Distribution in Online Social Networks

Kód výsledku v IS VaVaI

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

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Influence Maximization under Fairness Budget Distribution in Online Social Networks

Popis výsledku v původním jazyce

In social influence analysis, viral marketing, and other fields, the influence maximization problem is a fundamental one with critical applications and has attracted many researchers in the last decades. This problem asks to find a k-size seed set with the largest expected influence spread size. Our paper studies the problem of fairness budget distribution in influence maximization, aiming to find a seed set of size k fairly disseminated in target communities. Each community has certain lower and upper bounded budgets, and the number of each community&apos;s elements is selected into a seed set holding these bounds. Nevertheless, resolving this problem encounters two main challenges: strongly influential seed sets might not adhere to the fairness constraint, and it is an NP-hard problem. To address these shortcomings, we propose three algorithms (FBIM1, FBIM2, and FBIM3). These algorithms combine an improved greedy strategy for selecting seeds to ensure maximum coverage with the fairness constraints by generating sampling through a Reverse Influence Sampling framework. Our algorithms provide a (1/2 - epsilon)-approximation of the optimal solution, and require O(kT log ((8 + 2 epsilon)n ln + 2/delta + ln(nk)/epsilon(2))), O(kT log n/epsilon(2)k), and O(T/epsilon log k/epsilon log n/epsilon(2)k) complexity, respectively. We conducted experiments on real social networks. The result shows that our proposed algorithms are highly scalable while satisfying theoretical assurances, and that the coverage ratios with respect to the target communities are larger than those of the state-of-the-art alternatives; there are even cases in which our algorithms reaches 100% coverage with respect to target communities. In addition, our algorithms are feasible and effective even in cases involving big data; in particular, the results of the algorithms guarantee fairness constraints.

Název v anglickém jazyce

Influence Maximization under Fairness Budget Distribution in Online Social Networks

Popis výsledku anglicky

In social influence analysis, viral marketing, and other fields, the influence maximization problem is a fundamental one with critical applications and has attracted many researchers in the last decades. This problem asks to find a k-size seed set with the largest expected influence spread size. Our paper studies the problem of fairness budget distribution in influence maximization, aiming to find a seed set of size k fairly disseminated in target communities. Each community has certain lower and upper bounded budgets, and the number of each community&apos;s elements is selected into a seed set holding these bounds. Nevertheless, resolving this problem encounters two main challenges: strongly influential seed sets might not adhere to the fairness constraint, and it is an NP-hard problem. To address these shortcomings, we propose three algorithms (FBIM1, FBIM2, and FBIM3). These algorithms combine an improved greedy strategy for selecting seeds to ensure maximum coverage with the fairness constraints by generating sampling through a Reverse Influence Sampling framework. Our algorithms provide a (1/2 - epsilon)-approximation of the optimal solution, and require O(kT log ((8 + 2 epsilon)n ln + 2/delta + ln(nk)/epsilon(2))), O(kT log n/epsilon(2)k), and O(T/epsilon log k/epsilon log n/epsilon(2)k) complexity, respectively. We conducted experiments on real social networks. The result shows that our proposed algorithms are highly scalable while satisfying theoretical assurances, and that the coverage ratios with respect to the target communities are larger than those of the state-of-the-art alternatives; there are even cases in which our algorithms reaches 100% coverage with respect to target communities. In addition, our algorithms are feasible and effective even in cases involving big data; in particular, the results of the algorithms guarantee fairness constraints.

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

22

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

26

Strana od-do

nestrankovano

Kód UT WoS článku

000887620200001

EID výsledku v databázi Scopus

—