南華大學機構典藏系統:Item 987654321/24750
English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 18278/19583 (93%)
造訪人次 : 1024961      線上人數 : 1012
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋


    請使用永久網址來引用或連結此文件: http://nhuir.nhu.edu.tw/handle/987654321/24750


    題名: 搜尋 K-Clique Community 之研究
    其他題名: A Study on Finding K-Clique Community
    作者: 金家豪
    貢獻者: 南華大學資訊工程學系
    關鍵詞: 網路分析;偵測社群結構
    network analysis;detecting community structure
    日期: 2015
    上傳時間: 2016-11-08 10:44:02 (UTC+8)
    摘要: 真實世界網路中普遍存在社群結構，而偵測網路中的社群可以幫助我們更了解真實世界的運作。例如：偵測社群可以幫助我們在人際關係網路中找出社會群體、在蛋白質交互作用網中找出蛋白質複合體。現今已有許多偵測社群的方法，其中 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.
    顯示於類別:[資訊工程學系] 國科會計畫

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    1042221E343004.pdf772KbAdobe PDF414檢視/開啟


    在NHUIR中所有的資料項目都受到原著作權保護.

    TAIR相關文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋