pith. sign in

arxiv: 2605.09791 · v1 · submitted 2026-05-10 · 💻 cs.SI · cs.GT

Group Vitality Indices: Axioms and Algorithms

Natalia Kucharczuk , Oskar Skibski This is my paper

Pith reviewed 2026-05-12 02:55 UTC · model grok-4.3

classification 💻 cs.SI cs.GT
keywords vitality indicesgroup centralityShapley valuenetwork centralityaxiomatizationcomputational complexitysocial network analysisnode removal impact
0
0 comments X

The pith

Every vitality index for single nodes extends uniquely to groups of nodes using a group Shapley value.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Vitality indices assess a node's importance in a network by measuring the change when that node is removed. The paper proves that any such index has exactly one natural extension to groups of nodes that meets the fairness and efficiency axioms of a recently proposed group Shapley value. This extension turns individual removal-impact scores into collective ones without arbitrary choices. The authors also axiomatize the full class of group vitality indices, identify two normalized versions, and analyze their computational cost along with Group Attachment Centrality. The result matters for applications where teams or clusters, rather than lone actors, drive network behavior.

Core claim

We show that every vitality index admits a unique extension to groups, which can be defined using a group variant of the Shapley value recently proposed in the literature. We also provide an axiomatization of the entire class, along with two specific group vitality indices that satisfy additional normalization conditions. Furthermore, we study the computational properties of all vitality indices, as well as Group Attachment Centrality.

What carries the argument

The group Shapley value applied to a vitality index, which defines a node's group contribution as the average marginal change in network value over all possible orders of adding the group members.

If this is right

  • Every single-node vitality index gains a canonical group version without further choices.
  • The class of all group vitality indices is fully characterized by a set of axioms.
  • Two normalized group vitality indices exist that allow direct numerical comparisons across different base measures.
  • Polynomial-time or other efficient algorithms apply to computing the group values for many vitality indices.
  • Group Attachment Centrality inherits the same computational analysis as the broader class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same uniqueness argument may apply to other families of centrality measures if analogous group axioms can be stated.
  • In practice the construction supplies a fair way to rank or score teams whose joint removal would disrupt a network.
  • Approximation schemes developed for the single-node case can be lifted directly to the group setting via the same marginal-contribution averaging.
  • The link to cooperative game theory suggests similar axiomatic extensions could be attempted for path-based or flow-based centralities.

Load-bearing premise

Any reasonable group extension of a vitality index must satisfy the fairness, efficiency, and other axioms of the group Shapley value rather than some alternative aggregation rule.

What would settle it

An explicit vitality index together with two different group extensions that both satisfy the stated axioms, or a group extension that satisfies the axioms yet differs from the one constructed via the group Shapley value.

Figures

Figures reproduced from arXiv: 2605.09791 by Natalia Kucharczuk, Oskar Skibski.

Figure 1
Figure 1. Figure 1: Consider the problem of selecting two nodes in the graph above, based on Flow Betweenness [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Consider three groups: A = {2, 3, 4}, B = {4, 7, 11}, and C = {2, 6, 10}. Degree Centrality extended using the sum approach does not differentiate between these groups. When extended using the merge approach, common neighbors are avoided, making group C the best. In contrast, Group Degree Centrality (see Equation (1)) only avoids shared edges; therefore, groups B and C are better than A, but equally good. … view at source ↗
Figure 3
Figure 3. Figure 3: September 11 terrorist attack network. Group Attachment Centrality identifies Hamza Alghamdi [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Graph for Example 2. Both Group Degree and Attachment Centralities select [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

We consider the problem of assessing a group of nodes in a network. Our focus is on vitality indices -- a natural class of centrality measures that evaluate the importance of a node by examining the impact of its removal on the network. We conduct a comprehensive analysis of group vitality indices. Specifically, we show that every vitality index admits a unique extension to groups, which can be defined using a group variant of the Shapley value recently proposed in the literature. We also provide an axiomatization of the entire class, along with two specific group vitality indices that satisfy additional normalization conditions. Furthermore, we study the computational properties of all vitality indices, as well as Group Attachment Centrality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims that every vitality index (a centrality measure based on the impact of a node's removal) admits a unique extension to groups of nodes, which is defined using a group variant of the Shapley value. It provides an axiomatization of the full class of such group vitality indices, introduces two specific normalized examples, and analyzes the computational properties of vitality indices as well as Group Attachment Centrality.

Significance. If the uniqueness and axiomatization results hold, the work supplies a principled, axiom-based method for extending single-node vitality measures to groups, which is relevant for applications such as identifying critical node sets in social networks, infrastructure, and biological systems. The explicit uniqueness via the group Shapley value and the computational analysis are notable strengths that could support reproducible implementations.

major comments (1)
  1. [Uniqueness theorem (main results section)] The central uniqueness claim (abstract and the theorem establishing the group extension) is derived by requiring the extension to satisfy the group Shapley axioms (efficiency, symmetry, dummy-player property, etc.). The manuscript does not compare this to the direct alternative of defining group vitality as the change in the underlying network measure upon simultaneous removal of the entire group. If these diverge for general vitality indices, the uniqueness holds only inside the Shapley axiom class and does not rule out other natural extensions that preserve single-node semantics; this point is load-bearing for the claim of a unique extension.
minor comments (2)
  1. [Abstract] The abstract would benefit from briefly naming the key group-Shapley axioms used for uniqueness to improve immediate clarity.
  2. [Preliminaries and definitions] Notation distinguishing single-node vitality from its group extension should be introduced early and used consistently in definitions and proofs.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [Uniqueness theorem (main results section)] The central uniqueness claim (abstract and the theorem establishing the group extension) is derived by requiring the extension to satisfy the group Shapley axioms (efficiency, symmetry, dummy-player property, etc.). The manuscript does not compare this to the direct alternative of defining group vitality as the change in the underlying network measure upon simultaneous removal of the entire group. If these diverge for general vitality indices, the uniqueness holds only inside the Shapley axiom class and does not rule out other natural extensions that preserve single-node semantics; this point is load-bearing for the claim of a unique extension.

    Authors: We thank the referee for highlighting this important distinction. The uniqueness result establishes that there is a unique extension of any given vitality index to a group vitality index satisfying the group Shapley axioms (efficiency, symmetry, dummy-player property, and related properties). These axioms ensure consistency with the single-node case while enforcing fairness and additivity in the allocation of group contributions, following standard cooperative game theory. The direct alternative of defining group vitality via the change in the network measure after simultaneous removal of the group agrees with single-node vitality by construction. However, for general vitality indices, this direct definition does not necessarily satisfy the full axiomatic requirements (for example, it may violate linearity or additivity in the presence of node interactions). The axiomatic characterization therefore identifies the unique principled extension within the class of measures obeying these natural properties. We will add a clarifying paragraph in the revised manuscript (in the main results section following the uniqueness theorem) that explicitly compares the two approaches, notes where they may diverge, and justifies the focus on the axiomatic class. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines group vitality indices by extending single-node vitality measures via the group Shapley value construction drawn from the cited literature, then proves uniqueness under the standard axioms (efficiency, symmetry, dummy player, etc.). This is an axiomatic characterization: the extension is constructed from the given vitality index and the external axiom set rather than by redefining the input in terms of the output or fitting parameters to data. No equations in the abstract or described derivation reduce to their own inputs by construction, and the uniqueness result is conditional on the chosen axiom class without claiming to exhaust all possible group extensions. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the definition of vitality indices as removal-impact measures and on the group Shapley value being the canonical extension; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The group extension must coincide with the group Shapley value
    Invoked to obtain the uniqueness result stated in the abstract

pith-pipeline@v0.9.0 · 5404 in / 1113 out tokens · 44694 ms · 2026-05-12T02:55:57.876840+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 1 internal anchor

  1. [1]

    Error and attack tolerance of complex networks

    R \'e ka Albert, Hawoong Jeong, and Albert-L \'a szl \'o Barab \'a si. Error and attack tolerance of complex networks. Nature , 406(6794):378--382, 2000

    work page 2000

  2. [2]

    Ranking systems: the PageRank axioms

    Alon Altman and Moshe Tennenholtz. Ranking systems: the PageRank axioms. In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM-EC) , pages 1--8, 2005

    work page 2005

  3. [3]

    A connectivity game for graphs

    Rafael Amer and Jos \'e Miguel Gim \'e nez. A connectivity game for graphs. Mathematical Methods of Operations Research , 60(3):453--470, 2004

    work page 2004

  4. [4]

    Centrality measures in networks

    Francis Bloch, Matthew O Jackson, and Pietro Tebaldi. Centrality measures in networks. Social Choice and Welfare , 61(2):413--453, 2023

    work page 2023

  5. [5]

    Axioms for centrality

    Paolo Boldi and Sebastiano Vigna. Axioms for centrality. Internet Mathematics , 10(3-4):222--262, 2014

    work page 2014

  6. [6]

    Network analysis: Methodological foundations

    Ulrik Brandes and Thomas Erlebach. Network analysis: Methodological foundations . Springer-Verlag, 2005

    work page 2005

  7. [7]

    A survey on optimization studies of group centrality metrics

    Mustafa Can Camur and Chrysafis Vogiatzis. A survey on optimization studies of group centrality metrics. Networks , 84(4):491--508, 2024

    work page 2024

  8. [8]

    Computational aspects of cooperative game theory

    Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning , 5(6):1--168, 2011

    work page 2011

  9. [9]

    Everett and Stephen P

    Martin G. Everett and Stephen P. Borgatti. The centrality of groups and classes. Journal of Mathematical Sociology , 23(3):181--201, 1999

    work page 1999

  10. [10]

    Everett and Stephen P

    Martin G. Everett and Stephen P. Borgatti. Induced, endogenous and exogenous centrality. Social Networks , 32(4):339--344, 2010

    work page 2010

  11. [11]

    Freeman, Stephen P

    Linton C. Freeman, Stephen P. Borgatti, and Douglas R. White. Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks , 13(2):141--154, 1991

    work page 1991

  12. [12]

    Shapley values for feature selection: The good, the bad, and the axioms

    Daniel Fryer, Inga Str \"u mke, and Hien Nguyen. Shapley values for feature selection: The good, the bad, and the axioms. Ieee Access , 9:144352--144360, 2021

    work page 2021

  13. [13]

    Galler and Michael J

    Bernard A. Galler and Michael J. Fisher. An improved equivalence algorithm. Communications of the ACM , 7(5):301--303, 1964

    work page 1964

  14. [14]

    Axiomatic foundations of centrality in networks

    Manuj Garg. Axiomatic foundations of centrality in networks. Available at SSRN 1372441, 2009

    work page 2009

  15. [15]

    An axiomatic approach to the concept of interaction among players in cooperative games

    Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory , 28(4):547--565, 1999

    work page 1999

  16. [16]

    Coalitional games induced by matching problems: Complexity and islands of tractability for the shapley value

    Gianluigi Greco, Francesco Lupia, and Francesco Scarcello. Coalitional games induced by matching problems: Complexity and islands of tractability for the shapley value. Artificial Intelligence , 278:103180, 2020

    work page 2020

  17. [17]

    Sequential elimination and U nion S hapley value for group assessment in coalitional games

    Piotr K e pczy \'n ski and Oskar Skibski. Sequential elimination and U nion S hapley value for group assessment in coalitional games. arXiv preprint arXiv:2505.21122 , 2026

    work page internal anchor Pith review arXiv 2026

  18. [18]

    Kolaczyk, David B

    Eric D. Kolaczyk, David B. Chua, and Marc Barth \'e lemy. Group betweenness and co-betweenness: Inter-related notions of coalition centrality. Social Networks , 31(3):190--203, 2009

    work page 2009

  19. [19]

    Valdis E. Krebs. Mapping networks of terrorist cells. Connections , 24:43--52, 2002

    work page 2002

  20. [20]

    Choosing optimal seed nodes in competitive contagion

    Prem Kumar, Puneet Verma, Anurag Singh, and Hocine Cherifi. Choosing optimal seed nodes in competitive contagion. Frontiers in big Data , 2:16, 2019

    work page 2019

  21. [21]

    Cooperative game theoretic centrality analysis of terrorist networks: The cases of J emaah I slamiyah and A l Q aeda

    Roy Lindelauf, Herbert Hamers, and Bart Husslage. Cooperative game theoretic centrality analysis of terrorist networks: The cases of J emaah I slamiyah and A l Q aeda. European Journal of Operational Research , 229(1):230--238, 2013

    work page 2013

  22. [22]

    A unified approach to interpreting model predictions

    Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems , pages 4765--4774, 2017

    work page 2017

  23. [23]

    Axiomatic characterizations of generalized values

    Jean-Luc Marichal, Ivan Kojadinovic, and Katsushige Fujimoto. Axiomatic characterizations of generalized values. Discrete Applied Mathematics , 155(1):26--43, 2007

    work page 2007

  24. [24]

    Michalak, Talal Rahwan, Piotr L

    Tomasz P. Michalak, Talal Rahwan, Piotr L. Szczepa \'n ski, Oskar Skibski, Ramasuri Narayanam, Michael Wooldridge, and Nicholas R. Jennings. Computational analysis of connectivity games with applications to the investigation of terrorist networks. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI) , pages 293--301, 2013

    work page 2013

  25. [25]

    Roger B. Myerson. Conference structures and fair allocation rules. International Journal of Game Theory , 9:169--82, 1980

    work page 1980

  26. [26]

    On the centrality in a directed graph

    UJ Nieminen. On the centrality in a directed graph. Social Science Research , 2(4):371--378, 1973

    work page 1973

  27. [27]

    Social network analysis as an approach to combat terrorism: past, present and future research

    Steve Ressler. Social network analysis as an approach to combat terrorism: past, present and future research. Homeland Security Affairs , 2:1--10, 2006

    work page 2006

  28. [28]

    Modelling interdependent infrastructures

    Vittorio Rosato, Lior Issacharoff, Fabrizio Tiriticco, Sandro Meloni, Stefano Porcellinis, and Roberto Setola. Modelling interdependent infrastructures. International Journal of Critical Infrastructures , 4(1--2):63--79, 2008

    work page 2008

  29. [29]

    The centrality index of a graph

    Gert Sabidussi. The centrality index of a graph. Psychometrika , 31(4):581--603, 1966

    work page 1966

  30. [30]

    Lloyd S. Shapley. A value for n-person games. In H.W. Kuhn and A.W. Tucker, editors, Contributions to the Theory of Games , volume II, pages 307--317. Princeton University Press, 1953

    work page 1953

  31. [31]

    Michalak, and Talal Rahwan

    Oskar Skibski, Tomasz P. Michalak, and Talal Rahwan. Axiomatic characterization of game-theoretic centrality. Journal of Artificial Intelligence Research , 62:33--68, 2018

    work page 2018

  32. [32]

    Michalak, and Makoto Yokoo

    Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. Attachment centrality: Measure for connectivity in networks. Artificial Intelligence , 274:151--179, 2019

    work page 2019

  33. [33]

    Vitality indices are equivalent to induced game-theoretic centralities

    Oskar Skibski. Vitality indices are equivalent to induced game-theoretic centralities. In Zhi-Hua Zhou, editor, Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages 398--404, 2021

    work page 2021

  34. [34]

    Attachment centrality for weighted graphs

    Jadwiga Sosnowska and Oskar Skibski. Attachment centrality for weighted graphs. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages 416--422, 2017

    work page 2017

  35. [35]

    Rama Suri and Yadati Narahari

    N. Rama Suri and Yadati Narahari. Determining the top-k nodes in social networks using the S hapley value. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages 1509--1512, 2008

    work page 2008

  36. [36]

    A survey on centrality metrics and their network resilience analysis

    Zelin Wan, Yash Mahajan, Beom Woo Kang, Terrence J Moore, and Jin-Hee Cho. A survey on centrality metrics and their network resilience analysis. IEEE Access , 9:104773--104819, 2021

    work page 2021

  37. [37]

    Axiomatic characterization of PageRank

    Tomasz W a s and Oskar Skibski. Axiomatic characterization of PageRank . Artificial Intelligence , 318:103900, 2023

    work page 2023

  38. [38]

    Random walk decay centrality

    Tomasz W a s, Talal Rahwan, and Oskar Skibski. Random walk decay centrality. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 2197--2204, 2019

    work page 2019