An exact method for influence maximization based on deterministic linear threshold model. (English) Zbl 07700329
Summary: Influence maximization (IM) is a challenging combinatorial optimization problem on (social) networks given a diffusion model and limited choice for initial seed nodes. In a recent paper by M. Keskin and M. Güler [Turk. J. Electr. Eng. Comput. Sci. 26, No. 6, Article 26, 3383–3396 (2018; doi:10.3906/elk-1802-212)] an integer programming formalization of IM using the so-called deterministic linear threshold diffusion model was proposed. In fact, it is a special 0-1 linear program in which the objective is to maximize influence while minimizing the diffusion time. In this paper, by rigorous analysis, we show that the proposed algorithm can get stuck in locally optimal solution or cannot even start on certain input graphs. The identified problems are resolved by introducing further constraints which then leads to a correct algorithmic solution. Benchmarking results are shown to demonstrate the efficiency of the proposed method.
MSC:
| 90Bxx | Operations research and management science |
| 90C35 | Programming involving graphs or networks |
Software:
AMPLReferences:
| [1] | Acemoglu D, Ozdaglar A, Yildiz E (2011) Diffusion of innovations in social networks. In: 50th IEEE Conference on Decision and Control and European Control Conference pp 2329-2334 |
| [2] | Altarelli, F.; Braunstein, A.; Dall’Asta, L.; Zecchina, R., Optimizing spread dynamics on graphs by message passing, J of Stat Mechanics: Theory and Exp, 2013, P09011 (2013) · Zbl 1456.82420 · doi:10.1088/1742-5468/2013/09/P09011 |
| [3] | Chen, C-L; Pasiliao, EL; Boginski, V.; Chellappan, S.; Choo, K-KR; Phan, N., A cutting plane method for least cost influence maximization, Computational data and social networks, 499-511 (2020), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-030-66046-8_41 |
| [4] | Cheng, C-H; Kuo, Y-H; Zhou, Z., Outbreak minimization vs influence maximization: An optimization framework, BMC Medical Informatics and Decision Making, 20, 1, 1-13 (2020) · doi:10.1186/s12911-020-01281-0 |
| [5] | Farzaneh, G-B; Masoud, A.; Heshaam, F., MLPR: Efficient influence maximization in linear threshold propagation model using linear programming, Social Network Analysis and Mining, 11, 1-10 (2021) |
| [6] | Fourer R, Gay D, Kernighan B (1993) AMPL. a modeling language for mathematical programming. Thomson |
| [7] | Goldenberg, J.; Libai, B.; Muller, E., Talk of the network: A complex systems look at the underlying process of word-of-mouth, Marketing Letters, 12, 3, 211-223 (2001) · doi:10.1023/A:1011122126881 |
| [8] | Granovetter, M., Threshold models of collective behavior, Am J of Soc, 83, 6, 1420-1443 (1978) · doi:10.1086/226707 |
| [9] | Güney, E., An efficient linear programming based method for the influence maximization problem in social networks, Information Sci, 503, 589-605 (2019) · Zbl 1457.91306 · doi:10.1016/j.ins.2019.07.043 |
| [10] | Güney, E.; Leitner, M.; Ruthmair, M.; Sinnl, M., Large-scale influence maximization via maximal covering location, European J of Oper Res, 289, 1, 144-164 (2021) · Zbl 1487.91096 · doi:10.1016/j.ejor.2020.06.028 |
| [11] | Gursoy, F.; Gunnec, D., Influence maximization in social networks under deterministic linear threshold model, Knowledge-Based Syst, 161, 111-123 (2018) · doi:10.1016/j.knosys.2018.07.040 |
| [12] | Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J on Scientific and Stat Comput, 13, 5, 1194-1217 (1992) · Zbl 0760.65063 · doi:10.1137/0913069 |
| [13] | Kahr, M.; Leitner, M.; Ruthmair, M.; Sinnl, M., Benders decomposition for competitive influence maximization in (social) networks, Omega, 100 (2021) · doi:10.1016/j.omega.2020.102264 |
| [14] | Karampourniotis, P.; Szymanski, B.; Korniss, G., Influence maximization for fixed heterogeneous thresholds, Scientific Reports, 9, 5573 (2019) · doi:10.1038/s41598-019-41822-w |
| [15] | Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth acm sigkdd international conference on knowledge discovery and data mining pp 137-146 |
| [16] | Keskin, M.; Güler, M., Influence maximization in social networks: an integer programming approach, Turkish J of Electrical Eng & Comput Sci, 26, 6, 3383-3396 (2018) |
| [17] | Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Phys Rev E, 78 (2008) · doi:10.1103/PhysRevE.78.046110 |
| [18] | Li, Y.; Fan, J.; Wang, Y.; Tan, K-L, Influence maximization on social graphs: A survey, IEEE Trans on Knowledge and Data Eng, 30, 10, 1852-1872 (2018) · doi:10.1109/TKDE.2018.2807843 |
| [19] | Liu B, Cong G, Xu D, Zeng Y (2012) Time constrained influence maximization in social networks. In: 2012 IEEE 12th international conference on data mining pp 439-448 |
| [20] | Lu Z, Zhang W, Wu W, Fu B, Du D (2011, June) Approximation and inapproximation for the influence maximization problem in social networks under deterministic linear threshold model. In: 2011 31st international conference on distributed computing systems workshops pp 160-165 |
| [21] | Lu, Z.; Zhang, W.; Wu, W.; Kim, J.; Fu, B., The complexity of influence maximization problem in the deterministic linear threshold model, J of Combinatorial Optim, 24, 3, 374-378 (2012) · Zbl 1261.91041 · doi:10.1007/s10878-011-9393-3 |
| [22] | Michael K, Markus L, Ivana L (2022) The impact of passive social media users in (competitive) influence maximization. Technical report. University of Vienna, Austria |
| [23] | Nannicini, G.; Sartor, G.; Traversi, E.; Calvo, R., An exact algorithm for robust influence maximization, Math Program, 183, 419-453 (2020) · Zbl 1450.90020 · doi:10.1007/s10107-020-01507-z |
| [24] | Nemhauser, G.; Wolsey, L.; Fisher, M., An analysis of the approximations for maximizing submodular set functions, Math Program, 14, 265-294 (1978) · Zbl 0374.90045 · doi:10.1007/BF01588971 |
| [25] | Qiang, Z.; Pasiliao, EL; Zheng, QP, Model-based learning of information diffusion in social media networks, Appl Network Sci, 4, 1, 1-16 (2019) · doi:10.1007/s41109-019-0215-3 |
| [26] | Riquelme, F.; Gonzalez-Cantergiani, P.; Molinero, X.; Serna, M., Centrality measure in social networks based on linear threshold model, Knowledge-Based Syst, 140, 92-102 (2018) · doi:10.1016/j.knosys.2017.10.029 |
| [27] | Rosa, D.; Giua, A., On the spread of innovation in social networks, IFAC Proc Volumes, 46, 27, 322-327 (2013) · doi:10.3182/20130925-2-DE-4044.00006 |
| [28] | Shunyu, Y.; Neng, F.; Jie, H., Modeling the spread of infectious diseases through influence maximization, Optim Letters, 16, 1563-1586 (2022) · Zbl 1492.90091 · doi:10.1007/s11590-022-01853-1 |
| [29] | Talukder, A.; Alam, MGR; Tran, NH; Niyato, D.; Park, GH; Hong, CS, Threshold estimation models for linear threshold-based influential user mining in social networks, IEEE Access, 7, 105441-105461 (2019) · doi:10.1109/ACCESS.2019.2931925 |
| [30] | Watts, D.; Strogatz, S., Collective dynamics of ‘small-world’-networks, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139 · doi:10.1038/30918 |
| [31] | Wu, H-H; Küçükyavuz, S., A two-stage stochastic programming approach for influence maximization in social networks, Comput Optim and Appl, 69, 3, 563-595 (2018) · Zbl 1400.90238 · doi:10.1007/s10589-017-9958-x |
| [32] | Xu, R.; Bonato, A.; Mitzenmacher, M.; Prałat, P., An Lp norm relaxation approach to positive influence maximization in social network under the deterministic linear threshold model, Algorithms and models for the web graph, 144-155 (2013), Canada: Springer International Publishing, Canada · Zbl 1343.91042 · doi:10.1007/978-3-319-03536-9_12 |
| [33] | Yang, L.; Giua, A.; Li, Z., Minimizing the influence propagation in social networks for linear threshold models, IFACPapersOnLine, 50, 14465-14470 (2017) |
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.
