Submodular Influence Maximization with Hesitant Fuzzy Edge Probabilities

Authors

  • Sudipta Kotal * Department of Technical Sciences, Algebra Bernays University, Gradiš´canska 24, 10000 Zagreb, Croatia.
  • Tarasankar Pramanik Department of Technical Sciences, Algebra Bernays University, Gradiš´canska 24, 10000 Zagreb, Croatia. https://orcid.org/0000-0001-7582-2525

https://doi.org/10.48314/tsc.v1i3.68

Abstract

Influence maximization is usually studied by assigning a single propagation probability to each directed edge. In many real-world situations, however, experts and repeated calibration provide several possible probability values instead of one fixed choice. This uncertainty is represented by hesitant fuzzy elements and is interpreted through two models: a weighted finite scenario model and an independent edge-wise hesitation model. For the weighted scenario model, the expected influence spread is proved to be normalized, monotone, and submodular because it is formed as a nonnegative combination of live-edge reachability functions. Hence, the classical greedy algorithm retains its (1 − 1/e) approximation guarantee. For the independent edge-wise model, marginalization is shown to be exactly equivalent to the independent cascade model with the weighted mean probability of each hesitant element. Lower and upper
hesitant envelopes provide monotone submodular spread bounds and computable certificates for every admissible edge-probability realization. A Lipschitz sensitivity bound relates changes in expected spread to variations in edge probabilities. An explicit counterexample shows that the pointwise minimum of correlated scenario spreads need not be submodular, so robust optimization requires additional structure. The proposed framework preserves hesitant uncertainty while maintaining mathematically valid approximation guarantees.

Keywords:

Hesitant fuzzy set, Influence maximization, Submodular function, Independent cascade, Greedy algorithm, Robust envelope

References

  1. [1] Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146). ACM Digital Library. https://doi.org/10.1145/956750.956769
  2. [2] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 420-429). ACM Digital Library. https://doi.org/10.1145/1281192.1281239
  3. [3] Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014). Maximizing social influence in nearly optimal time. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (pp. 946-957). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973402.70
  4. [4] Tang, Y., Shi, Y., & Xiao, X. (2015). Influence maximization in near-linear time: A martingale approach. Proceedings of the 2015 ACM SIGMOD international conference on management of data (pp. 1539-1554). ACM Digital Library. https://doi.org/10.1145/2723372.2723734
  5. [5] Torra, V. (2010). Hesitant fuzzy sets. International journal of intelligent systems, 25(6), 529-539. https://doi.org/10.1002/int.20418
  6. [6] Xu, Z., & Xia, M. (2011). Distance and similarity measures for hesitant fuzzy sets. Information sciences, 181(11), 2128-2138. https://doi.org/10.1016/j.ins.2011.01.028
  7. [7] Xia, M., & Xu, Z. (2011). Hesitant fuzzy information aggregation in decision making. International journal of approximate reasoning, 52(3), 395-407. https://doi.org/10.1016/j.ijar.2010.09.002
  8. [8] Liao, H., Xu, Z., & Xia, M. (2014). Multiplicative consistency of hesitant fuzzy preference relation and its application in group decision making. International journal of information technology & decision making, 13(01), 47-76. https://doi.org/10.1142/S0219622014500035
  9. [9] Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14(1), 265-294. https://doi.org/10.1007/BF01588971
  10. [10] Fujishige, S. (2005). Submodular functions and optimization (Vol. 58). Elsevier. https://books.google.com/books?id=gdcRXdoV89QC&dq=Fujishige,+S.+(2005)
  11. [11] Krause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of machine learning research, 9(2), 235-284. https://jmlr.org/papers/v9/krause08a.html
  12. [12] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301), 13-30. https://doi.org/10.1080/01621459.1963.10500830
  13. [13] Sviridenko, M. (2004). A note on maximizing a submodular set function subject to a knapsack constraint. Operations research letters, 32(1), 41-43. https://doi.org/10.1016/S0167-6377(03)00062-2
  14. [14] Conforti, M., & Cornuéjols, G. (1984). Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete applied mathematics, 7(3), 251-274. https://doi.org/10.1016/0166-218X(84)90003-9
  15. [15] Goyal, A., Lu, W., & Lakshmanan, L. V. (2011). Celf++ optimizing the greedy algorithm for influence maximization in social networks. Proceedings of the 20th international conference companion on World wide web (pp. 47-48). ACM Digital Library. https://doi.org/10.1145/1963192.1963217

Downloads

Published

2025-09-15

Issue

Vol. 1 No. 3 (2025): Transactions on Soft Computing

Section

Articles

License

Copyright (c) 2026 Transactions on Soft Computing

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Kotal, S., & Pramanik, T. (2025). Submodular Influence Maximization with Hesitant Fuzzy Edge Probabilities. Transactions on Soft Computing , 1(3), 190-202. https://doi.org/10.48314/tsc.v1i3.68

Similar Articles

1-10 of 12

You may also start an advanced similarity search for this article.