Group Vitality Indices: Axioms and Algorithms

1 Introduction

The literature on centrality measures-a key tool in social network analysis-predominantly concentrates on individual nodes [Brandes and Erlebach, 2005]. However, in practice, centrality is often used to select a group of nodes that collectively serve a common goal [Kumar et al., 2019; Wan et al., 2021; Suri and Narahari, 2008]. Selecting nodes independently, one by one, ignores the synergies and interdependencies among them and leads to suboptimal solutions.

Group centrality measures address this limitation by providing a more holistic assessment of groups of elements [Camur and Vogiatzis, 2024; Kolaczyk et al., 2009]. However, extending node centralities to groups is a nontrivial challenge. For many centrality measures, it is unclear what the appropriate group-level generalization should be. Two simple ideas are (a) to sum the centralities of individual nodes, and (b) to merge the group into a single node and compute its centrality in the resulting graph. Both approaches have clear shortcomings: the sum approach ignores the co-dependencies among nodes, while the merge approach significantly alters the graph's structure. See Figure 1 for an example. For this reason, alternative extensions have been proposed for many centrality measures. For example, for distance-based centralities-such as closeness centrality-several variants of the group definitions have been proposed based on the distance from the group to the closest, farthest, or average node [Everett and Borgatti, 1999].

Vitality indices [Brandes and Erlebach, 2005], also referred to as induced centrality measures [Everett and Borgatti, 2010], form an important class of centrality measures. They are based on a natural idea: assessing a node's importance by evaluating the impact of its removal on the network. As a result, they are well-suited to identifying the elements whose removal causes the greatest disruption to the network. This is particularly relevant in robustness analysis of computer networks or the WWW [Albert et al., 2000] (e.g., designing fault-tolerant architectures, protecting vital nodes against cyber-attacks), but also transportation networks [Rosato et al., 2008] (e.g., designing redundant infrastructure) and social networks [Ressler, 2006] (e.g., epidemic control, target prioritization in terrorist networks). Several classical centralities-such as Degree Centrality and Flow Betweenness-fall within this category. Moreover, this class includes many so-called game-theoretic centrality measures, which are defined via coalitional games and often rely on the Shapley value [Lindelauf et al., 2013; Skibski et al., 2018].

Against this background, in this paper, we conduct the very first comprehensive analysis of group vitality indices and address several fundamental questions:

• Existence and Uniqueness: We show that every vitality index admits a unique extension to groups. Specifically, we define a class of group vitality indices and prove that each vitality index corresponds to a unique group variant within this class. To the best of our knowledge, this is

the first general existence and uniqueness result for any broad class of centrality measures.

• Axiomatic Characterization: We provide two axiomatic characterizations of group vitality indices, based on Group Balanced Contribution and Vertex Exclusion. Our results also reveal a direct connection to a group version of the Shapley value. In addition, we axiomatically characterize two specific measures-Group Degree and Group Attachment Centrality-which satisfy dual normalization conditions. The axiomatic approach is fundamental in centrality analysis, as it highlights similarities and differences among the many measures proposed in the literature.
• Computational Complexity: We show that, under mild assumptions on the underlying vitality index, finding a group that maximizes centrality is NP-hard. However, computing the centrality of a given group is no harder than computing individual node centralities; more precisely, it is polynomial-time computable whenever the node-level vitality index is polynomial-time computable. We also develop an approximation algorithm for Group Attachment Centrality based on a novel sampling method for the group Shapley value. This algorithm also supports efficient computation of nodelevel Attachment Centrality.

Related Work. Our theoretical results contribute to an active line of research on the axiomatic foundations of centrality measures. This line was initiated by Sabidussi [1966] and Nieminen [1973] over 50 years ago, and is currently being studied mostly in the AI, electronic commerce, and social choice communities.

Notably, Altman and Tennenholtz [2005] proposed an axiomatization of the Seeley Index, also known as the simplified PageRank, and W˛ as and Skibski [2023] developed an axiomatic characterization of PageRank in its full form. In turn, Garg [2009] studied distance-based centralities, and W˛ as et al. [2019] focused on random-walk-based ones. More recently, in a more general approach, Bloch et al. [2023] developed a joint axiomatic framework for centrality measures. Also, Boldi and Vigna [2014] analyzed the satisfiability of several axioms and concluded that Harmonic Centrality is the only popular centrality measure that satisfies all of them.

Most closely related are works that analyze vitality indices [Everett and Borgatti, 2010; Skibski, 2021] and gametheoretic centralities [Michalak et al., 2013; Skibski et al., 2018]. However, none of these studies focus on group centralities. In fact, our work is the first to address the axiomatic characterization of group centrality measures. We will discuss the most relevant results on vitality indices in the Preliminaries section.

Our algorithmic results are loosely related to research on the Shapley value in graph settings [Greco et al., 2020].

2 Preliminaries

A graph is a pair G = (V,E) such that V is the set of nodes and E is the set of edges, i.e., unordered pairs of nodes {u, v} ⊆ V . The set of all possible graphs is denoted by G.

The degree of a node is the number of its incident edges: deg(v) = |{e ∈ E : v ∈ e}|. A node v is isolated if deg(v) = 0. We refer to nodes with degree one as leaf nodes.

A graph is connected if there exists a path between any two nodes. For a given set of nodes S ⊆ V , the subgraph induced by S is the graph G[S] = (S, E[S]), where E[S] is the set of all edges from E between nodes in S. The subgraphs of G induced by the nodes V \{v} and V \S are denoted by G-v and G-S, respectively.

A maximal subset of nodes that induces a connected subgraph is called a component. The set of all components of a graph G is denoted by K(G).

A (node) centrality measure F is a function that, given a graph G = (V,E) and a node v ∈ V , returns a real value Fv(G) that corresponds to the node's importance-the higher the value, the more important the node. A group centrality measure F ′ assesses groups of nodes: given a graph G = (V,E) and a group of nodes S ⊆ V , it returns a real value FS(G). We assume F∅(G) = 0.

A group centrality measure F ′ extends a node centrality F if F ′{v} (G) = Fv(G) for every graph G = (V,E) and node v ∈ V . Two simple extensions of a node centrality to groups

• are:· sum approach: F ′S (G) = ∑v∈S Fv(G).
• merge approach: F ′S (G) = F[S](G[S]), where graph G[S] is obtained from G by merging nodes from S into one node: [S].

Clearly, the sum approach does not provide any additional information. In turn, the merge approach is not always desirable, as it modifies the whole structure of the graph.

2.1 Coalitional Games

Some of our results connect centrality analysis with cooperative game theory [Chalkiadakis et al., 2011]. A coalitional game is a pair (N, g) where N is the set of players and g : 2N → R is a characteristic function that evaluates each coalition, i.e., a group of players (with the assumption that g(∅) = 0). A classic measure of the importance of individual players in a game is the Shapley value: in a game (N, g), the importance of a player i ∈ N is given by:

This expression defines the value of a player as a weighted average of their marginal contributions across all possible coalitions. The importance of the Shapley value stems from its axiomatic characterization. Specifically, Shapley [1953] proved that it is the unique method that satisfies several desirable axioms: Efficiency, Symmetry, Additivity, and Null-player. More recently, the Shapley value has emerged as a key tool in explainable artificial intelligence, providing principled methods for attributing predictions to input features [Lundberg and Lee, 2017; Fryer et al., 2021].

The Shapley value has been also extended to groups. One of the classic method was proposed by Marichal et al. [2007]:

This method, roughly speaking, corresponds to the merge approach in the graph context: it is the payoff of a player obtained by merging coalition S into one player. Alternative definition was recently proposed by [K˛epczy´nski and Skibski, 2026] under the name Union Shapley value:

Clearly, for both definitions, if S = {i}, the group Shapley value coincides with the single-player definition. Other group definitions include the Interaction Index [Grabisch and Roubens, 1999].

2.2 Vitality Indices

A centrality measure F is a vitality index if there exists an invariant function f : G → R such that Fv(G) = f(G) - f(G- v). Two classic vitality indices are:

Degree Centrality. Dv(G) = deg(v) is a vitality index with the invariant function f(G) = |E| for every G = (V, E).

Flow Betweenness Centrality [Freeman et al., 1991].

Another group of vitality indices is formed by gametheoretic centralities. These are measures defined via coalitional games, almost uniformly using the Shapley value. The idea is to define a coalitional game based on a graph-where nodes are players-and then compute the Shapley value to obtain the importance of each node in the game, and thus in the graph. Examples include:

Connectivity Centrality [Amer and Giménez, 2004].

Both of these game-theoretic centralities are induced, meaning that the value of a coalition T in the game depends solely on the subgraph G[T]. Skibski [2021] proved that vitality indices are equivalent to induced game-theoretic centralities.

Formally, every vitality index F for every graph G = (V,E) and v ∈ V satisfies

Hence, it is an induced game-theoretic centrality. Conversely, for every induced game-theoretic centrality, there exists a function f such that Fv(G) = f(G) - f(G - v), which implies that it is a vitality index.

This result follows from the axiomatic characterization of vitality indices [Skibski, 2021]. Specifically, a centrality measure is a vitality index if and only if it satisfies Balanced Contribution-a property defined by Myerson [1980] in game-theoretic literature:

Balanced Contributions. For every graph G = (V,E) and two nodes u, v ∈ V , it holds that:

In particular, as a result of the Shapley value's axiomatic characterization, every vitality index satisfies the axiom of Fairness. This property in the network context means that adding an edge increases the centrality of both its endpoints equally.

3 Group Vitality Indices

In this section, we introduce the group variant of vitality indices and present several important results concerning it.

Group vitality indices have a natural definition. Let F be an arbitrary group centrality measure. We say it is a group vitality index if there exists an invariant function f : G → R such that FS(G) = f (G) - f (G - S).

We begin with a simple but important observation. If F is a (node) vitality index with an invariant function f, then a group vitality index F ′ with the same function f naturally extends F. Clearly, this is not the only group centrality that extends F , as centralities obtained through the sum and merge approach also extend it. However, as we now show, it is the only group vitality index that extends F .

Theorem 1. For a vitality index, there exists exactly one group vitality index that extends it.

Proof. Fix a vitality indexF. Assume there are two centrality indices F ′ and F ′′ with invariant functions f ′ and f ′′ , respectively, that extend F. Let G be the graph with the smallest number of vertices where F ′ and F ′′ differ, and let S be the group on which they differ. Group S has at least two nodes, as both centralities agree on single nodes and assign zero centrality to the empty group. Take v ∈ S. We get that:

Similarly, F ′′ S (G) = F ′′ {v} (G) + F ′′ S\{v} (G - v). However, graph G- v has fewer vertices than G, which implies F ′S\{v} (G - v) = F ′′ S\{v} (G - v), which combined with the fact that F ′{v} (G) = F ′′ {v} (G) leads to a contradiction.

To give an example, consider Degree Centrality. We have multiple options to extend it to groups:

• using the sum approach we can sum degrees of all its members: FS(G) = ∑v∈S deg(v); in this way, we count all edges between S and V \ S once, and edges between nodes from S twice;
• using the merge approach, we can count the neighbours of the group S, ignoring elements from S; thus, we do not count edges between members of S and count each edge to a node v from V \ S only once.

In turn, Theorem 1 states that if we look at Degree Centrality from the perspective of a vitality index, then there is only one group vitality index that extends it.

Definition 1. Group (Vitality) Degree Centrality is defined as

Thus, we count each edge incident to nodes from S exactly once. See Figure 2 for an illustration.

Consider now another vitality index, Attachment Centrality, defined as the Shapley value of the cooperative game gA(T) = 2(|T| - |K(G[T])|). It can be extended to groups using both standard approaches, as well as by replacing the Shapley value with one of the existing group variants of the Shapley value. However, Theorem 1 indicates that there is only one extension that qualifies as a group vitality index. To identify it, we rely on the invariant function.

Definition 2. Group Attachment Centrality is defined as

where f A(G) is the invariant function of (node-level) Attachment Centrality, defined for every graph G = (V, E) as

By reformulation, f A can be interpreted as a network-level metric that captures how well connected the graph is:

Hence, this function computes an average over all subgraph sizes. For each size s, it averages over all induced subgraphs of size s, and for each such subgraph evaluates a quantity that depends on the number of connected components relative to its size. This value ranges from 0, when all nodes in the subgraph are isolated, to 2|V |(s - 1)/s, when the subgraph is fully connected.

To axiomatically characterize the class of group vitality indices, we introduce two axioms. The first, Group Balanced Contribution, is a natural extension of Balanced Contributions [Myerson, 1980] to groups. It states that the removal of a group S affects a group T in the same way that the removal of T affects S. This axiom can be interpreted as a stability condition, familiar from the Shapley value axiomatization: if the group assessment represents a payoff or award, the "threat" posed by one group on the other is balanced by the reciprocal threat. Moreover, it implies Fairness, which requires that adding an edge affects both of its endpoints in the same way.

Group Balanced Contributions. For every graph G = (V, E) and two groups S, T ⊆ V , it holds that

The second axiom, Vertex Exclusion, is novel and states that the marginal contribution of a node to a group in a graph is equal to its centrality in that graph. This axiom provides a natural approach for extending node-level measures to groups, distinct from the standard sum and merge approaches: the value of a group can be computed by selecting an arbitrary node, adding its centrality in the current graph, and then removing it; the process is repeated with the remaining nodes until the group is exhausted. Interestingly, while this procedure may generally depend on the order of node selection, it is order-independent in the case of vitality indices.

Vertex Exclusion. For every graph G = (V, E), group S ⊆ V , and v ∈ S, it holds that

The following theorem states that each of these axioms uniquely characterizes the whole class.

Theorem 2. Given a group centrality measure F , the following three statements are equivalent:

• (a) F is a group vitality index;
• (b) F satisfies Vertex Exclusion;
• (c) F satisfies Group Balanced Contributions.

Proof (sketch). It is immediate that (a) ⇒ (b). To prove (b) ⇒ (c), observe that

which implies

by applying Vertex Exclusion |T| times. By symmetry of S and T , we obtain Group Balanced Contribution.

Finally, the proof of (c) ⇒ (a) relies on the Shapley valuelike form of measures that satisfy Balanced Contributions.

Lemma 1. If a group vitality index F satisfies Group Balanced Contributions, then it satisfies:

for every graph G = (V,E) and S ⊆ V , where g∗ (T) = ∑v∈T Fv(G[T ]) for every T ⊆ V .

This concludes the proof. 1

Lemma 1 reveals a connection to coalitional games. Specifically, out of several extensions of the Shapley value to groups, only one-the Union Shapley value [K˛epczy´nski and Skibski, 2026]-adheres to the definition of group vitality indices. From Lemma 1, we obtain the following result, analogous to the result for (node) vitality indices.

Corollary 1. For every group vitality index F, every graph G = (V, E) and coalition S ⊆ V it holds:

Proof. Immediate from Theorem 2 and Lemma 1.

4 Group Degree and Attachment: Two Normalized Measures

In this section, we will provide axiomatizations of two dual group vitality indices. We begin by presenting two natural axioms that concern nodes with at most one edge.

Isolated Node. For every graph G = (V, E) and an isolated node v ∈ V it holds Fv(G) = 0.

Leaf Node. For every graphs G = (V,E), G′ = (V ′ ,E′ ) and nodes v ∈ V , v′ ∈ V ′ with deg(v) = 1 = deg(v′ ) it holds Fv(G) = Fv′ (G′ ).

If a node is isolated, it clearly has zero importance; the Isolated Node axiom states its centrality is zero which is consistent with the vast majority of centrality measures. Furthermore, if a node has only one edge, then it has a minimal impact on the structure of the network. The Leaf Node axiom states such nodes always have the same centrality. For example, for Betweenness Centrality we have c = 0, and for Degree Centrality: c = 1. However, for some measures, e.g., for PageRank, the centrality of such nodes depend on the position in the network of their neighbours.

Now, consider an arbitrary connected component of a graph. What should be the sum of centralities of its elements? One approach would be to say the sum of centralities in each component should be normalized so it does depend only on the size of the component. In turn, an alternative approach would be to say the sum of centralities in each component should depend not on the number of nodes, but on the number of edges. These two ideas lead to the following axioms.

Node-Normalization. There exists a function h : N → R such that for every graph G = (V,E) and every connected component C ∈ K(G) it holds: ∑v∈C Fv(G) = h(|C|).

Edge-Normalization. There exists a function h : N → R such that for every graph G = (V,E) and every connected component C ∈ K(G) it holds: ∑v∈C Fv(G) = h(|E[C]|).

1 The extended version of our paper with the full proofs can be found at https://arxiv.org/abs/2605.09791.

We will now show that for each type of normalization axiom there exists exactly one centrality measure (up to a scalar multiplication).

Theorem 3. A group vitality index satisfies Isolated Node, Leaf Node and Node-Normalization if and only if it is Group Attachment Centrality (up to a scalar multiplication).

Theorem 4. A group vitality index satisfies Isolated Node, Leaf Node and Edge-Normalization if and only if it is Group Degree Centrality (up to a scalar multiplication).

Proof (sketch). The proof is based on the following steps:

• First, it is shown that for every vitality index satisfying Isolated Node and Leaf Node it holds Fv(G⋆ ) = c · Dv(G⋆ ) for any star graph G⋆ = (V, E), node v ∈ V and some constant c ∈ R.
• Using Node- and Edge-Normalization, we get that the sum of centralities in every connected component is fixed and equal to the case of a star graphs.
• Now, Lemma 1 implies uniqueness of the measure (up to a scalar multiplication).

Example 1. Consider the graph in Figure 3 that represents the terrorist group responsible for the September 11 attacks [Krebs, 2002]. While the top three nodes according to Attachment Centrality are #14, #1, and #3, Group Attachment Centrality selects #11 and #14 as the best pair, with a score of 6.33. This is because removing both nodes detaches nodes #12 and #15 from the rest of the graph.

For Group Degree Centrality, the pair #3 and #11 is the unique group with a score of 7 + 6 = 13. This follows from the fact that node #3 is incident to both nodes #14 and #1. ⌟

It is known that on trees both Attachment Centrality and Degree Centrality coincides [Skibski et al., 2019]. We will use this fact in the following example.

Example 2. Consider the graph in Figure 4, obtained from Figure 1 by adding the edges {A,C} and {B,D}. Due to isomorphism, all standard centrality measures assign equal importance to nodes A, B, C, and D. Moreover, these nodes are more important than the others.

Now consider the problem of selecting two nodes. According to Group Degree Centrality (Equation (1)), a group's score is determined by the number of edges incident to it. Hence, the groups {A,C} and {D,E} achieve the highest score, since removing them decreases the total number of edges by six.

In contrast, according to Attachment Centrality, nodes AD each have a centrality value of 2.5, their immediate neighbors have centrality 2, and the leaf nodes have centrality 1. Group Attachment Centrality selects the nodes whose removal most significantly disconnects the network. If nodes {A,D} (or {B,C}) are removed, the graph decomposes into four separate paths. The centrality of this group equals 2.5 + 3.0 = 5.5 (here, we apply the Vertex Exclusion principle: after removing A, the centrality of D becomes 3).

By contrast, removing group {A,B} (or {C,D}) leaves one long path intact and creates two short paths. As a result, this group performs worse, with a total score of 2.5 + 2.0 = 4.5. ⌟

Our axiomatizations are the first ones of Group Attachment and Degree Centralities. They can be considered an extension of two existing joint axiomatizations of their node analogs [Skibski et al., 2019; Sosnowska and Skibski, 2017], but they are partially different. In particular, other axiomatizations made use of locality axioms (under the name Locality and Additivity) and axioms that limit the value of centrality (such as Normalization and Monotonicity/Star-Max). In turn, we depend on duality of our normalization condition (Node/Edge-Normalization axioms).

5 Computational Results

For group centrality measures, two algorithmic questions are natural. The first is to compute the centrality of a specific group. The second is to find a group-usually of a specific size-that maximizes the centrality. In this section, we present general results for both problems for the whole class of vitality indices, under minimal assumptions on the index itself.

Let F be an arbitrary vitality index. Fix a graph G = (V, E) and a group S ⊆ V . Using the Vertex Exclusion axiom again, we have that for every node v ∈ S, it holds:

This implies a simple |S|-step recursive procedure for computing the centrality of S, based on the centrality of individual nodes, for all vitality indices. This leads to the following statement.

Corollary 2. If a node vitality index F of a single node in a graph with n nodes can be computed in time p(n), then for a group vitality index F ′ that extends F, the centrality of any set of vertices S can be computed in time |S| · p(n).

Clearly, if computing a node vitality index is NP-hard, then computing the corresponding group vitality index is also NPhard.

To analyze the second problem, we require some mild additional assumptions. We assume that the invariant function is anonymous, i.e., it gives the same value for isomorphic graphs: if for two graphs G = (V,E) and G′ = (V ′ ,E′ ) there exists a bijection b : V → V ′ such that E′ = {{b(u), b(v)} : {u, v} ∈ E}, then f(G) = f(G′ ). Moreover, it is natural to assume that the graph assessment is minimized when there are no edges in the graph. We are not aware of any vitality index that violates these assumptions. As we now show, for every group vitality index that satisfies these assumptions, finding a group of a given size that maximizes the centrality is NP-hard.

Proposition 1. Let F be a group vitality index with an anonymous invariant function f that satisfies f((V,E)) > f((V, ∅)) whenever |E| > 0. Then finding a set S of size k that maximizes the centrality FS(G) is NP-hard.

Proof. We use a reduction from the k-VERTEX COVER problem. Let G be an arbitrary graph, and suppose we have an algorithm that finds a set S of size k that maximizes the centrality FS(G). Let S∗ be the returned set. If S∗ is a vertex cover of G, then the answer to the VERTEX COVER problem is "yes". If S∗ is not a vertex cover, then a vertex cover of size k does not exist, and the answer is "no".

Indeed, suppose a vertex cover S′ of size k exists. Then,

since G-S′ is a set of isolated vertices.

On the other hand, since S∗ is not a vertex cover, G-S∗ = (V \ S∗ ,E) has some edges, i.e., |E| > 0. Therefore,

From our assumption, f ((V \S∗ , E)) > f ((V \S′ , ∅)), which implies FS′(G) > FS∗(G)-a contradiction, since S∗ was assumed to be the group with the largest centrality.

5.1 Approximation Algorithm

We have already shown that for every vitality index, computing the value of a group is as hard as computing the value for single nodes. However, computing Attachment Centrality is #P-complete, with polynomial-time algorithms known only for a narrow class of chordal graphs [Skibski et al., 2019]. To address this, we present an approximation algorithm based on a novel sampling method for the Union Shapley value.

To develop the approximation algorithm, we introduce a probabilistic interpretation of the Union Shapley value, which underpins group vitality indices.

Proposition 2. The Union Shapley value of coalition S in game (N, g) satisfies:

where Ω(N) is the set of all permutations of N, and Sπ i is the set of elements that appear in π no later than i, i.e., Sπ i = {j ∈ N : π(j) ≤ π(i)}.

Proof. For each coalition T ⊆ N, we count how many times T appears as Sπ i , i.e., the number of pairs (π, i) such that π ∈ Ω(N), i ∈ S, and T = Sπ i . This occurs if and only if:

• T appears in the first |T| positions of π, and
• i is the last element of T; thus i ∈ T ∩S.

For each i ∈ T ∩ S, there are (|T| - 1)!(|N| - |T|)! such permutations. Hence, the total number of such pairs is |T ∩ S| · (|T | - 1)!(|N| - |T |)!. Thus, the right-hand side of Equation (3) can be reformulated as:

which concludes the proof.

Algorithm 1 Approximation of Group Attachment Centrality

• Require: A graph G = (V, E) and a group S ⊆ V Ensure: The value AS(G) 1: result = 0 2: for i = 1 to number of samples do 3: π = random permutation of V 4: for all i ∈ S do 5: result += 2(|K(G[Sπ i \ S])| - |K(G[Sπ i ])| + |S ∩ Sπ i |)/|Sπ i ∩S| 6: end for 7: end for
• 8: return result/number of samples

Algorithm 1 presents the pseudocode for a Monte Carlo sampling algorithm to approximate Group Attachment Centrality.

The algorithm utilizes Proposition 2 for the coalitional game defined by Attachment Centrality. In this game, the marginal contribution of S to T simplifies to:

We note that this approximation algorithm can be easily extended to compute Attachment Centrality of all nodes. To do so, for each permutation, all players are considered in order, and their individual marginal contributions are computed and stored separately. A disjoint-set (union-find) data structure [Galler and Fisher, 1964] can be used to efficiently track the connected components throughout the computation.

6 Conclusions

In this paper, we have performed a comprehensive analysis of group vitality indices. First, we proved that every vitality index admits a unique extension to a group vitality index. Second, we provided two axiomatic characterizations of the entire class and showed that Group Degree and Attachment Centralities are the unique indices satisfying specific normalization conditions. Furthermore, we demonstrated that computing a group vitality index for a given group is as hard as computing a node vitality index, and that identifying the best group is always NP-hard under mild assumptions. Finally, we designed an approximation algorithm for computing Group Attachment Centrality.

Our work represents an initial step toward understanding the axiomatic properties of group centrality measures, and many promising directions remain for future research. For instance, an axiomatic analysis of other classical definitions of group measures could be developed, potentially by extending existing axiomatizations of node centralities. In particular, axiomatizing a group variant of PageRank appears both important and exciting. Further exploration of the connections between group centrality measures and coalitional game theory is another promising avenue. Finally, the axiom of Vertex Exclusion suggests a novel approach for defining group centrality, which may be applicable beyond vitality indices.

Ethical Statement

• There are no ethical issues.

Acknowledgments

Natalia Kucharczuk was supported by the National Science Centre under Grant No. 2018/31/B/ST6/03201. Oskar Skibski was supported by the National Science Centre under Grant No. 2023/50/E/ST6/00665.