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

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

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

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.