Centrality, 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.

On unweighted graphs, calculating betweenness centrality takes O time using Brandes' algorithm.

When specifically dealing with network graphs, oftentimes graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.

The closeness C_C(v) for a vertex v is the reciprocal of the sum of geodesic distance to all other vertices of V Sabidussi, G. (1966) The centrality index of a graph.

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 Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples.Social Networks 11, 137.

However, the additional requirement that all the entries in the eigenvector be positive implies (by the PerronFrobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.

Source: Wikipedia > Centrality