CONCURRENT INFLUENCE MAXIMIZATION IN SOCIAL GRAPH ON THE VORONOI GAME BASIS

UDC 519.833
DOI:10.26102/2310-6018/2019.26.3.009

B.A. Toropov


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.

Keywords: social network, influence spread, concurrent influence, Voronoi game, graph, centrality.

Full text:
Toropov_3_19_1.pdf