Betweenness centrality

For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices, that is, there exists at least one path such that either the number of edges that the path passes through (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized.Betweenness centrality was devised as a general measure of centrality:[1] it applies to a wide range of problems in network theory, including problems related to social networks, biology, transport and scientific cooperation.Therefore, the calculation may be rescaled by dividing through by the number of pairs of nodes not includingNote that this scales for the highest possible value, where one node is crossed by every single shortest path.This is often not the case, and a normalization can be performed without a loss of precision which results in: Note that this will always be a scaling from a smaller range into a larger range, so no precision is lost.In a weighted network the links connecting the nodes are no longer treated as binary interactions, but are weighted in proportion to their capacity, influence, frequency, etc., which adds another dimension of heterogeneity within the network beyond the topological effects.Analogous to the power law distribution of degree found in scale free networks, the strength of a given node follows a power law distribution as well.shows that the functional behavior can be approximated by a scaling form:[3]Percolation centrality is a version of weighted betweenness centrality, but it considers the 'state' of the source and target nodes of each shortest path in calculating this weight.Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios.The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links.Rumours or news about business offers and deals can also spread via social networks of people.The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads.The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks.The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node.The definition of PC may also be extended to include target node weights as well.time with an efficient implementation adapted from Brandes' algorithm.If the calculation needs to consider target node weights, the worst case time isCalculating 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, which takestime with the Floyd–Warshall algorithm, modified to not only find one but count all shortest paths between two nodes.On unweighted graphs, calculating betweenness centrality takes[5] In calculating betweenness and closeness centralities of all vertices in a graph, it is assumed 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.[7] An approximate, probabilistic estimation of betweenness centralities can be obtained much faster by sampling paths using a bidirectional breadth-first search.[8] In social network analysis, betweenness centrality can have different implications.From a macroscopic perspective, bridging positions or "structural holes" (indicated by high betweenness centrality) reflect power, because they allow the person on the bridging position to exercise control (e.g., decide whether to share information or not) over the persons it connects between.[9] From the microscopic perspective of ego networks (i.e., only considering first-degree connections), in online social networks a high betweenness centrality coincides with nominations of closest friends (i.e., strong interpersonal ties), because it reflects social capital investments into the relationship when distant social circles (e.g., family and university) are bridged (often resulting from an introduction by ego).[10] Betweenness centrality has been used to analyze the topological complexity of river networks as well as their use in maritime trade.