Friday, November 9, 2012

Intuition Behind Eigenvector Centrality

The following R code visualizes the network and provides intuitive connections between degree and eigenvector centrality as well as the power iteration method of estimating  the dominant eigenvector from a matrix.
# *------------------------------------------------------------------
# | 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

Created by Pretty R at inside-R.org

4 comments:

  1. Nice idea!

    just FYI in your code you use G before it is intialized!

    ReplyDelete
  2. Thanks! I was copying and pasting from Notepad++ into the prettyR synatx highlighter and apparently got out of order. Glad you noticed. The code should be fixed now.

    ReplyDelete
  3. For those who don't have R, how about showing the resulting graphs here on the site?

    ReplyDelete
  4. Stay tuned. I actually realized the other day, it would make the post a log better if I showed the graphs. For a similar example with graphs, check out they other posts tagged with social network analysis. One post compares R with net draw and includes graphs.

    ReplyDelete