Efficient Q-matrix Computation for the Visualization of Complex Networks

摘要

The Q-matrix representation of a large network graph is a transformation yielding meaningful visualizations which can reveal internal structure, help classify networks according to their application area, and in some cases distinguish and identify real networks from synthetically generated data. However, the issue remains whether computing the Q-matrix is prohibitively expensive for problem sizes encountered in practice. Given an undirected network graph, we describe an efficient near-linear time algorithm for computing its Q-matrix. Besides providing theoretical bounds, we present experimental results showing that application networks with millions of edges and vertices can be processed in seconds on desktop computers.