Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/111933
題名: | Finding maximal quasi-cliques containing a target vertex in a graph | 作者: | 陳良弼 Chou, Yuan Heng Wang, En Tzu Chen, Arbee L. P. |
貢獻者: | 資訊管理系 | 關鍵詞: | Graphic methods; Information management; Biological networks; Complete graphs; Dense sub-graphs; Maximal clique; Maximal quasi-cliques; Pruning techniques; Quasi-cliques; Synthetic datasets; Graph theory | 日期: | 七月-2015 | 上傳時間: | 14-八月-2017 | 摘要: | Many real-world phenomena such as social networks and biological networks can be modeled as graphs. Discovering dense sub-graphs from these graphs may be able to find interesting facts about the phenomena. Quasi-cliques are a type of dense graphs, which is close to the complete graphs. In this paper, we want to find all maximal quasi-cliques containing a target vertex in the graph for some applications. A quasi-clique is defined as a maximal quasi-clique if it is not contained by any other quasi-cliques. 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 maximal cliques. The experiment results reveal that our method outperforms the previous work both in real and synthetic datasets in most cases. | 關聯: | DATA 2015 - 4th International Conference on Data Management Technologies and Applications, Proceedings, (), 5-15 4th International Conference on Data Management Technologies and Applications, DATA 2015; Colmar, Alsace; France; 20 July 2015 到 22 July 2015; 代碼 113501 |
資料類型: | conference |
Appears in Collections: | 會議論文 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
index.html | 121 B | HTML2 | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.