Eigenvector centrality
Eigenvector centrality is a network centrality measure that assigns importance scores to nodes in a graph based on their connections to other high-importance nodes, rather than merely the number of connections.[1] It is mathematically defined as the principal eigenvector of the graph's adjacency matrix, where the centrality vector c satisfies \lambda c = A c with \lambda being the largest eigenvalue and A the adjacency matrix, ensuring that a node's score is proportional to the sum of its neighbors' scores.[1] This approach captures recursive influence in networks, making it suitable for directed or undirected graphs where structural position matters.[2]
The concept was introduced by sociologist Phillip Bonacich in 1972 as a way to compute status scores in social networks by factoring the overlap matrix and using its dominant eigenvector to weight cliques and positions.[2] Bonacich's formulation posits that centrality S_i for node i follows \lambda S_i = \sum_j r_{ij} S_j, where r_{ij} represents standardized relational ties, allowing for both positive and weighted dependencies that propagate through the network.[2] This eigenvector-based method extends beyond simple degree centrality by accounting for the quality of connections, and it relies on the Perron-Frobenius theorem to guarantee a unique positive solution for irreducible matrices in strongly connected graphs.[1]
Eigenvector centrality has notable applications in diverse fields, including web search algorithms and social influence modeling. A prominent variant is Google's PageRank, developed by Sergey Brin and Larry Page in 1998, which adapts eigenvector centrality to rank web pages by treating hyperlinks as votes of importance while incorporating a damping factor to handle the web's directed structure and avoid sinks.[3] In social networks, it models influence diffusion, such as in DeGroot's learning process where beliefs converge to the eigenvector under repeated averaging.[1] Economically, it applies to input-output models like Leontief's production networks, where it quantifies sector interdependencies.[1] Limitations include sensitivity to network bipartiteness, which can lead to oscillating solutions, and computational demands for large-scale graphs, often addressed via power iteration methods.[1]
Definition and Overview
Core Concept
Eigenvector centrality serves as a measure of a node's importance in a network, where the significance of a node is determined not just by its direct connections, but by its links to other influential nodes. This approach captures the idea that connections to high-status or central actors enhance a node's own prestige, reflecting a broader notion of influence propagation through the network structure.[4]
At its core, eigenvector centrality follows a recursive definition: the centrality score of a node is proportional to the sum of the centrality scores of its neighbors. This self-referential quality means that a node's importance is evaluated in the context of the entire network, iteratively accounting for indirect influences rather than isolating local properties.[5][6]
To illustrate, consider a simple undirected graph with three nodes labeled A, B, and C, connected in a line as A—B—C. Here, node B emerges as the most central because its score incorporates the contributions from both A and C; nodes A and C gain equal centrality from their link to B, but less than B due to fewer high-value connections. This example highlights how centrality flows recursively, rewarding nodes that connect to others with potential influence.[1]
In contrast to degree centrality, which assesses importance solely by the number of direct neighbors and thus remains a local measure, eigenvector centrality provides a global perspective by weighting connections based on the embedded importance of those neighbors.[4]
Historical Development
The mathematical foundations of eigenvector centrality lie in the Perron-Frobenius theorem, developed in the early 20th century for analyzing positive and nonnegative matrices. Oskar Perron introduced the theorem in 1907, proving that a positive matrix possesses a unique largest positive real eigenvalue, accompanied by a strictly positive eigenvector, which dominates all other eigenvalues in magnitude. Ferdinand Georg Frobenius extended this result in 1912 to irreducible nonnegative matrices, ensuring similar properties hold even with zero entries, provided the matrix structure allows irreducibility. These insights, initially applied to Markov chains and economic growth models, provided the spectral guarantees essential for centrality measures in network contexts.[7]
Eigenvector centrality emerged in social network analysis through the work of Phillip Bonacich in 1972. Bonacich proposed the measure as a way to assess actor status by leveraging the principal eigenvector of the network's adjacency matrix, emphasizing that influence derives from connections to other influential actors rather than mere connection count. This approach addressed limitations in earlier centrality metrics by incorporating recursive prestige. The seminal paper, titled "Factoring and weighting approaches to status scores and clique identification," appeared in the Journal of Mathematical Sociology and established eigenvector centrality as a key tool for identifying cliques and status hierarchies in social graphs.[5]
In the 1980s and 1990s, eigenvector centrality evolved significantly within graph theory and sociology, with Bonacich's 1987 paper "Power and centrality: A family of measures" introducing a parameterized generalization that accounted for attenuation and negative ties, enabling analysis of power imbalances in directed networks. This work, published in the American Journal of Sociology, broadened the measure's applicability to asymmetric relations and influence propagation. Throughout the decade, researchers in sociology integrated it into studies of social capital and inequality, while graph theorists explored its spectral properties for structural insights, fostering widespread adoption in network research by the late 1990s.[8][9]
Mathematical Foundations
The adjacency matrix A of a graph G = (V, E) with n = |V| vertices is an n \times n matrix where the entry A_{ij} indicates the presence and possibly the weight of an edge from vertex j to vertex i. For unweighted directed graphs, A_{ij} = 1 if there is a directed edge from j to i, and $0 otherwise; for undirected graphs, A is symmetric with A_{ij} = A_{ji} = 1 if an undirected edge exists between i and j. In weighted graphs, entries A_{ij} are non-negative real numbers representing edge strengths, such as similarities or interaction intensities.
Eigenvector centrality assigns to each vertex i a score x_i that is the i-th component of the principal eigenvector \mathbf{x} of A, satisfying the eigenvalue equation A \mathbf{x} = \lambda \mathbf{x}, where \lambda is the largest (dominant) eigenvalue. This formulation, introduced by Bonacich, defines centrality recursively: a vertex's importance depends not only on its direct connections but also on the importance of its neighbors, as captured by the global structure of A.
In component form, the equation expands to x_i = \frac{1}{\lambda} \sum_{j=1}^n A_{ij} x_j for each i, meaning the centrality of vertex i is the average centrality of its in-neighbors, scaled by \lambda. For undirected unweighted graphs, this simplifies to x_i = \frac{1}{\lambda} \sum_{j \sim i} x_j, where the sum is over neighbors j adjacent to i. This recursive definition converges to the steady-state influence distribution under the assumption that connections propagate importance iteratively.
The principal eigenvector corresponds to centrality due to the Perron-Frobenius theorem, which applies to irreducible non-negative matrices like the adjacency matrix of a strongly connected directed graph (or connected undirected graph). The theorem guarantees that the largest eigenvalue \lambda is real, simple, and positive, with a unique corresponding eigenvector \mathbf{x} having strictly positive components (up to scaling); moreover, \lambda exceeds the absolute value of all other eigenvalues, ensuring dominance. This positivity and uniqueness imply that high-centrality vertices are those embedded in dense substructures of influential neighbors, as the eigenvector aggregates paths of arbitrary length weighted by connectivity.[1]
For disconnected graphs, the adjacency matrix is reducible, so the Perron-Frobenius theorem applies separately to each irreducible block corresponding to a strongly connected component. The global principal eigenvector is dominated by the component with the largest Perron root (its \lambda), assigning positive centrality scores primarily within that component while other components receive near-zero scores in the overall vector; thus, eigenvector centrality typically focuses analysis on the largest connected component to identify network-wide influencers.[1]
Eigenvalue and Normalization
In eigenvector centrality, the dominant eigenvalue \lambda of the adjacency matrix A plays a crucial role as a scaling factor that quantifies the overall influence or amplification of connectivity within the network. The centrality vector x satisfies the equation A x = \lambda x, where \lambda > 0 is the largest eigenvalue (guaranteed by the Perron-Frobenius theorem for irreducible non-negative matrices), and each component x_i represents a node's centrality as a weighted sum of its neighbors' centralities scaled by $1/\lambda. This scaling implies that larger values of \lambda correspond to networks with higher average path lengths or denser interconnections that propagate influence more effectively across nodes.[1][10][11]
Due to the nature of eigenvectors, the centrality vector x is defined only up to a scalar multiple, meaning solutions are non-unique without normalization; however, the Perron-Frobenius theorem ensures a unique positive eigenvector (up to scaling) associated with \lambda, which is selected for its all-positive components that align with intuitive notions of centrality in connected networks. To obtain comparable scores, normalization is applied by dividing x by an appropriate norm, yielding x' = x / \|x\|_p for p = 1, 2, or \infty. The choice of norm depends on the desired interpretation: the L1 norm (\sum_i x'_i = 1) treats scores as relative shares of total centrality, suitable for probabilistic interpretations like influence distribution; the L\infty norm (\max_i x'_i = 1) expresses scores as fractions of the most central node, emphasizing relative prominence; and the L2 norm (\|x'\|_2 = 1) produces a unit vector, often used in iterative algorithms for numerical stability.[10][12]
Normalization impacts the interpretability of scores by shifting focus from absolute magnitudes (which depend on \lambda and network size) to relative or standardized measures, enabling comparisons within and sometimes across networks. For instance, L1 normalization facilitates viewing centralities as proportions of overall network influence, while L2 normalization preserves geometric properties like orthogonality in spectral analysis but may complicate direct probabilistic readings. Without normalization, scores remain arbitrary, but the positive eigenvector choice ensures consistent ranking regardless of scaling.[1][12]
Computation Methods
Power Iteration Algorithm
The power iteration algorithm provides an efficient iterative approach to approximate the principal eigenvector of a graph's adjacency matrix A, thereby computing eigenvector centrality scores for large networks where exact methods may be computationally prohibitive. The method begins by selecting an initial vector \mathbf{x}^{(0)}, often a uniform vector or one based on node degrees, which is then repeatedly multiplied by A and normalized to estimate the dominant eigenvector. This process leverages the fact that repeated application of A amplifies the component corresponding to the largest eigenvalue, allowing the vector to converge toward the desired centrality measure.[13][1]
The step-by-step procedure is as follows: (1) Initialize \mathbf{x}^{(0)} as a positive vector, such as the all-ones vector or the degree vector of the nodes. (2) For each iteration k \geq 0, compute \mathbf{y}^{(k+1)} = A \mathbf{x}^{(k)}. (3) Normalize \mathbf{x}^{(k+1)} = \mathbf{y}^{(k+1)} / \| \mathbf{y}^{(k+1)} \|_2 to ensure the vector remains bounded and scaled appropriately. (4) Repeat until the change between consecutive vectors falls below a tolerance threshold (e.g., \| \mathbf{x}^{(k+1)} - \mathbf{x}^{(k)} \| < \epsilon) or a maximum number of iterations is reached. Upon convergence, the components of \mathbf{x}^{(k+1)} serve as the eigenvector centrality scores, typically further normalized to sum to 1.[1][14][15]
Convergence of the power iteration is guaranteed under the condition that the dominant eigenvalue \lambda_1 is simple and strictly greater in magnitude than the second-largest eigenvalue |\lambda_2|, with the rate determined by the spectral gap ratio |\lambda_2 / \lambda_1|—larger gaps lead to faster convergence, often linear at rate |\lambda_2 / \lambda_1|. For irreducible non-negative matrices like adjacency matrices of connected undirected graphs, the Perron-Frobenius theorem ensures a positive dominant eigenvector, and the method converges from any positive initial vector. In practice, the algorithm typically requires 20-50 iterations for many real-world networks to achieve sufficient accuracy, depending on the graph's spectral properties and the tolerance.[16][17][15]
Here is pseudocode for the power iteration algorithm:
function EigenvectorCentralityPowerIteration(A, x0, tol=1e-6, max_iter=100):
x = x0 / ||x0||_2 // Initialize and normalize
for k in 1 to max_iter:
y = A * x // Matrix-vector multiplication
x_new = y / ||y||_2 // Normalize
if ||x_new - x||_2 < tol:
break
x = x_new
if k == max_iter:
warn("Convergence not achieved within max_iter")
return x // Centrality scores
function EigenvectorCentralityPowerIteration(A, x0, tol=1e-6, max_iter=100):
x = x0 / ||x0||_2 // Initialize and normalize
for k in 1 to max_iter:
y = A * x // Matrix-vector multiplication
x_new = y / ||y||_2 // Normalize
if ||x_new - x||_2 < tol:
break
x = x_new
if k == max_iter:
warn("Convergence not achieved within max_iter")
return x // Centrality scores
This implementation assumes A is the adjacency matrix and handles sparse representations efficiently via vector operations.[14][1]
For sparse graphs with n nodes and m edges, each iteration involves a matrix-vector multiplication costing O(m) time (or O(n d) where d is average degree), yielding an overall time complexity of O(k m) where k is the number of iterations until convergence. This makes the method scalable for large sparse networks, such as social or web graphs, outperforming dense matrix methods that scale as O(n^3).[15][18]
A practical tip for faster convergence is to initialize \mathbf{x}^{(0)} with the degree centrality vector, as eigenvector centrality is strongly correlated with degree in many networks, providing a better starting approximation in the eigenspace and reducing the number of required iterations. Normalization at each step ensures numerical stability, particularly for unweighted graphs, tying into the standard L2 normalization used in eigenvector centrality definitions.[13]
Direct Eigenvalue Solvers
Direct eigenvalue solvers provide non-iterative approaches to compute the exact eigenvectors of the adjacency matrix for eigenvector centrality, particularly effective for small to medium-sized dense graphs where precision is prioritized over computational speed.[19] These methods leverage established linear algebra techniques to solve the eigenvalue problem A \mathbf{v} = \lambda \mathbf{v}, where A is the adjacency matrix and the principal eigenvector \mathbf{v} corresponding to the largest eigenvalue \lambda defines the centrality scores.[20]
Standard libraries facilitate this computation; for instance, Python's NumPy library uses the numpy.linalg.eig function, which employs LAPACK routines based on the QR algorithm to find all eigenvalues and eigenvectors of a square matrix.[21] Similarly, MATLAB's eig function computes the full eigendecomposition, suitable for symmetric adjacency matrices in undirected graphs.[22] For symmetric matrices like undirected graph adjacencies, the QR algorithm iteratively applies QR decompositions to converge to the Schur form, from which eigenvalues and eigenvectors are extracted, while the Jacobi method uses successive rotations to diagonalize the matrix directly.[20][23]
The full process involves constructing the adjacency matrix A, invoking the solver to obtain all eigenvalues and eigenvectors, and selecting the eigenvector associated with the largest real eigenvalue (often the Perron-Frobenius eigenvalue for non-negative irreducible matrices).[19] The selected eigenvector is then normalized, typically to unit length or such that its components sum to 1, to yield the centrality measures.[1]
These direct methods yield exact results up to machine precision, making them ideal for applications requiring high accuracy on graphs with up to a few thousand nodes.[20] However, they incur O(n^3) time complexity for dense n \times n matrices due to the underlying decompositions, limiting scalability for very large networks compared to iterative alternatives like power iteration.[23]
Consider a simple undirected triangle graph with three nodes fully connected, represented by the symmetric adjacency matrix
A = \begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix}.
Applying a direct solver, such as the QR algorithm, reveals eigenvalues \lambda_1 = 2, \lambda_2 = -1, \lambda_3 = -1, with the principal eigenvector \mathbf{v}_1 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} (normalized to unit length), indicating equal centrality for all nodes as expected in a symmetric complete graph.[20] The centrality scores, after scaling to sum to 1, are \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right).[1]
Variants and Extensions
Katz Centrality
Katz centrality, also known as Katz-Bonacich centrality, extends eigenvector centrality by incorporating both direct and indirect influences on a node while attenuating the contribution of longer paths through a decay parameter. Introduced by Leo Katz in 1953 as a status index for sociometric analysis, it addresses limitations in simpler measures like degree centrality by considering the prestige of a node's connections rather than just their quantity. This approach quantifies a node's relative influence in directed networks, such as social choice graphs, where incoming links represent endorsements or choices.[24]
The core formulation defines the centrality vector \mathbf{x} recursively as the sum of baseline importance for each node and the attenuated centralities of its predecessors:
\mathbf{x} = \alpha A \mathbf{x} + \beta \mathbf{1}
Here, A is the adjacency matrix (with a_{ij} = 1 if there is a directed edge from j to i, and 0 otherwise), \alpha \in (0, 1/\lambda_{\max}) is the attenuation factor (where \lambda_{\max} is the largest eigenvalue of A), \beta > 0 is a scaling constant (typically set to 1 for unnormalized scores or $1 - \alpha for row-stochastic normalization), and \mathbf{1} is a vector of ones. Rearranging yields the closed-form solution:
\mathbf{x} = \beta (I - \alpha A)^{-1} \mathbf{1}
This expression represents the total discounted number of walks ending at each node, where walks of length k are weighted by \alpha^k. The inversion ensures convergence for \alpha < 1/\lambda_{\max}, avoiding issues in graphs without a dominant eigenvalue.[24][4]
In relation to eigenvector centrality, Katz centrality generalizes it by adding the \beta \mathbf{1} term, which assigns intrinsic value to isolated or low-degree nodes, preventing zero scores in disconnected components. As \beta \to 0 and \alpha \to 1/\lambda_{\max}, Katz centrality converges to the principal eigenvector (up to scaling), emphasizing global structure. The choice of \alpha tunes the measure: low values prioritize immediate neighbors (resembling degree centrality), while higher values capture broader network effects. Computationally, it involves solving a linear system (I - \alpha A)\mathbf{x} = \beta \mathbf{1}, which is efficient for sparse matrices using iterative methods like Gauss-Seidel, especially in large networks.[1][4]
Katz centrality has been influential in social sciences for modeling prestige and influence propagation, such as in citation networks or collaboration graphs, where it outperforms eigenvector measures in directed settings by balancing local and global importance. Its parametric flexibility allows adaptation to specific domains, like economic models of peer effects, and it remains a foundational method in network analysis software libraries.[24][4]
PageRank, developed by Sergey Brin and Lawrence Page, represents a specialized adaptation of eigenvector centrality tailored for ranking web pages based on their hyperlink structure.[25] Introduced in 1998, it conceptualizes hyperlinks as votes of importance from one page to another, where a page's rank is influenced not only by the quantity of incoming links but also by the quality of the linking pages.[25] This approach was patented in 2001 as a method for node ranking in linked databases.[26]
At its core, PageRank employs a random surfer model to simulate user navigation on the web. In this model, the surfer randomly follows outgoing hyperlinks with probability d (the damping factor, typically set to 0.85) or, with probability $1-d, teleports to a random page uniformly chosen from all n pages.[25] This teleportation mechanism prevents the surfer from getting trapped in portions of the web with no outgoing links and ensures convergence by introducing a uniform restart distribution. The resulting PageRank vector x satisfies the equation:
x = (1 - d) \frac{1}{n} + d A' x
where A' is the column-normalized adjacency matrix (with each column summing to 1, reflecting out-degree normalization), and \frac{1}{n} is the uniform vector of all ones divided by n.[25] This formulation handles dangling nodes—pages with no outgoing links—by treating them as linking uniformly to all pages during normalization, ensuring the matrix remains stochastic.[25]
Equivalently, x is the principal eigenvector of the Google matrix G, defined as:
G = \frac{1 - d}{n} E + d A'
where E is the n \times n matrix of all ones.[25] The damping factor d = 0.85 balances the influence of link-following versus random jumps, promoting numerical stability and reflecting empirical observations of web surfing behavior.[25]
Unlike the more general Katz centrality, which attenuates path contributions exponentially without specific web adaptations, PageRank incorporates explicit out-degree normalization to account for varying link densities across pages and enforces a uniform teleportation restart to model global web accessibility.[27]
Applications
Network Analysis in Social Sciences
In social network analysis, eigenvector centrality serves as a key measure for assessing prestige and status, assigning higher scores to actors whose connections link to other high-status actors, thereby capturing the recursive nature of influence in interpersonal structures. This contrasts with simpler metrics by emphasizing the quality of ties, where an individual's prestige derives from associations with influential peers, such as opinion leaders endorsed by fellow leaders. Pioneered by Bonacich in his 1972 work on status scores, this approach uses the principal eigenvector of the network's adjacency matrix to quantify such embedded status, providing a foundational tool for sociologists studying hierarchical dynamics.
Bonacich further refined these ideas in 1987, developing a family of centrality measures that explicitly link eigenvector-based scores to power and dependence in social exchange networks, revealing how centrality can both enable and constrain influence depending on network position. In citation networks, eigenvector centrality evaluates academic impact by prioritizing papers cited by other high-impact works, as demonstrated in analyses of interdisciplinary journals where it identifies key contributions beyond mere citation counts. Similarly, in friendship graphs, it gauges social capital by aggregating the centrality of an actor's contacts, showing how connections to well-networked individuals enhance access to resources and opportunities, such as in studies of medical students' performance where higher scores correlated with better outcomes (r = 0.31, p = 0.01).[28][29][30]
Sociological applications extend to inequality measures, where eigenvector centrality highlights disparities in influence; for instance, weak intergroup ties can amplify centrality imbalances, affecting resource allocation and power distributions across social divides. Bonacich's power-dependence framework has been empirically applied to model such inequalities in exchange settings, underscoring how central actors gain leverage over less connected ones. Compared to degree centrality, eigenvector centrality's advantage lies in its sensitivity to tie quality, avoiding overvaluation of isolated high-degree nodes, though it assumes positive reinforcement in connections, potentially underperforming in networks with mixed or negative relations.[31][28][28]
A illustrative case study involves a co-authorship network of 1,589 scientists in network theory, derived from 2,742 collaborative links compiled by Newman in 2006. Applying eigenvector centrality via tools like Gephi revealed Uetz P. and Cagney G. as the most central nodes (both scoring 1.00), reflecting their ties to prolific collaborators like Barabási A.-L., which amplified their structural influence despite not having the highest degree (34 for Barabási). This analysis, computed through power iteration on the adjacency matrix, demonstrated how eigenvector scores pinpoint key brokers in small-scale collaboration ecosystems, informing patterns of knowledge diffusion.[32][32]
Eigenvector centrality has played a pivotal role in web search engines by enabling the ranking of pages based on the importance of their incoming links, where the centrality of a page is determined by the centralities of the pages linking to it. In Google Search, this concept is operationalized through PageRank, a query-independent ranking algorithm that computes a global score for each web page by treating the web as a directed graph and solving for the principal eigenvector of its transition matrix, adjusted with a damping factor to model user navigation behavior.[3] Introduced in 1998, PageRank revolutionized search by prioritizing pages endorsed by other authoritative sources, leading to more relevant results compared to prior keyword-based methods.
Extensions of eigenvector centrality in information retrieval include personalized variants and related algorithms like HITS. Personalized PageRank adapts the standard computation by biasing the random surfer model toward user-specific pages, such as bookmarks or past queries, to deliver tailored rankings without recomputing the entire graph eigenvector.[3] Meanwhile, the HITS algorithm, developed concurrently in 1998, employs two coupled eigenvector computations to distinguish hubs (pages that link to many authorities) from authorities (pages linked by many hubs), focusing on query-dependent subgraphs for topic-specific ranking.
The adoption of these methods has significantly enhanced search relevance and robustness since 1998, with PageRank's damping factor (typically set to 0.85) mitigating spam by ensuring scores propagate even from isolated pages, preventing manipulation through link farms.[3] This approach propelled Google to dominance, handling over 100 million queries daily by the end of 2000 while delivering results that better reflect page importance over mere popularity.[33]
Beyond search ranking, eigenvector centrality supports recommendation systems in web contexts, such as predicting links in co-citation graphs where a document's score increases based on citations from high-centrality peers, facilitating suggestions for related content. For instance, in a simplified web graph, a hub page like a directory linking to authoritative pages can achieve a high hub score in HITS iterations, as its value aggregates the authorities' scores through iterative updates.
Comparisons with Other Centralities
Versus Degree Centrality
Degree centrality measures a node's local popularity by simply counting the number of its direct connections, or neighbors, in the network, treating all links equally regardless of the status of the connected nodes. In contrast, eigenvector centrality refines this approach by assigning higher importance to connections with influential neighbors, where a node's score depends recursively on the scores of its neighbors, emphasizing global influence over mere local connectivity. This weighting makes eigenvector centrality superior for capturing indirect prestige or power, as being linked to a high-status node amplifies one's own centrality more than an equivalent link to a low-status node.[34]
Consider a star graph, where one central node connects to all others, and peripheral nodes connect only to the center: the central node receives the maximum score under both degree centrality (degree n-1) and eigenvector centrality (due to its connections to all nodes), while peripherals score low on both (degree 1 and minimal eigenvector contribution). In a line graph (or path), endpoints have degree 1 and low eigenvector scores, internal nodes have degree 2 but eigenvector scores peak at the center and taper toward the ends, highlighting how eigenvector centrality better distinguishes nuanced positions beyond raw counts.[35]
Empirical studies show a high correlation between degree and eigenvector centrality in random graphs (coefficients ranging from 0.88 to 0.99), where uniform connectivity makes the measures align closely, but this correlation weakens or diverges in scale-free networks (coefficients around 0.66–0.91), where hubs amplify differences and eigenvector better identifies true influencers.[36][37] Degree centrality serves as a quick, computationally efficient approximation for very large graphs when global structure is less critical, but eigenvector centrality is preferred for precise influence assessment in heterogeneous networks.[38]
Versus Betweenness Centrality
Betweenness centrality measures a node's importance by calculating the fraction of shortest paths between all pairs of other nodes that pass through it, thereby quantifying the node's potential control over the flow of information or resources in the network.[39] This contrasts with eigenvector centrality, which assesses a node's influence based on its connections to other influential nodes, emphasizing recursive popularity within densely connected clusters rather than pathway mediation.[40] For instance, a node acting as a bridge between two separate cliques—such as a cut vertex linking otherwise disconnected communities—typically exhibits high betweenness centrality due to its role in nearly all shortest paths across the cliques, but only moderate eigenvector centrality because its limited direct ties to high-influence nodes within each clique dilute its recursive score.[41] Computationally, exact betweenness centrality requires O(n m) time using Brandes' algorithm on graphs with n nodes and m edges, making it more demanding for sparse networks compared to eigenvector centrality, which can be approximated efficiently through iterative power methods in O(k m) time for k iterations until convergence.[42] Due to these complementary perspectives—eigenvector centrality highlighting influential hubs in cohesive groups and betweenness centrality identifying brokerage positions—researchers often combine both measures to achieve more robust node rankings in network analysis, such as in social or collaboration studies.[40]