Revision c6e2ce5a thesis/ch2_centrality.tex
thesis/ch2_centrality.tex  

1  1 
%!TEX root = main.tex 
2  2  
3  3 
\chapter{Centrality} \label{sec:centrality} 
4 
Centrality\footnote{it is also refered to by other terms: centrality indices or centrality measures} is one the fundamental and useful measure in social network analysis to identify the influential vertices or edges in the network. However, how the vertices (or edges) are considered to be important depend on different centrality measures. In this thesis, we are concerned mainly with betweenness centrality, which belongs to the shortestpath based centrality according to the classification by \cite{Brandes:2005:NAM:1062400}. 

4 
Centrality\footnote{it is also referred to by other terms: centrality indices or centrality measures} is one the fundamental and useful measure in social network analysis to identify the influential vertices or edges in the network. However, how the vertices (or edges) are considered to be important depend on different centrality measures. In this thesis, we are concerned mainly with betweenness centrality, which belongs to the shortestpath based centrality according to the classification by \cite{Brandes:2005:NAM:1062400}.


5  5  
6 
Since \cite{Bavelas1948} first described the concept of centrality, many centrality indices were defined and used for different purposes. Since there is no single centrality indices that are supreme over all others, we should consider of which centrality indices to use in certain application.


6 
Since \cite{Bavelas1948} first described the concept of centrality, many centrality indices were defined and used for different purposes. Since there is no single centrality indices that are supreme over all others, we should consider which centrality indices to use in certain application. 

7  7  
8 
In \cref{sec:centrality_definition} we will begin with the definition of centrality. Then in \cref{sec:centrality_shortest_path_based} we will go deeper on the family of shortestpath based centrality, starting from the stress centrality, moving on to the betweenness centrality, and finally the relative betweenness centrality.


8 
In \cref{sec:centrality_definition} we begin with the definition of centrality. Then in \cref{sec:centrality_shortest_path_based} we go deeper on the family of shortestpath based centrality, starting from the stress centrality, moving on to the betweenness centrality, and finally the relative betweenness centrality.


9  9  
10  10 
For those who wants to have a broader knowledge on the centrality, then \citep{Brandes:2005:NAM:1062400} classified centrality for vertices and edges into nine families, and summarized them in great detail. 
11  11  
12 
In different paper, different type of notations are used for the same type of concepts. Hence, to keep this report coherent, I will use the same of notation for the same concept, and this might different from the notation used in the original papers.


12 
In different paper, different type of notations are used for the same type of concepts. Hence, to keep this report coherent, I use the same of notation for the same concept, and this might different from the notation used in the original papers. 

13  13  
14  14 
\section{Definition of centrality} \label{sec:centrality_definition} 
15 
Centrality index is defined by assigning the score representing the importance of nodes or edges in the network. When changing the way of assigning the score, we arrive at different centrality indices. But the underlying concept is that centrality indices must depend only on the structure of the network. \citet{Brandes:2005:NAM:1062400} pointed out the fact that even though there is no strict definition for centrality, we can still find the common ground shared by different centrality indices, and he coined the term \emph{Structure Index} 

15 
Centrality index can be roughly defined as a function assigning score representing the importance for nodes or edges in the network. When changing the way of assigning the score for each vertex, we arrive at different centrality indices. However, we cannot have arbitrary function assigning random values for nodes in graph, and call those values the centrality. 

16  
17 
\citet{Brandes:2005:NAM:1062400} pointed out that even though there is no strict definition for centrality, we can still find the common ground shared by different centrality indices. The underlying concept is that centrality indices must depend only on the structure of the network. To put it simply, centrality indices a way of assigning a score for each vertex (or edge) in the network, based completely on structure of the graph. Formally, he coined the term \emph{Structural Index}, and stated that a centrality index $c$ is required to be a structural index. 

16  18  
17  19 
\theoremstyle{definition} 
18 
\begin{definition}{Structure Index}


20 
\begin{definition}{\textbf{Structural Index}}


19  21 
Let $G=(V,E)$ be a weighted, directed or undirected multigraph and let $X$ represent the set of vertices or edges of $G$, respectively. A realvalued function $s$ is called a structural index if and only if the following condition is satisfied: $\forall x \in X: G \simeq H \Rightarrow s_G(x) = s_H(\phi(x)),$ where $s_G(x)$ denotes the value of $s(x)$ in G 
20  22 
\end{definition} 
21  23  
24 
Before beginning with the main section describing betweenness centrality, a simple centrality measure called \emph{degree centrality} is going to be presented, so that reader can have an easytounderstand example on what is centrality. The score of degree centrality for each node is equal to the number of connection that node has. See \cref{fig:degree_centrality}. Then later, we move on to more complex centrality measurements based on shortestpaths. 

25  
26 
\begin{figure}[hbp] 

27 
\centering 

28 
\includegraphics{images/line_graph_degree_horizontal.png} 

29 
\caption[Example for degree centrality]{Degree centrality score for each node} 

30 
\label{fig:degree_centrality} 

31 
\end{figure} 

32  
33  
22  34 
\section{Shortestpath based centrality} \label{sec:centrality_shortest_path_based} 
23 
This section presents two types of shortestpath based centrality. Shortest paths are defined on both vertices and edges. Basically those two centrality indices are based on the number of shortest paths between a pair of vertices or edges. \cref{sec:centrality_stress_centrality} and \cref{sec:centrality_bc} will present those two measures in deep.


35 
This section presents two types of shortestpath based centrality: \emph{stress centrality}, and \emph{betweenness centrality}. Basically those two centrality indices are based on the set of shortest paths between a pair of vertices or edges. \cref{sec:centrality_stress_centrality} and \cref{sec:centrality_bc} presents those two measures in deep.


24  36  
25 
In communication, information does not only flow in the shortest path, where the shortest path might represent the path where the total traverse time is shortest. However, in a lot of application, shortest path are chosen to forward information through the network. For example, in \textbf{XXXX is OLSR use shortest path to forward packets in the network}.


37 
In communication, information does not only flow in the shortest path, where the shortest path might represent the path where the total traversing time is shortest. However, in a lot of application, shortest path are chosen to forward information through the network. For example, OLSR routing protocol provides shortest path routes for all nodes in the network. And OLSR routing protocol is used widely in Wireless Community Networks  the network that we want to apply centrality to improve their existing routing protocol.


26  38  
27  39 
\subsubsection{Stress Centrality} \label{sec:centrality_stress_centrality} 
28 
The concept was by \cite{Shimblel1953}. 

40 
The concept was presented by \cite{Shimblel1953}, the idea is the know quantify how much information is flowing through a vertex in a network. With that definition, if a vertex $v$ lies on more shortest paths, then more information is passed through $v$ and it must handle a higher workload, or ``stress''. Formally, it is defined in \cref{eq:stress_centrality_long}. It is the summation over all possible source $s$, and all possible target $t$ that are different than $v$. 

41  
42 
\begin{equation} 

43 
\label{eq:stress_centrality_long} 

44 
c_S(v) = \sum_{s \neq v} \sum_{t \neq v} \sigma_{st}(v) 

45 
\end{equation} 

46 
where $\sigma_{st}(v)$ denotes the number of shortest paths containing $v$. To simplify the notation for \cref{eq:stress_centrality_long}, we might write it as follow: 

47  
48 
\begin{equation} 

49 
\label{eq:stress_centrality} 

50 
c_S(v) = \sum_{s \neq t \neq v} \sigma_{st}(v) 

51 
\end{equation} 

52 
However for the clarity, I will stick with the notation in \cref{eq:stress_centrality_long}. 

29  53  
30 
Different type of network (such as in wireless community network, in social networks) calls for different centrality indices.


54 
Note that the formula for stress centrality $c_S(v)$ does not include the shortest paths that start or end in $v$. And the stress centrality is calculated for all shortest paths between any pair of vertices.


31  55  
32 
\textbf{XXX Find out the application of stress centrality} 

33  56  
34 
Formally: 

57 
\subsubsection{Betweenness Centrality} \label{sec:centrality_bc} 

58 
The concept of \emph{betweenness centrality} was introduced independently by \citet{Freeman1977} and \citet{Anthonisse1971}. It can be viewed as a relative version of stress centrality. Here we first define the betweenness centrality, then continue with the motivation for betweenness centrality and its application. 

59  
60 
We define $\delta_{st}(v)$  the 

61 
\emph{pairdependency}\footnote{In \cite{Freeman1978215}, the term pairdependency is equivalent with the term \emph{dependency} used in \cite{Brandes01afaster}. To keep consistency, in this thesis, the definition of pairdependency and dependency follow the \cite{Brandes01afaster} } 

62 
of a pair $s, t \in V$ on an intermediary $v \in V$. 

35  63  
36  64 
\begin{equation} 
37 
\label{eq:stress_centrality_long}


38 
c_S(v) = \sum_{s \neq v \in V} \sum_{t \neq v \in V} \sigma_{st}(v)


65 
\label{eq:pair_dependency}


66 
\delta_{st}(v) = \frac{\sigma_{st}(v)}{\sigma_{st}}


39  67 
\end{equation} 
68 
where $\sigma_{st}(v)$) is the number of shortest paths from $s$ to $t$ that are passing through $v$. And $\sigma_{st}$ is the number of shortest paths from $s$ to $t$. $\delta_{st}(v)$ represents the probability that vertex $v$ falls randomly on any of the shortest paths connecting $s$ and $t$. Assume that the communication in the network follows the shortest path, then $\delta_{st}(v)$ can be interpreted as the probability that vertex $v$ can involve, intercept, enhance or inhibit the communication between $s$ and $t$. 

40  69  
41 
where $\sigma_{st}(v)$ denotes the number of shortest paths containing $v$. 

70 
The betweenness centrality of a single vertex $c_B(v)$ is defined as: 

71  
72 
\begin{equation} 

73 
\label{eq:betweenness_centrality} 

74 
c_B(v) = \sum_{s \neq v} \sum_{t \neq v} \delta_{st}(v) = \sum_{s \neq v} \sum_{t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}} 

75 
\end{equation} 

42  76  
43 
To simplify the notation for \cref{eq:stress_centrality_long}, we might write it as follow:


77 
From the original formula for betweenness centrality in \cref{eq:betweenness_centrality}, several variants for betweenness centrality was introduced in \cite{Brandes2008136}, such as edge betweenness centrality, group betweenness centrality, etc. The one we are mostly interested in is the betweenness centrality with endpoints vertices included. It means that the $c_S(v)$ take into account even the shortest paths starting or ending with $v$, and it doesn't require the source $s$ or the target vertex $t$ to be different from $v$. \cref{eq:betweenness_centrality_endpoints_inclusion} shows the formula for betweenness centrality with source and target included.


44  78  
45  79 
\begin{equation} 
46 
\label{eq:stress_centrality}


47 
c_S(v) = \sum_{s \neq t \neq v \in V} \sigma_{st}(v)


80 
\label{eq:betweenness_centrality_endpoints_inclusion}


81 
c_B(v) = \sum_{s \in V} \sum_{t \in V} \delta_{st}(v) = \sum_{s \in V} \sum_{t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}


48  82 
\end{equation} 
49  83  
50 
\subsubsection{Betweenness Centrality} \label{sec:centrality_bc} 

84 
\subsubsection{Relative Betweenness Centrality} 

85 
After introducing betweenness centrality, \citeauthor{Freeman1977} presented another measurement \cite{Freeman1977}, called \emph{relative betweenness centrality} under the argument that betweenness centrality cannot be used to compare the influential of vertices from network of different size (e.g. different number of nodes). 

86  
87 
He argued that for vertices $v, u$ to have the same betweenness centrality only mean that they have the same potential for control in absolute terms. That means they can facilitate or inhibit the same number of communications. Note, we implicitly assume that all communications are conducted along shortest paths. However, the $c_B$ does not show the relative potential for control within the network. \cref{fig:bc_vs_bc_relative} illustrate that even though $c_B(v) = c_B(u_i) = 3, i = 1, 2, 3, 4$, the potential for control of vertex $v$ is much larger than vertex $u_i$. For example, removing vertex $v$ and the network would be disconnected and no communication can happen between vertices. Therefore, $v$ have a total control of the network. Meanwhile, removing any $u_i$ does not have that same disastrous effect since each $u_i$ only control part of the communications between pair of vertices. 

88  
89 
\begin{figure}[h] 

90 
\centering 

91 
\begin{tabular}{c c} 

92 
\subfloat[fig 1][BC]{\includegraphics[scale=0.3]{images/star_3_bc.png}} & 

93 
\subfloat[fig 2][BC]{\includegraphics[scale=0.3]{images/star_6_bc.png}} \\ 

94 
\subfloat[fig 1][Relative BC]{\includegraphics[scale=0.3]{images/star_3_bcrelative.png}} & 

95 
\subfloat[fig 2][Relative BC]{\includegraphics[scale=0.3]{images/star_6_bcrelative.png}} \\ 

96 
\end{tabular} 

97 
\caption[Comparision for Betweenness Centrality and Relative Betweenness Centrality]{ 

98 
Comparision for Betweenness Centrality and Relative Betweenness Centrality: We see that even though the red nodes have the same betweenness centrality score, it is clearly that the red node of the left graph has more control over the traffic flow within the network. For example, when the red node of the left graph is destroyed, the graph is disconnected, and no information can flow between blue nodes. On the other hands, if any red node of the right graph is cut out from the graph, the graph is still connected. The relative betweenness centrality can reflect the important of the red node for both graphs better, by setting it to $1$ for the left graph, and $0.2$ for the right graph. 

99 
} 

100 
\label{fig:bc_vs_bc_relative} 

101 
\end{figure} 

102  
103 
When a vertex of interest $v$ is the center node of the star graph, just as \cref{fig:bc_vs_bc_relative} (a), its betweenness centrality score is the biggest score that a graph with $n$ nodes can have. And the maximum betweenness centrality score that a vertex can achieve is shown be to: 

104 
\begin{equation} 

105 
\label{eq:max_bc_score} 

106 
\max c_B(v) = \frac{n^2  3n + 2}{2} 

107 
\end{equation} 

51  108  
52 
The concept of \emph{betweenness centrality} was introduced independently by \citet{Freeman1977} and \citet{Anthonisse1971}. It can be viewed as a relative version of stress centrality. Here we will first define the betweenness centrality, then we will go on with the motivation for betweenness centrality and its application. 

53  
54 
We define $\delta_{st}(v)$  the 

55 
\emph{pairdependency} 

56 
\footnote{In \cite{Freeman1978215}, the term pairdependency is equivalent with the term \emph{dependency} used in \cite{Brandes01afaster}. To keep consistency, in this thesis, the definition of pairdependency and dependency follow the \cite{Brandes01afaster} } 

57 
of a pair $s, t \in V$ on an intermediary $v \in V$. 

58  
59 
\begin{equation} 

60 
\label{eq:pair_dependency} 

61 
\delta_{st}(v) = \frac{\sigma_{st}(v)}{\sigma_{st}} 

62 
\end{equation} 

63  
64 
where $\sigma_{st}(v)$) is the number of shortest paths from $s$ to $t$ that are passing through $v$. And $\sigma_{st}$ is the number of shortest paths from $s$ to $t$. $\delta_{st}(v)$ represents the probability that vertex $v$ falls randomly on any of the shortest paths connecting $s$ and $t$. Assume that the communication in the network follows the shortest path, then $\delta_{st}(v)$ can be interpreted as the probability that vertex $v$ can involve, intercept, enhance or inhibit the communication between $s$ and $t$. 

65  
66 
The betweenness centrality of a single vertex $c_B(v)$ is defined as: 

67  
68 
\begin{equation} 

69 
\label{eq:betweenness_centrality} 

70 
c_B(v) = \sum_{s \neq t \neq v \in V} \delta_{st}(v) = \sum_{s \neq t \neq v \in V} \frac{\sigma_{st}(v)}{\sigma_{st}} 

71 
\end{equation} 

72  
73 
introduced \cite{Freeman1977} \textbf{XXX} the betweenness centrality to address the problem of being unable to compare the potential for control for vertices in different networks with stress centrality. For example, in \cref{fig:stress_vs_bc_centrality}, the stress centrality for vertices $v, u_i$ are the same. But when removing one vertex $v$, all vertices in top row of the graph are disconnected from all the vertices in the bottom row. For the network with $u_i$, for example, removing one or two vertices $u_1, u_2$ does not disconnect the network. The information can still flow freely from the top row to the bottom row following the path passing through the remaining vertex $u_3$. Therefore, using stress centrality alone, we cannot decide on whether some node are more critical for the network than the others, and betweenness centrality came up as a measure to capture the potential for control a vertex has on the network. 

74  
75 
\begin{figure}[h] 

76 
\caption{ 

77 
$c_S(u_i) = 16$ and $c_B(u_i) = \frac{1}{3}, i = 1, 2, 3$ and $c_S(v) = 16$ but $c_B(v) = 1$. It shows that stress centrality cannot be used to determine to potential for control a vertex has. This example is taken from \cite{Brandes:2005:NAM:1062400} 

78 
} 

79 
\label{fig:stress_vs_bc_centrality} 

80 
\centering 

81 
\includegraphics[scale=1.0]{images/stress_vs_bc_centrality.png} 

82 
\end{figure} 

83  
84 
\begin{equation} 

85 
\label{eq:max_stress_centrality} 

86 
\max c_B(v) = \frac{n^2  3n + 2}{2} 

87 
\end{equation} 

88  
89 
\textbf{XXX The application of BC} 

90  
91 
\subsubsection{Relative Betweenness Centrality} 

92 
The socalled relative betweenness centrality measure $c'_B(v)$ was also introduced by \cite{Freeman1977}: 

93  
94 
\begin{equation} 

95 
\label{eq:bc_relative} 

96 
c'_B(v) = \frac{2 c_B(v)}{n^2  3n + 2} 

97 
\end{equation} 

98  
99 
where $c_B(v)$ is the betweenness centrality defined above, and $n$ is the number of vertices in the network. 

100  
101 
\citeauthor{Freeman1977} argued that for vertices $v, u$ to have the same betweenness centrality only mean that they have the same potential for control in absolute terms. That means they can facilitate or inhibit the same number of communitions. Note, we implicitly assume that all communications are conducted along shortest paths. However, the $c_B$ does not show the relative potential for control within the network. \cref{fig:bc_vs_bc_relative} illustrate that even though $c_B(v) = c_B(u_i) = 3, i = 1, 2, 3$, the potential for control of vertex $v$ is much larger than vertex $u_i$. For example, removing vertex $v$ and the network will be disconnected and no communication can happen between vertices. Therefore, $v$ have a total control of the network. Meanwhile, removing any $u_i$ does not have that same disastrous effect since each $u_i$ only control part of the communications between pair of vertices. 

102  
103 
\begin{figure}[h] 

104 
\caption{ 

105 
$c_B(v) = 3$ and $c'_B(v) = 1$, and $c_B(u_i) = 3, i = 1, 2, 3$ but $c'_B(u_i) = 0.2$. It shows that the same betweenness centrality for vertices $v, u_i$ for 2 different networks does not equal to the same potential for control for their respective networks. 

106 
} 

107 
\label{fig:bc_vs_bc_relative} 

108 
\centering 

109 
\begin{subfigure}{.45\textwidth} 

110 
% \centering 

111 
\includegraphics[scale=0.3]{images/star_3.png} 

112 
\caption{A subfigure} 

113 
\label{fig:sub1} 

114 
\end{subfigure}% 

115 
\begin{subfigure}{.45\textwidth} 

116 
\centering 

117 
\includegraphics[scale=0.3]{images/star_6.png} 

118 
\caption{A subfigure} 

119 
\label{fig:sub2} 

120 
\end{subfigure} 

121 
\end{figure} 

109 
The socalled \emph{relative betweenness centrality} measure $c'_B(v)$ is the fraction between thet betweenness centrality $c_B(v)$ in \cref{eq:betweenness_centrality} divided by its possible maximum score. See \cref{eq:bc_relative} for the formula of relative betweenness centrality $c'_B(v)$: 

122  110  
111 
\begin{equation} 

112 
\label{eq:bc_relative} 

113 
c'_B(v) = \frac{2 c_B(v)}{n^2  3n + 2} 

114 
\end{equation} 

115 
where $c_B(v)$ is the betweenness centrality defined in \cref{eq:betweenness_centrality}, and $n$ is the number of vertices in the network. 
Also available in: Unified diff