Project plan
Author
Carla Dickson
License
Creative Commons CC BY 4.0
Abstract
Betweenness centrality: shortest paths vs. random walks
Betweenness centrality: shortest paths vs. random walks
\documentclass[11pt]{article}
\usepackage[sort]{natbib}
\usepackage{fancyhdr}
\usepackage{amssymb}
\oddsidemargin 0.2cm
\topmargin -1.0cm
\textheight 24.0cm
\textwidth 15.25cm
\parindent=0pt
\parskip 1ex
\renewcommand{\baselinestretch}{1.1}
\pagestyle{fancy}
\lhead{\normalsize \textrm{Part 3 Project (Project Plan)}}
\chead{}
\rhead{\normalsize 22002905}
\lfoot{\normalsize \textrm{MA3PR}}
\cfoot{}
\rfoot{Dr D V Greetham}
\setlength{\fboxrule}{4pt} \setlength{\fboxsep}{2ex}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\begin{document}
\begin{center}
{\bf Betweenness centrality: shortest paths vs.random walks}
\end{center}
Network analysis is the method of representing a complex problem using a graph $G(V,E)$, where $V$ is the vertices of the graph and $E$ is the edges of the graph, and then analysing the graph as a network. The centrality of a network can be found using various measures \citep{2} such as betweenness centrality, first introduced by \citet{1}, which we will focus on. The betweenness of a node can, in short, be defined as the number of times a vertex $i$ is needed for the path a source vertex $s$ takes to reach it's target vertex $t$. However there are many variants to consider, most importantly which path will be taken to reach vertex $t$. Therefore this project aims to compare two different betweenness measures for various types of networks.
\\The simplest way to calculate betweenness centrality is by using the geodesic paths only and is called shortest path betweenness centrality. If $g_{ij}$ is the geodesic or shortest path from any vertex $i$ to vertex $j$ and $g_{ikj}$ is the geodesic path from vertex $i$ to $j$ which passes through a vertex $k$, the shortest path betweenness centrality of $k$ can be found by,
\begin{equation}
c_k^{BET}=\sum_{i}\sum_{j}\frac{g_{ikj}}{g_{ij}}.
\end{equation}
\\Equation (1) shows that shortest path betweenness centrality can be defined as the sum of the fraction of the geodesic between pairs of vertices that pass through $k$. However, realistically, not only the set of all shortest paths could be considered, for example only shortest paths up to a length $k$ may be considered for some problem which gives rise to k-shortest path betweenness as explored by \citet{3} and \citet{4}.
\\Now consider that the walk taken from the vertex $s$ to $t$ is by random walks as there is no necessity that only ideal paths, such as geodesic paths, may be used \citep{5}. Take a communication network as an example, if the information takes a random walk then it does not know where it is going and will simply go from vertex to vertex at random until it gets to vertex $t$ and will then stop.
\\Calculating the random walk betweenness of a network uses the same equations necessary to calculate the current flow betweenness \citep{5}. Define $G=(V,E)$ to be an electrical network, with a conductance function $c:V\rightarrow\mathbb{R}$, where an external current satisfies Kirchoff's current law and defined by the $s$-$t$-supply, $b_{st}:V\rightarrow\mathbb{R}$, enters the network at vertex $s$ and leaves at vertex $t$. Also, let $x:\overrightarrow{E}\rightarrow\mathbb{R}$ be a current in the network, where \overrightarrow{E} is the oriented edge set with oriented edges $\overrightarrow{e}$. Then the current-flow betweenness centrality $c_{CB}:V\rightarrow\mathbb{R}$ of an electrical network is given by,
\begin{equation}
c_{CB}=\frac{1}{(n-1)(n-2)}\sum_{s,t\in V}\frac{1}{2}\Big(-|b_{st}(v)|+\sum_{e\ni v}|x(\overrightarrow{e})|\Big) \hspace{1cm} \forall v\in V.
\end{equation}
\\Now let \textbf{M} be the matrix which is the probability that vertex $j$ will send a message to vertex $i$, where $M_{ij}=\frac{a_{ij}}{d_j}$ if $j\neq t$, and let \textbf{D} be the degree matrix of the graph so that $\textbf{D}^{-1}$ has inverted vertex degrees on its diagonal. The probability, $\textbf{v}^{st}$, to find the information at $i$ when it is on a random walk from vertex $s$ to $t$ is given by $\textbf{v}^{st}=D_t^{-1}.(I-M_t)^{-1}.\textbf{s}$, where \textbf{s} is a vector which is $1$ at vertex $s$ and $0$ everywhere else. This leads to show that random walk betweenness centrality is the same as the current-flow betweenness centrality shown in equation (2), hence $c_{RWB}(v)=c_{CB}(v)$.
\begin{thebibliography}{999}
\bibitem[Freeman(1977)]{1}{Freeman, L. C. (1977) ‘A set of measures of centrality based on Betweenness’, Sociometry, 40(1), p. 35. doi: 10.2307/3033543.}
\bibitem[Borgatti et al.(2005)]{2}{Borgatti, Stephen P.; Everett, Martin G. (2005). "A Graph-Theoretic Perspective on Centrality". Social Networks (Elsevier) 28: 446484. doi:10.1016/j.socnet.2005.11.005.}
\bibitem[White and Smyth (2003)]{3}{White, S. and Smyth, P. (2003) ‘Algorithms for estimating relative importance in networks’, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’03, . doi: 10.1145/956750.956782.}
\bibitem[Koschtzki et al.(2005)]{4}{Koschtzki, Dirk; Katharina A. Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, Oliver Zlotowski (2005). ”Centrality Indices”. In Ulrik Brandes, Thomas Erlebach.Network Analysis Methodological Foundations. LNCS 3418. Springer Verlag, Heidelberg, Germany. pp. 1660. ISBN 978-3-540-24979-5}
\bibitem[Newman(2005)]{5}{Newman, M. E. J. (2005) ‘A measure of betweenness centrality based on random walks’, Social Networks, 27(1), pp. 39–54. doi: 10.1016/j.socnet.2004.11.009.}
\end{thebibliography}{999}
\end{document}