| Branch: | Revision:

root / thesis / ch6_conclusion.tex @ c6e2ce5a

History | View | Annotate | Download (3.48 KB)

%!TEX root = main.tex

\chapter{Conclusion} \label{sec:conclusion}

In this work, we presented the performance evaluation for two algorithms to calculate betweenness centrality on Ubiquiti router. One state of the art algorithm was found out by Brandes in \cite{Brandes01afaster} (called BBC). Another algorithm is the heuristic version aimed to improve the Brandes's algorithm (denoted HBC). On the router, we tested with three real topology of Wireless Community Networks (WCNs), and it was shown that those topology, HBC were able to calculate faster than BBC from 3 to 7 times in \cref{fig:CN_real_speedup_ratio_BC_HBC}.

We also evaluate the performance for synthetic Community Networks graphs as well. Those graphs were generated algorithmically using \emph{NePa TesT} \cite{Baldesi2016}. The result for the synthetic CN networks is promising. When running on routers for synthetic CN graphs with 1000 nodes, HBC achieves a speed up ratio of 60 times over BBC. On average, when running on the Ubiquiti router, a CN network with 1000 nodes take almost 7 minutes with BBC, and less than 7 seconds with HBC. This is the huge improvement given the limited capacity of the router. Testing with synthetic CN graphs, the result also showed that HBC improved the performance over BBC.

Besides CN graphs (both the real topology and the randomly generated ones), we also performed the analysis with synthetic Erdos and Power Law graph. HBC takes longer time than BBC to finish the calculation. For example, for Erdos graph with 1000 nodes, BBC takes 24 seconds, and HBC takes 26.4 seconds. HBC even though does not guarantee that the performance would be improved over the BCC, its complexity in worst case is also the same as BBC ($\mathcal{O}(mn)$ for an unweighted graph, and $\mathcal{O}(mn + n^2 \log n)$ for a weighted graph).

We also carried out an analysis for CN, Erdos and Power Law graphs to see the reason why HBC works for CN graphs, but not for the others. We concluded that the size of the bi-connected components (BCCs) is the main factor affecting the performance of HBC. For Funk Feuer Wien -- a WCN in Vienna, the experiment shows that even though the biggest bi-connected components found contains almost half of nodes in the networks (46\% of total nodes), HBC can still run 3 times faster than BBC.

So far, we have shown that HBC is an algorithm to choose when we need to calculate betweenness centrality of the Wireless Community Networks real topologies. There are ways that we think can improve the performance further, which may be implemented in the future. One property of WCN is that the topology evolves over time since any nodes can leave and join the network. However, in general, the new incoming or recently-left nodes are those in peripheral of the network \cite{Maccari2015175}. We can thus keep track of the betweenness centrality in each bi-connected component, and we would only calculate the betweenness centrality again when there are modification in that BCC.

For this thesis, both algorithms were run on the set of predefined graph. In the future, we can extend the functionality of the program, so that it can extract the real-time topology of the WCN of interest, and perform all the necessary calculation. Also for the router in the testing environment, its sole task was to run the experiment. The router was not busy with forwarding packets or finding routes for packets as it has to do in the reality. It will be interesting to see how the HBC work with the constantly evolving topology, and with the busy router.