CENTRALITY

Within graph theory and network analysis, there are various measures of the 'centrality' of a vertex within a graph that determine the relative importance of a vertex within the graph (for example, how important a person is within a social network, or, in the theory of space syntax, how important a room is within a building or how well-used a road is within an urban network).
There are four measures of centrality that are widely used in network analysis: degree centrality, betweenness, closeness, and eigenvector centrality.

Contents

Degree Centrality

Betweenness

Closeness

Definition of closeness

Eigenvector centrality

Using the adjacency matrix to find eigenvector centrality

Further reading

See also

External links

Degree Centrality

The first, and simplest, is degree centrality. Degree centrality is defined as the number of links incident upon a node (i.e., the number of ties that a node has). Degree is often interpreted in terms of the immediate risk of node for catching whatever is flowing through the network (such as a virus, or some information). If the network is directed (meaning that ties have direction), then we usually define two separate measures of degree centrality, namely indegree and outdegree. Indegree is a count of the number of ties directed to the node, and outdegree is the number of ties that the node directs to others. For positive relations such as friendship or advice, we normally interpret indegree as a form of popularity, and outdegree as gregariousness.

Betweenness

'Betweenness' is a centrality measure of a vertex within a graph. Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.
For a graph $G:=(V,E)$ with ''n'' vertices, the betweenness $C\_B(v)$ for vertex $v$ is:
:$C\_B(v)=\; sum\_\{s$
eq v
eq t in V}rac{sigma_{st}(v)}{sigma_{st}}
where $sigma\_\{st\}$ is the number of shortest geodesic paths from ''s'' to ''t'', and $sigma\_\{st\}(v)$ is the number of shortest geodesic paths from ''s'' to ''t'' that pass through a vertex ''v''. This may be normalised by dividing through by the number of pairs of vertices not including ''v'', which is $(n-1)(n-2)$.

Closeness

Definition of closeness

In topology and related areas in mathematics, 'closeness' is one of the basic concepts in a topological space. Intuitively we say two sets are close if they are arbitrarily near to each other. The concept can be defined naturally in a metric space where a notion of distance between elements of the space is defined, but it can be generalized to topological spaces where we have no concrete way to measure distances.
In graph theory 'closeness' is a centrality measure of a vertex within a graph. Vertices that are 'shallow' to other vertices (that is, those that tend to have short geodesic distances to other vertices with in the graph) have higher closeness. Closeness is preferred in network analysis to mean shortest-path length, as it gives higher values to more central vertices, and so is usually positively associated with other measures such as degree.
In the network theory, 'closeness' is a sophisticated measure of centrality. It is defined as the mean geodesic (i.e the shortest path) between a vertex ''v'' and all other vertices reachable from it:
:
Closeness can be regarded as a measure of how long it will take information to spread from a given vertex to others in the network^[1].
Some define closeness to be the reciprocal of this quantity, but either ways the information communicated is the same (this time estimating the speed instead of the timespan). The closeness $C\_C(v)$ for a vertex $v$ is the reciprocal of the sum of geodesic distances to all other vertices in the graph^[2]:
:
===Defining geodesics and an algorithm to measure itNewman, M. E. J. (2001) Phys. Rev. E 64, 016132.===

A fundamental concept in graph theory is the "geodesic," or shortest path of vertices and edges that link two given vertices. There may not be a unique geodesic between two vertices: there may be two or more shortest paths, which may or may not share some vertices ('Fig.1'). The geodesic(s) between two vertices 'i' and 'j' can be calculated using the following algorithm, which is a modified form of the standard breadth-first search^[3].
# Assign vertex 'j' distance zero, to indicate that it is zero steps away from itself, and set 'd ← 0'.
# For each vertex 'k' whose assigned distance is 'd', follow each attached edge to the vertex 'm' at its other end and, if 'm' has not already been assigned a distance, assign it distance 'd + 1' and declare 'k' to be a predecessor of 'm'.
# If 'm' has already been assigned distance 'd + 1', then there is no need to do this again, but 'k' is still declared a predecessor of 'm'. If 'm' has already been assigned a distance ≤ 'd', no changes are to be done.
# Set 'd ← d + 1'.
# Repeat from step 2 until there are no unassigned vertices left.
Now the shortest path (if there is one) from 'i' to 'j' is the path you get by stepping from 'i' to its predecessor, and then to the predecessor of each successive vertex until 'j' is reached. If a vertex has two or more predecessors, then there are two or more shortest paths, each of which must be followed separately if we wish to know all shortest paths from 'i' to 'j'.
Fig.1 shows the shortest paths of collaborations in the Los Alamos Archive, calculated through the algorithm above, between two of the author’s colleagues the vertices A and B). Even though the two scientists work on social networks of various kinds, the shortest path between them does not run entirely through the collaborations in the field. For example, the vertex C represents the present author, and my connections to D and E derive from papers on topics unconnected with networks. It indicates that workers in the field come from different scientific "camps," rather than from a single group or institution. This may increase the chance that those workers will express independent opinions on the open questions of the field.
Different methods and algorithms can be introduced to measure closeness, like the ''random-walk centrality'' introduced by Noh and Rieger (2003) that is a measure of the speed with which randomly walking messages reach a vertex from elsewhere in the network—a sort of random-walk version of closeness centrality^[4].
The ''information centrality'' of Stephenson and Zelen (1989) is another closeness measure, which bears some similarity to that of Noh and Rieger. In essence it measures the harmonic mean length of paths ending at a vertex 'i', which is smaller if 'i' has many short paths connecting it to other vertices^[5].
Dangalchev (2006), in order to measure the network vulnerability, modifies the definition for closeness so it can be used for disconnected graphs and the total closeness is easier to
calculate Dangalchev Ch., Residual Closeness in Networks, Phisica A '365', 556 (2006).:
:$C\_C(v)=sum\_\{t\; in\; V\}2^\{-d\_G(v,t)\}.$

Eigenvector centrality

'Eigenvector centrality' is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.

Using the adjacency matrix to find eigenvector centrality

Let ''x''_''i'' denote the score of the ''i''th node. Let $A\_\{i,j\}$ be the adjacency matrix of the network. Hence $A\_\{i,j\}\; =\; 1$ if the ''i''th node is connected to the ''j''th node, and $A\_\{i,j\}\; =\; 0$ otherwise. More generally, the entries in ''A'' can be real numbers representing connection strengths.
For the $i^\{th\}$ node, let the centrality score be proportional to the sum of the scores of all nodes which are connected to it. Hence
:
(where $M(i)$ is the set of nodes that are connected to the $i^\{th\}$ node, ''N'' is the total number of nodes and $lambda$ is a constant),
or equivalently using the adjacency matrix,
:
in vector notation this can be rewritten as
:
or,
:$Amathbf\{x\}\; =\; \{lambda\}mathbf\{x\}$
which is the eigenvector equation.
In general, there will be many different eigenvalues $lambda$ for which an eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be positive implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.^[6] The $i^\{th\}$ component of this eigenvector then gives the centrality score of the $i^\{th\}$ node in the network.
Google's PageRank is a variant of the Eigenvector centrality measure.

Further reading

★ Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.

★ Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31, 581-603.

★ Freeman, L. C. (1977) A set of measures of centrality based on betweenness. ''Sociometry'' '40', 35--41.

See also

★ Centrality

★ Closeness

★ Distance in graphs

★ Graph theory

External links

★ WikiNet: Centrality

★ WikiNet: Betweenness