Statistics
| Branch: | Revision:

root / latex / report_feb_10.tex @ 4f432e4a

History | View | Annotate | Download (6.7 KB)

1 46d9d2ec Quynh PX Nguyen
\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}