Editing Centrality (section)

==Betweenness centrality==
{{Main|Betweenness centrality}}

[[File:Graph betweenness.svg|240px|right|thumb|Hue (from red&nbsp;=&nbsp;0 to blue&nbsp;=&nbsp;max) shows the node betweenness.]]

'''Betweenness''' is a centrality measure of a [[vertex (graph theory)|vertex]] within a [[Graph (discrete mathematics)|graph]] (there is also [[edge (graph theory)|edge]] betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by [[Linton Freeman]].<ref name="freeman1977">{{cite journal |last1 = Freeman |first1 = Linton | year=1977| title = A set of measures of centrality based upon betweenness | journal = Sociometry| volume=40|issue = 1 | pages=35–41 | doi=10.2307/3033543|jstor = 3033543 }}</ref> In his conception, vertices that have a high probability to occur on a randomly chosen [[shortest path problem|shortest path]] between two randomly chosen vertices have a high betweenness.

The betweenness of a vertex <math>v</math> in a graph <math>G:=(V,E)</math> with <math>V</math> vertices is computed as follows:

# For each pair of vertices (''s'',''t''), compute the [[Shortest path problem|shortest paths]] between them.
# For each pair of vertices (''s'',''t''), determine the fraction of shortest paths that pass through the vertex in question (here, vertex ''v'').
# Sum this fraction over all pairs of vertices (''s'',''t'').

More compactly the betweenness can be represented as:<ref name="brandes">{{cite journal |last1 = Brandes |first1 = Ulrik |author-link = Ulrik Brandes |year = 2001 |title = A faster algorithm for betweenness centrality |journal = Journal of Mathematical Sociology |volume = 25 |issue = 2 |pages = 163–177 |url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024 |access-date = October 11, 2011 |format = PDF |doi = 10.1080/0022250x.2001.9990249 |hdl = 10983/23603 |citeseerx = 10.1.1.11.2024 |s2cid = 13971996 |archive-date = March 4, 2016 |archive-url = https://web.archive.org/web/20160304055609/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024 |url-status = live }}</ref>

:<math>C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}}</math>

where <math>\sigma_{st}</math> is total number of shortest paths from node <math>s</math> to node <math>t</math> and <math>\sigma_{st}(v)</math> is the number of those paths that pass through <math>v</math>.  The betweenness may be normalised by dividing through the number of pairs of vertices not including ''v'', which for [[Digraph (mathematics)|directed graphs]] is <math>(n-1)(n-2)</math> and for undirected graphs is <math>(n-1)(n-2)/2</math>.  For example, in an undirected [[Star (graph theory)|star graph]], the center vertex (which is contained in every possible shortest path) would have a betweenness of <math>(n-1)(n-2)/2</math> (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 [[Big O notation|<math>O(V^3)</math>]] time with the [[Floyd–Warshall algorithm]]. However, on sparse graphs, [[Johnson's algorithm]] may be more efficient, taking [[Big O notation|<math>O(|V||E|+|V|^2 \log|V|)</math>]] time. In the case of unweighted graphs the calculations can be done with [[Brandes' algorithm]]<ref name=brandes/> which takes [[Big O notation|<math>O(|V||E|)</math>]] 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.<ref name="brandes" />