betaFeedback

WorksComputer Science

A Unified Framework for Extending Centrality Measures to Groups

Abstract

We propose a unified framework for extending centrality measures from individual nodes to groups. For each centrality measure, we introduce four group variants—maximum, minimum, sum, and proportional—which differ in how individual contributions are aggregated at the group level. The framework builds on a new unified perspective on major classes of centrality measures, according to which the score of a node can be expressed as a sum of assessments made by individual nodes, pairs of nodes, or groups of nodes. Each of the four variants then corresponds to a different rule for aggregating the assessments of the members of a group.

Introduction

Centrality measures are widely used across a range of research fields, including computer science, sociology, biology, economics, and engineering [37]. A common approach to selecting a group of nodes for a given objective is to rank the nodes according to an individual centrality measure and choose the top-ranked ones. Such strategies are used in network immunization [14, 2], in the identification of influential spreaders [24], and in studies of the vulnerability of the Internet to targeted attacks [1, 15]. However, selecting nodes solely according to their individual centrality scores ignores interactions and potential redundancy among the selected nodes, and may therefore lead to suboptimal groups [32]. For example, when promoting a product, selecting two influencers from different communities may provide a broader reach than selecting two individually more central influencers from the same one.

Group centrality measures address this limitation by evaluating groups of nodes as a whole. Group variants have been defined for several well-known centrality measures, including degree [20, 28], closeness [16], betweenness [11, 16], and PageRank [31], as well as for vitality indices [26]. However, existing approaches often rely on different underlying concepts, resulting in a fragmented landscape of group centrality definitions. This makes it difficult to compare different group measures and systematically extend other node centralities to groups.

To address this, we propose a unified framework for extending node centrality measures to groups. For each centrality measure expressed in our framework, we define four types of group extensions: Sum, Max, Min, and Proportional. These extensions differ in how they aggregate the evaluations of individual group members provided by a particular node, pair of nodes, or group of nodes. Our framework captures a wide range of existing group centrality measures as special cases, while also providing a systematic way to construct new variants (see § 6).

The following example illustrates how different group extensions of the same centrality measure can capture fundamentally different notions of group importance.

Example 1. Consider the problem of selecting locations for three stores along a street with nine buildings, as shown in Figure 1. A straightforward approach would be to select the three most central locations, {4, 5, 6}. But is this always the best choice?

Figure 1. Nine buildings arranged along a street. Which three should be selected as locations for new stores?

Following the intuition behind closeness centrality, assume that each node (building) evaluates a location by the negative of its distance to that location. Let the overall score of a group of locations be the sum of the assessments it receives from all nodes. How, then, should each node assess a group?

If the stores are of different types, each node may assess a group by summing its evaluations of all three locations. Under Sum aggregation, the unique optimal group is {4,5,6}\{4,5,6\}: the stores are placed in the three central buildings. The same result is obtained if each node assesses a group based on its evaluation of the farthest store, as in Min aggregation.

However, if the stores are of the same type, each node may assess a group based on its evaluation of the closest store. Under Max aggregation, the unique optimal group is {2,5,8}\{2,5,8\}: each selected node has a store at distance zero, while every other node has a store at distance one. Finally, nodes may care primarily about the closest store while also valuing alternatives in case that store is closed or a desired product is unavailable. Under Proportional aggregation, each node evaluates the group as a weighted sum of its evaluations of the three locations, assigning weights of 11, 1/21/2, and 1/31/3 to the closest, second closest, and farthest store, respectively. The unique optimal group is then {3,5,7}\{3,5,7\}, which yields an intermediate arrangement between the central locations preferred by Sum and Min and the more dispersed locations preferred by Max.

We provide detailed calculations in Example 2.

Our framework builds on a new unified representation of node centrality measures, which we call SPEC. In this representation, a node’s centrality is expressed as a sum of evaluations provided by individual nodes, pairs of nodes, or groups of nodes, possibly followed by a ranking-preserving conversion. We show that a wide range of classical centrality measures admit such a representation, including distance-based, medial, feedback, and vitality measures. While this representation is straightforward for some classes of centrality measures, others require more sophisticated interpretations. In particular, for feedback centralities, we build on a walk-based interpretation [45], whereas for vitality indices, we use their game-theoretic characterization [40].

The SPEC framework differs from existing approaches in its generality and purpose. Previous work has classified centrality measures according to their structural properties [9] or characterized them in terms of statistics based on paths, walks, and geodesics [4]. In contrast, SPEC allows for general evaluation functions and provides a common representation in terms of evaluations by sets of nodes, designed specifically to enable systematic extensions to groups. Furthermore, SPEC follows a recent line of research connecting centrality analysis with social choice theory by viewing the centrality of a node or group as the aggregation of assessments provided by separate evaluators, analogous to voters [41, 28, 35].

We complement our theoretical framework with an experimental analysis of the different group extensions on illustrative graphs. Our results demonstrate that the choice of aggregation rule can substantially affect which groups are considered optimal. In particular, the Proportional extension can produce selections that better reflect the relative sizes of different communities. For example, when selecting four nodes, it can favor allocating one of them to a community containing one quarter of the nodes in the graph.

Preliminaries

We focus on undirected, unweighted graphs. However, the framework and our results can also be extended to directed and weighted graphs. A graph G=(V,E)G=(V,E) consists of a set of nodes VV and a set of edges E⊆{{u,v}:u,v∈V, u≠v}E \subseteq\{\{u,v\}:u,v\in V,\ u\ne v\}. For an edge {u,v}∈E\{u,v\}\in E, nodes uu and vv are incident to the edge and adjacent to each other; they are also called neighbors. The number of incident edges of a node is its degree, denoted by deg⁡(v)\deg(v).

A walk is a sequence of nodes p=(u0,…,uk)p=(u_0,\ldots,u_k), where k≥0k\ge0, such that every pair of consecutive nodes is connected by an edge, i.e., {ui,ui+1}∈E\{u_i,u_{i+1}\}\in E for every i∈{0,…,k−1}i\in\{0,\ldots,k-1\}. The length of a walk is the number of traversed edges, i.e., kk. The set of all walks in a graph, including walks of size zero, is denoted by Ω(G)\Omega(G). The distance between nodes uu and vv, denoted by dist⁡G(u,v)\operatorname{dist}_G(u,v), is the length of a shortest walk between them. We set dist⁡G(u,v)=∞\operatorname{dist}_{G}(u,v)=\infty if no such walk exists and omit the subscript GG when the graph is clear from the context.

By MXM^{X} we denote the set of all nonempty finite multisets of XX. For M∈MXM \in M^{X}, let ∣M∣|M| denote its size, the number of elements in MM. We use the notation { ⁣{⋅} ⁣}\{\!\{ \cdot\}\!\} to list elements of the multiset.

SPEC representation

In this section, we introduce a unified representation, called SPEC, which will allow us to extend node centrality measures to groups.

A SPEC representation is a tuple R=(S,P,e,c)\mathcal{R}=(S,P,e,c) consisting of the following components:

  • A selector SS that assigns to each finite set of nodes WW a family of subsets S(W)⊆2WS(W) \subseteq2^{W}, called evaluators.

  • A policy PP that determines whether nodes S⊆VS \subseteq V evaluate themselves. We consider two options:

    • Exclusive policy Pexc(S)=SP_{\mathrm{exc}}(S)=S: nodes from SS are excluded.

    • Inclusive policy Pinc(S)=∅P_{\mathrm{inc}}(S)=\varnothing: no nodes are excluded.

  • An evaluation eG:2V×V→Re_{G}:2^{V}\times V\to\mathbb{R}. The value eG(U,v)e_{G}(U,v) specifies how an evaluator UU evaluates a node vv.

  • A conversion c:R→Rc:\mathbb{R}\to\mathbb{R} that is a strictly increasing function on the set of attainable aggregate evaluation scores and thus preserves the ranking of nodes.

The node centrality induced by a SPEC representation R=(S,P,e,c)\mathcal{R}=(S,P,e,c) is defined for every graph G=(V,E)G=(V,E) and node v∈Vv\in V as

FvR(G)=c(∑U∈S(V∖P({v}))eG(U,v)).F_{v}^{\mathcal{R}}(G)=c\left(\sum_{U\in S(V\setminus P(\{v\}))}e_{G}(U,v)\right).

Under this representation, a node vv is evaluated by a family of node sets selected by the selector SS. Depending on the policy PP, these sets may or may not contain vv itself. Each selected set, called an evaluator, assigns a value to vv according to the evaluation function eGe_{G}. The resulting values are summed and then transformed by the conversion function cc. See Figure 2 for an illustration.

Illustration of the SPEC framework

Figure 2. Illustration of the SPEC framework. The selector chooses candidate evaluators, the policy may exclude some of them, the remaining evaluators assign scores to node vv, and the resulting aggregate score is converted into the final centrality value.

Appendix A provides SPEC representations of various classical centrality measures. Below, we discuss a few illustrative examples.

Degree centrality

Degree centrality simply counts the number of edges incident to a node:

Fv(G)=∣{{u,v}∈E:u∈V}∣.F_{v}(G)=|\{\{u,v\}\in E:u\in V\}|.

To express it in the SPEC framework, we let each node other than vv assign a score of 1 to vv if they are connected, and 0 otherwise.

Definition 1. A SPEC representation of degree centrality is:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes are evaluators);

  • P=PexcP = P_{\mathrm{exc}} (a node does not evaluate itself);

  • eG({w},v)=1e_G(\{w\}, v) = 1 if {w,v}∈E\{w, v\} \in E, and 00 otherwise (node vv receives 1 from each neighbor and 0 from every other node);

  • c(r)=rc(r) = r (no conversion).

Closeness centrality

Closeness centrality [3] is a centrality measure typically defined for connected graphs. It assesses a node based on the sum of its distances to all other nodes:

Fv(G)=1∑u∈V∖{v}dist⁡(u,v).F_v(G) = \frac{1}{\sum_{u \in V \setminus\{v\}} \operatorname{dist}(u,v)}.

Unlike degree centrality, closeness centrality is not directly expressed as a sum of individual evaluations. However, we can represent it as a sum of negative distances to other nodes, followed by a conversion function that transforms this sum into its reciprocal.

Definition 2. A SPEC representation of closeness centrality is:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes are evaluators);

  • P=PexcP = P_{\mathrm{exc}} (a node does not evaluate itself);

  • eG({w},v)=−dist⁡(w,v)e_G(\{w\}, v) = -\operatorname{dist}(w,v) (node ww evaluates node vv by the negative of the distance between them);

  • c(r)=−1/rc(r) = -1/r (converts the negative sum of distances into the reciprocal of their sum).

Betweenness centrality

Betweenness centrality [18] measures how often a node lies on shortest paths between other nodes. It is defined as

Fv(G)=∑{s,t}⊆V∖{v},s≠tσst(v)σst.F_v(G) = \sum_{\substack{\{s,t\} \subseteq V \setminus\{v\},\,s \ne t}} \frac{\sigma_{st}(v)}{\sigma_{st}}.

where σst\sigma_{st} is the number of shortest paths between nodes ss and tt, and σst(v)\sigma_{st}(v) is the number of such paths that pass through node vv. If σst=0\sigma_{st} = 0, the corresponding fraction is defined to be 0. Betweenness centrality can be expressed in the SPEC framework by using pairs of nodes as evaluators.

Definition 3. A SPEC representation of betweenness centrality is:

  • S(W)={{s,t}⊆W:s≠t}S(W) = \{\{s,t\} \subseteq W : s \ne t\} (pairs of nodes are evaluators);

  • P=PexcP = P_{\mathrm{exc}} (a node does not evaluate itself);

  • eG({s,t},v)=σst(v)/σste_G(\{s,t\}, v) = \sigma_{st}(v)/\sigma_{st} (a pair of nodes s,ts,t evaluates node vv by the proportion of shortest paths between them that pass through vv);

  • c(r)=rc(r) = r (no conversion).

PageRank

Unlike centrality measures based on shortest paths, PageRank [34] takes into account walks of all lengths and measures the importance of a node based on their weighted contributions. PageRank has several variants; one standard version is defined as follows:

Fv(G)=1−α∣V∣∑(u0,…,uk)∈Ω(G)uk=vαk∏i=0k−1deg⁡(ui)F_v(G)=\frac{1-\alpha}{|V|}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_k=v}}\frac{\alpha^k}{\prod_{i=0}^{k-1}\deg(u_i)}

where α∈(0,1)\alpha\in(0,1) is a fixed damping factor.

A natural way to decompose this formula is to group walks by their starting nodes. This approach is also closely related to personalized PageRank, discussed in the original paper [34], where only selected nodes may have a positive probability of being chosen as starting points. In this way, each node evaluates other nodes based on the weighted contributions of walks starting at that node. Importantly, walks starting at the evaluated node must also be included.

Definition 4. A SPEC representation of PageRank is:

  • S(W)={{w}:w∈W}S(W)=\{\{w\}:w\in W\} (individual nodes are evaluators);

  • P=PincP=P_{\mathrm{inc}} (a node also evaluates itself);

  • eG({w},v)=1−α∣V∣∑(u0,…,uk)∈Ω(G)u0=w, uk=vαk∏i=0k−1deg⁡(ui)e_G(\{w\},v)=\frac{1-\alpha}{|V|}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_0=w,\ u_k=v}}\frac{\alpha^k}{\prod_{i=0}^{k-1}\deg(u_i)} (node ww evaluates node vv by the total weighted contribution of walks from ww to $v);

  • c(r)=rc(r)=r (no conversion).

See Figure 3 for a numerical example comparing degree, closeness and PageRank centralities. We note that a centrality measure may admit multiple SPEC representations. Different representations may reflect different perspectives on and interpretations of the same centrality measure. In the following sections, we show how the main classes of centrality measures can be represented within the SPEC framework.

Graph and table showing SPEC evaluations of node 5 for degree, closeness, and PageRank centrality

Figure 3. SPEC evaluations of node 5 for degree, closeness, and PageRank centrality. A dash indicates that the evaluator is excluded by the exclusive policy. The conversion is c(r)=−1/rc(r)=-1/r for closeness and c(r)=rc(r)=r for degree and PageRank. PageRank values are rounded to four decimal places.

Distance-based centralities

A centrality measure is distance-based [43] (or geometric [6]) if the importance of a node depends only on its distances to other nodes. Most distance-based centralities are additive and can be written in the form

Fv(G)=∑u∈V∖{v}f(dist⁡(u,v))F_v(G)=\sum_{u\in V\setminus\{v\}}f(\operatorname{dist}(u,v))

for some non-increasing function f:N>0∪{∞}→Rf:\mathbb{N}_{>0}\cup\{\infty\}\to\mathbb{R}, where f(∞)f(\infty) specifies the contribution of unreachable nodes.

This class includes many classical centralities, such as degree (with f(1)=1f(1)=1 and f(x)=0f(x)=0, otherwise), harmonic (with f(x)=1/xf(x)=1/x), decay (with f(x)=αxf(x)=\alpha^x for a fixed α∈(0,1)\alpha\in(0,1)), and kk-step reach (with f(x)=1f(x)=1 if x≤kx \le k and f(x)=0f(x)=0, otherwise). For these four measures, we set f(∞)=0f(\infty)=0. A prominent non-additive example is closeness centrality, which, on connected graphs with at least two nodes, induces the same ranking as the additive measure obtained by setting f(x)=−xf(x)=-x. This additive form was used in Example 1 and underlies the SPEC representation in Definition 2.

Additive distance-based centralities admit a natural SPEC representation. Individual nodes serve as evaluators (S(W)={{u}:u∈W}S(W)=\{\{u\}:u\in W\}), and the exclusive policy is used (P=PexcP=P_{\mathrm{exc}}). Each node uu evaluates a node v≠uv\ne u according to ff applied to their distance (eG({u},v)=f(dist⁡(u,v))e_G(\{u\},v)=f(\operatorname{dist}(u,v))), and no conversion is required (c(r)=rc(r)=r).

Medial centralities

Another major class of centrality measures consists of medial (or betweenness-like) centralities. These measures assess nodes according to their role as intermediaries between other nodes. To this end, they consider pairs of distinct nodes s,ts,t and quantify the contribution of the evaluated node vv to connecting them. For variants that exclude pairs containing vv, this can be expressed as

Fv(G)=∑{s,t}⊆V∖{v}, s≠tΔvs,t(G).F_v(G)=\sum_{\{s,t\}\subseteq V\setminus\{v\},\,s\ne t}\Delta_v^{s,t}(G).

where Δvs,t(G)\Delta_v^{s,t}(G) denotes the contribution of vv to the pair {s,t}\{s,t\}.

This class includes classical betweenness centrality (Δvs,t(G)=σst(v)/σst\Delta_v^{s,t}(G)=\sigma_{st}(v)/\sigma_{st}) and stress centrality (Δvs,t(G)=σst(v)\Delta_v^{s,t}(G)=\sigma_{st}(v)), as well as variants based on network flows, such as flow betweenness [19], and random walks [5, 33].

Measures of this form admit a natural SPEC representation. Pairs of distinct nodes serve as evaluators (S(W)={{s,t}:s,t∈W, s≠t}S(W)=\{\{s,t\}:s,t\in W,\ s\ne t\}), and the exclusive policy is used (P=PexcP=P_{\mathrm{exc}}). A pair {s,t}\{s,t\} evaluates node vv according to Δ\Delta (eG({s,t},v)=Δvs,t(G)e_G(\{s,t\},v)=\Delta_v^{s,t}(G)), and no conversion is required (c(r)=rc(r)=r). Variants that also include pairs containing the evaluated node can instead be represented using the inclusive policy (P=PincP=P_{\mathrm{inc}}).

Medial centralities can also be expressed in the SPEC representation, with paths rather than pairs of nodes serving as evaluators. We will discuss this formulation in more detail in § 6.

Feedback centrality measures

Feedback centralities [45] constitute one of the classical classes of centrality measures. These measures assess the importance of a node based on the number and importance of its neighbors. Most of them have a recursive definition of the form

Fv(G)=a(G)∑{u,v}∈E(Fu(G))c(deg⁡(u))d+b(G).F_v(G)=a(G)\sum_{\{u,v\}\in E}\frac{(F_u(G))^c}{(\deg(u))^d}+b(G).

where aa and bb are real-valued functions defined on graphs, and c,d∈{0,1}c,d\in\{0,1\}. This form captures several classical centrality measures:

  • degree centrality (a(G)=1a(G)=1, b(G)=c=d=0b(G)=c=d=0),

  • beta measure [44] (a(G)=d=1a(G)=d=1, b(G)=c=0b(G)=c=0),

  • eigenvector centrality [7] (a(G)=1/λ(G)a(G)=1/\lambda(G), b(G)=d=0b(G)=d=0, c=1c=1),

  • Seeley index [38] (a(G)=c=d=1a(G)=c=d=1, b(G)=0b(G)=0),

  • Katz centrality [23] (c=1c=1, d=0d=0, a(G)∈(0,1/λ(G))a(G)\in(0,1/\lambda(G)), b(G)>0b(G)>0), and

  • PageRank [34] (c=d=1c=d=1, a(G)=α∈(0,1)a(G)=\alpha\in(0,1), b(G)=(1−α)/∣V∣b(G)=(1-\alpha)/|V|),

where λ(G)\lambda(G) denotes the largest eigenvalue of the adjacency matrix.

For degree centrality and the beta measure, individual neighbors naturally serve as evaluators, assigning a score of 11 and 1/deg⁡(u)1/\deg(u), respectively, to a node vv adjacent to uu (see Definition 1). For other feedback centralities, however, assuming that only neighbors evaluate a node based on their own importance is less natural. First, the importance of each neighbor also depends on other:VEVENT nodes in the graph, whose contributions would not be represented directly. Second, each evaluator would assign the same score to all its neighbors, which limits the distinctions captured by group aggregation.

To address this, we use the walk-based interpretation of feedback centralities presented by Wąs and Skibski [45]. Specifically, individual nodes serve as evaluators (S(W)={{u}:u∈W}S(W) = \{\{u\} : u \in W\}), and the inclusive policy is used (P=PincP = P_{\mathrm{inc}}). Each node uu evaluates a node vv by the total weighted contribution of walks from uu to vv (for Katz centrality and PageRank) or by the limiting average of these contributions (for eigenvector centrality and the Seeley index). The weights assigned to walks depend on the centrality measure. No conversion is required (c(r)=rc(r) = r). See Appendix § 10 for details.

Vitality indices

Vitality indices [12, 17] evaluate nodes according to the change in a graph’s potential caused by their removal. This class consists of measures of the form

Fv(G)=p(G)−p(G−v)F_v(G) = p(G) - p(G-v)

for some real-valued potential function pp defined on graphs, where G−vG-v denotes the graph obtained by removing vv and its incident edges. This class includes degree centrality, flow betweenness centrality [19] and attachment centrality [42].

It is not immediately clear how to express vitality indices in terms of evaluations of a node vv by groups of nodes. However, such a representation follows from a game-theoretic perspective. Specifically, Skibski [40] proved that every vitality index admits the following Shapley-value representation:

Fv(G)=∑U⊆Vβ(∣V∣,∣U∣)(∑u∈U∪{v}Fu(G[U∪{v}])−∑u∈UFu(G[U]))F_v(G) = \sum_{U \subseteq V} \beta(|V|,|U|) \left( \sum_{u \in U \cup\{v\}} F_u(G[U \cup\{v\}]) - \sum_{u \in U} F_u(G[U]) \right)

where β(n,k)=k!(n−k−1)!/n!\beta(n,k) = k!(n-k-1)!/n! for k∈{0,…,n−1}k \in\{0,\ldots,n-1\} and β(n,n)=1\beta(n,n) = 1, and G[S]G[S] is the subgraph of GG induced by SS. In this representation, each group U⊆V∖{v}U \subseteq V \setminus\{v\} evaluates node vv by its weighted marginal contribution to the total centrality in the subgraph induced by U∪{v}U \cup\{v\}. Thus, the contribution to the potential of the entire graph is expressed as a weighted sum of contributions to total centrality in induced subgraphs.

This yields the following SPEC representation of vitality indices. All subsets of nodes serve as evaluators (S(W)=2WS(W) = 2^W), and the inclusive policy is used (P=PincP = P_{\mathrm{inc}}). For U⊆V∖{v}U \subseteq V \setminus\{v\}, the evaluation is given by

eG(U,v)=β(∣V∣,∣U∣)(∑u∈U∪{v}Fu(G[U∪{v}])−∑u∈UFu(G[U]))e_G(U,v) = \beta(|V|,|U|) \left( \sum_{u \in U \cup\{v\}} F_u(G[U \cup\{v\}]) - \sum_{u \in U} F_u(G[U]) \right)

No conversion is required (c(r)=rc(r) = r).

Group Extensions of SPEC

In this section, we present four ways of extending a centrality measure given by a SPEC representation to a group centrality measure. When a group rather than a single node is evaluated, each evaluator assigns a separate value to each node in the group. The four variants differ in how these values are aggregated.

Formally, an aggregation is a function A:RM→RA : \mathbb{R}^{M} \to\mathbb{R} such that A({x})=xA(\{x\}) = x for every x∈Rx \in\mathbb{R}. We consider four aggregations:

  • Sum sums all evaluations: Asum(M)=∑x∈MxA^{\mathrm{sum}}(M) = \sum_{x \in M} x.

  • Max selects the highest evaluation: Amax(M)=max⁡x∈MxA^{\mathrm{max}}(M) = \max_{x \in M} x.

  • Min selects the lowest evaluation: Amin(M)=min⁡x∈MxA^{\mathrm{min}}(M) = \min_{x \in M} x.

  • Proportional (Prop for short) takes a harmonically weighted sum of the evaluations, ordered from highest to lowest: Aprop(M)=∑i=1∣M∣xi/iA^{\mathrm{prop}}(M) = \sum_{i=1}^{|M|} x_i/i, where M~=(x1,…,x∣M∣)\widetilde{M} = (x_1,\ldots,x_{|M|}) lists the elements of MM in non-increasing order.

Given a SPEC representation R=(S,P,e,c)\mathcal{R}=(S,P,e,c) and an aggregation AA, we define the corresponding group centrality for a nonempty group S⊆VS\subseteq V by

FSR,A(G)=c(∑U∈S(V∖P(S))A({∣eG(U,v)∣}v∈S)).F_{S}^{\mathcal{R},A}(G)=c\left(\sum_{U\in S(V\setminus P(S))}A\left(\{|e_G(U,v)|\}_{v\in S}\right)\right).

Each admissible evaluator UU evaluates every node in SS, and AA combines these values into a single evaluation of the group. These group evaluations are then summed over all admissible evaluators, and the conversion function cc is applied to the resulting sum. Since A({∣x∣})=xA(\{|x|\})=x, the group centrality agrees with the original node centrality on singletons: F{v}R,A(G)=FvR(G)F_{\{v\}}^{\mathcal{R},A}(G)=F_v^{\mathcal{R}}(G).

Before we proceed with the analysis of specific group measures, let us provide some intuition about how the different aggregation rules work.

Sum aggregation.

The Sum aggregation simply sums all evaluations. This makes the resulting group centrality closely related to the sum of the individual node centralities. In fact, if the conversion is a positive linear scaling c(x)=αxc(x)=\alpha x for some α∈R>0\alpha\in\mathbb{R}_{>0}, which is often the case, and the inclusive policy PincP_{\mathrm{inc}} is used, the resulting group centrality is exactly equal to the sum of the individual node centralities:

FSR,Asum(G)=∑v∈Sα∑U∈S(V)eG(U,v)=∑v∈SFvR(G).F_{S}^{\mathcal{R},A^{\mathrm{sum}}}(G)=\sum_{v\in S}\alpha\sum_{U\in S(V)}e_G(U,v)=\sum_{v\in S}F_v^{\mathcal{R}}(G).

Max aggregation.

The Max aggregation retains only the highest evaluation. Thus, adding a new node to a group affects the aggregated evaluation of an evaluator only if the new node receives a higher evaluation than all nodes already in the group. Consequently, the Max aggregation tends to reward spreading the nodes of the group across the graph, so that many evaluators have a well-evaluated representative in the group.

The Max aggregation is also closely related to the approach of merging the group into a single node and then evaluating the resulting node using the original centrality measure, which we call the merge approach. For example, for additive distance-based centralities whose evaluation function ff is non-increasing in the distance, the Max aggregation coincides with the merge approach. Indeed, the distance from a node to the merged group is equal to its distance to the closest node in the group in the original graph. The merge approach has been criticized for modifying the structure of the graph, which may lead to unintended effects for some centrality measures [16]. For example, in the graph ①–②–③–④ ⑤–⑥–⑦–⑧ nodes 4 and 5 both have zero betweenness centrality, yet merging them produces a node with betweenness 9, artificially connecting two disconnected components. The Max aggregation operates on the original graph and therefore avoids this issue.

Min aggregation.

The Min aggregation retains only the lowest evaluation. Thus, if even one node in the group receives a low evaluation from an evaluator, the aggregated evaluation assigned by that evaluator is also low. Consequently, the Min aggregation tends to favor compact groups whose members receive relatively similar evaluations, rather than groups containing nodes that are far apart.

Prop aggregation.

The Prop aggregation takes a harmonically weighted sum of the evaluations. It often produces behavior intermediate between the Sum and Max aggregations: all evaluations are taken into account, but lower-ranked evaluations receive progressively smaller weights. In fact, for groups of size two, the Prop aggregation is exactly the arithmetic mean of the Max and Sum aggregations. The proportional nature of this aggregation results from diminishing returns when additional group members receive high evaluations from the same evaluators. To illustrate this, suppose that nodes are partitioned into disconnected communities and that each evaluator assigns value 1 to every node in its own community, including itself, and 0 to every node outside it. If a group contains kk nodes from a community of size mm, then this community contributes m(1+12+⋯+1k)m(1+\frac{1}{2}+\cdots+\frac{1}{k}) to the group score. Adding another node from the same community therefore increases the score by m/(k+1)m/(k+1). Consequently, an optimal group tends to allocate its members among communities proportionally to their sizes, reproducing the diminishing-returns principle underlying PAV in social choice theory [27].

Example 2. Recall Example 1. Our goal is to extend the assessment inspired by closeness centrality to groups, using evaluations eG({w},v)=−dist⁡(w,v)e_G(\{w\},v)=-\operatorname{dist}(w,v) and the conversion c(r)=−1/rc(r)=-1/r. Table 1 presents the scores obtained using all four aggregation rules under both policies.

GroupInclusive ClosenessExclusive Closeness
SUMMINMAXPROPSUMMINMAXPROP
{4,5,6}\{4,5,6\}1/621/621/291/291/121/126/1936/1931/541/541/241/241/121/121/291/29
{3,5,7}\{3,5,7\}1/681/681/381/381/81/83/953/951/521/521/281/281/81/83/763/76
{2,5,8}\{2,5,8\}1/781/781/471/471/61/66/2056/2051/541/541/321/321/61/63/743/74
{1,5,9}\{1,5,9\}1/921/921/561/561/81/83/1223/1221/601/601/361/361/81/81/281/28

Table 1. Scores of the extensions to groups of the closeness centrality for selected groups from Figure 1. Both versions of the policy are considered. Shaded cells indicate the maximum over all three-node groups for the corresponding aggregation rule and policy.

In Example 1, we used the inclusive policy: a node (building) in which a new store is located also evaluates the group. This is reasonable in our setting: the residents’ access to stores still matters even when a store is located in their own building. The SUM aggregation uniquely selects the group {4,5,6}\{4,5,6\}, which minimizes the total distance from all nodes to the selected locations and thus maximizes the sum of evaluations. The evaluations of this group by nodes 1,…,91,\ldots,9 are (−12,−9,−6,−3,−2,−3,−6,−9,−12)(-12,-9,-6,-3,-2,-3,-6,-9,-12), which sum to −62-62 and yield a final score of 1/621/62 after conversion. The MIN aggregation also uniquely selects {4,5,6}\{4,5,6\}: each node evaluates the group by the negative of its distance to the farthest selected location. The resulting evaluations are (−5,−4,−3,−2,−1,−2,−3,−4,−5)(-5,-4,-3,-2,-1,-2,-3,-4,-5), which sum to −29-29 and yield a final score of 1/291/29. In contrast, the MAX aggregation uniquely selects {2,5,8}\{2,5,8\}, as each node evaluates the group by the negative of its distance to the closest selected location. Every node therefore evaluates this group as either 00 or −1-1: the evaluations are (−1,0,−1,−1,0,−1,−1,0,−1)(-1,0,-1,-1,0,-1,-1,0,-1), yielding a final score of 1/61/6. Finally, the PROP aggregation uniquely selects {3,5,7}\{3,5,7\}, which scores higher under this aggregation than either {4,5,6}\{4,5,6\} or {2,5,8}\{2,5,8\}. This aggregation accounts not only for the closest store but also for alternatives, with weights (1,1/2,1/3)(1,1/2,1/3) assigned in order of increasing distance. The evaluations of {3,5,7}\{3,5,7\} by consecutive nodes are (−6,−25/6,−7/3,−5/2,−5/3,−5/2,−7/3,−25/6,−6)(-6,-25/6,-7/3,-5/2,-5/3,-5/2,-7/3,-25/6,-6), which sum to −95/3-95/3 and yield a final score of 3/953/95.

Alternatively, we can use the exclusive policy, under which the selected nodes no longer evaluate the group. This may be appropriate if, for example, each selected building is entirely converted into a store and no residents remain there. Under this policy, SUM uniquely selects {3,5,7}\{3,5,7\}, with a final score of 1/521/52, while PROP uniquely selects {2,5,8}\{2,5,8\}, with a final score of 3/743/74. Both groups are more spread out than their respective optima under the inclusive policy. This change arises because we omit the evaluations contributed by the selected nodes, whose values depend on the distances between the selected locations. The MIN aggregation still uniquely selects {4,5,6}\{4,5,6\}, but its final score increases to 1/241/24. The scores under MAX remain unchanged for every group because each selected node has distance zero to the closest selected location and contributes 0.

Group Values

In this section, we explore the group centrality measures resulting from our framework and their relationships to existing measures.

Group degree centrality

According to Definition 1, each node ww outside the group SS assigns a score of 1 to its neighbors in SS and 0 to all other members of SS.

Under the SUM aggregation, all these evaluations are summed, so the resulting group value equals the number of edges between SS and V∖SV \setminus S. This corresponds to the size of the edge boundary of SS, used for example by Li et al. [29].

Under the MAX aggregation, a node ww evaluates the group SS by 1 if at least one of its neighbors belongs to SS, and by 0 otherwise. Hence, the group value equals the number of nodes outside the group that have at least one neighbor in the group. This corresponds to the unnormalized group degree centrality [16].

Under the MIN aggregation, a node ww evaluates the group by 1 only if all members of SS are its neighbors. Hence, the group value equals the number of common neighbors of all nodes in SS. This corresponds to the co-degree of SS, considered by Gerbner et al. [20].

Under the PROP aggregation, a node ww evaluates the group SS by the harmonic number Hk=∑i=1k1/iH_k = \sum_{i=1}^{k} 1/i, where kk is the number of its neighbors in SS and H0=0H_0=0. This corresponds to the PAV group centrality index of Laußmann et al. [28]. See Figure 4 for an example.

Group degree centrality evaluations of the group $S=\{1,3\}$

Figure 4. Group degree centrality evaluations of the group S={1,3}S=\{1,3\} under four aggregation rules. Under the exclusive policy, only nodes outside the group serve as evaluators. Each evaluator assesses both nodes in the group, and these evaluations are aggregated. Since no conversion is applied, the group centralities are the sums of the aggregated evaluations.

Group closeness centrality

According to Definition 2, each node outside a group SS evaluates each node in SS by the negative of the distance between them. The resulting group extensions correspond to the exclusive variants discussed in Example 2.

Under the SUM, MAX, and MIN aggregations, the group score is the reciprocal of the sum, over all nodes outside the group, of (1) the sum of distances to all group members, (2) the distance to the closest group member, and (3) the distance to the farthest group member, respectively. These definitions correspond, up to normalization, to the mean, minimum, and maximum variants of group closeness introduced by Everett and Borgatti [16]. Specifically, our SUM variant corresponds to the mean variant, but uses the sum of distances instead of their average over the group members. Our MAX variant corresponds to the minimum-distance variant, since maximizing the negative distance selects the closest group member. Conversely, our MIN variant corresponds to the maximum-distance variant.

The group score obtained under the PROP aggregation lies between those obtained under the SUM and MAX aggregations. All distances from nodes outside the group to its members contribute to the score, but larger distances receive progressively smaller weights.

Group betweenness centrality

According to Definition 3, each pair of distinct nodes s,ts,t outside a group SS evaluates a node v∈Sv \in S by the fraction of shortest paths between them that pass through vv. If no path connects ss and tt, the evaluation is zero.

Under the SUM aggregation, each pair sums its evaluations of all group members. Thus, for groups of fixed size, the group value is proportional to the expected number of group members encountered on a uniformly chosen shortest path between a uniformly chosen pair of distinct nodes outside SS.

Under the MAX\mathrm{MAX} aggregation, each pair retains only the highest evaluation. This means that for a fixed pair {s,t}\{s,t\}, only the largest fraction of shortest paths passing through a single group member is counted. Importantly, this is not necessarily the fraction of shortest paths passing through at least one group member, as different paths may pass through different members.

In turn, under the MIN\mathrm{MIN} aggregation, each pair retains the lowest evaluation. Hence, this evaluation is positive only if every group member lies on at least one shortest path between the evaluating pair, although not necessarily on the same path.

Similarly to group closeness, the group value obtained under the PROP\mathrm{PROP} aggregation lies between those obtained under SUM\mathrm{SUM} and MAX\mathrm{MAX}. It accounts for the contributions of all group members, but assigns progressively smaller weights to lower evaluations.

We note that these definitions differ from the classical group betweenness centrality of Everett and Borgatti [16], defined as FS(G)=∑{s,t}⊆V∖S, s≠tσst(S)σstF_S(G) = \sum_{\{s,t\}\subseteq V\setminus S,\ s\ne t} \frac{\sigma_{st}(S)}{\sigma_{st}}, where σst(S)\sigma_{st}(S) denotes the number of shortest paths between ss and tt that pass through at least one member of SS. This definition cannot be recovered from the above SPEC representation of betweenness centrality. The reason is that each evaluating pair assesses the members of SS separately, and therefore cannot determine whether different group members lie on the same shortest path or on different shortest paths. For example, the pair {1,6}\{1,6\} cannot distinguish between the groups {2,3}\{2,3\} and {2,4}\{2,4\} in Figure 1, even though only the second group intersects both shortest paths between nodes 11 and 66.

Nevertheless, a group measure inducing the same ranking as classical group betweenness can be obtained from a SPEC representation of endpoint-inclusive betweenness centrality, in which shortest paths, rather than pairs of nodes, serve as evaluators. Specifically, every subset of nodes is a potential evaluator, but its evaluation is non-zero only if it forms a shortest path. Since every shortest path in an undirected, unweighted graph is an induced path, its vertex set uniquely determines the path and its endpoints.

Formally, all subsets serve as evaluators (S(W)=2WS(W) = 2^W), the inclusive policy is used (P=PincP = P_{\mathrm{inc}}), and no conversion is required (c(r)=rc(r) = r). The evaluation eG(U,v)=1/σste_G(U,v) = 1/\sigma_{st} if UU is the vertex set of a shortest path with endpoints s,ts,t containing vv, and 00 otherwise. For individual nodes, this representation yields endpoint-inclusive betweenness centrality, which also counts shortest paths starting or ending at the evaluated node. Under the MAX\mathrm{MAX} aggregation, each shortest path contributes 1/σst1/\sigma_{st} if it contains at least one group member, and 00 otherwise. This definition differs from classical group betweenness by also counting shortest paths whose endpoints belong to the evaluated group. However, for connected graphs, these additional contributions depend only on the group size, so both measures induce the same ranking of groups of a fixed size.

Group PageRank centrality

According to Definition 4, each node w∈Vw \in V, including nodes in the group, evaluates a node v∈Sv \in S by the total weighted contribution of walks from ww to vv. This evaluation is proportional to personalized PageRank, which has been used in recommender systems and to measure influence [21, 13]. Thus, the evaluations can be interpreted as the relevance or influence of a node vv from the perspective of another node ww.

Under the SUM\mathrm{SUM} aggregation, the group value equals the sum of the individual PageRank scores, since the inclusive policy and identity conversion are used. Under the MAX\mathrm{MAX} aggregation, each evaluator retains only the highest evaluation of a group member. A group receives a high score when many nodes assign high relevance to at least one of its members. An equivalent approach, up to normalization, was used by Lindgren et al. [30].

Under the MIN\mathrm{MIN} aggregation, each evaluator retains only the lowest evaluation of a group member. Thus, a node assigns a high evaluation to a group only if it considers all group members highly relevant. Finally, under the PROP\mathrm{PROP} aggregation, all evaluations are aggregated in non-increasing order using harmonic weights. This models situations where having multiple relevant group members is beneficial, but additional members provide diminishing returns.

We note that the Group-PageRank measure [31] and several other group centrality measures can also be expressed within our framework; see Appendix § 11 for details.

Experiments

In this section, we illustrate how different group extensions of classical centrality measures behave. We consider four centrality measures: degree, closeness, betweenness, and PageRank with damping factor α=0.85\alpha= 0.85, with their SPEC representations defined in § 3. Each SPEC representation is extended to groups using the four aggregations: Sum, Min, Max, and Prop, resulting in sixteen group centrality measures.

To illustrate which nodes are selected in optimal groups, we generate 50-node graphs by first sampling node positions and then connecting pairs of nodes whose Euclidean distance is below a given threshold dd. We consider the square [−5,5]2[-5, 5]^2 and sample node positions according to three different spatial distributions. Any point generated outside the square is moved to the closest point within the square. Since closeness centrality is defined only for connected graphs, we discard any generated graph that is disconnected.

For each of the sixteen group centrality measures and each spatial distribution, we compute an optimal group of size kk and mark its nodes in green. We repeat this procedure for 1000 randomly generated graphs and superimpose the selected nodes.

The results are presented in Figure 5.

Figure 5. Spatial distributions of nodes selected in optimal groups for three random geometric graph models: Circle, Two circles, and Rectangle. For each model, the panels show the locations of nodes selected in optimal groups across 1000 randomly generated graphs, with darker regions indicating more frequent selection. Rows correspond to the underlying centrality measures (degree, closeness, betweenness, and PageRank), while columns correspond to the four aggregation rules (Sum, Min, Max, and Prop). The bottom-left panel for each model shows the underlying spatial distribution of all nodes for comparison.

Circle

In the first spatial distribution, both coordinates of each node are independently drawn from a Gaussian distribution N(0,1.5)\mathcal{N}(0, 1.5), producing a roughly circular cloud of nodes. Two nodes are connected by an edge if their Euclidean distance is at most d=1.5d = 1.5. The size of the optimal group is k=4k = 4.

We observe that the Max aggregation produces more spatially dispersed selections than the other aggregations for all four centrality measures, favoring groups in which each node in the graph has a selected node nearby. Interestingly, for degree and closeness centralities, this happens even at the expense of selecting nodes near the center, leaving a visible gap around the origin. For PageRank, nodes near the periphery are also selected relatively frequently. This may be partially explained by the influence of leaf nodes, which transfer their entire PageRank contribution to their only neighbor. In contrast, the Sum and Min aggregations predominantly select nodes near the center, with a noticeably wider spread for betweenness centrality. The Prop aggregation generally produces an intermediate pattern between Sum and Max: it still favors central nodes but also selects nodes farther from the center.

Two circles

In the second spatial distribution, three quarters of the nodes (rounded up) have both coordinates independently drawn from N(−1.5,1)N(-1.5, 1). The remaining nodes have both coordinates drawn from N(1.5,1)N(1.5, 1). This produces two roughly circular clouds of nodes, one containing approximately three times as many nodes as the other. As before, two nodes are connected by an edge if their Euclidean distance is at most d=1.5d = 1.5, and the size of groups is k=4k = 4.

For degree, closeness, and PageRank centralities, the Sum and Min aggregations select nodes almost exclusively from the larger cloud, where the most central nodes are concentrated. In particular, for closeness under Min, selecting nodes from both clouds can significantly decrease the score, as nodes in the larger cloud must then account for the distance to a distant group member. Under the Prop aggregation, some selected nodes also come from the smaller cloud, with closeness centrality showing a visible tendency to select nodes in the region connecting the two clouds. As in the single-circle case, the Max aggregation favors more dispersed selections, leaving a gap near the center of the larger cloud. For betweenness centrality, all four aggregations concentrate on nodes connecting the two clouds, with Max selecting more nodes from the larger cloud.

Rectangle

In the third spatial distribution, node coordinates are drawn uniformly from the rectangle [−5,5]×[−2,2][-5, 5] \times[-2, 2]. Two nodes are connected by an edge if their Euclidean distance is at most d=1d = 1, and groups of size k=3k = 3 are selected.

We observe that the results for closeness centrality resemble those from Example 1, with Sum and Min favoring nodes near the center, Max selecting three widely separated nodes, and Prop producing an intermediate arrangement. For PageRank, nodes near the ends of the rectangle are selected more frequently, particularly under the Max and Prop aggregations. This may be partially explained by the influence of leaf nodes, which can increase the PageRank of their neighbors. For example, in a path graph, the nodes adjacent to the endpoints have the highest PageRank. In contrast, for betweenness centrality, selected nodes are more concentrated near the center of the rectangle. For degree centrality, the averaged distributions resemble those for closeness, but this similarity is largely due to averaging over multiple graph instances: in individual graphs, selected nodes tend to be clustered together.

Conclusions

We developed a general framework for extending centrality measures to groups. We proposed four extensions of each measure based on different ways of aggregating evaluations: Sum, Max, Min, and Proportional. The framework builds on a new unified representation of classical centrality measures, which we call the SPEC representation. Our experimental analysis showed that different variants capture different notions of an optimal group.

Our work opens up several directions for future research. It would be interesting to study the SPEC representation axiomatically and characterize existing classes of centrality measures through restrictions on its components. Extending existing axiomatic characterizations to group centrality measures could also shed new light on their behavior. Finally, evaluating the proposed group centrality measures in real-world applications and assessing their practical usefulness would be a valuable next step.

Acknowledgments

This work was supported by the Polish National Science Centre Grants No. 2018/31/B/ST6/03201 and 2023/50/E/ST6/00665.

SPEC Representations of Centrality Measures

The node centrality induced by a SPEC representation R=(S,P,e,c)\mathcal{R} = (S, P, e, c) is defined as

FvR(G)=c(∑U∈S(V∖P({v}))eG(U,v))F_v^{\mathcal{R}}(G) = c\left(\sum_{U \in\mathcal{S}(V \setminus P(\{v\}))} e_G(U,v)\right)

for every graph G=(V,E)G = (V, E) and node v∈Vv \in V. In the following representations, we specify the evaluation function only for the subsets selected by the selector; for all other subsets, its value is set to zero.

Degree centrality admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=1e_G(\{w\}, v) = 1 if {w,v}∈E\{w,v\} \in E, and 00 otherwise (node vv receives 1 from each neighbor and 0 from every other node);

  • c(r)=rc(r) = r (no conversion).

Distance-based centralities

Closeness centrality [3] for connected graphs with at least two nodes admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=−dist⁡(w,v)e_G(\{w\}, v) = -\operatorname{dist}(w,v) (node ww evaluates node vv by the negative of the distance between them);

  • c(r)=−1/rc(r) = -1/r (converts the negative sum of distances into the reciprocal of their sum).

Harmonic centrality [36] admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=1/dist⁡(w,v)e_G(\{w\}, v) = 1/\operatorname{dist}(w,v), with 1/∞=01/\infty= 0 (node ww evaluates node vv by the reciprocal of the distance between them);

  • c(r)=rc(r) = r (no conversion).

Decay centrality [22] with α∈(0,1)\alpha\in(0,1) admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=αdist⁡(w,v)e_G(\{w\}, v) = \alpha^{\operatorname{dist}(w,v)}, with α∞=0\alpha^\infty= 0 (node ww evaluates node vv by raising α\alpha to the power of the distance between them);

  • c(r)=rc(r) = r (no conversion).

kk-step reach centrality [10] with k≥1k \ge1 admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\}: w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=1e_G(\{w\}, v) = 1 if dist⁡(w,v)≤k\operatorname{dist}(w,v) \le k, and 00 otherwise (node ww assigns 1 to nodes at distance at most kk and 0 to all other nodes);

  • c(r)=rc(r) = r (no conversion).

Medial centralities

Betweenness centrality [18] admits the following SPEC representation:

  • S(W)={{s,t}⊆W:s≠t}S(W) = \{\{s,t\} \subseteq W : s \ne t\} (pairs of distinct nodes serve as evaluators);

  • P=PexcP = P_{exc} (pairs containing the evaluated node are excluded);

  • eG({s,t},v)=σst(v)σste_G(\{s,t\},v) = \frac{\sigma_{st}(v)}{\sigma_{st}} if σst>0\sigma_{st} > 0, and 00 otherwise (a pair of nodes s,ts,t evaluates node vv by the proportion of shortest paths between them that pass through vv);

  • c(r)=rc(r) = r (no conversion).

Stress centrality [39] admits the following SPEC representation:

  • S(W)={{s,t}⊆W:s≠t}S(W) = \{\{s,t\} \subseteq W : s \ne t\} (pairs of distinct nodes serve as evaluators);

  • P=PexcP = P_{exc} (pairs containing the evaluated node are excluded);

  • eG({s,t},v)=σst(v)e_G(\{s,t\},v) = \sigma_{st}(v) (a pair of nodes s,ts,t evaluates node vv by the number of shortest paths between them that pass through vv);

  • c(r)=rc(r) = r (no conversion).

Flow betweenness centrality [19] admits the following SPEC representation:

  • S(W)={{s,t}⊆W:s≠t}S(W) = \{\{s,t\} \subseteq W : s \ne t\} (pairs of distinct nodes serve as evaluators);

  • P=PexcP = P_{exc} (pairs containing the evaluated node are excluded);

  • eG({s,t},v)=flow⁡s,t(G)−flow⁡s,t(G−v)e_G(\{s,t\},v) = \operatorname{flow}_{s,t}(G)-\operatorname{flow}_{s,t}(G-v) (a pair of nodes s,ts,t evaluates node vv by the reduction in the maximum flow between them caused by removing vv);

  • c(r)=rc(r) = r (no conversion).

Here, flow⁡s,t(G)\operatorname{flow}_{s,t}(G) denotes the maximum number of pairwise edge-disjoint paths between ss and tt.

Random-walk counting betweenness centrality [5] admits the following SPEC representation for connected graphs with at least two nodes:

  • S(W)={{s,t}⊆W:s≠t}S(W) = \{\{s,t\} \subseteq W : s \ne t\} (pairs of distinct nodes serve as evaluators);

  • P=PincP = P_{inc} (pairs {s,t}\{s,t\} may contain node vv);

  • eG({s,t},v)=1∣V∣(∣V∣−1)∑k=0∞(P(ωs,t(k)=v)+P(ωt,s(k)=v))e_G(\{s,t\},v) = \frac{1}{|V|(|V|-1)} \sum_{k=0}^{\infty} \left(\mathbb{P}(\omega_{s,t}(k)=v) + \mathbb{P}(\omega_{t,s}(k)=v)\right), where ωs,t(k)\omega_{s,t}(k) denotes the position at step kk of a random walk starting at ss that ends when entering tt (a pair of nodes s,ts,t evaluates node vv by the normalized expected total number of visits to vv during random walks in both directions);

  • c(r)=rc(r) = r (no conversion).

Feedback centralities

Beta measure [44] admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\} : w \in W\} (individual nodes serve as evaluators);

  • P=PexcP = P_{exc} (a node does not evaluate itself);

  • eG({w},v)=1/deg⁡(w)e_G(\{w\},v) = 1/\deg(w) if {w,v}∈E\{w,v\} \in E, and 00 otherwise (node vv receives 1/deg⁡(w)1/\deg(w) from each neighbor and 0 from every other node);

  • c(r)=rc(r) = r (no conversion).

Eigenvector centrality [7] for connected graphs admits the following SPEC representation:

  • S(W)={{w}:w∈W}S(W) = \{\{w\} : w \in W\} (individual nodes serve as evaluators);

  • P=PincP = P_{inc} (a node also evaluates itself);

  • eG({w},v)=1∣V∣lim⁡K→∞1K∑k=0K−1∑(u0,…,uk)∈Ω(G)u0=w, uk=v(1/λ)ke_G(\{w\},v)=\frac{1}{|V|}\lim_{K\to\infty}\frac{1}{K}\sum_{k=0}^{K-1}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_0=w,\ u_k=v}}(1/\lambda)^k (node ww evaluates node vv by the total weighted contribution of walks from ww to vv);

  • c(r)=rc(r)=r (no conversion).

Seeley index [38] for connected graphs with at least two nodes admits the following SPEC representation:

  • S(W)={{w}:w∈W}\mathcal{S}(W)=\{\{w\}:w\in W\} (individual nodes serve as evaluators);

  • P=PincP=P_{\mathrm{inc}} (a node also evaluates itself);

  • eG({w},v)=1∣V∣lim⁡K→∞1K∑k=0K−1∑(u0,…,uk)∈Ω(G)u0=w, uk=v1∏i=0k−1deg⁡(ui)e_G(\{w\},v)=\frac{1}{|V|}\lim_{K\to\infty}\frac{1}{K}\sum_{k=0}^{K-1}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_0=w,\ u_k=v}}\frac{1}{\prod_{i=0}^{k-1}\deg(u_i)} (node ww evaluates node vv by its limiting average contribution of weighted walks from ww to vv);

  • c(r)=rc(r)=r (no conversion).

For undirected connected graphs, the Seeley index is equivalent to normalized degree centrality. We include its walk-based representation because it naturally extends to directed graphs.

Katz centrality [23] with parameters α∈(0,1/λ(G))\alpha\in(0,1/\lambda(G)) and b>0b>0 admits the following SPEC representation:

  • S(W)={{w}:w∈W}\mathcal{S}(W)=\{\{w\}:w\in W\} (individual nodes serve as evaluators);

  • P=PincP=P_{\mathrm{inc}} (a node also evaluates itself);

  • eG({w},v)=b∑k=0∞∑(u0,…,uk)∈Ω(G)u0=w, uk=vαke_G(\{w\},v)=b\sum_{k=0}^{\infty}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_0=w,\ u_k=v}}\alpha^k (node ww evaluates node vv by the total weighted contribution of walks from ww to vv);

  • c(r)=rc(r)=r (no conversion).

PageRank [34] with damping factor α∈(0,1)\alpha\in(0,1), for graphs without isolated nodes, admits the following SPEC representation:

  • S(W)={{w}:w∈W}\mathcal{S}(W)=\{\{w\}:w\in W\} (individual nodes serve as evaluators);

  • P=PincP=P_{\mathrm{inc}} (a node also evaluates itself);

  • eG({w},v)=1−α∣V∣∑k=0∞∑(u0,…,uk)∈Ω(G)u0=w, uk=vαk∏i=0k−1deg⁡(ui)e_G(\{w\},v)=\frac{1-\alpha}{|V|}\sum_{k=0}^{\infty}\sum_{\substack{(u_0,\ldots,u_k)\in\Omega(G)\\u_0=w,\ u_k=v}}\frac{\alpha^k}{\prod_{i=0}^{k-1}\deg(u_i)} (node ww evaluates node vv by the total weighted contribution of walks from ww to vv);

  • c(r)=rc(r)=r (no conversion).

Vitality indices

Attachment centrality [42] admits the following SPEC representation:

  • S(W)=2W\mathcal{S}(W)=2^W (all subsets of nodes serve as evaluators);

  • P=PincP=P_{\mathrm{inc}} (evaluators containing the evaluated node are allowed, but their evaluations are set to zero);

  • eG(U,v)=2β(∣V∣,∣U∣)(∣K(G[U])∣−∣K(G[U∪{v}])∣+1)e_G(U,v)=2\beta(|V|,|U|)(|K(G[U])|-|K(G[U\cup\{v\}])|+1) if v∉Uv\notin U, and 00 otherwise (group UU evaluates node vv by its weighted contribution to connecting components of G[U]G[U]);

  • c(r)=rc(r)=r (no conversion).

Here, β(n,k)=k!(n−k−1)!/n!\beta(n,k)=k!(n-k-1)!/n! for 0≤k<n0\leq k<n, and K(H)K(H) denotes the set of connected components of graph HH.

Group centralities in SPEC Representation

In this section we describe how existing values from the literature fit within our framework.

Group-PageRank [31], assuming the target set T=V\mathcal{T}=V, admits the following SPEC representation with SUM aggregation:

  • S(W)={∅}∪{{w}:w∈W}\mathcal{S}(W)=\{\varnothing\}\cup\{\{w\}:w\in W\} (the empty set and all singletons serve as evaluators);

  • P=PexcP=P_{\mathrm{exc}} (group nodes do not evaluate each other);

  • eG({w},v)=α∣V∣PRw(G)(1−α)deg⁡(w)e_G(\{w\},v)=\frac{\alpha|V|\mathrm{PR}_w(G)}{(1-\alpha)\deg(w)} if {w,v}∈E\{w,v\}\in E and 0 otherwise, eG(∅,v)=1e_G(\varnothing,v)=1 (singletons contribute their appropriately scaled PageRank worth to their neighbors and the empty set always contributes 1, adding S\mathcal{S} to the final value);

  • c(r)=rc(r)=r (no conversion).

Here α\alpha is the damping factor of Group-PageRank, and PRw(G)\mathrm{PR}_w(G) denotes the single-node PageRank value with damping factor α\alpha of node ww.

Co-betweenness [25] admits the following SPEC representation with MIN aggregation:

  • S(W)=2W\mathcal{S}(W)=2^W (all subsets of nodes serve as evaluators);

  • P=PincP=P_{\mathrm{inc}} (subsets containing nodes from the group also evaluate);

  • eG(U,v)=1σsUtUe_G(U,v)=\frac{1}{\sigma_{s_Ut_U}} if U∈UGU\in\mathcal{U}_G, v∈Uv\in U, v≠sUv\ne s_U and v≠tUv\ne t_U and 0 otherwise (paths contribute one over the number of shortest paths between their ends if the node is on the path but not on its endpoints);

  • c(r)=rc(r)=r (no conversion).

In undirected graphs with positive edge weights and no multi-edges, shortest paths up to reversal are uniquely determined by their node sets. This is because its endpoints are the unique farthest pair in the set, and distances from either endpoint determine the order of its nodes. Here, UG\mathcal{U}_G is the family of these node sets, and sU,tUs_U,t_U denote start and end of the path associated with U∈UGU\in\mathcal{U}_G.

M-reach [8] admits the following SPEC representation with MAX aggregation:

  • S(W)={{w}:w∈W}\mathcal{S}(W)=\{\{w\}:w\in W\} (singletons serve as evaluators);

  • P=PexcP=P_{\mathrm{exc}} (group nodes do not assess each other);

  • eG({w},v)=1e_G(\{w\},v)=1 if dist⁡(w,v)≤m\operatorname{dist}(w,v)\le m and 0 otherwise (node vv receives 1 from all nodes not further than mm);

  • c(r)=rc(r)=r (no conversion).

Here, mm is a parameter of the value.

References

  1. [1]Réka Albert, Hawong Jeong, and Albert-László Barabási. 2000. Error and attack tolerance of complex networks. Nature 406, 6794 (2000), 378–382.
  2. [2]Fabrizio Altarelli, Alfredo Braunstein, Luca Dall’Asta, Joseph Rushton Wakeling, and Riccardo Zecchina. 2014. Containing epidemic outbreaks by message-passing techniques. Physical Review X 4, 2 (2014), 021024.DOI
  3. [3]Alex Bavelas. 1948. A mathematical model for group structures. Human organization 7, 3 (1948), 16–30.DOI
  4. [4]Francis Bloch, Matthew O Jackson, and Pietro Tebaldi. 2023. Centrality measures in networks. Social Choice and Welfare 61, 2 (2023), 413–453.
  5. [5]Florian Blöchl, Fabian J. Theis, Fernando Vega-Redondo, and Eric O’N. Fisher. 2011. Vertex centralities in input-output networks reveal the structure of modern economies. Physical Review E 83, 4 (2011), 046127.pubmed.ncbi.nlm.nih.gov/21599260
  6. [6]Paolo Boldi, Flavio Furia, and Chiara Prezioso. 2025. Linear geometric centralities. In International Workshop on Modelling and Mining Networks. Springer, 1–16.DOI
  7. [7]Phillip Bonacich. 1972. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology 2, 1 (1972), 113–120.DOI
  8. [8]Stephen P. Borgatti. 2006. Identifying sets of key players in a social network. Computational & Mathematical Organization Theory 12, 1 (2006), 21–34.DOI
  9. [9]Stephen P. Borgatti and Martin G. Everett. 2006. A graph-theoretic perspective on centrality. Social Networks 28(4) (2006), 466–484.DOI
  10. [10]Stephen P. Borgatti, Martin G. Everett, and Jeffrey C Johnson. 2013. Analyzing Social Networks. SAGE Publications Limited.
  11. [11]Ulrik Brandes. 2008. On variants of shortest-path betweenness centrality and their generic computation. Social Networks 30, 2 (2008), 136–145.DOI
  12. [12]Ulrik Brandes and Thomas Erlebach. 2005. Network analysis: Methodological foundations. Springer-Verlag.
  13. [13]Marco Bressan, Stefano Leucci, Alessandro Panconesi, Prabhakar Raghavan, and Erisa Terolli. 2016. The limits of popularity-based recommendations, and the role of social ties. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 745–754.DOI
  14. [14]Yiping Chen, Gerald Paul, Shlomo Havlin, Fredrik Liljeros, and H Eugene Stanley. 2008. Finding a better immunization strategy. Physical Review Letters 101, 5 (2008), 058701.pubmed.ncbi.nlm.nih.gov/18764435
  15. [15]Reuven Cohen, Keren Erez, Daniel Ben-Avraham, and Shlomo Havlin. 2001. Breakdown of the internet under intentional attack. Physical Review Letters 86, 16 (2001), 3682.DOI
  16. [16]Martin G. Everett and Stephen P. Borgatti. 1999. The centrality of groups and classes. Journal of Mathematical Sociology 23, 3 (1999), 181–201.DOI
  17. [17]Martin G. Everett and Stephen P. Borgatti. 2010. Induced, endogenous and exogenous centrality. Social Networks 32, 4 (2010), 339–344.DOI
  18. [18]Linton C. Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1 (1977), 35–41.DOI
  19. [19]Linton C. Freeman, Stephen P. Borgatti, and Douglas R. White. 1991. Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks 13, 2 (1991), 141–154.DOI
  20. [20]Dániel Gerbner, Zoltán Lóránt Nagy, and Máté Vizer. 2022. Unified approach to the generalized Turán problem and supersaturation. Discrete Mathematics 345, 3 (2022), 112743.DOI
  21. [21]Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. 2013. WTF: The who to follow service at twitter. In Proceedings of the 22nd International Conference on World Wide Web (WWW). ACM, 505–514.
  22. [22]Matthew O. Jackson. 2005. A survey of network formation models: stability and efficiency. In Group Formation in Economics: Networks, Clubs, and Coalitions. Cambridge University Press: Cambridge, MA, USA, 11–49.
  23. [23]Leo Katz. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1 (1953), 39–43.DOI
  24. [24]Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Ley Muchnik, H Eugene Stanley, and Hernán A Makse. 2010. Identification of influential spreaders in complex networks. Nature physics 6, 11 (2010), 888–893.
  25. [25]Eric D. Kolaczyk, David B. Chua, and Marc Barthélémy. 2009. Group betweenness and co-betweenness: Inter-related notions of coalition centrality. Social Networks 31, 3 (2009), 190–203.DOI
  26. [26]Natalia Kucharczuk and Oskar Skibski. 2026. Group Vitality Indices: Axioms and Algorithms. In Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI). 3461–3469.arxiv.org/abs/2605.09791
  27. [27]Martin Lackner and Piotr Skowron. 2023. Multi-winner voting with approval preferences. Springer Nature.
  28. [28]Christian Laußmann, Katharina Volz, Ulrik Brandes, and Jörg Rothe. 2026. Voting for centrality. Computational and Mathematical Organization Theory 32, 3 (2026), 23.
  29. [29]Yixin Li, Yiqiang Sheng, and Xiaozhou Ye. 2020. Group centrality algorithms based on the h-index for identifying influential nodes in large-scale networks. Int. J. Innovative Comput. Inf. Control 16, 4 (2020), 1183–1201.
  30. [30]Erik Lindgren, Shanshan Wu, and Alexandros G Dimakis. 2016. Leveraging sparsity for efficient submodular data summarization. Advances in Neural Information Processing Systems 29 (2016).arxiv.org/abs/1703.02690
  31. [31]Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. 2014. Influence maximization over large-scale social networks: A bounded linear approach. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. 171–180.DOI
  32. [32]Flaviano Morone and Hernán A Makse. 2015. Influence maximization in complex networks through optimal percolation. Nature 524, 7563 (2015), 65–68.DOI
  33. [33]Mark E. J. Newman. 2005. A measure of betweenness centrality based on random walks. Social Networks 27, 1 (2005), 39–54.
  34. [34]Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. Technical Report. Stanford InfoLab.
  35. [35]Georgios Papasotiriopoulos, Oskar Skibski, Piotr Skowron, and Tomasz Wąs. 2026. Proportional Selection in Networks. In Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI). 3514–3522. doi:10.24963/ijcai.2026/391
  36. [36]Yannick Rochat. 2009. Closeness centrality extended to unconnected graphs: The harmonic centrality index. In ASNA.
  37. [37]Carla Sciarra, Guido Chiarotti, Francesco Laio, and Luca Ridolfi. 2018. A change of perspective in network centrality. Scientific reports 8, 1 (2018), 15269.arxiv.org/abs/1805.08740
  38. [38]John R Seeley. 1949. The net of reciprocal influence. a problem in treating sociometric data. Canadian Journal of Experimental Psychology 3 (1949), 234.DOI
  39. [39]Alfonso Shimbel. 1953. Structural parameters of communication networks. Bulletin of Mathematical Biophysics 15, 4 (1953), 501–507.DOI
  40. [40]Oskar Skibski. 2021. Vitality Indices are Equivalent to Induced Game-Theoretic Centralities. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), Zhi-Hua Zhou (Ed.). 398–404.DOI
  41. [41]Oskar Skibski. 2023. Closeness centrality via the Condorcet principle. Social Networks 74 (2023), 13–18.arxiv.org/abs/2112.00494
  42. [42]Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. 2019. Attachment centrality: Measure for connectivity in networks. Artificial Intelligence 274 (2019), 151–179.DOI
  43. [43]Oskar Skibski and Jadwiga Sosnowska. 2018. Axioms for Distance-Based Centralities. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI). 1218–1225.
  44. [44]René van den Brink and Robert P. Gilles. 1994. A social power index for hierarchically structured populations of economic agents. In Imperfections and Behavior in Economic Organizations. Springer, 279–318.
  45. [45]Tomasz Wąs and Oskar Skibski. 2021. An Axiom System for Feedback Centralities. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), Zhi-Hua Zhou (Ed.). 443–449.arxiv.org/abs/2105.03146

Paper details

vlnc:W_3mufykj9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents