Centrality

Social network analysis methods examine topology of a network in order to find interesting structure within it. Network structure, however, is the product of both its topology (or social links) and the dynamical processes (or flow) taking place on the network. The flow determines how ideas, pathogens, or influence flow along social links. Borgatti [2005], for example, argued that a node's centrality, a measure often used to identify important or influential actors in a social network, gives a summary of its participation in the flow taking place on the network.

Random walks: PageRank


To see the movie, click here .

The movie above shows a random walk on the Karate Club network [Zachary, 1977], a benchmark network used for social network analysis. At each time step, with probability a the random walker chooses one of the out-neighbors of the current node at random and moves to it, and with probability (1-a) it teleports, or jumps, to a random node. Each visit by the walker increases the size of the node. After a long time, the size of nodes will reach a stationary distribution, given by PageRank.

Epidemics: Alpha-Centrality

An epidemic represents another type of flow on a network. An epidemic is a dynamic process that, unlike the random walk, simultaneously transitions to all the neighbors of a given node (and successfully infects each node, or survives at that node, with a probability a). The movie above shows an epidemic spreading on the Karate Club graph. Under some conditions, it reaches a stationary state, given by Alpha-Centrality. Alpha-Centrality was introduced by Bonacich [1987] as a generalization of the Katz index of a node. When infection probability is at epidemic threshold, Alpha-Centrality is proportional to Eigenvector centrality. This measure, introduced by Bonacich [2001] is given by the eigenvector corresponding to the largest eigenvalue of the adjacency matrix of the graph [Ghosh and Lerman, 2011]. Incidentally, the epidemic threshold is given by the inverse of the largest eigenvalue of the adjacency matrix [Wang et al., 2003].

Matlab code

Let A be unweighted adjacency matrix, such as A(i,j)=1 if an edge exists between nodes i and j, and 0 otherwise.
N=size(A,1);
e=ones(1,N);
t=ones(N,1);
Di=diag(e*A); % diagonal matrix of in-degrees
Do=diag(A*t); % diagonal matrix of out-degrees

PageRank

a=0.3; % damping factor
s=e/N; % uniform starting vector
pr=s;
for i=1:100
     pr=(1-a)*s+a*pr*Do*A;
end
100*pr'

Alpha-Centrality

a=0.1; % damping factor has to be smaller than 1/lambda0, where lambda0 is largest eigenvalue of A
s=A*t;
cr=s;
for i=1:20
    cr=s+a*A*cr;
end
cr

References


Copyright 2013 University of Southern California Information Sciences Institute