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.

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].

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 |

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' |

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 |

- P. Bonacich and P. Lloyd. Eigenvector-like measures of centrality for asymmetric relations. Social Networks, 23(3):191-201, 2001.
- P. Bonacich. Power and Centrality, a family of measures. 1987
- S. Borgatti. Centrality and network flow. Social Networks, 27(1):55{71, January 2005.
- R. Ghosh and K. Lerman. Parameterized centrality metric for network analysis. Physical Review E, 83(6):066118, 2011. paper
- Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos. Epidemic spreading in real networks: an eigenvalue viewpoint. In Proceedings of the 22nd Symposium on Reliable Distributed Systems, pages 25-34, Los Alamitos, CA, USA, October 2003. IEEE.
- W. W. Zachary. An information ow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452{473, 1977.

Copyright 2013 University of Southern California Information Sciences Institute