Influence Maximization under Fairness Budget Distribution in Online Social Networks

Bich-Ngan T. Nguyen, Phuong N. H. Pham, Le Van-Vang () and Václav Snášel
Additional contact information
Bich-Ngan T. Nguyen: Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh City 700000, Vietnam
Phuong N. H. Pham: Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh City 700000, Vietnam
Le Van-Vang: Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City 700000, Vietnam
Václav Snášel: Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 17.listopadu 15/2172, 708 33 Ostrava, Czech Republic

Mathematics, 2022, vol. 10, issue 22, 1-26

Abstract: 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’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 ( FBIM 1 , FBIM 2 , and FBIM 3 ). 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 − ϵ ) -approximation of the optimal solution, and require O k T log ( 8 + 2 ϵ ) n ln 2 δ + ln ( k n ) ϵ 2 , O k T log n ϵ 2 k , and O T ϵ log k ϵ log n ϵ 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.

Keywords: fairness budget; submodular maximization; influence maximization; sampling; approximation algorithm; viral marketing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/22/4185/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/22/4185/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:22:p:4185-:d:967334

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().