View source for Centrality

{{Short description|Degree of connectedness within a graph}}
{{for|the statistical concept|Central tendency}}

{{Network Science}}

In [[graph theory]] and [[network theory|network analysis]], indicators of '''centrality''' assign numbers or rankings to [[vertex (graph theory)|nodes]] within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a [[social network]], key infrastructure nodes in the [[Internet]] or [[urban network]]s, [[super-spreader]]s of disease, and brain networks.<ref name="10.1016/j.tics.2013.09.012">{{cite journal | vauthors = van den Heuvel MP, Sporns O | title = Network hubs in the human brain | journal = Trends in Cognitive Sciences | volume = 17 | issue = 12 | pages = 683–96 | date = December 2013 | pmid = 24231140 | doi = 10.1016/j.tics.2013.09.012 | s2cid = 18644584 }}</ref><ref name="10.1038/s41598-021-81767-7">{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = Topological impact of negative links on the stability of resting-state brain network | journal = Scientific Reports | date = January 2021 | volume = 11 | issue = 1 | page = 2176 | pmid = 33500525 | pmc = 7838299 | doi = 10.1038/s41598-021-81767-7 | bibcode = 2021NatSR..11.2176S | url = }}</ref> Centrality concepts were first developed in [[social network analysis]], and many of the terms used to measure centrality reflect their [[sociology|sociological]] origin.<ref name="NewmanNetworks">Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press.</ref>

==Definition and characterization of centrality indices==
Centrality indices are answers to the question "What characterizes an important vertex?" The answer is given in terms of a real-valued function on the vertices of a graph, where the values produced are expected to provide a ranking which identifies the most important nodes.<ref name="Bonacich1987">{{cite journal |last1= Bonacich |first1= Phillip|year= 1987 |title= Power and Centrality: A Family of Measures | journal=American Journal of Sociology |volume= 92|issue= 5|pages= 1170–1182|doi=10.1086/228631 |s2cid= 145392072}}<!--|access-date=July 11, 2014--></ref><ref name="Borgatti2005">{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |citeseerx= 10.1.1.387.419}}<!--|access-date= July 11, 2014--></ref><ref name="Negre et al.-2018">{{cite journal |
author = Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista.|
title = Eigenvector centrality for characterization of protein allosteric pathways|
journal = Proceedings of the National Academy of Sciences|
volume = 115|
number = 52|
pages = E12201–E12208|
year = 2018|
doi = 10.1073/pnas.1810452115|
pmid = 30530700|
pmc = 6310864|
arxiv = 1706.02327|
bibcode = 2018PNAS..11512201N|
doi-access = free}}</ref>

The word "importance" has a wide number of meanings, leading to many different definitions of centrality. Two categorization schemes have been proposed. "Importance" can be conceived in relation to a type of flow or transfer across the network. This allows centralities to be classified by the type of flow they consider important.<ref name=Borgatti2005/> "Importance" can alternatively be conceived as involvement in the cohesiveness of the network. This allows centralities to be classified based on how they measure cohesiveness.<ref name="Borgatti2006">{{cite journal |last1= Borgatti |first1= Stephen P.|last2= Everett |first2= Martin G.|year= 2006 |title= A Graph-Theoretic Perspective on Centrality |journal=Social Networks |volume= 28|issue= 4|pages= 466–484|doi=10.1016/j.socnet.2005.11.005 }}<!--|access-date= July 11, 2014--></ref> Both of these approaches divide centralities in distinct categories. A further conclusion is that a centrality which is appropriate for one category will often "get it wrong" when applied to a different category.<ref name=Borgatti2005/> 

Many, though not all, centrality measures effectively count the number of [[Path (graph theory)|paths]] (also called walks) of some type going through a given vertex; the measures differ in how the relevant walks are defined and counted. Restricting consideration to this group allows for taxonomy which places many centralities on a spectrum from those concerned with walks of length one ([[#Degree centrality|degree centrality]]) to infinite walks ([[#Eigenvector centrality|eigenvector centrality]]).<ref name=Bonacich1987/><ref name="Benzi2013">{{cite journal | last1=Benzi | first1=Michele | last2=Klymko| first2=Christine | year=2013 |title= A matrix analysis of different centrality measures |arxiv=1312.6722 | doi=10.1137/130950550 | volume=36 | issue=2 | journal=SIAM Journal on Matrix Analysis and Applications | pages=686–706| s2cid=7088515 }}</ref> Other centrality measures, such as [[betweenness centrality]] focus not just on overall connectedness but occupying positions that are pivotal to the network's connectivity. 

===Characterization by network flows===
A network can be considered a description of the paths along which something flows. This allows a characterization based on the type of flow and the type of path encoded by the centrality. A flow can be based on transfers, where each indivisible item goes from one node to another, like a package delivery going from the delivery site to the client's house. A second case is serial duplication, in which an item is replicated so that both the source and the target have it. An example is the propagation of information through gossip, with the information being propagated in a private way and with both the source and the target nodes being informed at the end of the process. The last case is parallel duplication, with the item being duplicated to several links at the same time, like a radio broadcast which provides the same information to many listeners at once.<ref name=Borgatti2005/>

Likewise, the type of path can be constrained to [[Distance (graph theory)|geodesics]] (shortest paths), [[Glossary of graph theory terms#path|paths]]  (no vertex is visited more than once), [[Glossary of graph theory terms#trail|trails]] (vertices can be visited multiple times, no edge is traversed more than once), or [[Glossary of graph theory terms#walk|walks]] (vertices and edges can be visited/traversed multiple times).<ref name=Borgatti2005/>

===Characterization by walk structure===
An alternative classification can be derived from how the centrality is constructed. This again splits into two classes. Centralities are either ''radial'' or ''medial.'' Radial centralities count walks which start/end from the given vertex. The [[#Degree centrality|degree]] and [[#Eigenvector centrality|eigenvalue]] centralities are examples of radial centralities, counting the number of walks of length one or length infinity. Medial centralities count walks which pass through the given vertex. The canonical example is Freeman's [[#Betweenness centrality|betweenness]] centrality, the number of shortest paths which pass through the given vertex.<ref name=Borgatti2006/>

Likewise, the counting can capture either the ''volume'' or the ''length'' of walks. Volume is the total number of walks of the given type. The three examples from the previous paragraph fall into this category. Length captures the distance from the given vertex to the remaining vertices in the graph. [[#Closeness centrality|Closeness]] centrality, the total geodesic distance from a given vertex to all other vertices, is the best known example.<ref name=Borgatti2006/> Note that this classification is independent of the type of walk counted (i.e. walk, trail, path, geodesic).

Borgatti and Everett propose that this typology provides insight into how best to compare centrality measures. Centralities placed in the same box in this 2×2  classification are similar enough to make plausible alternatives; one can reasonably compare which is better for a given application. Measures from different boxes, however, are categorically distinct. Any evaluation of relative fitness can only occur within the context of predetermining which category is more applicable, rendering the comparison moot.<ref name=Borgatti2006/>

===Radial-volume centralities exist on a spectrum===
The characterization by walk structure shows that almost all centralities in wide use are radial-volume measures. These encode the belief that a vertex's centrality is a function of the centrality of the vertices it is associated with. Centralities distinguish themselves on how association is defined.

Bonacich showed that if association is defined in terms of [[Glossary of graph theory terms#walk|walks]], then a family of centralities can be defined based on the length of walk considered.<ref name="Bonacich1987"/> [[#Degree centrality|Degree centrality]] counts walks of length one, while [[#Eigenvector centrality|eigenvalue centrality]] counts walks of length infinity. Alternative definitions of association are also reasonable. [[Alpha centrality]] allows vertices to have an external source of influence. Estrada's subgraph centrality proposes only counting closed paths (triangles, squares, etc.).

The heart of such measures is the observation that powers of the graph's adjacency matrix gives the number of walks of length given by that power.  Similarly, the matrix exponential is also closely related to the number of walks of a given length. An initial transformation of the adjacency matrix allows a different definition of the type of walk counted. Under either approach, the centrality of a vertex can be expressed as an infinite sum, either

:<math>\sum_{k=0}^\infty A_{R}^{k} \beta^k </math>

for matrix powers or

:<math>\sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!}</math>

for matrix exponentials, where

* <math>k</math> is walk length,
* <math>A_R</math> is the transformed adjacency matrix, and
* <math>\beta</math> is a discount parameter which ensures convergence of the sum.

Bonacich's family of measures does not transform the adjacency matrix. [[Alpha centrality]] replaces the adjacency matrix with its [[resolvent formalism|resolvent]]. Subgraph centrality replaces the adjacency matrix with its trace. A startling conclusion is that regardless of the initial transformation of the adjacency matrix, all such approaches have common limiting behavior. As <math>\beta</math> approaches zero, the indices converge to [[#Degree centrality|degree centrality]]. As <math>\beta</math> approaches its maximal value, the indices converge to [[#Eigenvector centrality|eigenvalue centrality]].<ref name=Benzi2013/>

===Game-theoretic centrality===
The common feature of most of the aforementioned standard measures is that they assess the
importance of a node by focusing only on the role that a node plays by itself. However,
in many applications such an approach is inadequate because of synergies that may occur
if the functioning of nodes is considered in groups.

[[File:Game-theoretic centrality.png|Example of game-theoretic centrality]]

For example, consider the problem of stopping an epidemic. Looking at above image of network, which nodes should we vaccinate? Based on previously described measures, we want to recognize nodes that are the most important in disease spreading. Approaches based only on centralities, that focus on individual features of nodes, may not be good idea. Nodes in the red square, individually cannot stop disease spreading, but considering them as a group, we clearly see that they can stop disease if it has started in nodes <math>v_1</math>, <math>v_4</math>, and <math>v_5</math>. Game-theoretic centralities try to consult described problems and opportunities, using tools from game-theory. The approach proposed in <ref>Michalak, Aadithya, Szczepański, Ravindran, & Jennings {{ArXiv|1402.0567}}</ref> uses the [[Shapley value]]. Because of the time-complexity hardness of the Shapley value calculation, most efforts in this domain are driven into implementing new algorithms and methods which rely on a peculiar topology of the network or a special character of the problem. Such an approach may lead to reducing time-complexity from exponential to polynomial.

Similarly, the solution concept [[authority distribution]] (<ref>{{cite journal |last1=Hu |first1=Xingwei |first2=Lloyd |last2=Shapley |title=On Authority Distributions in Organizations |journal=Games and Economic Behavior |volume=45 |pages=132–170 |year=2003 | doi = 10.1016/s0899-8256(03)00130-1 }}</ref>) applies the [[Shapley-Shubik power index]], rather than the [[Shapley value]], to measure the bilateral direct influence between the players. The distribution is indeed a type of eigenvector centrality. It is used to sort big data objects in Hu (2020),<ref>{{cite journal|last=Hu|first=Xingwei|year=2020|volume=7|title=Sorting big data by revealed preference with application to college ranking |journal=Journal of Big Data|doi=10.1186/s40537-020-00300-1| arxiv=2003.12198|doi-access=free}}</ref> such as ranking U.S. colleges.

== Important limitations ==
Centrality indices have two important limitations, one obvious and the other subtle. The obvious limitation is that a centrality which is optimal for one application is often sub-optimal for a different application. Indeed, if this were not so, we would not need so many different centralities. An illustration of this phenomenon is provided by the [[Krackhardt kite graph]], for which three different notions of centrality give three different choices of the most central vertex.<ref>{{cite journal|title=Assessing the Political Landscape: Structure, Cognition, and Power in Organizations|first=David|last=Krackhardt|author-link=David Krackhardt|journal=Administrative Science Quarterly|volume=35|issue=2|date=June 1990|pages=342–369|doi=10.2307/2393394|jstor=2393394}}</ref>

The more subtle limitation is the commonly held fallacy that vertex centrality indicates the relative importance of vertices. Centrality indices are explicitly designed to produce a ranking which allows indication of the most important vertices.<ref name=Bonacich1987/><ref name=Borgatti2005/> This they do well, under the limitation just noted. They are not designed to measure the influence of nodes in general. Recently, network physicists have begun developing  [[node influence metric]]s to address this problem.

The error is two-fold. Firstly, a ranking only orders vertices by importance, it does not quantify the difference in importance between different levels of the ranking. This may be mitigated by applying [[#Freeman centralization|Freeman centralization]] to the centrality measure in question, which provide some insight to the importance of nodes depending on the differences of their centralization scores. Furthermore, Freeman centralization enables one to compare several networks by comparing their highest centralization scores.<ref name="Freeman1979"/>

Secondly, the features which (correctly) identify the most important vertices in a given network/application do not necessarily generalize to the remaining vertices. 
For the majority of other network nodes the rankings may be meaningless.<ref name="Lawyer2015" /><ref name="daSilva2012">{{cite journal | last1=da Silva|first1=Renato |last2=Viana|first2=Matheus|last3=da F. Costa |first3=Luciano| title=Predicting epidemic outbreak from individual features of the spreaders| journal=J. Stat. Mech.: Theory Exp. | year=2012|volume=2012|pages=P07005|number=7 | doi=10.1088/1742-5468/2012/07/p07005|arxiv=1202.0024|bibcode=2012JSMTE..07..005A|s2cid=2530998 }}</ref><ref name="Bauer2012">{{cite journal | last1=Bauer|first1=Frank | last2=Lizier|first2=Joseph|title=Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach| journal=Europhys Lett | year=2012| volume=99| pages=68007|number=6 | doi=10.1209/0295-5075/99/68007|arxiv=1203.0502|bibcode=2012EL.....9968007B|s2cid=9728486 }}</ref><ref name="Sikic2013">{{ cite journal| last1= Sikic| first1=Mile|last2=Lancic|first2=Alen|last3=Antulov-Fantulin|first3=Nino|last4=Stefanic|first4=Hrvoje| title = Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? |journal = The European Physical Journal B |volume=86 |number=10 |pages=1–13 |year=2013 | doi=10.1140/epjb/e2013-31025-5|arxiv=1110.2558 | bibcode=2013EPJB...86..440S| s2cid=12052238}}</ref> This explains why, for example, only the first few results of a Google image search appear in a reasonable order. The pagerank is a highly unstable measure, showing frequent rank reversals after small adjustments of the jump parameter.<ref name="Ghoshal2011">{{cite journal | last1=Ghoshal | first1= G. | last2= Barabsi |first2= A L | title = Ranking stability and super-stable nodes in complex networks. | journal = Nat Commun | volume =2 | page = 394| year= 2011 | doi=10.1038/ncomms1396 | pmid= 21772265 | bibcode=2011NatCo...2..394G | doi-access= free }}</ref>

While the failure of centrality indices to generalize to the rest of the network may at first seem counter-intuitive, it follows directly from the above definitions.
Complex networks have heterogeneous topology. To the extent that the optimal measure depends on the network structure of the most important vertices, a measure which is optimal for such vertices is sub-optimal for the remainder of the network.<ref name="Lawyer2015">{{cite journal |last1= Lawyer |first1= Glenn |year= 2015 |title= Understanding the spreading power of all nodes in a network: a continuous-time perspective |journal=Sci Rep |volume=5|pages=8665|doi=10.1038/srep08665 |pmid=25727453 |pmc=4345333|arxiv=1405.6707|bibcode=2015NatSR...5E8665L}}</ref>

==Degree centrality==
{{Main|Degree (graph theory)}}
[[File:Wp-01.png|thumb|505x505px|Examples of A) [[Betweenness centrality]], B) [[Closeness centrality]], C) [[Eigenvector centrality]], D) [[Degree centrality]], E) [[#Harmonic centrality|Harmonic centrality]] and F) [[Katz centrality]] of the same random geometric graph.]]




Historically first and conceptually simplest is '''degree centrality''', which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely [[indegree]] and [[outdegree]]. Accordingly, indegree is a count of the number of ties directed to the node and outdegree is the number of ties that the node directs to others. When ties are associated to some positive aspects such as friendship or collaboration, indegree is often interpreted as a form of popularity, and outdegree as gregariousness.

The degree centrality of a vertex <math>v</math>, for a given graph <math>G:=(V,E)</math> with <math>|V|</math> vertices and <math>|E|</math> edges, is defined as

:<math>C_D(v)= \deg(v)</math>

Calculating degree centrality for all the nodes in a graph takes [[big theta|<math>\Theta(V^2)</math>]] in a [[dense matrix|dense]] [[adjacency matrix]] representation of the graph, and for edges takes <math>\Theta(E)</math> in a [[sparse matrix]] representation.

The definition of centrality on the node level can be extended to the whole graph, in which case we are speaking of ''graph centralization''.<ref>Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.</ref> Let <math>v*</math> be the node with highest degree centrality in <math>G</math>. Let <math>X:=(Y,Z)</math> be the <math>|Y|</math>-node connected graph that maximizes the following quantity (with <math>y*</math> being the node with highest degree centrality in <math>X</math>):

:<math>H= \sum^{|Y|}_{j=1} [C_D(y*)-C_D(y_j)]</math>

Correspondingly, the degree centralization of the graph <math>G</math> is as follows:

:<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)]}{H}</math>

The value of <math>H</math> is maximized when the graph <math>X</math> contains one central node to which all other nodes are connected (a [[star graph]]), and in this case

:<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math>

So, for any graph <math>G:=(V,E),</math>

:<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}</math>
Also, a new extensive global measure for degree centrality named Tendency to Make Hub (TMH) defines as follows:<ref name="10.1038/s41598-021-81767-7"/>
:<math>\text{TMH} = \frac{\sum^{|V|}_{i=1} \deg(v)^2 }{\sum^{|V|}_{i=1} \deg(v) }</math>
where TMH increases by appearance of degree centrality in the network.

==Closeness centrality==
{{Main|Closeness centrality}}In a [[Connected component (graph theory)|connected]] [[Graph (discrete mathematics)|graph]], the [[Normalization (statistics)|normalized]] '''closeness centrality''' (or '''closeness''') of a node is the average length of the [[Shortest path problem|shortest path]] between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

Closeness was defined by [[Alex Bavelas]] (1950) as the [[Multiplicative inverse|reciprocal]] of the '''farness''',<ref>Alex Bavelas. Communication patterns in task-oriented groups. ''J. Acoust. Soc. Am'', '''22'''(6):725–730, 1950.</ref><ref>{{cite journal|year=1966|title=The centrality index of a graph|journal=Psychometrika|volume=31|issue=4|pages=581–603|doi=10.1007/bf02289527|pmid=5232444|hdl=10338.dmlcz/101401|last1=Sabidussi|first1=G|s2cid=119981743|hdl-access=free}}</ref> that is <math display="inline">C_B(v)= (\sum_u d(u,v))^{-1}</math> where <math>d(u,v)</math> is the [[Distance (graph theory)|distance]] between vertices ''u'' and ''v''. However, when speaking of closeness centrality, people usually refer to its normalized form, given by the previous formula multiplied by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph
: <math>C(v)= \frac{N-1}{\sum_u d(u,v)} .</math>
This normalisation allows comparisons between nodes of graphs of different sizes. For many graphs, there is a strong correlation between the inverse of closeness and the logarithm of degree,<ref>{{Cite journal |last1=Evans |first1=Tim S. |last2=Chen |first2=Bingsheng |date=2022 |title=Linking the network centrality measures closeness and degree |journal=Communications Physics |language=en |volume=5 |issue=1 |pages=172 |doi=10.1038/s42005-022-00949-5 |arxiv=2108.01149 |bibcode=2022CmPhy...5..172E |s2cid=236881169 |issn=2399-3650|doi-access=free }}</ref> <math>(C(v))^{-1} \approx -\alpha \ln(k_v) + \beta</math> where <math>k_v</math> is the degree of vertex ''v'' while α and β are constants for each network.

Taking distances ''from'' or ''to'' all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in [[directed graph]]s (e.g. a website can have a high closeness centrality from outgoing link, but low closeness centrality from incoming links).

===Harmonic centrality===
In a (not necessarily connected) graph, the '''harmonic centrality''' reverses the sum and reciprocal operations in the definition of closeness centrality:

: <math>H(v)= \sum_{u | u \neq v} \frac{1}{d(u,v)}</math>

where <math>1 / d(u,v) = 0</math> if there is no path from ''u'' to ''v''. Harmonic centrality can be normalized by dividing by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph.

Harmonic centrality was proposed by [[Massimo Marchiori|Marchiori]] and [[Vito Latora|Latora]] (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and Its Applications  | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M | s2cid = 10523345 }}</ref> and then independently by Dekker (2005), using the name "valued centrality,"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html|access-date=2017-02-18|archive-date=2020-12-04|archive-url=https://web.archive.org/web/20201204145511/https://www.cmu.edu/joss/content/articles/volume6/dekker/index.html|url-status=live}}</ref> and by Rochat (2009).<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf | access-date = 2017-02-19 | archive-date = 2017-08-16 | archive-url = https://web.archive.org/web/20170816173227/https://infoscience.epfl.ch/record/200525/files/%5BEN%5DASNA09.pdf | url-status = live }}</ref>

==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" />

==Eigenvector centrality==
{{main|Eigenvector centrality}}
'''Eigenvector centrality''' (also called '''eigencentrality''') is a measure of the influence of a [[node (networking)|node]] in a [[network (mathematics)|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.<ref name=newman>{{cite encyclopedia|title = The mathematics of networks|url = http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|author = M. E. J. Newman|access-date = 2006-11-09|archive-date = 2021-01-22|archive-url = https://web.archive.org/web/20210122220704/http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|url-status = live|encyclopedia=The New Palgrave Dictionary of Economics|publisher=Springer|year=2016|editor1-first=Steven|editor1-last=Durlauf|editor2-first=Lawrence E.|editor2-last=Blume|edition=2nd|pages=465ff}}</ref><ref name="Negre et al.-2018"/> [[Google]]'s [[PageRank]] and the [[Katz centrality]] are variants of the eigenvector centrality.<ref name="ams">{{Cite web | url=http://www.ams.org/samplings/feature-column/fcarc-pagerank | title=How Google Finds Your Needle in the Web's Haystack|publisher=American Mathematical Society |work=AMS Feature Column|date=December 2006|first=David|last=Austin| access-date=2011-08-24 | archive-date=2018-01-11 | archive-url=https://web.archive.org/web/20180111084551/http://www.ams.org/samplings/feature-column/fcarc-pagerank | url-status=live }}</ref>

=== Using the adjacency matrix to find eigenvector centrality ===
For a given graph <math>G:=(V,E)</math> with <math>|V|</math> number of vertices let <math>A = (a_{v,t})</math> be the [[adjacency matrix]], i.e. <math>a_{v,t} = 1</math> if vertex <math>v</math> is linked to vertex <math>t</math>, and <math>a_{v,t} = 0</math> otherwise. The relative centrality score <math>x_v</math> of vertex <math>v</math> can be defined as the nonnegative solution over the set of vertices <math>v \in V</math> to the equations:

:<math>x_v = \frac{1}{\lambda} \sum_{t \in M(v)}x_t = \frac{1}{\lambda} \sum_{t \in G} a_{v,t}x_t</math>

where <math>M(v)</math> is a set of the neighbors of <math>v</math> and <math>\lambda</math> is a constant. With a small rearrangement this can be rewritten in vector notation as the [[eigenvector]] equation

:<math>\mathbf{Ax} = {\lambda}\mathbf{x}</math>.

In general, there will be many different [[eigenvalue]]s <math>\lambda</math> for which a non-zero eigenvector solution exists. Since the entries in the adjacency matrix are non-negative, there is a unique largest eigenvalue, which is real and positive, by the [[Perron–Frobenius theorem]]. This greatest eigenvalue results in the desired centrality measure.<ref name=newman/> The <math>v^{th}</math> component of the related eigenvector then gives the relative centrality score of the vertex <math>v</math> in the network. The eigenvector is only defined up to a common factor, so only the ratios of the centralities of the vertices are well defined. To define an absolute score one must normalise the eigenvector, e.g., such that the sum over all vertices is 1 or the total number of vertices ''n''. [[Power iteration]] is one of many [[eigenvalue algorithm]]s that may be used to find this dominant eigenvector.<ref name="ams" /> Furthermore, this can be generalized so that the entries in ''A'' can be real numbers representing connection strengths, as in a [[stochastic matrix]].

==Katz centrality==
{{main|Katz centrality}}
'''Katz centrality'''<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref> is a generalization of degree centrality. Degree centrality measures the number of direct neighbors, and Katz centrality measures the number of all nodes that can be connected through a path, while the contributions of distant nodes are penalized. Mathematically, it is defined as

:<math>x_i = \sum_{k=1}^{\infin}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>

where <math>\alpha</math> is an attenuation factor in  <math>(0,1)</math>.

Katz centrality can be viewed as a variant of eigenvector centrality. Another form of Katz centrality is

:<math>x_i = \alpha \sum_{j =1}^N a_{ij}(x_j+1).</math>

Compared to the expression of eigenvector centrality, <math>x_j</math> is replaced by  <math>x_j+1.</math>

It is shown that<ref>{{cite journal | last1 = Bonacich | first1 = P | year = 1991 | title = Simultaneous group and individual centralities | journal = Social Networks | volume = 13 | issue = 2| pages = 155–168 | doi=10.1016/0378-8733(91)90018-o}}</ref> the principal eigenvector (associated with the largest eigenvalue of <math>A</math>, the adjacency matrix) is the limit of Katz centrality as <math>\alpha</math> approaches <math>\tfrac{1}{\lambda}</math> from below.

== PageRank centrality ==
{{main|PageRank}}'''PageRank''' satisfies the following equation

:<math>x_i = \alpha \sum_{j } a_{ji}\frac{x_j}{L(j)} + \frac{1-\alpha}{N},</math>

where

:<math>L(j) = \sum_{i} a_{ji}</math>

is the number of neighbors of node <math>j</math> (or number of outbound links in a directed graph). Compared to eigenvector centrality and Katz centrality, one major difference is the scaling factor <math>L(j)</math>. Another difference between PageRank and eigenvector centrality is that the PageRank vector is a left hand eigenvector (note the factor <math>a_{ji}</math> has indices reversed).<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] {{webarchive | url= https://web.archive.org/web/20120131083328/http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf |date=January 31, 2012 }} 20Q: About Networked Life</ref>

==Percolation centrality==
A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network. However, these measures quantify the importance of a node in purely topological terms, and the value of the node does not depend on the ‘state’ of the node in any way. It remains constant regardless of network dynamics. This is true even for the weighted betweenness measures. However, a node may very well be centrally located in terms of betweenness centrality or another centrality measure, but may not be ‘centrally’ located in the context of a network in which there is percolation. Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. 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. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverable or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. 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. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.<ref name="piraveenan2013">{{cite journal |last1 = Piraveenan |first1 = M. |last2 = Prokopenko |first2 = M.|last3 = Hossain|first3 = L. |year=2013| title = Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks | journal = PLOS ONE | volume=8 | issue=1 | doi=10.1371/journal.pone.0053095 | pages=e53095 | pmid=23349699 | pmc=3551907| bibcode=2013PLoSO...853095P |doi-access = free }}</ref>

'''Percolation centrality''' is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

:<math>PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v}</math>

where <math>\sigma_{sr}</math> is total number of shortest paths from node <math>s</math> to node <math>r</math> and <math>\sigma_{sr}(v)</math> is the number of those paths that pass through <math>v</math>. The percolation state of the node <math>i</math> at time <math>t</math> is denoted by <math>{x^t}_i</math> and two special cases are when <math>{x^t}_i=0</math> which indicates a non-percolated state at time <math>t</math> whereas when <math>{x^t}_i=1</math> which indicates a fully percolated state at time <math>t</math>. 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. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in [[Big O notation|<math>O(NM)</math>]] time with an efficient implementation adopted from Brandes' fast algorithm and if the calculation needs to consider target nodes weights, the worst case time is [[Big O notation|<math>O(N^3)</math>]].

==Cross-clique centrality==
'''Cross-clique centrality''' of a single node in a complex graph determines the connectivity of a node to different [[clique (graph theory)|clique]]s. A node with high cross-clique connectivity facilitates the propagation of information or disease in a graph. Cliques are subgraphs in which every node is connected to every other node in the clique. The cross-clique connectivity of a node <math>v</math> for a given graph <math>G:=(V,E)</math> with <math>|V|</math> vertices and <math>|E|</math> edges, is defined as <math>X(v)</math> where <math>X(v)</math> is the number of cliques to which vertex <math>v</math> belongs.  This measure was used by Faghani in 2013 <ref name="xssworms">{{cite journal |last1 = Faghani|first1 = Mohamamd Reza| year=2013| title = A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks | journal = IEEE Transactions on Information Forensics and Security|volume = 8|issue = 11|pages = 1815–1826|doi = 10.1109/TIFS.2013.2280884|s2cid = 13587900}}</ref> but was first proposed by Everett and Borgatti in 1998 where they called it clique-overlap centrality.

==Freeman centralization==
The '''centralization''' of any network is a measure of how central its most central node is in relation to how central all the other nodes are.<ref name="Freeman1979">{{citation | journal = Social Networks | last1 = Freeman | first1 = Linton C. | year = 1979 | volume = 1 | issue = 3 | pages = 215–239 | title = centrality in social networks: Conceptual clarification | url = http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | doi = 10.1016/0378-8733(78)90021-7 | citeseerx = 10.1.1.227.9549 | s2cid = 751590 | access-date = 2014-07-31 | archive-url = https://web.archive.org/web/20160222033108/http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | archive-date = 2016-02-22 | url-status = dead }}</ref> Centralization measures then (a) calculate the sum in differences in centrality between the most central node in a network and all other nodes; and (b) divide this quantity by the theoretically largest such sum of differences in any network of the same size.<ref name="Freeman1979"/>  Thus, every centrality measure can have its own centralization measure.  Defined formally, if <math>C_x(p_i)</math> is any centrality measure of point <math>i</math>, if <math>C_x(p_*)</math> is the largest such measure in the network, and if:

:<math>\max \sum_{i=1}^{N} (C_x(p_*)-C_x(p_i))</math>

is the largest sum of differences in point centrality <math>C_x</math> for any graph with the same number of nodes, then the centralization of the network is:<ref name="Freeman1979"/>

:<math>C_x=\frac{\sum_{i=1}^{N} (C_x(p_*)-C_x(p_i))}{\max \sum_{i=1}^{N} (C_x(p_*)-C_x(p_i))}.</math>

The concept is due to [[Linton Freeman]].

== Dissimilarity-based centrality measures ==
[[File:Srep17095-f1.jpg|thumbnail|In the illustrated network, green and red nodes are the most dissimilar because they do not share neighbors between them. So, the green one contributes more to the centrality of the red one than the gray ones, because the red one can access to the blue ones only through the green, and the gray nodes are redundant for the red one, because it can access directly to each gray node without any intermediary.]]
In order to obtain better results in the ranking of the nodes of a given network,  in <ref>{{Cite journal|title = Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|journal = Scientific Reports|date = 2015-11-25|pmc = 4658528|pmid = 26603652|volume = 5|doi = 10.1038/srep17095|first1 = A. J.|last1 = Alvarez-Socorro|first2 = G. C.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz|pages=17095|bibcode = 2015NatSR...517095A}}</ref> are used dissimilarity measures (specific to the theory of classification and data mining) to enrich the centrality measures in complex networks. This is illustrated with [[eigenvector centrality]], calculating the centrality of each node through the solution of the eigenvalue problem

:<math>W\mathbf{c}=\lambda \mathbf{c}</math>

where <math>W_{ij}=A_{ij}D_{ij}</math> (coordinate-to-coordinate product) and <math>D_{ij}</math> is an arbitrary [[Matrix similarity|dissimilarity]] matrix, defined through a dissimilarity measure, e.g., [[Jaccard index|Jaccard]] dissimilarity given by

:<math>D_{ij}=1-\dfrac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}</math>

Where this measure permits us to quantify the topological contribution (which is why is called contribution centrality) of each node to the centrality of a given node, having more weight/relevance those nodes with greater dissimilarity, since these allow to the given node access to nodes that which themselves can not access directly.

Is noteworthy that <math>W</math> is non-negative because <math>A</math> and <math>D</math> are non-negative matrices, so we can use the [[Perron–Frobenius theorem]] to ensure that the above problem has a unique solution for ''λ'' = ''λ<sub>max</sub>'' with '''c''' non-negative, allowing us to infer the centrality of each node in the network. Therefore, the centrality of the i-th node is

:<math>c_i=\dfrac{1}{n}\sum_{j=1}^{n}W_{ij}c_{j}, \,\,\,\,\,\, i=1,\cdots,n</math>

where <math>n</math> is the number of the nodes in the network. Several dissimilarity measures and networks were tested in <ref>{{Cite web|url = http://www.nature.com/article-assets/npg/srep/2015/151125/srep17095/extref/srep17095-s1.pdf|title = Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|publisher = Nature Publishing Group|last1 = Alvarez-Socorro|first1 = A.J.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz|access-date = 2015-12-29|archive-date = 2016-03-07|archive-url = https://web.archive.org/web/20160307214705/http://www.nature.com/article-assets/npg/srep/2015/151125/srep17095/extref/srep17095-s1.pdf|url-status = live}}</ref> obtaining improved results in the studied cases.

== Centrality measures used in transportation networks ==
Transportation networks such as road networks and railway networks are studied extensively in transportation science and urban planning. A number of recent studies have focused on using centrality measures to analyze transportation networks. While many of these studies simply use generic centrality measures such as Betweenness Centrality, custom centrality measures have also been defined specifically for transportation network analysis. Prominent among them is '''Transportation Centrality'''.<ref name="Piraveenan-2023">{{Cite journal |last1=Piraveenan |first1=Mahendra |last2=Saripada |first2=Naressa Belle |date=2023 |title=Transportation Centrality: Quantifying the Relative Importance of Nodes in Transportation Networks Based on Traffic Modeling |journal=IEEE Access |volume=11 |pages=142214–142234 |doi=10.1109/ACCESS.2023.3339121 |issn=2169-3536|doi-access=free |bibcode=2023IEEEA..11n2214P }}</ref>

Transportation centrality measures the summation of the  proportions of paths from pairs of nodes in a network which go through the node under consideration. In this respect it is similar to Betweenness Centrality. However, unlike Betweenness Centrality which considers only shortest paths, Transportation Centrality considers all possible paths between a pair of nodes. Therefore, Transportation Centrality is a generic version of Betweenness Centrality, and under certain conditions, it indeed reduces to Betweenness Centrality.

Transportation Centrality of a given node ''v'' is defined as:<ref name="Piraveenan-2023" />


<math>TC(v)=1/((N-1)(N-2))\Sigma_{s\neq v \neq t} \frac{\Sigma_{i \in P^v_{s,t}}  e^{-\beta C^i_{s,t}}}{\Sigma_{j \in P^v_{s,t}}  e^{-\beta C^j_{s,t}}} </math>

==See also==
* [[Alpha centrality]]
* [[Core–periphery structure]]
* [[Distance (graph theory)|Distance in graphs]]

==Notes and references==
{{Reflist}}

==Further reading==
* Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.)  ''Network Analysis: Methodological Foundations'', pp.&nbsp;16–61, LNCS 3418, Springer-Verlag.

[[Category:Graph theory]]
[[Category:Graph algorithms]]
[[Category:Algebraic graph theory]]
[[Category:Networks]]
[[Category:Network analysis]]
[[Category:Network theory]]
[[Category:Graph distance]]