摘要
使用傳統方法計算一個圖的直徑(diameter，即圖中所有兩點間的最大距離)需要O(mn)的時間，其中n為圖中的點個數，m為邊的個數。然而隨著網路發展迅速，社會網路有著數億的節點是十分常見的，此時O(mn)就顯得非常耗時。因此這篇論文中，我們將介紹一個改良演算法，用在無向無權重的大圖中測定diameter並降低計算成本。Worst case還是維持O(mn)，然而在實作上，特別是在大多數social network的圖上，只需要O(m)的執行時間即可。在測定diameter中最重要的一環就是如何挑點作為BFS的起點，在本論文中我們將介紹一個快速且不錯的挑法。
並列摘要
The diameter of a graph is the maximum distance among all the pairs of nodes. Determining the diameter of a graph in the tradition way costs O(mn) time, where n is the number of nodes and m is the number of edges. A social network can be modelled as a graph. With the rapid expansion of social networks, it is not unusual that the number of nodes of a social network may be 100 million or more. Therefore, in this thesis we propose a new approach to the problem of computing the diameter of large undirected unweighted graphs. The worst case time complexity is still O(mn). In practice, especially for social network graphs, the running time is O(m). How to select a proper node as the starting node of a BFS process is the most important issue when computing the diameter. We show how to choose the good nodes with small cost.