یک رویکرد برنامه ریزی دوسطحی برای مسأله توسعه تأثیر در شبکه در فضای رقابتی

نوع مقاله : مقاله پژوهشی

نویسنده

دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

10.22055/jamm.2020.29355.1712

چکیده

شبکه های اجتماعی در بازاریابی محصولات نقش مهمی ایفا می کنند. در این مقاله، مسأله توسعة تأثیر در شبکه های اجتماعی در فضای رقابتی بررسی می گردد که در آن، کاربران شبکه تحت تأثیر تبلیغات مثبت و منفی قرار دارند. ابتدا رهبر تعدادی از اعضای شبکه اجتماعی را به عنوان بذر مثبت انتخاب و سپس، پیرو با اطلاع کامل از تصمیمات رهبر، افراد دیگری را به عنوان بذر منفی انتخاب می نماید و تأثیرات مثبت و منفی در شبکه توسعه می یابند. هدف رهبر، بیشینه سازی سود حاصل از افرادی است که تحت تأثیر مثبت قرار می گیرند و هدف پیرو کمینه سازی این مقدار است. مسأله در قالب یک مدل برنامه ریزی دوسطحی فرمولبندی و برای حل آن، یک الگوریتم دقیق مبتنی بر تجزیه ارائه می شود. نتایج محاسباتی عملکرد مدل و الگوریتم را ارزیابی می کنند.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

A bi-level programming approach for spread of influence in competitive environment

نویسنده [English]

  • Farnaz Hooshmand Khaligh
Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran
چکیده [English]

Social networks have a great role in viral marketing by which, a company selects a few influential users as seeds to introduce a new product with the hope that the influence is cascaded throughout the network within a finite number of time-stages. This paper addresses the problem of spreading influence in a competitive network in which the users are affected by both positive and negative propaganda. First, some users are selected as seeds by the leader, and then, the follower, with the full knowledge of the leader's decisions, selects some other users as negative seeds. Afterwards, the positive and negative influences spread throughout the network. The leader's objective is to maximize the number of positive active users. However, the follower's objective is to minimize this value. First, the problem is formulated as a bilevel programming model, and then, an exact decomposition-based algorithm is developed to solve it. Computational results evaluates the performance of the proposed model and algorithm on some instances taken from the literature.

کلیدواژه‌ها [English]

  • Spread of influence
  • Social network
  • Bilevel programming
  • Exact decomposition-based algorithm