Network centrality네트워크 중심도

How close is a node to everyone else?

Degree is the simplest centrality: the number of neighbors, G.degree(i) ≡ len(G.neighbors(i)). In the small network below, node 3 has the most links, so it is the hub. Closeness asks a different question. Add up the distances \(l_{ij}\) from node \(i\) to every other node and take the inverse:

\[ g_i = \frac{1}{\sum_{j\neq i} l_{ij}}, \qquad \tilde g_i = (N-1)\,g_i = \frac{1}{\sum_{j\neq i} l_{ij}\,/\,(N-1)} \]

A short total distance means high closeness. The rescaled version \(\tilde g_i\) is the inverse of the average distance from \(i\). Pick a node, then pick any other node in the list to see the shortest paths behind each distance.

Why rescale by \(N-1\)

The sum in \(g_i\) has \(N-1\) terms, so it grows with the size of the network. In the language of thermodynamics it is extensive, like volume: two rabbits have twice the volume of one, but not twice the temperature. Raw closeness therefore shrinks as the network grows, and you cannot compare it across networks. Dividing by the number of terms gives an average, which behaves like an intensive quantity. It still drifts down slowly, because average distances themselves grow like \(\log N\), but it no longer collapses. Rankings inside one network do not change either way.

Who sits on the shortest paths?

Take every pair of nodes \(h\) and \(j\), find the shortest paths between them, and give each node in the middle a point. When there are several shortest paths, the point is shared out: \(\sigma_{hj}\) counts the shortest paths from \(h\) to \(j\) and \(\sigma_{hj}(i)\) counts the ones through \(i\).

\[ b_i = \sum_{h\neq j\neq i} \frac{\sigma_{hj}(i)}{\sigma_{hj}}, \qquad \tilde b_i = \frac{b_i}{(N-1)(N-2)/2} \]

The normalized \(\tilde b_i\) divides by the number of pairs that do not include \(i\), for the same reason closeness is rescaled. Replace “node \(i\)” with “link \(i\)” and you get edge betweenness. Nodes and links with high betweenness carry most of the traffic, so they are the bottlenecks for transport and spreading. Below, look at one pair at a time, or pick a node or a link and step through every pair that adds to its betweenness.

Many links, or the only bridge

Degree and betweenness often go together, but not always. In both networks below, node 3 is highlighted. On the left it has many links and modest betweenness. On the right it has only two links, yet every path between the group of four and the group of five must cross it, so \(b_3 = 4\times 5 = 20\). Pick any node to see its values.

Degree and betweenness usually agree

Plot every node’s betweenness against its degree. In most networks the cloud runs up and to the right: hubs lie on many shortest paths simply because so many paths can pass through them. Goh and colleagues found this in the internet’s router-level map. Networks made of tight groups joined by a few links break the pattern. The nodes at the ends of those links have ordinary degree but carry all the traffic between groups.

Centrality distributions

Ranking finds the single most important node, which is a question about extreme values. To understand a whole network you need the full spectrum: how many nodes have each value. Count the \(n_k\) nodes with degree \(k\) and you get a histogram with \(\sum_k n_k = N\). Divide by \(N\) and you get relative frequencies \(f_k = n_k/N\), which approach the probability distribution \(p_k\) as the network grows. Betweenness and closeness are not whole numbers, so they are counted in bins.

Choosing the axes

A distribution that spans several orders of magnitude needs logarithmic axes. On linear axes an exponential \(p(k)\propto e^{-k}\) and a power law \(p(k)\propto k^{-3}\) look much alike. A semi-log plot turns the exponential into a straight line. A log–log plot turns the power law into a straight line and shows how much heavier its tail is.

Cumulative distributions

Large values are rare, so the tail of \(p(k)\) is noisy. The cumulative distribution \(P(k)=\sum_{k'\ge k} p(k')\), the share of nodes with value at least \(k\), averages that noise out. For a power law it is again a power law, one step shallower: \(p(k)\propto k^{-\gamma}\) gives \(P(k)\propto k^{-(\gamma-1)}\), defined for \(\gamma>1\). For an exponential it stays exponential. Real networks such as Twitter and Wikipedia show heavy tails spanning several orders of magnitude, for degree and for betweenness alike.

How wide is the distribution?

Hubs are nodes with exceptionally large degree, but in a heavy-tailed distribution they are not exceptional in a mathematical sense: they are part of the same smooth tail. A single number captures how broad that tail is. Average the squared degrees and compare with the squared average:

\[ \langle k^2\rangle = \frac{1}{N}\sum_i k_i^2, \qquad \kappa = \frac{\langle k^2\rangle}{\langle k\rangle^2} \]

When degrees cluster around one value \(k_0\), both averages are close to \(k_0^2\) and \(\kappa\approx 1\). When a few hubs have huge degrees, their squares dominate \(\langle k^2\rangle\) and \(\kappa\gg 1\). For a random network \(\kappa = 1 + 1/\langle k\rangle\) whatever its size. For a power law with \(\gamma<3\), \(\kappa\) keeps growing as the network grows, because the largest hub does.