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. In this paper, we introduce a strategic
network-formation game based on the betweenness centrality. In this game, nodes
are selfish players, each of which has some budget to build connections. The goal
of each player is to fully utilize her budget to strategically build connections
so that her betweenness centrality is as large as possible. We refer to this game
as the bounded budget betweenness centrality game or the B3C game. We present
both theoretical and experimental results about this game. Theoretically, we show
that a general B3C game may not have any nontransient Nash equilibrium and it is
in fact NP-hard to determine whether nontransient Nash equilibria exist.
Experimentally, we studied the family of uniform B3C games, in which there is an
equal amount of information exchange between every pair of nodes, every
connection has the same construction cost and every node has enough budget to
build k connections. We have discovered several interesting Nash equilibria when
k = 2. Our experiments have also inspired us to establish some theoretical
results about uniform B3C games. For example, we show that, when k is a variable,
it is NP-hard to compute a best response of a node in uniform B^{3}C
games; we also prove that a family of symmetric graphs called Abelian Cayley
graphs cannot be Nash equilibria for k=2 when the graph is large enough, but
there is a unique nontransient Nash equilibrium when k=1. We conjecture, based on
our experiments, that every uniform B3C game has a Nash equilibrium, and more
strongly, has a Nash equilibrium that is Eulerian.