Szczegóły publikacji
Opis bibliograficzny
Distributed computing of distance-based graph invariants for analysis and visualization of complex networks / Wojciech CZECH, Wojciech Mielczarek, Witold DZWINEL // Concurrency and Computation : Practice and Experience ; ISSN 1532-0626. — 2017 — vol. 29 iss. 9 spec. iss.: Multi and many-core computing for parallel metaheuristics (McM 2015) and Algorithmic advances for parallel architectures (PPAM 2015) art. no. e4054, s. 1–21. — Bibliogr. s. 20–21, Summ. — Publikacja dostępna online od: 2016-12-23. — 11th international conference on Parallel Processing and Applied Mathematics PPAM 2015 : September 6–9, 2015, Krakow, Poland
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 104304 |
---|---|
Data dodania do BaDAP | 2017-05-22 |
Tekst źródłowy | URL |
DOI | 10.1002/cpe.4054 |
Rok publikacji | 2017 |
Typ publikacji | referat w czasopiśmie |
Otwarty dostęp | |
Czasopismo/seria | Concurrency and Computation : Practice & Experience |
Abstract
We present a new framework for analysis and visualization of complex networks based on structural information retrieved from their distance k-graphs and B-matrices. The construction of B-matrices for graphs with more than 1 million edges requires massive Breadth-First Search (BFS) computations and is facilitated using new software prepared for distributed environments. Our framework benefits from data parallelism inherent to all-pair shortest-path problem and extends Cassovary, an open-source in-memory graph processing engine, to enable multinode computation of distance k-graphs and related graph descriptors. We also introduce a new type of B-matrix, constructed using clustering coefficient vertex invariant, which can be generated with a computational effort comparable with the one required for a previously known degree B-matrix, while delivering an additional set of information about graph structure. Our approach enables efficient generation of expressive, multidimensional descriptors useful in graph embedding and graph mining tasks. The experiments showed that the new framework is scalable and for specific all-pair shortest-path task provides better performance than existing generic graph processing frameworks. We further present how the developed tools helped in the analysis and visualization of real-world graphs from Stanford Large Network Dataset Collection. Copyright © 2016 John Wiley & Sons, Ltd.