許多應用的問題都可以用圖論的問題來表示，例如：在社會學上的人際關係分析問題、在生物學上的必要性蛋白質預測、在社會學或生物學上的網路中偵測社群結構等等。我們可以把原本問題中的運作物件視為圖形上的一個點，任意兩個物件若有關係存在時，則在圖形上用一條邊將他們連起來。在建構完圖形並把原本問題轉成圖論上的問題後，則原本問題就從圖論角度來思考，並用圖論的技巧加上解決。在許多的應用問題上，研究人員常常想找出網路上比較重要的物件或關係。對於這個問題有很多種研究方法，其中一種方法是把這問題轉成圖論的問題後，在所有配對的最短路徑中，若有些點或邊被經過的比率比一般的點或邊來的高很多時，則視這些點所代表的物件或邊所代表的關係比較重要。這種計算點或邊在所有配對的最短路徑中被經過的比率的測量方式被稱之為計算點或邊的中介性，是一個網路分析的重要工具。由於中介性廣泛地被運用在各種領域的問題上，但它需要相當多的計算時間，因此我們想在實際運用層面上進行改進計算它所需的時間。對於這個研究題材，我們認為有兩個研究方向值得進行。第一個研究方向是，若已知圖形上所有點或邊的中介性，在圖形結構發生變動時，我們想設計一個利用這些的已知資訊以減少計算時間的演算法；第二個研究方向是，對於找出擁有最大中介性的點或邊的問題，設計出一個快速且準確性高的啟發式演算法。 ; Many problems can be represented as graph theoretical problems, such as human relationship analysis in social studies, essential protein prediction in biological studies, community structure detection in social and biological networks, etc. We can construct a graph by using vertices to represent objects in the original problem and linking any two vertices with an edge if there is a relationship between those two objects. After we create the graph, this problem can be viewed as a graph theoretical problem and solved by graph theoretical skills. In many applications, the researchers often want to find out which objects or relationships are more important than others in the network. There are many kinds of research methods for this problem. One of them is to model this problem as a graph problem which is to find out the vertices or edges with high fractions of shortest paths going through them. This measure is called betweenness centrality and it is very useful for network analysis. Betweenness centrality is widely used in many study areas, but it is time-consuming to determine the betweenness centrality. Therefore, we want to make it more efficient in the application problems. For this topic, we think there are two possible research directions. The one is that if we get all the betweenness centrality of vertices or edges, we want to design a algorithm which uses the information that we already know to reduce the calculating time when the graph structure changed; the other one is that to design an efficient and somewhat accurate heuristic algorithm for finding the vertex or edge with the maximum betweenness centrality. ; 研究期間 9708 ~ 9807
