Fast Parallel All-Subgraph Enumeration Using Multicore Machines
Joint Authors
Shahrivari, Saeed
Jalili, Saeed
Source
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-06-16
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
Enumerating all subgraphs of an input graph is an important task for analyzing complex networks.
Valuable information can be extracted about the characteristics of the input graph using all-subgraph enumeration.
Notwithstanding, the number of subgraphs grows exponentially with growth of the input graph or by increasing the size of the subgraphs to be enumerated.
Hence, all-subgraph enumeration is very time consuming when the size of the subgraphs or the input graph is big.
We propose a parallel solution named Subenum which in contrast to available solutions can perform much faster.
Subenum enumerates subgraphs using edges instead of vertices, and this approach leads to a parallel and load-balanced enumeration algorithm that can have efficient execution on current multicore and multiprocessor machines.
Also, Subenum uses a fast heuristic which can effectively accelerate non-isomorphism subgraph enumeration.
Subenum can efficiently use external memory, and unlike other subgraph enumeration methods, it is not associated with the main memory limits of the used machine.
Hence, Subenum can handle large input graphs and subgraph sizes that other solutions cannot handle.
Several experiments are done using real-world input graphs.
Compared to the available solutions, Subenum can enumerate subgraphs several orders of magnitude faster and the experimental results show that the performance of Subenum scales almost linearly by using additional processor cores.
American Psychological Association (APA)
Shahrivari, Saeed& Jalili, Saeed. 2015. Fast Parallel All-Subgraph Enumeration Using Multicore Machines. Scientific Programming،Vol. 2015, no. 2015, pp.1-11.
https://search.emarefa.net/detail/BIM-1076554
Modern Language Association (MLA)
Shahrivari, Saeed& Jalili, Saeed. Fast Parallel All-Subgraph Enumeration Using Multicore Machines. Scientific Programming No. 2015 (2015), pp.1-11.
https://search.emarefa.net/detail/BIM-1076554
American Medical Association (AMA)
Shahrivari, Saeed& Jalili, Saeed. Fast Parallel All-Subgraph Enumeration Using Multicore Machines. Scientific Programming. 2015. Vol. 2015, no. 2015, pp.1-11.
https://search.emarefa.net/detail/BIM-1076554
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1076554