A Scalable Parallel Approach for Subgraph Census Computation
A Scalable Parallel Approach for Subgraph Census Computation
dc.contributor.author | David Oliveira Aparício | en |
dc.contributor.author | Pedro Reis Paredes | en |
dc.contributor.author | Pedro Manuel Ribeiro | en |
dc.date.accessioned | 2018-01-18T15:01:50Z | |
dc.date.available | 2018-01-18T15:01:50Z | |
dc.date.issued | 2014 | en |
dc.description.abstract | Counting the occurrences of small subgraphs in large networks is a fundamental graph mining metric with several possible applications. Computing frequencies of those subgraphs is also known as the subgraph census problem, which is a computationally hard task. In this paper we provide a parallel multicore algorithm for this purpose. At its core we use FaSE, an efficient network-centric sequential subgraph census algorithm, which is able to substantially decrease the number of isomorphism tests needed when compared to past approaches. We use one thread per core and employ a dynamic load balancing scheme capable of dealing with the highly unbalanced search tree induced by FaSE and effectively redistributing work during execution. We assessed the scalability of our algorithm on a varied set of representative networks and achieved near linear speedup up to 32 cores while obtaining a high efficiency for the total 64 cores of our machine. | en |
dc.identifier.uri | http://repositorio.inesctec.pt/handle/123456789/6963 | |
dc.identifier.uri | http://dx.doi.org/10.1007/978-3-319-14313-2_17 | en |
dc.language | eng | en |
dc.relation | 6048 | en |
dc.relation | 6238 | en |
dc.relation | 5316 | en |
dc.rights | info:eu-repo/semantics/openAccess | en |
dc.title | A Scalable Parallel Approach for Subgraph Census Computation | en |
dc.type | conferenceObject | en |
dc.type | Publication | en |
Files
Original bundle
1 - 1 of 1