root / latex / report_feb_10.tex @ 4ca27bae
History | View | Annotate | Download (6.7 KB)
| 1 |
\documentclass[12pt]{article}
|
|---|---|
| 2 |
% This first part of the file is called the PREAMBLE. It includes |
| 3 |
% customizations and command definitions. The preamble is everything |
| 4 |
% between \documentclass and \begin{document}.
|
| 5 |
|
| 6 |
\usepackage[margin=1in]{geometry} % set the margins to 1in on all sides
|
| 7 |
\usepackage{graphicx} % to include figures
|
| 8 |
\graphicspath{ {report_images/} } % '/' is needed
|
| 9 |
\usepackage{epstopdf} % for the .ps image
|
| 10 |
\epstopdfsetup{update}
|
| 11 |
\DeclareGraphicsExtensions{.eps}
|
| 12 |
\epstopdfDeclareGraphicsRule{.eps}{pdf}{.pdf}{ps2pdf -dEPSCrop -dNOSAFER #1 \OutputFile}
|
| 13 |
\usepackage[noabbrev,capitalise]{cleveref}
|
| 14 |
\usepackage{amsmath} % great math stuff
|
| 15 |
\usepackage{amsfonts} % for blackboard bold, etc
|
| 16 |
\usepackage{amsthm} % better theorem environments
|
| 17 |
\usepackage{listings} % to add code
|
| 18 |
\lstset{language=Java}
|
| 19 |
\renewcommand{\lstlistingname}{Code} % change "Listing 1.1" to "Code 1.1"
|
| 20 |
|
| 21 |
\usepackage[utf8]{inputenc}
|
| 22 |
\usepackage{color}
|
| 23 |
|
| 24 |
\usepackage{cite}
|
| 25 |
|
| 26 |
\usepackage[colorlinks]{hyperref} % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url
|
| 27 |
\hypersetup{citecolor=green}
|
| 28 |
\hypersetup{linkcolor=red}
|
| 29 |
\hypersetup{urlcolor=blue}
|
| 30 |
\usepackage{cleveref}
|
| 31 |
|
| 32 |
\definecolor{codegreen}{rgb}{0,0.6,0}
|
| 33 |
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
|
| 34 |
\definecolor{codepurple}{rgb}{0.58,0,0.82}
|
| 35 |
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
|
| 36 |
|
| 37 |
\lstdefinestyle{mystyle}{
|
| 38 |
backgroundcolor=\color{backcolour},
|
| 39 |
commentstyle=\color{codegreen},
|
| 40 |
keywordstyle=\color{magenta},
|
| 41 |
numberstyle=\tiny\color{codegray},
|
| 42 |
stringstyle=\color{codepurple},
|
| 43 |
basicstyle=\footnotesize, |
| 44 |
breakatwhitespace=false, |
| 45 |
breaklines=true, |
| 46 |
captionpos=b, |
| 47 |
keepspaces=true, |
| 48 |
numbers=left, |
| 49 |
numbersep=5pt, |
| 50 |
showspaces=false, |
| 51 |
showstringspaces=false, |
| 52 |
showtabs=false, |
| 53 |
tabsize=2 |
| 54 |
} |
| 55 |
|
| 56 |
\lstset{style=mystyle}
|
| 57 |
\DeclareMathOperator{\id}{id}
|
| 58 |
|
| 59 |
\newcommand{\bd}[1]{\mathbf{#1}} % for bolding symbols
|
| 60 |
\newcommand{\RR}{\mathbb{R}} % for Real numbers
|
| 61 |
\newcommand{\ZZ}{\mathbb{Z}} % for Integers
|
| 62 |
\newcommand{\col}[1]{\left[\begin{matrix} #1 \end{matrix} \right]}
|
| 63 |
\newcommand{\comb}[2]{\binom{#1^2 + #2^2}{#1+#2}}
|
| 64 |
|
| 65 |
\usepackage[T1]{fontenc}
|
| 66 |
\AtBeginDocument{%
|
| 67 |
\begingroup\lccode`~=`_% |
| 68 |
\lowercase{\endgroup\let~}_%
|
| 69 |
\catcode`_=12 |
| 70 |
} |
| 71 |
|
| 72 |
\usepackage{booktabs} % To thicken table lines
|
| 73 |
|
| 74 |
\usepackage{algorithm}
|
| 75 |
\usepackage[noend]{algpseudocode} % For pseudocode
|
| 76 |
|
| 77 |
\begin{document}
|
| 78 |
|
| 79 |
\title{Thesis - Report Feb 10 - Heuristic Betweenness Centrality vs Brandes Betweenness Centrality}
|
| 80 |
|
| 81 |
\author{Quynh Nguyen - DISI - University of Trento}
|
| 82 |
|
| 83 |
\maketitle |
| 84 |
\clearpage |
| 85 |
|
| 86 |
\section{The discrepency between Heuristic Betweenness Centrality (HBC) and Brandes Betweenness Centrality (BBC)}
|
| 87 |
\textbf{Summary:} the gap between the default version (of both networkx and BGL) to calculate BC is due to the inclusion of the source.
|
| 88 |
|
| 89 |
Algorithm 2 in \cite{Brandes2008136} show the variant of calculating betweenness centrality with endpoints included. The paper also mentions that we can "restrict the inclusion of endpoints to either sources or targets".
|
| 90 |
|
| 91 |
\begin{algorithm}
|
| 92 |
\caption{Including endpoints (both sources + targets)}\label{accumulation_endpoints}
|
| 93 |
\begin{algorithmic}[1]
|
| 94 |
\Procedure{accumulation}{}
|
| 95 |
\State $c_B[s] \leftarrow c_B[s] + (|S| - 1)$ |
| 96 |
\For{$v \in V$}
|
| 97 |
$\delta[v] \leftarrow 0$ |
| 98 |
\EndFor |
| 99 |
|
| 100 |
\While{$S$ not empty}
|
| 101 |
\State pop $w \leftarrow S$ |
| 102 |
\For{$v \in Pred[w]$}
|
| 103 |
$\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (1 + \delta[w])$
|
| 104 |
\EndFor |
| 105 |
\If{$w \neq s$}
|
| 106 |
$c_B[w] \leftarrow c_B[w] + \delta[w] + 1$ \Comment{$w$ is target of $s$ once}
|
| 107 |
\EndIf |
| 108 |
\EndWhile |
| 109 |
\EndProcedure |
| 110 |
\end{algorithmic}
|
| 111 |
\end{algorithm}
|
| 112 |
|
| 113 |
\begin{algorithm}
|
| 114 |
\caption{Including targets}\label{accumulation_targets}
|
| 115 |
\begin{algorithmic}[1]
|
| 116 |
\Procedure{accumulation}{}
|
| 117 |
\For{$v \in V$}
|
| 118 |
$\delta[v] \leftarrow 0$ |
| 119 |
\EndFor |
| 120 |
|
| 121 |
\While{$S$ not empty}
|
| 122 |
\State pop $w \leftarrow S$ |
| 123 |
\For{$v \in Pred[w]$}
|
| 124 |
$\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (1 + \delta[w])$
|
| 125 |
\EndFor |
| 126 |
\If{$w \neq s$}
|
| 127 |
$c_B[w] \leftarrow c_B[w] + \delta[w] + 1$ \Comment{$w$ is target of $s$ once}
|
| 128 |
\EndIf |
| 129 |
\EndWhile |
| 130 |
\EndProcedure |
| 131 |
\end{algorithmic}
|
| 132 |
\end{algorithm}
|
| 133 |
|
| 134 |
\begin{algorithm}
|
| 135 |
\caption{Heuristic Betweenness Centrality}\label{accumulation_heuristic}
|
| 136 |
\begin{algorithmic}[1]
|
| 137 |
\Procedure{accumulation}{}
|
| 138 |
\For{$v \in V$}
|
| 139 |
$\delta[v] \leftarrow 0$ |
| 140 |
\EndFor |
| 141 |
\While{$S$ not empty}
|
| 142 |
\State pop $w \leftarrow S$ |
| 143 |
\State $h \leftarrow $ get_the_communication_intensity_between $(w, s)$ |
| 144 |
\For{$v \in Pred[w]$}
|
| 145 |
$\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (h + \delta[w])$
|
| 146 |
\EndFor |
| 147 |
\If{$w \neq s$}
|
| 148 |
$c_B[w] \leftarrow c_B[w] + \delta[w] + h$ |
| 149 |
\EndIf |
| 150 |
\EndWhile |
| 151 |
\EndProcedure |
| 152 |
\end{algorithmic}
|
| 153 |
\end{algorithm}
|
| 154 |
|
| 155 |
\begin{figure}[h]
|
| 156 |
\caption{Comparison between 3 different accumulation functions \ref{accumulation_endpoints}, \ref{accumulation_targets}, \ref{accumulation_heuristic}}
|
| 157 |
\label{fig:comparison_including_either_source_target}
|
| 158 |
\includegraphics[]{comparison_including_either_source_target.eps}
|
| 159 |
\end{figure}
|
| 160 |
|
| 161 |
\section{The BC inter}
|
| 162 |
Lemma 4.2 in \cite{PuzisZEDB12} shows that the BC for articulation points are the sum of BC in each bi-connected components, subtracted by the \texttt{BC inter}. However, when I subtract the \texttt{BC inter} from the \texttt{BC sum}, the results are not meaningful as shown in figure \ref{fig:substracted_by_bc_inter} and \ref{fig:not_substracted_by_bc_inter}
|
| 163 |
|
| 164 |
\begin{figure}[h]
|
| 165 |
\caption{Heuristic BC is NOT subtracted by BC inter}
|
| 166 |
\label{fig:not_substracted_by_bc_inter}
|
| 167 |
\includegraphics[]{feb10_bc_inter.eps}
|
| 168 |
\end{figure}
|
| 169 |
|
| 170 |
\begin{figure}[h]
|
| 171 |
\caption{Heuristic BC is subtracted by BC inter}
|
| 172 |
\label{fig:substracted_by_bc_inter}
|
| 173 |
\includegraphics[]{feb10_subtracted_by_bc_inter.eps}
|
| 174 |
\end{figure}
|
| 175 |
|
| 176 |
\clearpage |
| 177 |
|
| 178 |
\bibliography{references}{}
|
| 179 |
\bibliographystyle{plain}
|
| 180 |
|
| 181 |
\end{document}
|