這篇論文將著重在討論基於最短路徑(Shortest Path) 的方式來計算的中心性(Centrality)，包含介數中心性(Betweenness Centrality，簡稱BC) 及緊密中心性(Closeness Centrality，簡稱CC)。這兩種中心性測量方式都是運用最短路徑的特性來計算及判斷所有點對整個圖(Graph) 的影響程度。在這篇論文當中，我們所提出的框架主要是以CPU/GPU 的結構，運用GPU(Graphics Processing Units) 多核及平行的架構幫助我們分散運算獨立的工作。一般在計算BC 和CC 的演算法會單純以不同的遍歷方式去做計算。我們除了在遍歷的方式上運用GPU 架構，也針對圖的結構去做調整。利用分支度(Degree) 為1 的點及關節點(Articulation Vertex) 作為切割圖點，讓原本的圖能夠分割成較小的子圖。這樣的子圖分別為獨立的子圖，因各子圖的獨立關係能夠很好運用平行計算的方式減少計算的時間，也可以減少各點遍歷的深度。

This thesis explores centrality measures based on shortest paths, specifically Betweenness Centrality (BC) and Closeness Centrality (CC). These metrics leverage shortest path information to evaluate the significance of each node within the graph. We propose a framework that utilizes a CPU/GPU architecture to achieve efficient computation. The GPU’s parallel computing capabilities enable effective task scheduling across all its cores.
Moreover, we introduce modifications to the graph structure by identifying degree-1 and
articulation vertices. This separation allows us to break the graph into smaller subgraphs with independent relationships. Leveraging GPU’s parallelism, we can perform computations in parallel, leading to reduced computation time and minimized vertex traversal depth compared to traditional BC and CC calculations.

[1] Alex Bavelas, “A Mathematical Model for Group Structures,” Human Organization, pp. 7:16–30,
1948.
[2] Linton Clarke Freeman, “Centrality in Social Networks: Conceptual Clarication,” Social Networks,
pp. 1:215–239, 1979.
[3] Paolo Boldi and Sebastiano Vigna, “Axioms for Centrality,” Social and Information Networks, Computer
Science, arXiv, 2013.
[4] L. Katz, “A New Status Index Derived from Sociometric Analysis,” Psychometrika, pp. 18(1):39–43,
1953.
[5] Jon M. Kleinberg, “Authoritative Sources in A Hyperlinked Environment,” Journal of the ACM,
pp. 46(5):604–632, 1999.
[6] Sergey Brin and Lawrence Page, “The Anatomy of A Large-scale Hypertextual Web Search Engine,”
Computer Networks and ISDN Systems, pp. 30(1):107–117, 1998.
[7] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, “The PageRank Citation Ranking:
Bringing Order to The Web,” Technical report, Stanford Digital Library Technologies Project,
Stanford University, Stanford, CA, USA, 1998.
[8] Jac M. Anthonisse, “The Rush in A Directed Graph,” Technical report, Amsterdam: University of
Amsterdam Mathematical Centre, 1971.
[9] Linton Clarke Freeman, “A Set of Measures of Centrality Based on Betweenness,” Sociometry,
pp. 40:35–41, 1977.
[10] Edsger W. Dijkstra, “A Note on Two Problems in Connecion with Graphs,” Numerische Math, vol. 1,
no. 1, pp. 269–271, 1959.
[11] Richard Bellman, ““On A Routing Problem,” Quarterly of Applied Mathematics, vol. 16, no. 1,
pp. 87–90, 1958.
[12] Lester R. Ford Jr., “Network Flow Theory,” Santa Monica, CA, USA: Rand Corporation, 1956.
[13] Edward F. Moore, “The Shortest Path Through A Maze,” Proceedings of an International Symposium
on the theory of switching, Part II, Apr.2-5, 1957. Cambridge, Massachusetts: Harvard Univ. Press.,
pp. 285–292, 1957.
[14] Julian Shun and Guy E. Blelloch, “Ligra: A Lightweight Graph Processing Framework for Shared
Memory,” Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel
Programming (PPoPP’13), pp. 135–146, 2013.
[15] Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad
Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, and John D. Owens, “Gunrock: GPU Graph
Analytics,” ACM Transactions on Parallel Computing, vol. 4, no. 1, pp. 3:1–3:49, 2017.
[16] Sungpack Hong, Sang Kyun Kim, Tayo Oguntebi, and Kunle Olukotun, “Accelerating CUDA Graph
Algorithms at Maximum Warp,” Proceedings of the 16th ACM symposium on Principles and practice
of parallel programming (New York, NY, USA, 2011), pp. 267–276, 2011.
[17] Duane Merrill, Michael Garland, and Andrew Grimshaw, “Scalable GPU Graph Traversal,” Proceedings
of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming,
pp. 117–128, 2012.
[18] Duane Merrill, Michael Garland, and Andrew Grimshaw, “High Performance and Scalable GPU
Graph Traversal,” ACM Transactions on Parallel Computing, Volume 1, pp. 1–30, 2015.
[19] Federico Busato and Nicola Bombieri, “BFS-4K: An Efficient Implementation of BFS for Kepler GPU
Architectures,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 7, pp. 1826–1838,
2015.
[20] Federico Busato and Nicola Bombieri, “An Efficient Implementation of The Bellman-ford Algorithm
for Kepler GPU Architectures,” IEEE Transaction on Parallel Distributed Systems, vol. 27, no. 8,
pp. 2222–2233, 2016.
[21] Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality,” Journal of Mathematical Sociology
25, 2, pp. 163–177, 2001.
[22] Sarıyüce Ahmet Erdem, Kaya Kamer, Saule Erik, and Ümit V. Çatalyürek, “Graph Manipulations for
Fast Centrality Computation,” ACM Transactions on Knowledge Discovery from Data 11, 3(2017),
pp. 1–25, 2017.
[23] Sarıyüce Ahmet Erdem, Kaya Kamer, Saule Erik, and Ümit V. Çatalyürek, “Shattering and Compressing
Networks for Betweenness Centrality,” Proceedings of the SIAM International Conference
on Data Mining, SDM, 2013.
[24] Alex Bavelas, “Communication Patterns in Task-oriented Groups,” Journal of the Acoustical Society
of America, 1950.
[25] John Hopcroft and Robert Tarjan, “Algorithm 447: Efficient Algorithms for Graph Manipulation,”
Communications of the ACM 16 (6), pp. 372–378, 1973.
[26] Jure Leskovec and Andrej Krevl, “SNAP Datasets: Stanford large network dataset collection,” June 2014.
[27] Ryan A. Rossi and Nesreen K. Ahmed, “The network data repository with interactive graph analytics
and visualization,” in AAAI, 2015.
[28] Adam McLaughlin and David A. Bader, “Accelerating GPU Betweenness Centrality,” Communications
of the ACM, Volume 61, pp. 85–92, 2018.
[29] Sarıyüce Ahmet Erdem, Kaya Kamer, Saule Erik, and Ümit V. Çatalyürek, “Betweenness Centrality on
GPUs and Heterogeneous Architechitures,” GPGPU-6: Proceeding of the 6th Workshop on General
Purpose Processor Using Graphics Processing Units, pp. 76–85, 2013.