Maximizing profit of multiple adoptions in social networks with a martingale approach

Bin Liu (), Yuxia Yan (), Qizhi Fang (), Junyu Dong (), Weili Wu () and Huijuan Wang ()
Additional contact information
Bin Liu: Ocean University of China
Yuxia Yan: Ocean University of China
Qizhi Fang: Ocean University of China
Junyu Dong: Ocean University of China
Weili Wu: University of Texas at Dallas
Huijuan Wang: Qingdao University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 1, No 1, 20 pages

Abstract: Abstract Information propagation plays an important role in social network, which helps shaping consumer’s purchasing decisions. Most of existing works focus on maximizing the influence of one product. But in our reality life, the majority of the companies produce various products for meeting customer needs. So it is important to learn about how to distribute the limited budget to maximize the companies profits. In this paper, we use the martingale technique to handle the Profit Maximization with Multiple Adoptions ( $$PM^{2}A$$ P M 2 A ) problem, which aims to identify a seed set for each product with overall activation cost at most B such that the expected total profit is maximized. We design a $$PM^{2}AM$$ P M 2 A M algorithm which returns a $$(\frac{1}{2}(1-\frac{1}{e^{2}})-\varepsilon )$$ ( 1 2 ( 1 - 1 e 2 ) - ε ) -approximate solution and runs in $$O\left( (k^{*}+\ell )(m+n)nqp_{max}\ln nq/ (\varepsilon ^{2}\cdot p_{min})\right) $$ O ( k ∗ + ℓ ) ( m + n ) n q p max ln n q / ( ε 2 · p min ) expected time.

Keywords: Profit maximization; Social network; Approximation algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0361-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:38:y:2019:i:1:d:10.1007_s10878-018-0361-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0361-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().