There are four measures of centrality that are widely used in network analysis: degree centrality, betweenness, closeness, and eigenvector centrality.
For a graph with n vertices, the betweenness for vertex is:
where is the number of shortest geodesic paths from s to t, and 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 .
Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph. This takes time with the Floyd–Warshall algorithm. On a sparse graph, Johnson's algorithm may be more efficient, taking time.
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 distance (i.e the shortest path) between a vertex v and all other vertices reachable from it:
where is the size of the network's 'connectivity component' V reachable from v. Closeness can be regarded as a measure of how long it will take information to spread from a given vertex to other reachable vertices in the network.
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 for a vertex is the reciprocal of the sum of geodesic distances to all other vertices of V:
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.
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.
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 :
For the node, let the centrality score be proportional to the sum of the scores of all nodes which are connected to it. Hence
where is the set of nodes that are connected to the node, N is the total number of nodes and is a constant. In vector notation this can be rewritten as
In general, there will be many different eigenvalues 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. The component of the related eigenvector then gives the centrality score of the node in the network. Power iteration is one of many eigenvalue algorithms that may be used to find this dominant eigenvector.
Information, Resources and Transaction Cost Economics: The Effects of Informal Network Centrality on Teams and Team Performance
Jan 01, 2008; ABSTRACT This study presents a theoretical framework for studying the effects of extra-group social networks on teams. Building...