TY - GEN
T1 - A new graph-partitioning algorithm for large-scale knowledge graph
AU - Zhong, Jiang
AU - Wang, Chen
AU - Li, Qi
AU - Li, Qing
N1 - Publisher Copyright:
© 2018, Springer Nature Switzerland AG.
PY - 2018
Y1 - 2018
N2 - Large-scale knowledge graph is finding widely practical applications in many fields such as information retrieval, question answering, health care, and knowledge management and so on. To carry out computations on such large-scale knowledge graphs with millions of entities and facts, partitioning of the graphs is necessary. However, the existing partitioning algorithms are difficult to meet the requirements on both partition efficiency and partition quality at the same time. In this paper, we utilize the community-based characteristic that real-world graphs are mostly power-law distribution, and propose a new graph-partitioning algorithm (called MCS) based on message cluster and streaming partitioning. Compared with the traditional algorithms, MCS is closer to or even surpasses Metis package in the partition quality. In the partition efficiency, we use the PageRank algorithm in the spark cluster system to compute the Twitter graph data, and the total time of MCS is lower than that of Hash partitioning. With an increasing number of iterations, the effect is more obvious, which proves the effectiveness of MCS.
AB - Large-scale knowledge graph is finding widely practical applications in many fields such as information retrieval, question answering, health care, and knowledge management and so on. To carry out computations on such large-scale knowledge graphs with millions of entities and facts, partitioning of the graphs is necessary. However, the existing partitioning algorithms are difficult to meet the requirements on both partition efficiency and partition quality at the same time. In this paper, we utilize the community-based characteristic that real-world graphs are mostly power-law distribution, and propose a new graph-partitioning algorithm (called MCS) based on message cluster and streaming partitioning. Compared with the traditional algorithms, MCS is closer to or even surpasses Metis package in the partition quality. In the partition efficiency, we use the PageRank algorithm in the spark cluster system to compute the Twitter graph data, and the total time of MCS is lower than that of Hash partitioning. With an increasing number of iterations, the effect is more obvious, which proves the effectiveness of MCS.
KW - Community detection
KW - Graph partitioning
KW - Large-scale knowledge graph
KW - Parallel computing
KW - Streaming partitioning
UR - https://www.scopus.com/pages/publications/85059779437
U2 - 10.1007/978-3-030-05090-0_37
DO - 10.1007/978-3-030-05090-0_37
M3 - 会议稿件
AN - SCOPUS:85059779437
SN - 9783030050894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 434
EP - 444
BT - Advanced Data Mining and Applications - 14th International Conference, ADMA 2018, Proceedings
A2 - Gan, Guojun
A2 - Li, Xue
A2 - Wang, Shuliang
A2 - Li, Bohan
PB - Springer Verlag
T2 - 14th International Conference on Advanced Data Mining and Applications, ADMA 2018
Y2 - 16 November 2018 through 18 November 2018
ER -