Group centrality · Lablypedia

Related on Lably

Through Heuristic, Degree (graph theory) and Graph (discrete mathematics)

Lab · Class 11Psychology Experiments Lab · Class 6–12Graphic Design Lab · Class 6–12Data Visualization Lab Lab · Class 8–9Introduction to Graphs

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.

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) = | ⋃_{v \in S} N (v) ∖ 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.

5 more chapters are free with a Lably account.

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} dist (v, S)}

where

dist (v, S) := min_{u \in S} 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} 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 \neq v \neq t \in V} \frac{σ_{s t} (S)}{σ_{s t}}

where $σ_{s t}$ is the total number of $s$ - $t$ paths and $σ_{s t} (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_{C F} (S) = \frac{n}{\sum_{u \in V} v_{u S} (u)}

where $v_{u S} (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

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{matrix} max & \sum_{v \in V} y_{v} \\ s. t. & \sum_{v \in V} x_{v} = k \\ \forall v \in V : {\begin{cases} x_{v} + y_{v} \leq 1 \\ y_{v} \leq \sum_{u \in N (v)} x_{u} \\ x_{v}, y_{v} \in {0, 1} \end{cases} \end{matrix}

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) ∖ S |$ , where $S = {v \in V ∣ 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.

<span id="mwug"></span><span class="linenos" data-line="1" id="mwuw"></span><span class="w" id="mwvA"> </span><span class="k" id="mwvQ">function</span><span class="w" id="mwvg"> </span><span class="n" id="mwvw">greedy</span><span class="p" id="mwwA">(</span><span class="n" id="mwwQ">G</span><span class="w" id="mwwg"> </span><span class="p" id="mwww">:</span><span class="w" id="mwxA"> </span><span class="n" id="mwxQ">graph</span><span class="p" id="mwxg">,</span><span class="w" id="mwxw"> </span><span class="n" id="mwyA">k</span><span class="w" id="mwyQ"> </span><span class="p" id="mwyg">:</span><span class="w" id="mwyw"> </span><span class="n" id="mwzA">positive</span><span class="w" id="mwzQ"> </span><span class="n" id="mwzg">integer</span><span class="p" id="mwzw">):</span> <span class="linenos" data-line="2" id="mw0A"></span><span class="w" id="mw0Q"> </span><span class="n" id="mw0g">S</span><span class="w" id="mw0w"> </span><span class="err" id="mw1A">←</span><span class="w" id="mw1Q"> </span><span class="p" id="mw1g">{}</span> <span class="linenos" data-line="3" id="mw1w"></span><span class="w" id="mw2A"> </span><span class="k" id="mw2Q">while</span><span class="w" id="mw2g"> </span><span class="p" id="mw2w">|</span><span class="n" id="mw3A">S</span><span class="p" id="mw3Q">|</span><span class="w" id="mw3g"> </span><span class="p" id="mw3w"><</span><span class="w" id="mw4A"> </span><span class="n" id="mw4Q">k</span><span class="w" id="mw4g"> </span><span class="k" id="mw4w">do</span><span class="p" id="mw5A">:</span> <span class="linenos" data-line="4" id="mw5Q"></span><span class="w" id="mw5g"> </span><span class="n" id="mw5w">v</span><span class="w" id="mw6A"> </span><span class="err" id="mw6Q">←</span><span class="w" id="mw6g"> </span><span class="n" id="mw6w">vertex</span><span class="w" id="mw7A"> </span><span class="n" id="mw7Q">maximizing</span><span class="w" id="mw7g"> </span><span class="n" id="mw7w">centrality</span><span class="w" id="mw8A"> </span><span class="n" id="mw8Q">of</span><span class="w" id="mw8g"> </span><span class="n" id="mw8w">S</span><span class="w" id="mw9A"> </span><span class="err" id="mw9Q">∪</span><span class="w" id="mw9g"> </span><span class="p" id="mw9w">{</span><span class="n" id="mw-A">v</span><span class="p" id="mw-Q">}</span> <span class="linenos" data-line="5" id="mw-g"></span><span class="w" id="mw-w"> </span><span class="n" id="mw_A">S</span><span class="w" id="mw_Q"> </span><span class="err" id="mw_g">←</span><span class="w" id="mw_w"> </span><span class="n" id="mwAQA">S</span><span class="w" id="mwAQE"> </span><span class="err" id="mwAQI">∪</span><span class="w" id="mwAQM"> </span><span class="p" id="mwAQQ">{</span><span class="n" id="mwAQU">v</span><span class="p" id="mwAQY">}</span> <span class="linenos" data-line="6" id="mwAQc"></span><span class="w" id="mwAQg"> </span><span class="k" id="mwAQk">return</span><span class="w" id="mwAQo"> </span><span class="n" id="mwAQs">S</span>

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.