Fractional Budget Allocation for Influence Maximization

Abhishek K. Umrawal; Vaneet Aggarwal; Christopher J. Quinn

doi:10.1109/CDC49753.2023.10384250

Fractional Budget Allocation for Influence Maximization

Abhishek K. Umrawal, Vaneet Aggarwal, Christopher J. Quinn

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint. We propose and analyze an efficient (1-1/e) - approximation algorithm. We run experiments on a real-world social network to show the performance of our method in contrast to methods proposed for other generalizations of influence maximization.

Original language	English (US)
Title of host publication	2023 62nd IEEE Conference on Decision and Control, CDC 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4327-4332
Number of pages	6
ISBN (Electronic)	9798350301243
DOIs	https://doi.org/10.1109/CDC49753.2023.10384250
State	Published - 2023
Event	62nd IEEE Conference on Decision and Control, CDC 2023 - Singapore, Singapore Duration: Dec 13 2023 → Dec 15 2023

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	62nd IEEE Conference on Decision and Control, CDC 2023
Country/Territory	Singapore
City	Singapore
Period	12/13/23 → 12/15/23

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC49753.2023.10384250

Library availability

Discover UIUC Full Text

Cite this

Fractional Budget Allocation for Influence Maximization. / Umrawal, Abhishek K.; Aggarwal, Vaneet; Quinn, Christopher J.
2023 62nd IEEE Conference on Decision and Control, CDC 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 4327-4332 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Umrawal, AK, Aggarwal, V & Quinn, CJ 2023, Fractional Budget Allocation for Influence Maximization. in 2023 62nd IEEE Conference on Decision and Control, CDC 2023. Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 4327-4332, 62nd IEEE Conference on Decision and Control, CDC 2023, Singapore, Singapore, 12/13/23. https://doi.org/10.1109/CDC49753.2023.10384250

@inproceedings{4646bbc2fe8444b3aeb351437ed85045,

title = "Fractional Budget Allocation for Influence Maximization",

abstract = "We consider a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint. We propose and analyze an efficient (1-1/e) - approximation algorithm. We run experiments on a real-world social network to show the performance of our method in contrast to methods proposed for other generalizations of influence maximization.",

author = "Umrawal, {Abhishek K.} and Vaneet Aggarwal and Quinn, {Christopher J.}",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 62nd IEEE Conference on Decision and Control, CDC 2023 ; Conference date: 13-12-2023 Through 15-12-2023",

year = "2023",

doi = "10.1109/CDC49753.2023.10384250",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4327--4332",

booktitle = "2023 62nd IEEE Conference on Decision and Control, CDC 2023",

address = "United States",

}

TY - GEN

T1 - Fractional Budget Allocation for Influence Maximization

AU - Umrawal, Abhishek K.

AU - Aggarwal, Vaneet

AU - Quinn, Christopher J.

PY - 2023

Y1 - 2023

N2 - We consider a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint. We propose and analyze an efficient (1-1/e) - approximation algorithm. We run experiments on a real-world social network to show the performance of our method in contrast to methods proposed for other generalizations of influence maximization.

AB - We consider a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint. We propose and analyze an efficient (1-1/e) - approximation algorithm. We run experiments on a real-world social network to show the performance of our method in contrast to methods proposed for other generalizations of influence maximization.

UR - http://www.scopus.com/inward/record.url?scp=85184816751&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85184816751&partnerID=8YFLogxK

U2 - 10.1109/CDC49753.2023.10384250

DO - 10.1109/CDC49753.2023.10384250

M3 - Conference contribution

AN - SCOPUS:85184816751

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4327

EP - 4332

BT - 2023 62nd IEEE Conference on Decision and Control, CDC 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 62nd IEEE Conference on Decision and Control, CDC 2023

Y2 - 13 December 2023 through 15 December 2023

ER -

Fractional Budget Allocation for Influence Maximization

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this