Revision c6e2ce5a thesis/ideas.tex

View differences:

thesis/ideas.tex
187 187

  
188 188
        feel of
189 189

  
190
\section{Experiment setup}
191
 Cores is a hardware term that describes the number of independent central processing units in a single computing component (die or chip).
192

  
193
       A Thread, or thread of execution, is a software term for the basic ordered sequence of instructions that can be passed through or processed by a single CPU core.
194

  
195
       Intel® Hyper-Threading Technology (Intel® HT Technology) delivers two processing threads per physical core. Highly threaded applications can get more work done in parallel, completing tasks sooner.
190 196

  
191 197

  
192 198
\section{Questions}
......
230 236
    Then, 1 chapter about the result
231 237

  
232 238
    Bibliography: 20 - 3.0
239

  
240

  
241
\section{Scope}
242
        The scope of the paper:
243
        \begin{itemize}
244
            \item no self-loop
245
            \item no multigraph: graph with no parallel edges
246
            \item unweighted and weighted graph
247
            \item can apply to connected or disconnected graph. In the disconnected graph, certain vertices are not reachable from vertices in a different component. This yeilds the zero shortest paths counts, and as a result those 2 endpoints contributes 0 toward the betweenness.
248
        \end{itemize}
249

  
250
    connected graph: since the betweenness centrality is calculated based on shortest paths. In the disconnected graph, certain vertices are not reachable from vertices in a different component. This yields the zero shortest paths counts for betweenness centrality.
251

  
252

  
253
\section{Notation}
254
    A graph $G=(V,E)$ contains a set of vertices (nodes) $V$ and a set of edges (links) $E$. We assume we assume that al graphs are undirected and connected. \textbf{XXX check the modification for directed graph}
255

  
256
    $m = |E|$ is the number of edges in graph $G$
257

  
258
    $n = |V|$ is the number of vertices in graph $G$
259

  
260
    Let $\omega$ be a weight function on the edges. We assume that $\omega(e) > 0, e \in E$ for weighted graphs. And we define $\omega(e) = 1, e \in E$ for unweighted graphs. If for $s, t \in V$ and ${s, t} \in E$, then we can also use $\omega(s, t)$ to denote the weight of the edge between $s$ and $t$.
261

  
262
    The \emph{length} of a path is the sum of weights of all edges along the path. We use $d(s, t)$ to denote the \emph{distance} between vertices $s$ and $t$, i.e. the minimum length of any path connecting $s$ and $t$.
263

  
264
\section{Result}
265

  
266
        \begin{figure}[h]
267
        \caption{}
268
        \label{fig:histogram_num_of_nodes_CN200}
269
        \centering
270
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_CN200.png}
271
        \end{figure}
272

  
273
        \begin{figure}[h]
274
        \caption{}
275
        \label{fig:histogram_num_of_nodes_ER200}
276
        \centering
277
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_ER200.png}
278
        \end{figure}
279

  
280
        \begin{figure}[h]
281
        \caption{}
282
        \label{fig:histogram_num_of_nodes_PL200}
283
        \centering
284
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_PL200.png}
285
        \end{figure}
286

  
287

  
288
\section{Counting shortest paths}
289
    In the end, I choose not to describe those algorithms in the final version of my thesis
290

  
291
    \textbf{XXX What is the input}: the source vertex $s$
292
        \textbf{XXX What is the output?}:
293

  
294
        \subsection{Breadth-First Search for unweighted graph}
295
            I understood the algorithm, but how can I explain it to another person?
296

  
297

  
298

  
299
        \subsection{Dijkstra's algorithm for weighted graph}
300
            The Dijkstra's algorithm can be modified so that when given a source vertex $s$, the output will be the set of predecessors and the number of shortest paths from $s$ to other $t \neq s \in V$
301

  
302
            \begin{algorithm}
303
            \caption{Dijkstra's algorithm} \label{algo:dijkstra}
304
            \begin{algorithmic}[1]
305
                \Procedure{Dijkstra for SSSP with source vertex s}{}
306
                    \State $S \leftarrow$ empty stack
307
                    \State $P[w] \leftarrow$ empty list, $w \in V$
308
                    \State $\sigma[t] \leftarrow 0, t \in V$; $\sigma[s] \leftarrow 1$
309
                    \State $d[t] \leftarrow -1, t \in V$; $d[s] \leftarrow 0$
310
                    \State $Q \leftarrow $ empty queue
311
                    \State enqueue $s \rightarrow Q$
312
                    \While{$Q$ \emph{not empty}}
313
                        dequeue $v \leftarrow Q$
314
                        push $v \rightarrow S$
315

  
316
                    \EndWhile
317
                \EndProcedure
318
            \end{algorithmic}
319
            \end{algorithm}
320

  
233 321
\clearpage
234 322
\bibliography{references}{}
235 323
\bibliographystyle{plain}

Also available in: Unified diff