Vitality Indices are Equivalent to Induced Game-Theoretic Centralities

1 Introduction

Centrality measures, methods that identify the most important nodes in a network, are one of the most widely used tools of network analysis. Apart from the always popular degree, closeness, betweenness and eigenvector centralities introduced a few decades ago, more than a hundred other methods have been proposed in the literature. Given this, it is becoming more and more complicated to determine which measure should be used in a specific application at hand. The high-level goal of this paper is to deepen the understanding of centrality measures which is essential to make an informed choice.

Centrality measures are based on various ideas and factors taken into account in nodes' evaluation. Distance-based centralities, such as closeness centrality, assess the importance of a node by looking at the distance to other nodes in a graph. Medial centralities, such as betweenness centrality, look how often a node is an intermediary in the network. In turn, feedback centralities, such as eigenvector centrality, define the importance of a node recursively as a function of the importance of its neighbors. Apart of these three classes, Brandes and Erlebach [2005] in their book characterize also vitality indices, random-walk based centralities and current-flow centralities.

In this paper, we focus on vitality indices. Centrality measures from this class look at the impact the removal of the node has on the quality of the network. More specifically, a centrality measure is a vitality index if there exists some invariant function that assesses the quality of a network such that the centrality of a node equals the difference between the value of a graph with and without the node. In result, vitality indices are a good tool to identify elements whose removal would damage the network the most. This is, for example, the case in covert network analysis where the focus is typically on the key leaders to be eliminated from the network [Everton, 2009; Ressler, 2006]. As written by Everett and Borgatti [2010], the idea behind vitality indices "has been in use-knowingly or not-for several decades".

While vitality indices form a natural class of centralities, its theoretical analysis is lacking. In this paper, we lay down the theoretical foundations of vitality indices and study their relationship to other classes of centralities.

Our first result is the axiomatic characterization of vitality indices. Specifically, we show that a centrality measure is a vitality index if and only if it satisfies an axiom called Balanced Contributions. This axiom states that the impact of one node on the centrality of the second node is the same as the impact of the second node on the centrality of the first one.

Balanced Contributions was originally proposed by Myerson [1980] in coalitional game theory literature. By exploring the link between game theory literature and centrality analysis, we get that vitality indices are equivalent to a natural subclass of game-theoretic centralities: induced game-theoretic centralities based on the Shapley value. This result sheds a new light on the vitality indices and provides a new approach to defining invariant functions.

Furthermore, we study the connection between vitality indices and other classes of centrality measures. Our axiomatic characterization allows us to easily determine which known centrality measures are vitality indices (note that, in general, the answer "no" requires proving that there exist no invariant function that results in this specific measure). For distancebased centralities we show that only degree centrality (up to a scalar modification) is a vitality index. Furthermore, we show that out of the most important medial and feedback centralities only flow betweenness centrality [Freeman et al., 1991] is a vitality index. Our results show that vitality indices, while they coincide with game-theoretic centralities, form an almost independent class of centrality measures.

Our work belongs to a line of research that focus on the axiomatic approach to centrality analysis [Boldi and Vigna, 2014; Bloch et al., 2016]. So far, however, vitality indices have not been analyzed (see Related Work for details).

2 Preliminaries

In this paper, we consider undirected, unweighted simple graphs. However, we note that the main results, including Theorems 3 and 5, easily translate to directed and weighted graphs.

A graph is a pair G = (V,E) where V is the set of nodes and E is the set of unordered pairs of nodes called edges. The set of all possible graphs will be denoted by G.

An edge {u, v} is said to be incident to u and v. The set of all edges incident to v in G is denoted by Γv(G). Two nodes u, v are called adjacent if they are connected by an edge, i.e., if {u, v} ∈ E. If node u is adjacent to node v, then it is called a neighbor of v. The set of neighbors of node v is denoted by Nv(G). A node is isolated if it has no neighbors.

For a set of nodes S ⊆ V , a subgraph induced by S, denoted by G[S], is a graph over set S that contains all edges from G that connect nodes from S. Formally: G[S] = (S, {{u, v} ∈ E : u, v ∈ S}).

A path is a sequence of nodes p = (v0, . . . , vk) such that every two consecutive nodes are adjacent. If vi = u for some i ∈ {0, . . . , k}, then we write that u ∈ p which means that path p goes through node u. The length of a path is the number of edges that it goes through, i.e., the length of the sequence of nodes minus one. The set of shortest paths between u and v in G is denoted by Πu,v(G).

The distance between two nodes is the length of a shortest path that starts in one node and ends in the other node. For two nodes u, v, we denote the distance between them in graph G by distu,v(G). We assume that distv,v(G) = 0 for every v ∈ V and distu,v(G) = ∞ if there is no path between u and v in G.

A graph is connected if there exists a path between any two nodes. If not, the graph is disconnected and consists of several connected parts, called (connected) components. Formally, a component of a graph is a set of nodes S that contains all nodes adjacent to nodes from S. The set of all components of graph G is denoted by K(G).

For two nodes, u, v, the flow from u to v in a graph is the maximal number of edge-disjoint paths between u and v. We denote it by flowu,v(G). Intuitively, the flow is the number of units (e.g., of information) that can be transferred from u to v under the assumption that each edge can transfer only one unit. If the graph is connected, then clearly flowu,v(G) ≥ 1 for every u, v ∈ V . For notational convenience, we assume that flowu,v(G) = 0 if u ̸∈ V or v ̸∈ V . The total flow in graph G, denoted by flow(G), is the sum of flows between any pair of nodes in a graph: flow(G) = ∑u,v∈V flowu,v(G).

For a node or an edge x we will denote by G-x the graph obtained from G by removing x. We will also use the Iverson bracket: [γ] = 1 if statement γ is true and [γ] = 0, otherwise.

2.1 CentralityMeasures

A centrality measure F is a function that for every graph G = (V,E) and for its every node v ∈ V assigns a real value, denoted by Fv(G). This value represents the importance of a node in a graph, referred to as the centrality of the node. We denote by FΣ(G) the sum of centralities of all nodes in graph G. Also, for notational convenience, we will assume that Fv(G) = 0 if v ̸∈ V .

The most famous centrality measures are as follows:

Degree centrality [Freeman, 1977] assesses a node by the number of its incident edges: Dv(G) = |{u ∈ V : {u, v} ∈ E}|.

Closeness centrality [Bavelas, 1950] evaluates how central a node is by looking at the sum of distances to all other nodes in a graph: Cv(G) = 1/ ∑u∈V distu,v(G). Closeness centrality is defined only for connected graphs.

Betweenness centrality [Freeman, 1977] evaluates the role of a node as an intermediary by looking how often it is on the shortest paths between other nodes: Bv(G) = ∑u,w∈V \{v} |{p ∈ Πu,w(G) : v ∈ p}|/|Πu,w(G)|. Here, we assume that pairs of nodes u,w for which Πu,w(G) = ∅ are not taken into account.

2.2 Vitality Indices

In this paper, we concentrate on vitality indices:

Definition 1. A centrality measure is a vitality index if there exists an invariant function f : G → R such that for every G = (V, E), v ∈ V :

We assume that f(∅, ∅) = 0.

An invariant function can be any method that assesses the quality of the network. It may be the Wiener index, i.e., the sum of distances between all pairs of nodes in a graph, or simply the number of edges in a graph. In such a case, we will obtain the degree centrality: if we take f(V,E) = |E|, then f(G) -f(G-v) = Dv(G). Hence, degree centrality is a vitality index.

Another important vitality index is an alternative to betweenness centrality based on a notion of flow in a graph.

Flow betweenness centrality [Freeman et al., 1991]

determines the role of a node as an intermediary by the amount of flow the node is responsible for: FBv(G) = flow(G) - flow(G - v).

See Figure 1 for an illustration. We discuss an alternative definition of flow betweenness centrality in Section 6.

3 Axiomatic Characterization

In this section, we provide a characterization of the vitality indices.

We begin by introducing the notion of a contribution of one node to the centrality of another node. The contribution of node u to the centrality of node v measured with F in graph G, denoted by ∆Fu,v (G), is defined as follows:

As we can see, for every two nodes u, v the contribution of u to the centrality of v is equal to the contribution of v to the centrality of u. This property of a centrality is called Balanced Contributions [Myerson, 1980].

Balanced Contributions: For every graph G =

(V, E) and two nodes u, v ∈ V : 1

See Figure 2 for an illustration. Balanced Contributions was originally proposed as a fairness and stability condition of a payoff division in coalitional games. We will introduce coalitional games in the next section. In a nutshell, if the centrality is interpreted as a payment or an award of a node, then Balanced Contributions states that every two nodes have the same negotiating power by posing the same threat against each other.

It is easy to verify that every vitality index satisfies Balanced Contributions. Let F be a vitality index based on invariant function f and take an arbitrary graph G = (V,E) and nodes u, v ∈ V . We have:

Since both expressions on the right-hand side are equal, this implies that the expressions on the left-hand side are also equal. Hence, Balanced Contributions is satisfied.

1 We note that Balanced Contributions appears in the literature also in a weaker version in which only incident edges of a node are removed, but not the node itself: Fu(G) -Fu(G- Γv(G)) = Fv(G) - Fv(G - Γu(G)) [Skibski et al., 2018; Sosnowska and Skibski, 2017].

Our main result, however, is stronger: in what follows we will prove that a centrality measure satisfies Balanced Contributions if and only if it is a vitality index. In other words, not only vitality indices satisfy Balanced Contributions but if a centrality measure satisfies Balanced Contributions, then it must be a vitality index.

To this end, we begin with the following lemma.

Lemma 1. If F satisfies Balanced Contributions, then for every graph G = (V, E) and node v ∈ V it holds:

Lemma 1 provides a formula for every centrality that satisfies Balanced Contributions. However, to show that every centrality measure that satisfies Balanced Contributions is a vitality index we need to find an invariant function f : G → R. The following lemma specifies this function.

Lemma 2. If F satisfies Balanced Contributions, then for a function f : G → R defined as follows:

we have Fv(G) = f(G) - f(G - v) for every graph G = (V, E) and node v ∈ V .

Lemma 2 implies the characterization of vitality indices.

Theorem 3. A centrality is a vitality index if and only if it satisfies Balanced Contributions.

Theorem 3 can easily be proved using Lemma 2. We note, however, it is also possible to prove it indirectly using results of Myerson [1980] and Hart and Mas-Colell [1989] from the coalitional game theory literature.

Balanced Contributions is a strong property. In particular, it is easy to verify that it implies Fairness that states that removing an edge from the graph decreases the centrality of both its endpoints equally [Myerson, 1977]. Both properties are desirable in some settings, but may not be intuitive in others. For example, Balanced Contributions and Fairness have been argued to be a reasonable requirement when nodes are assessed by their role in keeping the network connected [Skibski et al., 2018]. However, in social networks, a link between two people may be more profitable for the person with the lower social standing. Theorem 3 implies that if Balanced Contributions does not fit a specific application, then vitality indices do not fit this application either.

4 Game-Theoretic Perspective

Balanced Contributions was originally proposed by Myerson [1980] in a setting of coalitional games. In this section, we introduce coalitional games which gives an additional insight on vitality indices and explain the origins of formulas from Lemmas 1 and 2.

A coalitional game is a pair (N, f) where N is the set of players and f : 2N → R is a characteristic function that assigns a real value to every subset of players (with f(∅) = 0). In coalitional games, a subset of players is called a coalition. The set of all possible games will be denoted by CG.

Given this, a value of a game is a function ϕ that for each player i ∈ N in a game (N, f) assigns a payoff, denoted by ϕi(N, f). This payoff is interpreted as the fair or expected share of the value of the grand coalition of all players: f(N). Arguably, the most popular such value is the Shapley value (SV) defined as follows [Shapley, 1953]:

The value f(S ∪{i})-f(S) is called the marginal contribution of player i to coalition S. This formula has the following interpretation: Assume that players form a grand coalition by entering one by one in a random order. As a player enters, she receives a payoff that equals its marginal contribution to the group of players that she joins. Now, the Shapley value is the expected payoff of a player over all possible orders.

Shapley [1953] proved that the Shapley value is the unique value that satisfies four axioms: Efficiency, Symmetry, Additivity and Null-Player. However, many more axiomatizations have been proposed in the literature. In particular, Myerson [1980] proved that the Shapley value is the only value that satisfies Efficiency and Balanced Contributions. Furthermore, Hart and Mas-Colell [1989] showed that the Shapley value is the only value that satisfies Efficiency and Potential: an axiom that states the value of a player is a difference in the assessment of a game with and without a player for some assessment function. Our results from Section 3 can be considered a translation of the equivalence of both axiomatizations for the setting of centrality measures.

By comparing Equations (3) and (1) we see that the formula from Lemma 1 presents the Shapley value of some game. Formula from Lemma 2 is the potential of the same game. Using Theorem 3 we get the following observation.

Corollary 4. A vitality index F in graph G = (V,E) is the Shapley value of a game (V, f) defined as f(S) = FΣ(G[S]) for every S ⊆ N.

Corollary 4 shows a different view on vitality indices: if we fix not an invariant function, but the desirable sum of centralities, then the vitality index is equal to the Shapley value of the resulting game, i.e., a fair division of this sum between nodes. This is the idea behind game-theoretic centralities: measures based on coalitional game theory. A game-theoretic centrality first assesses every subset of nodes in a graph. Such an assessment forms a coalition game in which the role of each player/node is evaluated using the value of the game.

Formally, a game-theoretic centrality is a composition of two functions F = ϕ ◦ r, where ϕ is a value of the game that the centrality is based on and r : G → CG is a representation function that maps an arbitrary graph G = (V,E) to a coalition game (V, rG); hence, Fv(G) = (ϕ ◦ r)v(G) = ϕv(V, rG). If ϕ is the Shapley value, then we say that the centrality is Shapley-value based (SV-based). Note that this definition does not impose any restrictions on r. In particular, rG(S) may depend not only on G[S]. Examples of gametheoretic centralities include:

Connectivity centrality [Amer and Giménez, 2004]:

Attachment centrality [Skibski et al., 2019]:

Michalak et al.'s centrality [Michalak et al., 2013]:

Corollary 4 implies that every vitality index is a gametheoretic centrality. The opposite, however, it not true: not every game-theoretic centrality is a vitality index. In what follows, we indentify a subclass of all game-theoretic centralities which is equivalent to vitality indices. Specifically, a game-theoretic centrality is called induced if rG(S) depends solely on G[S] for every graph G = (V,E) and set S ⊆ V [Skibski et al., 2018]. Now, the following theorem shows that there is a one-to-one correspondence between vitality indices and SV-based induced game-theoretic centralities.

Theorem 5. A centrality measure is a vitality index if and only if it is an SV-based induced game-theoretic centrality.

Connectivity and attachment centralities are induced, hence they are also vitality indices. Michalak et al.'s centrality is not induced and it is not a vitality index.

Theorem 5 shows equivalence between vitality indices and SV-based induced game-theoretic centralities. Both these classes evaluate a node by looking at its contribution to some function (invariant function or the sum of centralities) that assesses the quality of a graph. However, there is a significant difference in both approaches: vitality indices look only at the marginal contribution to the whole graph, while gametheoretic centralities consider marginal contributions to all induced subgraphs that contain the node in question. As a result, both functions (invariant function and the sum of centralities) have different roles and can be different.

In particular, Everett and Borgatti [2010] argued that an invariant function should be sufficiently sensitive to node removal-otherwise, the centrality will not be meaningful. For example, the clique number of a graph is not a good invariant function, as it may not change at all if there is more than one maximal cliques in a graph. The same can be said about simple functions that assess the connectivity of a graph such as f(G) = [G is connected] or f(G) = 2(|V | - |K(G)|). Both these invariant functions would identify cut-vertices and the second function would also highlight nodes which removal is more damaging to the network. However, if the graph is 2-connected, all nodes would have equal centralities. In contrary, such insensitive functions are a good candidate for the sum of centralities and are used by connectivity and attachment centralities. In such manner, the role of keeping the network connected is measured in a way that takes into account the contribution to all possible subgraphs.

Table 1 contains examples of invariant functions and the corresponding sum of centralities for several vitality indices.

5 Distance-Based Centralities

Distance-based centralities form a large and widely used class of centrality measures. These centralities try to assess how close the node is to the center of a graph. To this end, they use the distances to other nodes as the source of this information.

Formally, let distv(G) be the list of distances from v to other nodes in graph G sorted increasingly:

where (u1, . . . , u|V |-1) is the list of nodes from V \{v} such that distui (G) ≤ distuj (G) for every 1 ≤ i ≤ j < |V |. For example, for graph G from Figure 3 we have distv(G) = (1, 2, 2, 3). A centrality measure F is a distance-based centrality if there exists a function d such that

Out of standard centrality measures described in the preliminaries both degree and closeness centralities are distancebased. Apart from them, there is a number of other distancebased centralities proposed in the literature:

Decay centrality [Jackson, 2005]:

Harmonic centrality [Rochat, 2009]:

K-step reach centrality [Borgatti et al., 2013]:

Note that all of them are defined also for disconnected graphs assuming that 1/∞ = 0 and δ∞ = 0 for δ ∈ (0, 1).

In what follows, we show that among all distance-based centralities proposed in the literature only degree centrality is a vitality index. More precisely, if a distance-based centrality is a vitality index, then it is a linear function of degree centrality.

To this end, we begin by showing that the distance-based centrality of a node does not change if we remove all edges except for its incident edges.

Lemma 6. If a distance-based centrality F is a vitality index, then for every graph G = (V, E) and node v ∈ V :

Let us illustrate the proof on graph G from Figure 3. Let L1 = {w1} and L2 = {w2, w3} be sets of nodes at distance 1 and 2 from v, respectively. Now, let us construct two graphs G′ , G′′ based on G. The first graph, G′ , is obtained from G by adding a new node u connected to v and all nodes from L1 and L2. The second graph, G′′ , is obtained fromG′ by removing all edges between nodes from L1 and L2. In this way, all shortest paths between v and any other node go through u.

Both graphs were constructed in a way that distv(G′ ) = distv(G′′ ) and distu(G′ ) = distu(G′′ ). This implies that:

Consider graphs obtained from G′ and G′′ by removing node v. Since u is connected to all nodes from L1 and L2, distance from u to any node (other than v which is removed) is the same in graph G′ - v as in graph G′′ - v. Hence, we get that distu(G′ - v) = distu(G′′ - v) which implies Fu(G′ - v) = Fu(G′′ - v) and

We know that F is a vitality index, which from Theorem 3 means that it satisfies Balanced Contributions. By applying Balanced Contributions for both sides we get:

Since Fv(G′ ) = Fv(G′′ ) and G′ - u = G we get that

Fv(G) = Fv(G′′ - u). In graph G′′ - u node v is connected

only with nodes from L1 and these nodes are not connected

with nodes from L2. Hence, we see that distv(G′′ - u) =

distv(V, Γv(G)) which concludes the proof.

Lemma 6 implies that we can concentrate only on graphs in which all edges are incident to the studied node. By focusing on such graphs and using Balanced Contributions we prove the following result.

Lemma 7. If a distance-based centrality F is a vitality index, then there exists a constant a ∈ R such that:

Combining both lemmas we get the main theorem.

Theorem 8. A distance-based centrality F is a vitality index if and only if there exists a ∈ R and b1, b2, · · · ∈ R such that

for every graph G = (V, E) and v ∈ V . In particular, decay, harmonic and k-step reach centralities are not vitality indices.

As a centrality measure is a function from all possible graphs, b1, b2, . . . are (possibly different) constants that correspond to graphs with 1, 2, . . . nodes. We note that Everett and Borgatti [2010] already showed that closeness centrality is not a vitality index.

6 Medial &Feedback Centralities

The class of medial centralities consists of measures that assess the role of a node in connecting other nodes in a graph. As we will show out of popular centralities from this class only flow betweenness centrality is a vitality index. Since there is no consensus on the definition of medial centralities in the literature, we cannot provide a more general result as we did in the case of distance-based centralities.

The most popular medial centrality is betweenness centrality. There are two well-known alternatives: stress centrality and already introduced flow betweenness centrality. Below, we introduce and discuss its popular alternative definition more consistent with other medial centralities.

In what follows we show that betweenness and stress centralities as well as flow betweeness centrality (alt. definition) are not vitality indices. To this end, we will use graph G from Figure 2 which was designed specifically to serve as a counterexample in these proofs. In this graph, node u is on the shortest path between nodes v and w1, hence it gains from the fact that v is in the graph. In turn, node v is not an intermediary between any nodes as both its neighbors are directly connected, so its benefit from node u is lower.

Proposition 9. Betweenness, stress and flow betweenness (alt. definition) centralities are not vitality indices.

The last class of centralities that we discuss is the class of feedback centralities. Such centrality measures assess the importance of a node based on the number and the importance of its neighbors. This method usually leads to a system of recursive equations. The simplest feedback centrality is degree centrality. Other prominent examples are:

Eigenvector centrality [Bonacich, 1972]: Ev(G) = 1/λ · ∑{u,v}∈E Eu(G), where λ is the largest eigenvalue of an adjacency matrix. This equation does not imply a unique solution, so we additionally assume that ∑v∈V Ev(G) = 1.

As it turns out, these two centralities are not vitality indices. Intuitively, we see from the definitions that a more important node has a higher impact on the centralities of other nodes. However, removing a node may affect the whole structure of a graph, so a more precise argument is required.

To show that eigenvector and PageRank centralities are not vitality indices we will consider a graph from Figure 4. In this graph, node v is the most central one, as it is connected to all nodes except for u. Removing node u from the graph does not affect the position of v much. In turn, node u is the least central, but if we remove v, then all nodes, including u, will become equally important.

Proposition 10. Eigenvector and PageRank centralities are not vitality indices.

7 RelatedWork

The class of vitality indices has been formally defined by Brandes and Erlebach [2005]. The authors analyzed how closeness centrality and stress centrality can be redefined in order to fit the definition of vitality indices. Everett and Borgatti [2010] analyzed vitality indices in which the invariant function is the sum of centralities of all nodes in a graph for popular centralities and studied the decomposition of such centralities into endogenous and exogenous parts.

Our work belongs to a line of research that focus on the axiomatic approach to centrality analysis [Boldi and Vigna, 2014; Bloch et al., 2016; Skibski et al., 2018]. However, so far, vitality indices have not been analyzed. Here, a lot of work is focused on feedback centralities [Altman and Tennenholtz, 2005; W˛ as and Skibski, 2020]. Also, axiomatic characterizations of the class of distance-based centralities were proposed [Garg, 2009; Skibski and Sosnowska, 2018]. There is also an increasing number of papers on gametheoretic centralities [Skibski et al., 2019; Istrate et al., 2020; Becker et al., 2020]. Our Theorem 5 provides also an axiomatic characterization of SV-based induced game-theoretic centralities. Skibski et al. [2018] provided similar axiomatizations for game-theoretic centralities, but focused on axioms that do not change the set of nodes. In particular, Balanced Contributions considered there is weaker than our definition as it considers removing all edges incident to a node, but not the node itself.

8 Conclusions

In this paper, we provided an axiomatic characterization of vitality indices. Building upon this, we explored a connection with coalitional game theory and showed equivalence between vitality indices and Shapley-value based induced game-theoretic centralities. We also proved that out of the most popular centrality measures only degree and flow betweenness centralities are vitality indices.

In our future work, we plan to further explore the class of vitality indices and link to coalitional game theory. In particular, it would be interesting to analyze what restrictions on the invariant function are imposed by the desirable properties of the resulting vitality index. Another idea is testing how effective are vitality indices in applications in which centralities are used to identify nodes which removal damages the network the most, e.g., in the centrality attack literature.

Acknowledgements

This work was supported by the Polish National Science Centre grant 2018/31/B/ST6/03201.