Aeolus:Label Propagation-Based Community Discovery Algorithm Framework On GPU

Community structure has important research value in the fields of the Internet,social networks,and biological networks.The community detection algorithm,as a technique for extracting community structures from graphs,has become a research hotspot.As a heterogeneous hardware with a massive number of computing cores and ultra-high memory bandwidth,GPU can speed up the execution of algorithms.However,due to the increasing graph size and the irregular characteristics of graph data,writing correct and efficient GPU algorithms has great challenges.And the current community detection algorithm on the GPU cannot detect overlapping communities.Therefore,this paper proposes a community discovery algorithm framework based on tag propagation on the GPU to solve these problems.The research contents of this thesis are as follows:1)Summarize the traditional community discovery algorithms,focusing on the unsupervised,high-performance,and interpretable label propagation algorithms.At the same time,the current research status of community discovery algorithms on GPUs is reviewed.And analyze the characteristics of GPU in algorithm acceleration.2)Propose a community discovery system based on label propagation on GPU: Aeolus.Aeolus hides GPU programming details and provides four programming interfaces that can be flexibly configured.It also designs and implements support for large-scale graphs based on out-of-core memory and compressed graphs.Aeolus provides low-level support for users to build high-performance and configurable community discovery applications.3)Verify the application of Aeolus on specific algorithms by examples,and test the accuracy and performance of the framework by experiments.The experiments show that the community discovery algorithm developed by Aeolus can greatly improve the performance of the algorithm without losing accuracy.In some graphs,the performance even better than manually tuned label propagation algorithms on GPUs.