CONCURRENT INFLUENCE MAXIMIZATION IN SOCIAL GRAPH ON THE VORONOI GAME BASIS

Social networks by their nature are a environment for promoting ideas, goods, technology and innovations in a broad sense. The decision of an individual to accept or reject the promoted innovation depends to a significant extent on the decisions of his environment in the social network. In the case of competitive distribution of two or more mutually exclusive influences in the social network, the results in the form of subsets of the network participants who fell under each of the influences will largely depend on subsets of the participants who initiated these influences. The game-theoretic model of competitive distribution of influences assumes that each influence is controlled by the player who selects the corresponding subset of participants-initiators. It is shown that such a game is essentially a game of Voronoi, carried out in a complex structured space. Some properties of the rational strategy of the player making the last move are considered, as well as the possibility of developing such a strategy with the help of greedy algorithms. Competitive centrality metrics promising for use in greedy algorithms of formation of a subset of participants-initiators by the last player are proposed. It is shown that there is a pronounced interdependence between competitive centrality in proximity, competitive centrality in intermediacy (isolating centrality) and the resulting number of network participants who fell under the influence of the player making the last move.

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. Prepata F., Shamos М. Vichislitelnaya geometria: Vvedenie. ‒ M.: Mir, 1989. 478 p.

4. Torbenko A.M. Modeli lineinogo goroda: obzor I tipologia // Journal Novoi economicheskoi associacii. No. 1 (25), 2015. p. 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.