Eigenvector centrality

In graph theory, eigenvector centrality (also called eigencentrality or prestige score[1]) is a measure of the influence of a node in a 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.[2] [3]

Google's PageRank and the Katz centrality are variants of the eigenvector centrality.[4]

Using the adjacency matrix to find eigenvector centrality

For a given graph ${\displaystyle G:=(V,E)}$ with ${\displaystyle |V|}$ vertices let ${\displaystyle A=(a_{v,t})}$ be the adjacency matrix, i.e. ${\displaystyle a_{v,t}=1}$ if vertex ${\displaystyle v}$ is linked to vertex ${\displaystyle t}$, and ${\displaystyle a_{v,t}=0}$ otherwise. The relative centrality, ${\displaystyle x}$, score of vertex ${\displaystyle v}$ can be defined as:

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}}$

where ${\displaystyle M(v)}$ is a set of the neighbors of ${\displaystyle v}$ and ${\displaystyle \lambda }$ is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation

${\displaystyle \mathbf {Ax} =\lambda \mathbf {x} }$

In general, there will be many different eigenvalues ${\displaystyle \lambda }$ for which a non-zero eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be non-negative implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.[5] The ${\displaystyle v^{\text{th}}}$ component of the related eigenvector then gives the relative centrality score of the vertex ${\displaystyle v}$ 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 eigen vector 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.[4] 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.[1] The PageRank of a node ${\displaystyle v}$ has recursive dependence on the PageRank of other nodes that point to it. The normalized adjacency matrix ${\displaystyle N}$ is defined as:

$${\displaystyle 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}}}$$

where ${\displaystyle od(u)}$ is the out-degree of node ${\displaystyle u}$. The normalized normalized eigenvector centrality score is defined as:

$${\displaystyle p(v)=\sum _{u}{N^{T}(v,u)\cdot p(u)}}$$

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.[6]

The earliest use of eigenvector centrality is by Edmund Landau in an 1895 paper on scoring chess tournaments.[7][8]

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.[9][10]
• In neuroscience, the eigenvector centrality of a neuron in a model neural network has been found to correlate with its relative firing rate.[6]
• In a standard class of models of opinion updating or learning (sometimes called DeGroot learning models), the social influence of a node over eventual opinions is equal to its eigenvector centrality.
• The definition of eigenvector centrality has been extended to multiplex or multilayer networks.[11]
• In a study using data from the Philippines, the authors showed how political candidates' families had disproportionately high eigenvector centrality in local intermarriage networks.[12]
• In a economic public goods problems, a person's eigenvector centrality can be interpreted as how much that person's preferences influence an efficient social outcome (formally, a Pareto weight in a Pareto efficient social outcome).[13]

See also

• Centrality

References

1. Zaki, Mohammed J.; Meira, Jr., Wagner (2014). Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press. ISBN 9780521766333.
2. M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved 2006-11-09. Cite journal requires |journal= (help)
3. 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. (2018). "Eigenvector centrality for characterization of protein allosteric pathways". Proceedings of the National Academy of Sciences. 115 (52): E12201–E12208. doi:10.1073/pnas.1810452115. PMC 6310864. PMID 30530700.CS1 maint: multiple names: authors list (link)
4. David Austin. "How Google Finds Your Needle in the Web's Haystack". AMS.
5. M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved 2006-11-09. Cite journal requires |journal= (help)
6. cite paper | author = Fletcher, Jack McKay and Wennekers, Thomas| title = From Structure to Activity: Using Centrality Measures to Predict Neuronal Activity| journal = International Journal of Neural Systems| volume = 0| number = 0| pages = 1750013| year = 2017| doi = 10.1142/S0129065717500137| url = http://www.worldscientific.com/doi/abs/10.1142/S0129065717500137 }}
7. Edmund Landau (1895). "Zur relativen Wertbemessung der Turnierresultate". Deutsches Wochenschach (11): 366–369. doi:10.1007/978-1-4615-4819-5_23.
8. Holme, Peter (15 April 2019). "Firsts in network science". Retrieved 17 April 2019.
9. Altman, Alon; Tennenholtz, Moshe (2005). Ranking systems. New York, New York, USA: ACM Press. doi:10.1145/1064009.1064010. ISBN 1-59593-049-3.
10. Palacios-Huerta, Ignacio; Volij, Oscar (2004). "The Measurement of Intellectual Influence". Econometrica. The Econometric Society. 72 (3): 963–977. doi:10.1111/j.1468-0262.2004.00519.x. hdl:10419/80143. ISSN 0012-9682.
11. Solá, Luis; Romance, Miguel; Criado, Regino; Flores, Julio; García del Amo, Alejandro; Boccaletti, Stefano (2013). "Eigenvector centrality of nodes in multiplex networks". Chaos: An Interdisciplinary Journal of Nonlinear Science. AIP Publishing. 23 (3): 033131. doi:10.1063/1.4818544. ISSN 1054-1500.
12. Cruz, Cesi; Labonne, Julien; Querubin, Pablo (2017). "Politician Family Networks and Electoral Outcomes: Evidence from the Philippines". American Economic Review. University of Chicago Press. 107 (10): 3006–37. doi:10.1257/aer.20150343.
13. Elliott, Matthew; Golub, Benjamin (2019). "A Network Approach to Public Goods". Journal of Political Economy. University of Chicago Press. 127 (2): 730–776. doi:10.1086/701032. ISSN 0022-3808.