| 摘要: | 許多應用的問題都可以用圖論的問題來表示，例如：在社會學上的人際關係網路分析、在生物學上的蛋白質複合體偵測等。我們可以把原本問題中的運作物件視為圖形上的一個點，任意兩個物件若有關係存在時，則在圖形上用一條邊將他們連起來。在建構圖形並把原本問題轉成圖論上的問題後，則原本問題就從圖論角度來思考，並用圖論的技巧加上解決。在許多的真實世界的網路中，普遍存在社群結構；所謂的社群結構指的是在相同社群的節點其互動關係要比不同社群的節點來得較為頻繁。偵測社群是一個十分重要的題目，因為它的應用十分地廣泛。例如：偵測社群可以幫助我們在社會人際關係網路找出社會群體、在引用論文文獻所構成的網路中找出相同主題的論文、在蛋白質交互作用網中找出蛋白質複合體、在網際網路上找出相同話題的網頁。由於這是一個十分重要的研究題目，因此我們想對這個主題進行相關的研究。在本計劃中，預計將進行的主要研究有三項。第一，由於目前偵測社群的方法有很多，但卻沒有一個令人滿意的評估其結果之方法，因此我們想提出一個較好的評估指標；第二，在我們目前看到的偵測社群方法中，發現 HRG (Hierarchical Random Graphs) 這種方法所使用概念很好，但其所需的計算時間太長且結果在較大的圖形中表現不是很理想，因此我們認為它有很大的改進空間；第三，我們認為各種方法都只不過是觀察出部份社群的特性，因此我們想綜合各種方法的結果，以提供一個更具代表性的結果。 ; Many problems can be represented as graph theory problems, such as human relationship network analysis in social studies, and detecting protein complexes in Protein-Protein Interaction network in biological studies, etc. We can construct a graph by adding vertices to represent objects in the original problem and linking any two vertices with an edge if there is a relationship between these two objects. After we create the graph and transfer the original problem to a graph theory problem, this problem can be solved by graph theoretical skills. Community, in which vertices are joined tightly together, between which there are only looser edges, exists in many real network networks. Detecting community in a network is a very important research topic, because it has many practical applications. For example, detecting communities can help us find out real social groupings in a social network, related papers on a single topic in a citation network, protein complexes in Protein-Protein Interaction network, and web pages on related topics in the internet. Because detecting community in a network is a very important research topic, we intend to perform a study on it. There are three main goals in this project. First, there are many community detecting methods up to now, but which one is better than others? Unfortunately, there is no satisfactory measure to judge them so far. Therefore, we plan to propose a new measure of the quality of a particular division of a network. Second, among all community detecting methods we reviewed, we think the modeling of HRG (Hierarchical Random Graphs) method contains some good ideas but the method itself costs lots of time to detect community and works not very well in a large network. Hence, we think there is an opportunity to improve it. Third, because we believe these community detecting methods only explore some partial properties of community, we intend to integrate some results of these methods and generate more overall results. ; 研究期間 9808 ~ 9907 |
