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