in question (here, vertex v). Sum this fraction over all pairs of vertices (s,t). More compactly the betweenness can be represented as: where is total number of shortest paths from node to node and is the number of those paths that pass through . The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is and for undirected 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 (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0. From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm which takes time. Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often 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. Eigenvector centrality Eigenvector centrality (also called eigencentrality) is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. Google's PageRank and the Katz centrality are variants of the eigenvector centrality. Using the adjacency matrix to find eigenvector centrality For a given graph with number of vertices let be the adjacency matrix, i.e. if vertex is linked to vertex , and otherwise. The relative centrality score of vertex can be defined as: where is a set of the neighbors of and is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation In general, there will be many different eigenvalues for which a non-zero eigenvector solution exists. Since the entries in the adjacency