Centrality-constrained graph embedding
This work addresses the need for graph visualizations that prioritize structural insights over aesthetics, which is incremental for applications like travel-time maps.
The paper tackled the problem of visualizing graphs with emphasis on structural properties like node centrality, by developing a constrained multi-dimensional scaling approach that incorporates graph smoothness to reduce edge crossings. The result is an efficient algorithm that converges and can embed large graphs with thousands of nodes.
Visual rendering of graphs is a key task in the mapping of complex network data. Although most graph drawing algorithms emphasize aesthetic appeal, certain applications such as travel-time maps place more importance on visualization of structural network properties. The present paper advocates a graph embedding approach with centrality considerations to comply with node hierarchy. The problem is formulated as one of constrained multi-dimensional scaling (MDS), and it is solved via block coordinate descent iterations with successive approximations and guaranteed convergence to a KKT point. In addition, a regularization term enforcing graph smoothness is incorporated with the goal of reducing edge crossings. Experimental results demonstrate that the algorithm converges, and can be used to efficiently embed large graphs on the order of thousands of nodes.