Group centrality

Template:Network Science In graph theory and network analysis, group centrality generalizes the concept of centrality to sets of nodes in a network. Introduced by Everett and Borgatti in 1999, group centrality measures are intended to lift the restriction of usual centrality measures only applying to individual nodes. For instance, the analysis of the centrality or marginalization of certain groups in the network of an organization can be enabled by group centrality measures.

One complication when searching for groups of a given size $k$ with maximum group centrality arises from the fact that for many measures, this problem is NP-hard. Therefore, heuristics and approximation algorithms are typically used in practical applications.

Groups with maximum group degree centrality (left), group closeness (middle), and group betweenness (right) marked in red, for $k=3$.

Group degree centrality

In analogy to the conceptually simple degree centrality, which measures the degree of a node, the group degree centrality of a group $S$ of nodes is simply defined as the number of non-group nodes adjacent to nodes in $S$. Formally, the group degree centrality $C_D(S)$ of a group $S\subseteq V$ of a given graph $G=(V,E)$ is defined as

$C_D(S)=|\bigcup _{v\in S}N(v)\setminus S|$

When the size $k$ is part of the input, the problem of determining a set $S$ of size $k$ with maximum group degree centrality is NP-hard.

Group closeness centrality

In a connected graph, the normalized group closeness centrality (or group closeness) of a group is the reciprocal of the average length of the shortest path between the group and all other nodes in the graph. More precisely, the group closeness centrality $C(S)$ of a group $S\subseteq V$ in a connected graph $G=(V,E)$ is defined as

$C(S)=\frac{|V|-|S|}{\sum _{v\in V}\text{dist}(v,S)}$,

where

$\text{dist}(v,S):=\underset{u\in S}{min}\text{dist}(v,u)$

denotes the distance of $v$ to $S$, that is, the distance to the closest node in $S$. Hence, just like Closeness centrality, this measure can be regarded as the normalized variant of the reciprocal of a farness measure, which for the group case is given as $f(S)={\sum }_{v\in V}\text{dist}(v,S)$.

The problem of finding a group $S$ of given size $k$ with maximum group closeness is NP-hard.

Group betweenness centrality

Group betweenness centrality is the generalization of betweenness centrality and similarly quantifies the number of times group nodes act as a bridge along the shortest path between two other nodes. Formally, for a graph $G=(V,E)$ it is defined as

$C_B(S)=\sum _{s\ne v\ne t\in V}\frac{{\sigma }_{st}(S)}{{\sigma }_{st}}$

where ${\sigma }_{st}$ is the total number of $s$-$t$ paths and ${\sigma }_{st}(S)$ is the number of $s$-$t$ paths passing through $S$. Analagously to individual betweenness, group betweenness may be normalized by dividing through the number of pairs of nodes not including the group $S$, which for directed graphs is $(n-|S|)(n-|S|-1)$ and for undirected graphs is $\frac{1}{2}(n-|S|)(n-|S|-1)$, where $n=|V|$.

Finding the group $S$ of a given size $k$ with maximum group betweenness is NP-hard.

Group current flow closeness centrality

Group current flow closeness centrality generalizes current flow closeness of individual nodes. Unlike conventional (group) closeness, current flow closeness not only considers the length, but also the number of shortest paths by treating the graph as a resistor network and considering current flow in this network, rather than shortest paths. Let $G=(V,E)$ be a graph (representing a resistor network with edge resistances) and $S\subseteq V$. Then formally, group current flow closeness is defined as

$C_{CF}(S)=\frac{n}{\sum _{u\in V}{v}_{uS}(u)}$,

where $v_{uS}(u)$ is the voltage of $u$ when a unit current enters $G$ at $u$ and leaves it at $S$.

The maximization problem is NP-hard.

Other group centrality measures

• Group eigenvector centrality
• Group harmonic centrality
• GED-Walk centrality

Algorithms

Result of the greedy algorithm on the Tutte graph for $k=1,\mathrm{...},5$ for group degree centrality (top), group closeness (middle), and group betweenness (bottom). Note how the result of the greedy algorithm for any $k$ is a subset of the solution for $k+1$. Since the Tutte graph is regular, every 2-independent set, i.e., a set where nodes are at least distance three apart, is a maximum degree centrality group.

For many group centrality measures, the problem of finding a group of a given size with maximum centrality can be formulated as an integer linear program. For example, consider the following integer linear program for group degree centrality maximization:

$\begin{array}{cc}\text{max}& \sum _{v\in V}{y}_v\\ \text{s. t.}& \sum _{v\in V}{x}_v=k\\ & \mathrm{\forall }v\in V:\{\begin{array}{c}{x}_v+y_v\le 1\\ y_v\le \sum _{u\in N(v)}{x}_u\\ x_v,y_v\in \{0,1\}\end{array}\end{array}$

Here, the $x_v$ variables indicate whether $v$ is in the group, while the $y_v$ variables indicate if $v$ is a non-group neighbor. Thus, the objective function corresponds to $C_D(S)=|N(S)\setminus S|$, where $S=\{v\in V\mid x_v=1\}$. This objective is maximized under the constraint $|S|={\sum }_{v\in V}{x}_v=k$, as required.

Since it is NP-hard for many group centrality measures to find a subset $S\subseteq V$ of the vertices of a graph $G=(V,E)$ with $|S|=k$ that maximizes the centrality of $S$, numerous heuristics and approximation algorithms have been proposed. One widely used greedy algorithm can be expressed as follows in pseudocode.

 function greedy(G : graph, k : positive integer):
     S ← {}
     while |S| < k do:
          v ← vertex maximizing centrality of S ∪ {v}
          S ← S ∪ {v}
     return S

Note how the vertex chosen in line 4 is not necessarily uniquely determined, and therefore neither is the result of the greedy algorithm.

For non-negative monotone submodular set functions, such as GED-Walk centrality, this greedy algorithm is already guaranteed to yield a $(1-1/e)$-approximation. For other measures like group closeness, which do not satisfy submodularity, this algorithm can still be a useful heuristic.

Implementations

The software library NetworkX supports the evaluation of group degree centrality, group closeness and group betweenness, as well as obtaining the most prominent group with respect to group betweenness centrality.

The network analysis toolkit NetworKit supports the evaluation and maximization of group degree centrality, group closeness, group harmonic centrality, group betweenness and more.

See also

• Centrality
• Core–periphery structure
• Distance in graphs

Further reading

• Carrington PJ, Scott J, Wasserman S, eds. Models and Methods in Social Network Analysis, pp. 57–76, Cambridge University Press; 2005.