English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54371/62179 (87%)
Visitors : 9052587      Online Users : 103
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    National Tsing Hua University Institutional Repository > 電機資訊學院 > 資訊工程學系 > 博碩士論文  >  在圖上尋找最大的並包含目標點的類完全子圖

    Please use this identifier to cite or link to this item: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86695

    Title: 在圖上尋找最大的並包含目標點的類完全子圖
    Authors: 周元亨
    Description: GH02101062655
    Date: 2014
    Keywords: 類完全圖
    Abstract: 在現實世界中,許多的網路應用都可以被模組化成圖形,像是社交網絡或是生物網路等。在這些圖形上尋找一些密集的子圖集團是一個有趣的研究。這些密集的子圖集團有一種我們稱為類完全圖,它是一種近似完全圖的圖形。在本篇論文中,我們想要針對圖形上特定的一個目標點v,找出所有包含v點的類完全圖,而且這些類完全圖必須要是最大的。最大的類完全圖代表不會有一個更大的類完全圖可以包含自己。我們準備了一個演算法來解決此問題並且提出了幾種改善的法方能夠增進此演算法的性能。此外我們針對這個問題中的特殊情況又提出了另一個演算法來解決它。我們在實驗部分做了兩組人造資料集以及一組實際資料集。實驗結果顯示我們的方法和過去的方法比較,在大部分的情況下都有較好的效率。
    In real world, many applications such as social networks and biological networks can be modeled as graphs. Discovering dense sub-graphs from these graphs is an interesting study. Quasi-cliques are a type of dense graphs, which are close to the complete graphs. In this thesis, we want to find all of the maximal quasi-cliques for a target vertex in a graph. The maximal quasi-clique represents that the vertices in a quasi-clique are not totally contained by another quasi-clique. We propose an algorithm to solve this problem and use several pruning techniques to improve the performance. Moreover, we propose another algorithm to solve a special case of this problem, .i.e. finding the cliques. The experiment results reveal that our method outperforms the previous work both in real and synthetic datasets in most cases.
    URI: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/86695
    Source: http://thesis.nthu.edu.tw/cgi-bin/gs/hugsweb.cgi?o=dnthucdr&i=sGH02101062655.id
    Appears in Collections:[資訊工程學系] 博碩士論文

    Files in This Item:

    File SizeFormat
    GH02101062655.pdf132KbAdobe PDF259View/Open


    SFX Query


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