{{short description|Measure in graph theory}} In graph theory, '''eigenvector centrality''' (also called '''eigencentrality''' or '''prestige score<ref name=":0">{{Cite book|last1=Zaki|first1=Mohammed J.|title=Data Mining and Analysis: Fundamental Concepts and Algorithms|last2=Meira |first2=Wagner Jr.|publisher=Cambridge University Press|year=2014|isbn=9780521766333}}</ref>''') is a measure of the influence of a node in a connected network. Relative scores are assigned 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. A high eigenvector score means that a node is connected to many nodes who themselves have high scores.<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>{{cite journal |last1 = Negre |first1 = Christian F. A. |last2 = Morzan |first2 = Uriel N. |last3 = Hendrickson |first3 = Heidi P. |last4 = Pal |first4 = Rhitankar |last5 = Lisi |first5 = George P. |last6 = Loria |first6 = J. Patrick |last7 = Rivalta |first7 = Ivan |last8 = Ho |first8 = Junming |last9 = Batista |first9 = Victor S. |title = Eigenvector centrality for characterization of protein allosteric pathways |journal = Proceedings of the National Academy of Sciences |date = 2018 |volume = 115 |issue = 52 |arxiv = 1706.02327 |bibcode = 2018PNAS..11512201N |doi = 10.1073/pnas.1810452115 |doi-access = free |pmid = 30530700 |pmc = 6310864 }} </ref>
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|author=David Austin|publisher=AMS}}</ref>
== Using the adjacency matrix to find eigenvector centrality == For a given graph <math>G:=(V,E)</math> with <math>|V|</math> 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:
: <math>x_v = \frac 1 \lambda \sum_{t \in M(v)} x_t = \frac 1 \lambda \sum_{t \in V} a_{v,t} x_t </math>
where <math>M(v)</math> is the set of 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 eigenvalues <math>\lambda</math> for which a non-zero eigenvector solution exists. However, the connectedness assumption and the additional requirement that all the entries in the eigenvector be non-negative imply (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.<ref>{{cite journal|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}}</ref> The <math>v^\text{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 algorithms 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.
== Normalized eigenvector centrality scoring == Google's PageRank is based on the normalized eigenvector centrality, or normalized prestige, combined with a random jump assumption.<ref name=":0" /> The PageRank of a node <math>v</math> has recursive dependence on the PageRank of other nodes that point to it. The normalized adjacency matrix ''<math>N</math>'' is defined as:<math display="block">N(u,v) = \begin{cases} {1 \over \operatorname{od}(u)}, & \text{if } (u,v) \in E \\ 0, & \text{if }(u,v) \not\in E \end{cases}</math>where <math>od(u)</math> is the out-degree of node <math>u</math>, or in vector form:
: <math> \mathbf{N} = \mathbf{diag}(\mathbf{Ae})^{-1} \mathbf{A}</math>,
where <math>\mathbf{e}</math> is the vector of ones, and <math>\mathbf{diag}(\mathbf{x})</math> is the diagonal matrix of vector <math>\mathbf{x}</math>. <math>\mathbf{N}</math> is a row-stochastic matrix.
The normalized eigenvector prestige score is defined as:
: <math>p(v) = \sum_{u} {N^T(v,u) \cdot p(u)},</math> or in vector form, : <math>\mathbf{p} = \mathbf{N}^T \mathbf{p}.</math>
== Applications == Eigenvector centrality is a measure of the influence a node has on a network. If a node is pointed to by many nodes (which also have high eigenvector centrality) then that node will have high eigenvector centrality.<ref name="sta">{{cite journal |last1 = Fletcher |first1 = Jack Mckay |last2 = Wennekers |first2 = Thomas |title = From Structure to Activity: Using Centrality Measures to Predict Neuronal Activity |journal = International Journal of Neural Systems |date = 2018 |volume = 28 |issue = 2 | doi = 10.1142/S0129065717500137 |doi-access = free |pmid = 28076982 |hdl = 10026.1/9713 |hdl-access = free}}</ref>
The earliest use of eigenvector centrality is by Edmund Landau in an 1895 paper on scoring chess tournaments.<ref>{{cite journal | author = Edmund Landau |year = 1895 |title = Zur relativen Wertbemessung der Turnierresultate |journal = Deutsches Wochenschach |volume= 11|issue=42|pages = 366–369}}</ref><ref>{{cite web|url=https://petterhol.me/2019/04/15/firsts-in-network-science/ |title=Firsts in network science |last=Holme |first=Peter |date=15 April 2019 |access-date=17 April 2019}}</ref>
More recently, researchers across many fields have analyzed applications, manifestations, and extensions of eigenvector centrality in a variety of domains: * Eigenvector centrality is the unique measure satisfying certain natural axioms for a ranking system.<ref name="Altman Tennenholtz 2005 p. ">{{cite conference | last1=Altman | first1=Alon | last2=Tennenholtz | first2=Moshe | title=Proceedings of the 6th ACM conference on Electronic commerce - EC '05 | chapter=Ranking systems | publisher=ACM Press | location=New York, New York, USA | year=2005 | pages=1–8 | isbn=1-59593-049-3 | doi=10.1145/1064009.1064010 }}</ref><ref name="Palacios-Huerta Volij 2004 pp. 963–977">{{cite journal | last1=Palacios-Huerta | first1=Ignacio | last2=Volij | first2=Oscar | title=The Measurement of Intellectual Influence | journal=Econometrica | publisher=The Econometric Society | volume=72 | issue=3 | year=2004 | issn=0012-9682 | doi=10.1111/j.1468-0262.2004.00519.x | pages=963–977| hdl=10419/80143 | url=http://volij.co.il/publications/papers/Rankings.pdf | hdl-access=free }}</ref> * In neuroscience, the eigenvector centrality of a neuron in a model neural network has been found to correlate with its relative firing rate.<ref name="sta" /> * Eigenvector centrality and related concepts have been used to model opinion influence in sociology and economics, as in the DeGroot learning model. * The definition of eigenvector centrality has been extended to multiplex <ref name="Solá Romance Criado Flores 2013 p=033131">{{cite journal | last1=Solá | first1=Luis | last2=Romance | first2=Miguel | last3=Criado | first3=Regino | last4=Flores | first4=Julio | last5=García del Amo | first5=Alejandro | last6=Boccaletti | first6=Stefano | title=Eigenvector centrality of nodes in multiplex networks | journal=Chaos: An Interdisciplinary Journal of Nonlinear Science | volume=23 | issue=3 | year=2013 | issn=1054-1500 | doi=10.1063/1.4818544 | page=033131| pmid=24089967 | arxiv=1305.7445 | bibcode=2013Chaos..23c3131S | s2cid=14556381 | url=http://oa.upm.es/31184/ }}</ref> and multilayer networks through the concept of versatility <ref name="De Domenico et al NatComms 2015">{{cite journal | last1=De Domenico | first1=Manlio | last2=Solè-Ribalta | first2=ALbert | last3=Omodei | first3=Elisa | last4=Gòmez | first4=Sergio | last5=Arenas | first5=Alex | title=Ranking in interconnected multilayer networks reveals versatile nodes| journal=Nature Communications | volume=6 | year=2015 | issn=2041-1723 | doi=10.1063/1.4818544 | page=6868| pmid=25904405 | s2cid=14556381 | url=https://www.nature.com/articles/ncomms7868 | arxiv=1305.7445 | bibcode=2013Chaos..23c3131S }}</ref> * In a study using data from the Philippines, researchers showed how political candidates' families had disproportionately high eigenvector centrality in local intermarriage networks.<ref>{{cite journal | last1=Cruz| first1=Cesi| last2=Labonne| first2=Julien| last3=Querubin| first3=Pablo| title=Politician Family Networks and Electoral Outcomes: Evidence from the Philippines | journal=American Economic Review | publisher=University of Chicago Press | volume=107| issue=10 | year=2017 | doi=10.1257/aer.20150343| pages=3006–37 | doi-access=free}}</ref> * Eigenvector centrality has been extensively applied to study economic outcomes, including cooperation in social networks.<ref>{{Cite book|last=Jackson|first=Matthew O.|url=http://www.jstor.org/stable/j.ctvcm4gh1|title=Social and Economic Networks|date=2010-11-01|publisher=Princeton University Press|isbn=978-1-4008-3399-3|doi=10.2307/j.ctvcm4gh1|jstor=j.ctvcm4gh1}}</ref> In economic public goods problems, a person's eigenvector centrality can be interpreted as how much that person's preferences influence an efficient social outcome.<ref name="Elliott Golub 2019 pp. 730–776">{{cite journal|last1=Elliott|first1=Matthew|last2=Golub|first2=Benjamin|year=2019|title=A Network Approach to Public Goods|url=https://authors.library.caltech.edu/41754/|journal=Journal of Political Economy|publisher=University of Chicago Press|volume=127|issue=2|pages=730–776|doi=10.1086/701032|issn=0022-3808|s2cid=158834906}}</ref>
== See also == * Centrality
== References == {{Reflist}}
Category:Graph theory Category:Network analysis