Please use this identifier to cite or link to this item:
https://ah.nccu.edu.tw/handle/140.119/111933
|
| Title: | Finding maximal quasi-cliques containing a target vertex in a graph |
| Authors: | 陳良弼 Chou, Yuan Heng Wang, En Tzu Chen, Arbee L. P. |
| Contributors: | 資訊管理系 |
| Keywords: | Graphic methods;Information management;Biological networks;Complete graphs;Dense sub-graphs;Maximal clique;Maximal quasi-cliques;Pruning techniques;Quasi-cliques;Synthetic datasets;Graph theory |
| Date: | 2015-07 |
| Issue Date: | 2017-08-14 15:33:55 (UTC+8) |
| Abstract: | 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. |
| Relation: | 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 |
| Data Type: | conference |
| Appears in Collections: | [資訊管理學系] 會議論文 |
Files in This Item:
|
All items in 學術集成 are protected by copyright, with all rights reserved.
| 社群 sharing |