IMPLEMENTATION OF STRUCTURAL HOLE SEARCHING ON GRAPHS USING GPU (GRAPHICS PROCESSING UNIT)

• Main Author: Setya, Antonio
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/51213
• Institution: Institut Teknologi Bandung

Structural holes are groups of nodes in a graph that have an important role of connecting other nodes. If this group is removed from the graph, the graph may become disconnected. To find structural holes in big graphs, an efficient way is needed to process the graph in order to keep the running time low and not to consume too much memory. One way to search forstructural holesis to utilize the Fiedler vector of the Laplacian matrix of the graph. Fiedler vector is the eigenvector of the second smallest eigenvalues of the matrix. This technique, however, uses too much memory and has a bad time complexity. Other way of finding structural holes is to use betweenness centrality. Compared to using Fiedler vector, it has better time complexity and able to work with sparse data formats, which enables it to lower memory usage, and there is already a technique of calculating betweenness centrality on the GPU. We choose betweenness centrality as the main technique to find structural holes, leveraging the power of GPU. Compressed sparse row matrix is used to store the graph. From our testing, we find that using betweenness centrality with GPU yields faster running time and lower memory usage compared when using Fiedler vector on bigger graphs. We find that the running time is faster when the graph has 250 nodes or more, and the memory usage is lower when the graph has 500 nodes or more. Keyword