Abstract
Cloud computing is widely utilized in today’s internet service, which severely requires the ability of processing graphs of billion vertices rapidly in the situation such as social network analyze, bio-informational network analyze and semantic processing. Therefore, graph processing has a significant role in the research and development of high-performance computing. However, many problems such as music and movie recommendation web, LDA topic model can be solved by modeling these data into bipartite graph and computing it with graph processing engines. As the most important step in preprocessing, graph partitioning is a relatively mature technology. However, most of classic graph partitioning algorithms require iterative calculation for several times, which causes huge time complexity especially adapting to big data. There are some rapid algorithms these years, which cannot be used in bipartite graph directly. Therefore, this thesis proposed a new bipartite graph partitioning algorithm, BiFennel, which effectively decrease graph processing time and network loading by reducing vertex replication factor and maintaining work balance. Afterwards, this thesis applies BiFennel to a popular graph engine called PowerGraph and proves it gets up to 1.69 times overall runtime speedup of graph processing and 2.32 times network load reduction comparing to the best competitor, Aweto. Besides, the algorithm doesn’t meet a degradation when graph scale increases, so does its scalability.