Bounded budget betweenness centrality game for strategic network formations (Q655424)

In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest path exchanges. This paper studies a strategic network formation game in which nodes build connections subject to a budget constraint in order to maximize their betweenness in the network. The betweenness definition is generalized to only count shortest paths with a length limit \(\ell \) in betweenness calculation. This game is referred to as the bounded budget betweenness centrality game and denoted by \(\ell - \text B^{3}\)C game, where \(\ell \) is the path length constraint parameter. Complexity and constructive existence results are provided about Nash equilibria of this game. For the nonuniform version of the game where node budgets, link costs, and pairwise communication weights may vary, it is shown that Nash equilibria may not exist and that it is NP-hard to decide whether Nash equilibria exist. For the uniform version of the game where link costs and pairwise communication weights are one and each node can build \(k\) links, two families of Nash equilibria are constructed based on shift graphs, and the properties of such Nash equilibria are studied. Complexity of computing best responses is also studied and it is shown that the task is polynomial for uniform \(2- B^3C\) games and NP-hard for other games.