Influence Maximization under Fairness Budget Distribution in Online Social Networks

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Influence Maximization under Fairness Budget Distribution in Online Social Networks

Original language description

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.

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

22

Country of publishing house

CH - SWITZERLAND

Number of pages

26

Pages from-to

nestrankovano

UT code for WoS article

000887620200001

EID of the result in the Scopus database

—