Centrality

The answer is given in terms of a real-valued function on the vertices of a graph, where the values produced are expected to provide a ranking which identifies the most important nodes.

The canonical example is Freeman's betweenness centrality, the number of shortest paths which pass through the given vertex.

Centralities placed in the same box in this 2×2 classification are similar enough to make plausible alternatives; one can reasonably compare which is better for a given application.

Any evaluation of relative fitness can only occur within the context of predetermining which category is more applicable, rendering the comparison moot.

An initial transformation of the adjacency matrix allows a different definition of the type of walk counted.

A startling conclusion is that regardless of the initial transformation of the adjacency matrix, all such approaches have common limiting behavior.

Because of the time-complexity hardness of the Shapley value calculation, most efforts in this domain are driven into implementing new algorithms and methods which rely on a peculiar topology of the network or a special character of the problem.

Similarly, the solution concept authority distribution ([10]) applies the Shapley-Shubik power index, rather than the Shapley value, to measure the bilateral direct influence between the players.

[12] The more subtle limitation is the commonly held fallacy that vertex centrality indicates the relative importance of vertices.

Recently, network physicists have begun developing node influence metrics to address this problem.

[14][15][16][17] This explains why, for example, only the first few results of a Google image search appear in a reasonable order.

The pagerank is a highly unstable measure, showing frequent rank reversals after small adjustments of the jump parameter.

[18] While the failure of centrality indices to generalize to the rest of the network may at first seem counter-intuitive, it follows directly from the above definitions.

The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information).

When ties are associated to some positive aspects such as friendship or collaboration, indegree is often interpreted as a form of popularity, and outdegree as gregariousness.

is the distance between vertices u and v. However, when speaking of closeness centrality, people usually refer to its normalized form, given by the previous formula multiplied by

Taking distances from or to all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in directed graphs (e.g. a website can have a high closeness centrality from outgoing link, but low closeness centrality from incoming links).

The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is

For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of

Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges.

In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.

With a small rearrangement this can be rewritten in vector notation as the eigenvector equation In general, there will be many different eigenvalues

Since the entries in the adjacency matrix are non-negative, there is a unique largest eigenvalue, which is real and positive, by the Perron–Frobenius theorem.

[29] Furthermore, this can be generalized so that the entries in A can be real numbers representing connection strengths, as in a stochastic matrix.

[32] A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network.

The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links.

The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads.

The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks.

The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).

A node with high cross-clique connectivity facilitates the propagation of information or disease in a graph.

Examples of A) Betweenness centrality , B) Closeness centrality , C) Eigenvector centrality , D) Degree centrality , E) Harmonic centrality and F) Katz centrality of the same random geometric graph.
Hue (from red = 0 to blue = max) shows the node betweenness.
In the illustrated network, green and red nodes are the most dissimilar because they do not share neighbors between them. So, the green one contributes more to the centrality of the red one than the gray ones, because the red one can access to the blue ones only through the green, and the gray nodes are redundant for the red one, because it can access directly to each gray node without any intermediary.