Shared-memory Graph Truss Decomposition

被引：27

作者：

Kabir, Humayun ^{[1
]}

Madduri, Kamesh ^{[1
]}

机构：

[1] Penn State Univ, Comp Sci & Engn, University Pk, PA 16802 USA

来源：

2017 IEEE 24TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING (HIPC) | 2017年

基金：

美国国家科学基金会;

关键词：

k-truss; k-core; multicore; graph analysis;

D O I：

10.1109/HiPC.2017.00012

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present PKT, a new shared-memory parallel algorithm and OpenMP implementation for the truss decomposition of large sparse graphs. A k-truss is a dense subgraph definition that can be considered a relaxation of a clique. Truss decomposition refers to a partitioning of all the edges in the graph based on their k-truss membership. The truss decomposition of a graph has many applications. We show that our new approach PKT consistently outperforms other truss decomposition approaches for a collection of large sparse graphs and on a 24-core shared-memory server. PKT is based on a recently proposed algorithm for k-core decomposition.

引用

页码：13 / 22

页数：10

共 46 条

[11] Functional Parallelism with Shared Memory and Distributed Memory Approaches
Kandegedara, Mahesh
Ranasinghe, D. N.
IEEE REGION 10 COLLOQUIUM AND THIRD INTERNATIONAL CONFERENCE ON INDUSTRIAL AND INFORMATION SYSTEMS, VOLS 1 AND 2, 2008, : 496 - 501
[12] OpenMP parallel implementation of stiffly stable time-stepping projection/GMRES(ILU(0)) implicit simulation of incompressible fluid flows on shared-memory, multicore architecture
Xu, Xiao
APPLIED MATHEMATICS AND COMPUTATION, 2019, 355 : 238 - 252
[13] Efficient Distributed Core Graph Decomposition
Zhang, Wenqian
Yang, Zhengyi
Wen, Dong
Wang, Xiaoyang
2023 23RD IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOPS, ICDMW 2023, 2023, : 1023 - 1031
[14] Core decomposition and maintenance in weighted graph
Zhou, Wei
Huang, Hong
Hua, Qiang-Sheng
Yu, Dongxiao
Jin, Hai
Fu, Xiaoming
WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS, 2021, 24 (02): : 541 - 561
[15] Core decomposition and maintenance in weighted graph
Wei Zhou
Hong Huang
Qiang-Sheng Hua
Dongxiao Yu
Hai Jin
Xiaoming Fu
World Wide Web, 2021, 24 : 541 - 561
[16] A NUMA-Aware Parallel Truss Decomposition Algorithm for Large Scale Graphs
Mou, Zhebin
Xiao, Nong
Chen, Zhiguang
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2021, PT II, 2022, 13156 : 193 - 212
[17] Teaching Shared Memory Parallel Concepts with OpenMP
Adams, Joel
Brown, Richard
Shoop, Elizabeth
PROCEEDINGS OF THE 45TH ACM TECHNICAL SYMPOSIUM ON COMPUTER SCIENCE EDUCATION (SIGCSE'14), 2014, : 743 - 743
[18] K-Truss Decomposition of Large Networks on a Single Consumer-Grade Machine
Wu, Jian
Goshulak, Alison
Srinivasan, Venkatesh
Thomo, Alex
2018 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM), 2018, : 873 - 880
[19] A Two-stage Algorithm Based on Prediction and Search for Maxk-Truss Decomposition
Tang, Jiahao
Liu, Lingbin
Jia, Jinfang
Wu, Li
Wang, Xiaoying
Huang, Jianqiang
2022 IEEE 28TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, ICPADS, 2022, : 491 - 498
[20] A Study on Influence of Design Pattern in Shared Memory Multiprocessor Application
Liu Wenjun
2010 THE 3RD INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND INDUSTRIAL APPLICATION (PACIIA2010), VOL I, 2010, : 439 - 441

← 1 2 3 4 5 →