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

摘要

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