×

Maximizing profit of multiple adoptions in social networks with a martingale approach. (English) Zbl 1425.91376

Summary: 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\)) 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\) algorithm which returns a \((\frac{1}{2}(1-\frac{1}{e^{2}})-\varepsilon)\)-approximate solution and runs in \(O\left( (k^{*}+\ell)(m+n)nqp_{max}\ln nq/ (\varepsilon^{2}\cdot p_{min})\right) \) expected time.

MSC:

91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: ICDM, pp 88-97
[2] Chen W, Cummings A, Ke T, Liu Z, Rincn D, Sun X, Wang Y, Wei W, Yuan Y (2011) Influence maximization in social networks when negative opinions may emerge and propagate. In: SDM, pp 379-390
[3] Chen W, Lu W, Zhang N (2012) Time-critical influence maximization in social network with time-delayed diffusion process. In: Association for the advancement of artificial intelligence
[4] Chen X, Nong Q, Feng Y, Cao Y, Gong S, Fang Q, Ko Ker-I (2017) Centralized and decentralized rumor blocking problems. J Comb Optim 34:314-329 · Zbl 1383.90006 · doi:10.1007/s10878-016-0067-z
[5] Chen T, Liu B, Liu W, Fang Q, Yuan J, Wu W (2018) Maximizing profit of multiple adoptions in social networks. J Glob Optim (submitted)
[6] Dinh TN, Zhang H, Nguyen DT, Thai MT (2014) Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE/ACM Trans Netw 22:2001-2011 · doi:10.1109/TNET.2013.2290714
[7] Kempe D, Kleinberg JM, Tardos V (2003) Maximizing the spread of influence through a social network. In: KDD, pp 137-146 · Zbl 1337.91069
[8] Krause A, Golovin D (2013) Submodular function maximization. Cambridge University Press, Cambridge · doi:10.1017/CBO9781139177801.004
[9] Leskovec J, Kraus A, Guestrin C, Faloutsos C, VanBriesen J, Glance NS (2007) Cost-effective outbreak detection in networks. In: KDD, pp 420-429
[10] Nemhauser G, Wolsey L (1978) An analysis of approximations for maximizing submodular set functions. Math Program 265-294 · Zbl 0374.90045
[11] Nguyen DT, Zhang H, Das S, Thai MT, Dinh TN (2013) Least cost influence in multiplex social networks: model representation and analysis. In: ICDM, pp 567-576
[12] Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: SIGMOD, pp 75-86
[13] Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: SIGMOD, pp 1539-1554
[14] Tong G, Wu W, Guo L, Li D, Liu C, Liu B, Du D (2017) An efficient randomized algorithm for rumor blocking in online social networks. IEEE Trans Netw Sci Eng. https://doi.org/10.1109/TNSE.2017.2783190
[15] Wu W, Du H, Wang H, Wu L, Duan Z, Tian C (2018) On general threshold and general cascade models of social influence. J Comb Optim 35:209-215 · Zbl 1390.91271 · doi:10.1007/s10878-017-0165-6
[16] Zhang H, Kuhnle A (2016) Profit maximization for multiple products in online social networks. In: INFOCOM, pp 1-9
[17] Zhang H, Mishra S, Thai MT (2014) Recent advances in information diffusion and influence maximization in complex social networks, in Opportunistic Mobile Social Networks. CRC Press, Taylor and Francis Group, Boca Raton
[18] Zhang Z, Xu W, Wu W, Du D (2017) A novel approach for detecting multiple rumor sources in networks with partial observations. J Comb Optim 33:132-146 · Zbl 1366.90206 · doi:10.1007/s10878-015-9939-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.