МАКСИМИЗАЦИЯ КОНКУРЕНТНОГО ВЛИЯНИЯ В СОЦИАЛЬНЫХ СЕТЯХ НА ОСНОВЕ ИГРЫ ВОРОНОГО

Социальные сети по своей природе являются средой продвижения идей, товаров, технологий и инноваций в широком смысле. Решение индивида о принятии или отвержении продвигаемой инновации в существенной степени зависит от решений его окружения в социальной сети. В случае конкурентного распространения в социальной сети двух и более взаимоисключающих влияний, результаты в виде подмножеств участников сети, попавших под каждое из влияний, будут в значительной степени зависеть от подмножеств участников, являвшихся инициаторами этих влияний. Теоретико-игровая модель конкурентного распространения влияний предполагает, что каждым влиянием управляет игрок, отбирающий соответствующее подмножество участников-инициаторов. Показано, что такая игра по сути является игрой Вороного, осуществляемой в сложно структурированном пространстве. Рассматриваются некоторые свойства рациональной стратегии игрока, делающего ход последним, а также возможность выработки такой стратегии при помощи жадных алгоритмов. Предложены конкурентные метрики центральности, перспективные для использования в жадных алгоритмах формирования подмножества участников-инициаторов последним игроком. Показано, что имеется выраженная взаимозависимость между конкурентной центральностью по близости, конкурентной центральностью по промежуточности (изолирующей центральностью) и результирующим количеством участников сети, попавших под влияние игрока, делающего последний ход.

1. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence in a social network // In: Proc. 9th KDD, 2003. pp. 137–146.

2. Voronoi, G. Nouvelles applications des paramètres continus à la théorie des formes quadratiques // J Reine Angew Math No. 134, 1908. pp. 198–287.

3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. ‒ М.: Мир, 1989. 478 C.

4. Торбенко А.М. Модели линейного города: обзор и типология // Журнал Новой экономической ассоциации. № 1 (25), 2015. С. 12-38.

5. Eaton C.B., Lipsey R.G. The Principle of Minimum Differentiation Reconsidered: Some New Developments in the Theory of Spatial Competition // The Review of Economic Studies. Vol. 42. No. 1, 1975. pp. 27–49.

6. Downs A. An Economic Theory of Political Action in a Democracy // The Journal of Political Economy. Vol. 65, No. 2, 1957. pp. 135-150.

7. Ahn, H., Cheng, S., Cheong, O., Golin, M., van Oostrom, R.: Competitive facility location along a highway // In: Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Guilin, China, 2001. pp. 237–246.

8. Cheong, O., Har-Peled, S., Linial, N., Matousek, J.: The one-round Voronoi game // Discrete and Computational Geometry. No. 31, 2004. pp. 125–138.

9. Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 520 p

10. Jackson M.O., Wolinsky A. A Strategic Model of Social and Economic Networks // Journal of Economic Theory. Vol. 71. No. 1, 1996. pp. 44 – 74.

11. Freeman, L. A Set of Measures of Centrality Based on Betweenness // Sociometry, Vol. 40. No. 1, 1977. pp. 35-41.