| 摘要: | 許多應用的問題都可以透過圖形理論解決它，例如：社會學的人際關係網路分析、生物學的蛋白質複合體偵測等。我們把原本問題中，運作之物件視為圖形上的一個點，若任意兩個物件有關係存在時，則在圖形上用一條邊將他們連起來。在建構完圖形並把原本問題以圖論的方式表示，則原本問題就可從圖論角度來思考，並可藉由圖論的技巧解決它。在許多真實世界的網路中，普遍存在社群結構。一般而言，社群結構指的是，在相同社群的節點其互動關係要比不同社群的節點來得較為頻繁。偵測社群結構是一個十分重要的題目，因為它的應用十分地廣泛。例如：偵測社群結構可以幫助我們從社會人際關係網路中探索出社會群體、在引用論文文獻所構成的網路中挖掘出相同主題的論文、從蛋白質交互作用網中預測出蛋白質複合體。由於這是一個十分重要的研究題目，因此已經有許多偵測社群結構的演算法。我們認為，目前各種的方法，都是觀察出社群結構在某單一面向的特性，再利用該特性所發展出來。在本研究中，首先將運用各種偵測方法產生各種可能的社群結構，並研究其共識部份，再透過共識部份研究之成果，以設計出能夠提供更好分群結果的方法，以協助生物學家探索蛋白質的功能，或提供給社會學家作為研究人際關係網路分析的工具。 Many problems can be represented as graph theory problems, for example, human relationship network analysis in social studies and detecting protein complexes in Protein-Protein Interaction networks in biological studies. Taking an object as a vertex and connecting any two objects that have direct interaction by an edge, we build networks from original problems. After we create the networks and transform the problems into graph theoretical problems, then the problems can be solved by some graph theoretical techniques. Communities, in which vertices are joined together tightly, between which there are only looser edges, exist in many real networks. Detecting communities in a network is a very important research topic, because it has many practical applications. For example, detecting communities can help us identifies real social groupings in social networks, related papers on a single topic in citation networks, protein complexes in Protein-Protein Interaction networks, and web pages on a related topic on the World Wide Web. Because detecting communities in a network is an important research topic, many algorithms have been designed to solve this problem. We believe that the design philosophies of different detection methods are based on different properties of communities; in other words, by observing variety of properties of communities, researchers develop their detection algorithms. In this project, we propose to study the consensus of different clustering results, and using the consensus structure, we intend to design a better community detection method. 研究期間：9908 ~ 10007 |
