搜尋 K-Clique Community 之研究

NHUIR > College of Science and Technology > Department of Computer Science and Information Engineering > NSTC Project > Item 987654321/24750

Please use this identifier to cite or link to this item: http://nhuir.nhu.edu.tw/handle/987654321/24750

Title:	搜尋 K-Clique Community 之研究
Other Titles:	A Study on Finding K-Clique Community
Authors:	金家豪
Contributors:	南華大學資訊工程學系
Keywords:	網路分析;偵測社群結構 network analysis;detecting community structure
Date:	2015
Issue Date:	2016-11-08 10:44:02 (UTC+8)
Abstract:	真實世界網路中普遍存在社群結構，而偵測網路中的社群可以幫助我們更了解真實世界的運作。例如：偵測社群可以幫助我們在人際關係網路中找出社會群體、在蛋白質交互作用網中找出蛋白質複合體。現今已有許多偵測社群的方法，其中 CPM (Clique Percolation Method) 是一種常被使用的偵測方法。CPM 找到的社群被稱之為 k-clique community，它是由一群 k-clique 所聯集，其中任何一個 k-clique 可經由一連串相鄰 k-clique 到達其他處在相同社群的 k-clique，而兩個 k-clique 相鄰代表這兩個大小為 k 的clique 共用 k-1 個節點。 CPM 所需的計算時間較長導致它無法處理大型網路，因此已有人提出如何減少計算尋找 k-clique community 所需時間。我們參考前人的作法設計出一個平行演算法以加速尋找 k-clique community，實驗顯示我們方法的整體效能比前人方法來得好但其缺點為對於記憶體的要求較高，因此我們希望在這個成果下繼續改進。此外，我們將嘗試把空間資訊加入 CPM的方法中，例如：在人際關係網路中考慮人們所在的地理位置或在蛋白質交互作用網路中加入蛋白質在細胞內之位置資訊，以提升偵測網路社群的準確性。 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 networks in biological studies. We can construct a network by adding nodes to represent objects in the original problem and linking any two nodes with an edge if there is a relationship between the two objects. After we create networks and transfer the original problems to graph theory problems, the problems can be viewed as graph theory problems and solved by graph theory's skills. Community, in which nodes are joined tightly together, 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 a Protein-Protein Interaction network and web pages on related topics in the internet. Therefore, detecting communities in real networks can help to understand how real world works. Because detecting community in a network is a very important research topic, there are many detecting community methods are developed. Among these methods, CPM (Clique Percolation Method) is a widely used method. CPM detects communities by finding k-clique community which is the union of all cliques of size k that can be reached through adjacent (sharing k-1 nodes) k-cliques. Finding k-clique communities is a time-consuming task. To solve this problem, we developed a parallel algorithm to reduce the running time of finding k-clique communities. Experimental results showed that our method outperforms previous ones, however, our method is high memory-demanded and we want to improve it in this project. Besides, we will try to use objects' localization information to help us detect community structure from networks.
Appears in Collections:	[Department of Computer Science and Information Engineering] NSTC Project

Files in This Item:

File	Description	Size	Format
1042221E343004.pdf		772Kb	Adobe PDF	414	View/Open

Loading...