Editing Centrality (section)

==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 a  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.