Revision c6e2ce5a thesis/ideas.tex
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® HyperThreading 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 selfloop 

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{BreadthFirst 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