Some results on non-progressive spread of influence in graphs

Soltani, Hossein; Hosseinzadeh, Samaneh

doi:10.22108/toc.2023.133649.1988

تعداد نشریات	42
تعداد شماره‌ها	1,513
تعداد مقالات	12,470
تعداد مشاهده مقاله	24,703,989
تعداد دریافت فایل اصل مقاله	10,426,626

	Some results on non-progressive spread of influence in graphs
Transactions on Combinatorics
مقالات آماده انتشار، اصلاح شده برای چاپ، انتشار آنلاین از تاریخ 20 اسفند 1401 اصل مقاله (449.95 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.133649.1988
نویسندگان
Hossein Soltani^* ؛ Samaneh Hosseinzadeh
Faculty of Science, Urmia University of Technology, Urmia, Iran
چکیده
This paper studies the non-progressive spread of influence with threshold model in social networks. Consider a graph $G$ with a threshold function $\tau$ on its vertex set. Spread of influence is a discrete dynamic process as follows. For a given set of initially infected vertices at time step $0$ each vertex $v$ gets infected at time step $i$, $i\geq1$, if and only if the number of infected neighbors are at least $\tau(v)$ in time step $i-1$. Our goal is to find the minimum cardinality of initially infected vertices (perfect target set) such that eventually all of the vertices get infected at some time step $\ell$. In this paper an upper bound for the convergence time of the process is given for graphs with general thresholds. Then an integer linear programming for the size of minimum perfect target set is presented. Then we give a lower bound for the size of perfect target sets with strict majority threshold on graphs which all of the vertices have even degrees. It is shown that the later bound is asymptotically tight.
کلیدواژه‌ها
Spread of Influence؛ Target Set؛ Dynamic Monopoly؛ Non-Progressive

مراجع
[1] E. Ackerman, O. Ben-Zwi and G. Wolfovitz, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411 (2010) 4017–4022. [2] C.-L. Chang and Y.-D. Lyuu, Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades, Theoret. Comput. Sci., 468 (2013) 37–49. [3] N. Chen, On the approximability of influence in social networks, SIAM J. Discrete Math., 2 (2009) 1400–1415. [4] M. C. Dourado, L. D. Penso, D. Rautenbach and J. L. Szwarc ter, Reversible iterative graph processes, Theoret. Comput. Sci., 460 (2012) 16–25. [5] M. Fazli, M. Ghodsi, J. Habibi, P. Jalaly, V. Mirrokni and S. Sadeghian, On non-progressive spread of influence through social networks, Theoret. Comput. Sci., 550 (2014) 36–50. [6] M. A. Fazli, On dynamic monopolies of cubic graphs, The CSI Journal on Computer Science and Engineering, 15 (2017) 39–44. [7] P. Flocchini, E. Lodi, F. Luccio, L. Pagli and N. Santoro, Dynamic monopolies in tori, Discrete Appl. Math., 137 (2004) 197–212. [8] C. Jeger and A. N. Zehmakan, Dynamic monopolies in two-way bootstrap percolation, Discrete Appl. Math., 262 (2019) 116–126. [9] D. Kempe, J. Kleinberg and E. Tardos, Maximizing the spread of influence through a social network, in: Proceed- ings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, Association for Computing Machinery, New York, NY, USA, (2003) 137–146. [10] K. Khoshkhah, H. Soltani and M. Zaker, Dynamic monopolies in directed graphs: The spread of unilateral influence in social networks, Discrete Appl. Math., 171 (2014) 81–89. [11] K. Khoshkhah, H. Soltani and M. Zaker, On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optim., 9 (2012) 77–83. [12] B. Moazzez and H. Soltani, Facets of the dynamic monopoly polytope: Linear ordering formulation, Discrete Optim., 40 (2021) 19 pp. [13] D. Peleg, Size bounds for dynamic monopolies, Discrete Appl. Math., 86 (1998) 263–273. [14] H. Soltani and B. Moazzez, A polyhedral study of dynamic monopolies, Ann. Oper. Res., 279 71–87. [15] H. Soltani and M. Zaker, On dynamic monopolies of graphs with probabilistic thresholds, Bull. Aust. Math. Soc., 90 (2014) 363–375. [16] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math., 312 (2012) 1136–1143.
آمار تعداد مشاهده مقاله: 49 تعداد دریافت فایل اصل مقاله: 33

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Some results on non-progressive spread of influence in graphs