最大完全子圖問題於 GPU 運算架構之研究｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	吳孟傑 Meng-Chieh Wu
論文名稱：	最大完全子圖問題於 GPU 運算架構之研究 A Study of the Maximum Clique Problem on GPU Computing
指導教授：	陳維美 Wei-Mei Chen
口試委員:	林昌鴻 Chang-Hong Lin 林淵翔 Yuan-Hsiang Lin
學位類別：	碩士 Master
系所名稱：	電資學院 - 電子工程系 Department of Electronic and Computer Engineering
論文出版年：	2019
畢業學年度：	107
語文別：	中文
論文頁數：	58
中文關鍵詞：	極大子圖列舉、最大子圖、平行演算法、GPGPU
外文關鍵詞：	maximal clique enumeration, maximum clique, parallel algorithm, GPGPU
相關次數：	點閱：283 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

Maximum Clique Problem(MCP) 為一個解決最大子圖的方法，能夠在圖形中找出最大完全子圖以及這個最大完全子圖包含的點數總量，在圖論中為 NP hard 問題，其應用在於分析社交圖形分析、金融經濟、蛋白質組成、電子郵件網路等。而最常被用來解決的方法為 branch and bound，利用所找出的 clique 作為門檻，去判斷現有的條件加上有可能被加入的條件是否需要進行搜尋。而在 maximum clique 的問題上，使用 GPU 來解決的方法並不多。本論文利用原本解決列舉極大子圖的 Bron-Kerbosch 演算法，加入 branch and bound 的條件，找出 potential maximum clique 忽略不必要的計算來節省運算時間，並實作於 GPU 上，在平行化的過程中，配合 GPU 的架構設計演算法，也在實驗中探討 ordering 對於 maximal clique 及 maximum clique 的影響，並分析了在什麼狀況下使用哪種演算法會有比較好的效果。

Maximum Clique Problem (MCP) is a method for solving the maximum clique which can be used to find the maximum complete subgraph in a graph and the total number of points contained in this maximum clique. In Graph Theory it is a NP hard problem with the applications of analyzing social pattern analysis, finance and economy, protein composition, and email network. The most frequently used method for solving this problem is branch and bound, where the identified clique serves as the threshold to determine whether or not a search is needed based on existing conditions and the conditions which could be added. For maximum clique problems, there are not many methods which can solve them with GPU. In this dissertation the Bron-Kerbosch algorithm, which was original for solving enumeration of maximum subgraph, is used in conjunction with the conditions of branch and bound to find potential maximum clique while neglecting unnecessary calculations to save computing time, and it is implemented on GPU. The process of parallelization is done in coordination with the architecture design algorithm of GPU, the impact of the sequence of number of points on maximal clique and maximum clique are investigated in the experiment, and the algorithm with better performance under each condition is analyzed.

論文摘要...................................... III
Abstract...................................... IV
目錄............................................. V
圖目錄 ......................................... VIII
表目錄......................................... X
1緒論......................................... 1
1 研究動機................................... 1
2 研究背景................................... 2
3 論文架構................................... 3
GPU架構與介紹.................................. 4
1 NVIDIAGPU歷史.............................. 4
2 NVIDIA運算架構CUDA.......................... 4
2.1 CUDA中軟體對應硬體....................... 6
2.2 全域記憶體 ............................. 7
2.3 共享記憶體 ............................. 8
3文獻探討. ..................................... 10
1 Clique介紹.................................. 10
2 Bron-Kerbosch algothrim........................... 11
3 Bron-Kerbosch algothrim with a pivot .................... 12
4 Bron-Kerbosch algorithm with degeneracy. . . . . . . . . . . . . . . . . . 15
5 Parallel variant of Bron-Kerbosch algorithm . . . . . . . . . . . . . . . . . 16
6 GPU版本的Bron-Kerbosch algorithm ................... 17
7 GBK ..................................... 17
7.1 資料結構............................... 18
7.2 GBK之集合計算 .......................... 20
7.3 Maximal clique examination..................... 21
7.4 Pivot selection ............................ 21
7.5 Clique expansion........................... 23
研究方法 ...................................... 25
1 Size of maximal clique的下界........................ 25
2 Size of maximal clique的上界........................ 26
3 Ordering對於搜尋maximum clique的影響 ................ 26
4 計算the size of maximal clique ....................... 27
5 加入條件篩選後的演算法.......................... 28
5實驗結果與分析.................................. 31
1 實驗環境................................... 31
2 社交圖形threshold設定........................... 32
3 實驗資料................................... 32
4 實驗結果分析 ................................ 32
4.1 Degeneracy order在 maximal clique 與 maximum clique 的作用差異 38
4.2 Ordering對執行時間的影響 .................... 38
4.3 GPU的架構限制 .......................... 39
4.4 演算法條件比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
                                

[1] E. A. Akkoyunlu, The enumeration of maximal cliques of large graphs, SIAM Journal on Computing, 2:1 (1973), 1–6.
[2] L.Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem, Zeitschriftfür Operations Research, 34:3 (1990), 207–217.
[3] B. Balasundaram, S. Butenko, and I. V. Hicks, Clique relaxations in social network analysis: The maximum k-plex problem, Operations Research, 59:1 (2011), 133–142.
[4] N. Bell and J. Hoberock, Thrust:a productivity-oriented library for cuda, GPU computing gems Jade edition, 359–371 , 2011
[5] V. Boginski, S. Butenk, and P. M. Pardalos, Mining market data: A network approach, Computers & Operations Research, 33:11 (2006), 3171–3184.
[6] C. Bron and J. Kerbosch, Algorithm 457:finding all cliques of an undirected graph, Communications of the ACM, 16:9 (1973), 575–577.
[7] R. Carraghan and P. M. Pardalos, An exact algorithm for the maximum clique problem,” Operations Research Letters, 9:6 (1990), 375–382.
[8] F. Cazals and C. Karande, A note on the problem of reporting maximal cliques, The oretical Computer Science, 564–568 , 2008
[9] N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, 14:1 (1985), 210–223.
[10] P. Daniluk, G. Firlik, and B. Lesyng, Implementation of a maximum clique search pro- cedure on CUDA, Journal of Heuristics, 25:2 (2019), 247–271.
[11] E. P. Duarte, T. Garrett, L. C. Bona, R. Carmo, and A. P. Züge, Finding stable cliques of PlanetLab nodes, 317–322, 2010.
[12] D. Eppstein, M. Löffler, and D. Strash, Listing all maximal cliques insparse graphs in near-optimal time, International Symposium on Algorithms and Computation. Springer, 403–414, 2010
[13] T. Fahle, Simple and fast: Improving a branch-and-bound algorithm for maximum clique, In European Symposium on Algorithms, 485–498, September 2002
[14] B. Hou, Z. Wang, Q. Chen, B. Suo, C. Fang, Z. Li, and Z. G. Ives, Efficient maximal clique enumeration over graph data, Data Science and Engineering 1:4 (2016), 219– 230.
[15] J. Jenkins, I. Arkatkar, J. D. Owens, A. Choudhary, and N. F. Samatova, Lessons learned from exploring the backtracking paradigm on the GPU, In European Conference on Parallel Processing, Springer, 425-437, 2011.
[16] C. John, M. Grossman, and T. McKercher, Professional Cuda C Programming, 2014
[17] The koblenz network collection–KONECT, http://konect.uni-koblenz.de/networks, 2016
[18] J. Konc and J. Dušanka, An improved branch and bound algorithm for the maximum clique problem , Communications in Mathematical and in Computer Chemistry, 58 (2007), 569–590.
[19] J. Leskovec and A. Krevl, SNAP Datasets: Stanford large network dataset collection, http://snap.stanford.edu/data, 2014
[20] D. R. Lick and A. T. White, k-Degenerate graphs, Canadian Journal of Mathematics, 22:5 (1970), 1082–1096.
[21] N. Malod-Dognin, R. Andonov, and N. Yanev, Maximum cliques in protein structure comparison, Lecture Notes in Computer Science, 106–117, 2010
[22] K. Makino and T. Uno, New algorithms for enumerating all maximal cliques, in Scandinavian Workshop on Algorithm Theory. Springer, 260–272, 2004
[23] C. McCreesh and P. Prosser, Multi-threading a state-of-the-art maximum clique algorithm, Algorithms, 6:4 (2013), 618–635.
[24] J. W. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, 3:1 (1965), 23–28.
[25] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian Journal of Mathematics, 3:1 (1965), 533–540.
[26] A. P. Mukherjee, P. Xu, and S. Tirthapura, Enumeration of maximal cliques from an uncertain graph, IEEE Transactions on Knowledge and Data Engineering, 29:3 (2017), 543–555.
[27] P. R. Östergård, A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 192–207, 2002
[28] J. Pattillo, N. Youssef, and S. Butenko, Clique relaxation models in social network analysis. In M. T. Thai, P. M. Pardalos (Eds.), Handbook of optimization in complex networks:Theory and applications. Springer optimization and its applications, 143– 162, 2012
[29] Y. W. Peng, T. H. Wu, and W. M. Chen, Accelerating the Bron-Kerbosch algorithm for maximal clique enumeration using GPU, submitted.
[30] W. Pullan, F. Mascia, and M. Brunato, Cooperating local search for the maximum clique problem, Journal of Heuristics, 17:2 (2011), 181–199.
[31] M. G. Ravetti and P. Moscato, Identification of a 5-protein biomarker molecular signa- ture for predicting Alzheimer’s disease, PLoS One, 3:9 (2008), 3111–3122.
[32] R. A. Rossi, D. F. Gleich, and A. H. Gebremedhin, Parallel maximum clique algorithms with applications to network analysis, SIAM Journal on Scientific Computing, 37:5 (2015), 589–616.
[33] M. C. Schmidt, N. F. Samatova, K. Thomas, and B. H. Park, Ascalable parallel algorithm for maximal clique enumeration , Journal of Parallel and Distributed Compuing, 69:4 (2009), 417–428.
[34] P. Segundo San, J. Artieda, M. Batsyn, and P. M. Pardalos, An enhanced bitstring encoding for exact maximum clique search in sparse graphs, Optimization Methods and Software, 32:2 (2017), 312–335.
[35] P. Segundo San, A. Lopez, J. Artieda, and P. M. Pardalos, A parallel maximum clique algorithm for large and massive sparse graphs , Optimization Letters, 11:2 (2017), 343– 358.
[36] P. SegundoSan, A. Lopez, M. Batsyn, A. Nikolaev, and P. M. Pardalos, Improved initial vertex ordering for exact maximum clique search , Applied Intelligence, 45:3 (2016), 868–880.
[37] E. Tomita and T.Seki, An efficient branch-and-bound algorithm for finding a maximum clique, International Conference on Discrete Mathematics and Theoretical Computer Science, 278–289, 2003
[38] E. Tomita and T. Seki, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, Journal of Global optimization, 37:1 (2007), 95–111.
[39] E. Tomita, T. Seki, H. Takanori, S. Takahashi, and M. Wakatsuki, A simple and faster branch-and-bound algorithm for finding a maximum clique, In International Workshop on Algorithms and Computation, 191–203, 2010
[40] E. Tomita, A. Tanaka, and H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, 28– 42, 2006
[41] E. Tomita, K. Yoshida, T. Hatta, A.Nagao, H. Ito, and M. Wakatsuki, A much faster branch-and-bound algorithm for finding a maximum clique, In International Workshop on Frontiers in Algorithmics, 215–226, 2016
[42] Q. Wu and J.K. Hao, A review on algorithms for maximum clique problems, European Journal of Operational Research, 242:3 (2015), 693–709.
[43] M. Xiao and H. Nagamochi, Exact algorithms for maximum in dependent set, Information and Computation, 126–146, 2017
[44] A. P. Züge and R. Carmo, On comparing algorithms for the maximum clique problem, Discrete Applied Mathematics, 1–13, 2018

全文公開日期 2024/08/21 (校內網路)
全文公開日期本全文未授權公開 (校外網路)
全文公開日期本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)

簡易檢索 / 詳目顯示

相關論文