Distributed computing of distance-based graph invariants foranalysis and visualization of complex networks

摘要

We present a new framework for analysis and visualization of complex networks based on structural informationretrieved from their distance k-graphs and B-matrices. The construction of B-matrices for graphswith more than 1 million edges requires massive Breadth-First Search (BFS) computations and is facilitatedusing new software prepared for distributed environments. Our framework benefits from data parallelisminherent to all-pair shortest-path problem and extends Cassovary, an open-source in-memory graph processingengine, to enable multinode computation of distance k-graphs and related graph descriptors. Wealso introduce a new type of B-matrix, constructed using clustering coefficient vertex invariant, which canbe generated with a computational effort comparable with the one required for a previously known degreeB-matrix, while delivering an additional set of information about graph structure. Our approach enables efficientgeneration of expressive, multidimensional descriptors useful in graph embedding and graph miningtasks. The experiments showed that the new framework is scalable and for specific all-pair shortest-path taskprovides better performance than existing generic graph processing frameworks.We further present how thedeveloped tools helped in the analysis and visualization of real-world graphs from Stanford Large NetworkDataset Collection.