Intuition Behind Eigenvector Centrality

EV Centrality v3.r

# r code to support post: http://econometricsense.blogspot.com/2012/11/update-more-intuition-behind.html

# *------------------------------------------------------------------
# | PROGRAM NAME: EV Centrality v3
# | DATE: 11/9/12
# | CREATED BY: MATT BOGARD
# | PROJECT FILE: P:\R  Code References\SNA            
# *----------------------------------------------------------------
# | PURPOSE:  An update to my companion code to Justification and Application of
# |  Eigenvector Centrality by Leo Spizzirri        
# |  https://www.math.washington.edu/~morrow/336_11/papers/leo.pdf
# *------------------------------------------------------------------
 
# specify the adjacency matrix
A <- matrix(c(0,1,0,0,0,0,
                        1,0,1,0,0,0,
                        0,1,0,1,1,1,
                        0,0,1,0,1,0,
                        0,0,1,1,0,1,
                        0,0,1,0,1,0 ),6,6, byrow= TRUE)
 
# plot the network
library(igraph)
G<-graph.adjacency(A, mode=c("undirected")) # convert adjacency matrix to an igraph object
plot(G, layout = layout.fruchterman.reingold)  # initial plot
cent<-data.frame(bet=betweenness(G),eig=evcent(G)$vector) # calculate betweeness & eigenvector centrality 
 
# create vertex names and scale by centrality
plot(G, layout = layout.fruchterman.reingold, vertex.size = 20*evcent(G)$vector, vertex.label = as.factor(rownames(cent)), main = 'Network Visualization in R')
 
#-----------------------------------------------------------------
# compute eigenvalues and eigenvectors directly via eigen function
#------------------------------------------------------------------            
EV <- eigen(A) 
max(EV$values)  # find the maximum eigenvalue
 
# get the eigenvector associated with the largest eigenvalue
centrality <- data.frame(EV$vectors[,1]) 
names(centrality) <- "Centrality"
print(centrality)
 
#-------------------------------------------------
# user defined calculations for degree centrality
#--------------------------------------------------
 
# compute degree centrality
x <- c(1,1,1,1,1,1)
 
A%*%x # sum of all 1st degree connections
# gives sum of # of 1st degree connections of neighbors
A%*%A%*%x
# gives sum of # of 2nd degree connections of neighbors
A%*%A%*%A%*%x
 
#-----------------------------------------------------
#  intuition behind eigenvector centraltiy
#----------------------------------------------------
 
# function for iterative summation      
MM <- function(k,M){
                  B_k <- NULL
       B_k <- M
 
           for (i in 1:k){
    B_k <- B_k%*%M
     }
     return(B_k)
}  
# sum of # of 1st degree connections of neighbors for each vertex
MM(1,A)%*%x
# sum of # of 2nd degree connections of neighbors for each vertex
MM(2,A)%*%x
# sum of # of 3rd degree connections of neighbors for each vertex
MM(3,A)%*%x
 
# if we normalize this with each iteration as k -> infinity 
# the resulting vector approaches the EV of A 
 
# k = 1
MM(1,A)%*%x/(norm(MM(1,A)%*%x,type="F"))
# k = 10
MM(10,A)%*%x/(norm(MM(10,A)%*%x,type="F"))
# k = 100
MM(100,A)%*%x/(norm(MM(100,A)%*%x,type="F"))
 
# this is essentially the power iteration algorithm for computing EV centrality