Eigenvector Centrality
From DML
Contents |
[edit] Overview
Below are notes gathered on the topic of Eigenvector Centrality.
Bonacich(2007) said:
Bonacich(1972) suggested that the eigenvector of the largest eigenvalue of an adjacency matrix could make a good network centrality measure. Unlike degree, which weights every contact equally, the eigenvector weights contacts according to their centralities. Eigenvector centrality can also be seen as a weighted sum of not only direct connections but indirect connections of every length. Thus it takes into account the entire pattern in the network.
[edit] Papers
- Some unique properties of eigenvector centrality - P. Bonacich. Social Networks, 29(4):555 – 564, 2007.
- Eigenvector-like measures of centrality for asymmetric relations - Phillip Bonacich, and Paulette Lloyd
- The mathematics of networks - M. E. J. Newman
- Centrality Estimation in Large Networks
- Wikipedia (not a paper)
- On Weighting Edges with Respect to Given Prestige
- P. Bonacich. '72
[edit] Pseudo-code
Principal eigenvector of the (possibly valued) adjacency matrix of a network.
Eigenvector centrality Is like a recursive version of degree centrality. The basic algorithm is as follows:
1. Start by assigning centrality score of 1 to all nodes (v_i = 1 for all i in the network)
2. Recompute scores of each node as weighted sum of centralities of all nodes in a node's neighborhood: v_i = sum_{j \in N} x_{ij}*v_j
3. Normalize v by dividing each value by the largest value
4. Repeat steps 2 and 3 until values of v stop changing.
A node is central to the extent that the node is connected to others who are central. An actor who is high on eigenvector centrality is connected to many actors who are themselves connected to many actors.
(Adapted from AnalyticTech)
[edit] Implementation 1: iGraph
function (graph, scale = TRUE, weights = NULL, options = igraph.arpack.default)
{
if (!is.igraph(graph)) {
stop("Not a graph object")
}
scale <- as.logical(scale)
if (is.null(weights) && "weight" %in% list.edge.attributes(graph)) {
weights <- E(graph)$weight
}
if (!is.null(weights) && any(!is.na(weights))) {
weights <- as.numeric(weights)
}
else {
weights <- NULL
}
options.tmp <- igraph.arpack.default
options.tmp[names(options)] <- options
options <- options.tmp
on.exit(.Call("R_igraph_finalizer", PACKAGE = "igraph"))
res <- .Call("R_igraph_eigenvector_centrality", graph, scale,
weights, options, PACKAGE = "igraph")
res
}
[edit] Implementation 2: NetworkX
def eigenvector_centrality(G,v=False):
"""
Eigenvector centrality for nodes (a measure of influence, based on
a node's neighbors connections).
Returns a dictionary of eigenvector centrality values keyed by node.
Eigenvector centrality is always between 0 and 1.
WARNING: Eigenvector centrality should ONLY be calculated on symmetric
network data (i->j & j-i), and this method REQUIRES the NumPy LinAlg package
Contact: Andrew Conway
agconway@gmail.com
Runtime: O(n^3)
Ref: Mathematics of networks, M. E. J. Newman, in The New Palgrave Encyclopedia of Economics,
2nd edition, L. E. Blume and S. N. Durlauf (eds.), Palgrave Macmillan, Basingstoke.
http://www-personal.umich.edu/~mejn/papers/palgrave.pdf
"""
from numpy.linalg import eig
from networkx.spectrum import adj_matrix
eigenvector_centrality = {}
G_mat = adj_matrix(G)
G_ev = eig(G_mat) # NumPy implementation of generalized eigenvector
G_evals = G_ev[0] # Eigenvalues array
G_evec_mat = G_ev[1] # Full N X N Eigenvector matrix
G_evals = G_evals.tolist()
# Error handling for complex numbers
try:
dominant_eigvector = G_evals.index(max(G_evals)) # Index of dominant Eigenvector
for i in range (0,G.number_of_nodes()):
eigenvector_centrality[i] = abs(G_evec_mat[i,dominant_eigvector])
except TypeError:
# For some arrays we must handle complex numbers by extracting 'real' portion
complex_temp = list()
for d in range(0,len(G_evals)):
complex_temp.append(G_evals[d].real)
dominant_eigvector = complex_temp.index(max(complex_temp)) # Index of dominant Eigenvector
for i in range (0,G.number_of_nodes()):
eigenvector_centrality[i] = abs(G_evec_mat[i,dominant_eigvector].real)
if not v:
return eigenvector_centrality
else:
return eigenvector_centrality[v]
[edit] Recap
Explanation about the igraph code above:
Eigenvector centrality scores correspond to the values of the first eigenvector of the graph adjacency matrix; these scores may, in turn, be interpreted as arising from a reciprocal process in which the centrality of each actor is proportional to the sum of the centralities of those actors to whom he or she is connected. In general, vertices with high eigenvector centralities are those which are connected to many other vertices which are, in turn, connected to many others (and so on). (The perceptive may realize that this implies that the largest values will be obtained by individuals in large cliques (or high-density substructures). This is also intelligible from an algebraic point of view, with the first eigenvector being closely related to the best rank-1 approximation of the adjacency matrix (a relationship which is easy to see in the special case of a diagonalizable symmetric real matrix via the $S Lambda S^{-1}$ decomposition).) [1]
