Actions for Fast Parallel Triad Census and Triangle Listing on Shared-Memory Platforms

Email RIS file
Bookmark
Report an Issue

Fast Parallel Triad Census and Triangle Listing on Shared-Memory Platforms

Author
Parimalarangan, Sindhuja
Published
[University Park, Pennsylvania] : Pennsylvania State University, 2016.
Physical Description
1 electronic document
Additional Creators
Madduri, Kamesh
Access Online

Availability

I Want It
I Want It

Finding items...

Graduate Program
Restrictions on Access
Open Access.
Summary
Triad census and triangle counting are essential graph analysis measures used in areas such as social network analysis and systems biology. Triad census is a graph analytic for comparative network analysis and to characterize local structure in directed networks. For large sparse graphs, an algorithm by Batagelj and Mrvar is considered the state-of-the-art for computing triad census. In this work, we present a new parallel algorithm for triad census. Our algorithm takes advantage of a specific graph vertex identifier ordering to reduce the operation count. We also develop several new variants for exact triangle counting and triangle listing in large sparse, undirected graphs. Further, we implement a parallel sampling-based algorithm for approximate triangle counting. We show that our parallel triangle counting variants outperform other recently-developed triangle counting methods on current Intel multicore and manycore processors. We also achieve good strong scaling for both triad census and triangle counting on these platforms.
Other Subject(s)
Genre(s)
Dissertation Note
M.S. Pennsylvania State University 2016.
Reproduction Note
Library holds archival microfiches negative and service copy. 1 fiche. (Micrographics International, 2016)
Technical Details
The full text of the dissertation is available as an Adobe Acrobat .pdf file ; Adobe Acrobat Reader required to view the file.
View MARC record | catkey: 17735227