中介向心性是網路分析中，用來量化網路中各個部份的重要性，以協助研究者有系統的找出想要研究的部分的一個重要方法。中介向心性的使用相當的廣泛，但其特性使計算時間一直居高不下。目前已知最快的演算法，在有權重圖上需要Ο(|V|2logV+VE)的時間，在無權重圖上需要Ο(VE)的時間。但在某些應用，如Girvan和Newman的演算法上，仍然花去太多時間。 Girvan和Newman認為，中介向心性越高的邊，越有可能是連接二個社群的邊。他們因此設計出一個演算法，不斷重複進行「計算所有邊的中介向心性→移除擁有最高中介向心性的邊」的動作，來建立一個表達網路中各個社群間的階層式關係之系統樹狀圖。 在本篇論文中，我們以隨機抽樣的啟發式邊中介向心性計算，來加快找到網路上擁有最大中介向心性的邊的速度，這同時也可用來加快Girvan和Newman之演算法。另外，我們也設計了一個適用於遞減網路上的改良中介向心性計算，來加速Girvan和Newman之演算法。我們在11個隨機產生的網路和5個非隨機產生的網路上測詴此改良演算法。在隨機網路上，執行速度最高加快為約原本的34倍；在非隨機網路上，執行速度最高加快為約原本的15倍。 In network analysis, betweenness centrality is essential for researchers to measure the importance of each parts of the network and find out the part to be study further. Betweenness centrality has a widespread use, but it is costly to compute. Currently, the fastest known algorithm requires Ο(|V|2logV+VE) time on weighted graph and Ο(VE) time on unweighted graph. But in some applications, such as the algorithm of Girvan and Newman, still cost too much time for computing. Girvan and Newman thought that the edge which has the higher betweenness centrality has more probability to be the edge which connects two communities. According to this, they designed an algorithm which does the operation “compute the betweenness centrality of all edges → remove the edge which has the highest betweenness centrality” repeatedly and then constructs a dendrogram which represents the hierarchical relationships between the vertices of the network. In this thesis, we use a random sampling heuristic betweenness centrality computation to accelerate the speed of finding the edge which has the maximum betweenness centrality. This can also be used to speed up the algorithm of Girvan and Newman. Besides, we also design an improved exact betweenness centrality compute which is suitable for decremental networks to accelerate the algorithm of Girvan and Newman. We test the improved algorithm on 11 random generated networks and 5 non-random generated networks. On random generated networks, we gained a maximum speedup about 34 times. On non-random generated networks, we gained a maximum speedup about 15 times.
