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

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