Within graph theory and network analysis, there are various measures of centrality of a vertex within a graph, used to indicate the relative importance of the vertex.
For a graph with n vertices, the degree centrality for vertex is the fraction of the total number vertices that are the node's neighbors:
Betweenness is a centrality measure of a vertex within a graph (there is also an analogous betweenness measure for edges). Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.
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 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. On unweighted graphs, calculating betweenness centrality takes time using Brandes' algorithm [1].
Closeness centrality of a vertex can be defined as the reciprocal of the average geodesic distances to all other vertices of V :
where is the size of the network V. By convention, if there is no path between v and t, so that the lowest centrality value, that of an isolate, is .
Egonet software reports this value multiplied by 100.
Different methods and algorithms have been introduced to measure closeness. Two measures similar to the one above are described in Newman (2003) [2] and Sabidussi (2003) [3]. In addition, Noh and Rieger (2003) [4] discuss random-walk centrality, while Stephenson and Zelen (1989) introduce information centrality, which employs the harmonic instead of the arithmetic mean of path lengths [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 [6]:
{{
cite document}}
: Cite document requires |publisher=
(
help); Unknown parameter |url=
ignored (
help)
Within graph theory and network analysis, there are various measures of centrality of a vertex within a graph, used to indicate the relative importance of the vertex.
For a graph with n vertices, the degree centrality for vertex is the fraction of the total number vertices that are the node's neighbors:
Betweenness is a centrality measure of a vertex within a graph (there is also an analogous betweenness measure for edges). Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.
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 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. On unweighted graphs, calculating betweenness centrality takes time using Brandes' algorithm [1].
Closeness centrality of a vertex can be defined as the reciprocal of the average geodesic distances to all other vertices of V :
where is the size of the network V. By convention, if there is no path between v and t, so that the lowest centrality value, that of an isolate, is .
Egonet software reports this value multiplied by 100.
Different methods and algorithms have been introduced to measure closeness. Two measures similar to the one above are described in Newman (2003) [2] and Sabidussi (2003) [3]. In addition, Noh and Rieger (2003) [4] discuss random-walk centrality, while Stephenson and Zelen (1989) introduce information centrality, which employs the harmonic instead of the arithmetic mean of path lengths [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 [6]:
{{
cite document}}
: Cite document requires |publisher=
(
help); Unknown parameter |url=
ignored (
help)