Some results on non-progressive spread of influence in graphs
محل انتشار: فصلنامه معادلات در ترکیبات، دوره: 13، شماره: 2
سال انتشار: 1403
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 33
فایل این مقاله در 10 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_COMB-13-2_003
تاریخ نمایه سازی: 18 فروردین 1403
چکیده مقاله:
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 ۰ each vertex v gets infected at time step i, i\geq۱, if and only if the number of infected neighbors are at least \tau(v) in time step i-۱. 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.
کلیدواژه ها:
نویسندگان
Samaneh Hosseinzadeh
Faculty of Science, Urmia University of Technology, Urmia, Iran
Hossein Soltani
Faculty of Science, Urmia University of Technology, Urmia, Iran
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :