Abstract
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.
Introduction
Traditional graph drawing algorithms, such as force-directed layouts, often prioritize aesthetic qualities like uniform edge lengths and minimal node overlap. However, in many real-world networks—including transportation systems and social hierarchies—certain nodes possess greater structural importance than others. Standard visualization techniques frequently obscure these hierarchies.
This paper addresses the challenge of creating radial layouts where a node's distance from the origin is strictly determined by its centrality (e.g., betweenness or closeness centrality). The goal is to map node hierarchy directly to geometry while maintaining the network's structural connectivity. Mathematically, this involves solving a non-convex and non-smooth optimization problem to find coordinates that respect both centrality constraints and graph-based dissimilarities.
Methodology
The proposed framework is based on Constrained Multi-Dimensional Scaling (MDS). The objective function utilizes the "stress" criterion, aiming to match Euclidean distances in the embedding space to the Euclidean Commute-Time Distance (ECTD) of the graph. ECTD is chosen for its robustness, as it considers all possible paths between nodes rather than just the shortest path.
To enforce the hierarchy, a radial constraint is imposed: the norm of each node's coordinate vector must equal a predefined function of its centrality. This ensures that high-centrality nodes are positioned near the center, while peripheral nodes are pushed outward.
The optimization problem is solved using Block Coordinate Descent (BCD) with Successive Approximations. By decoupling the nodes and solving for one at a time, the authors employ a convex upper bound for the non-smooth stress function—a technique akin to Majorization-Minimization. This approach guarantees convergence to a stationary (KKT) point.
Furthermore, a Graph Laplacian-based smoothness regularization term is added to the objective. This penalty encourages adjacent nodes to remain close, effectively reducing the "spaghetti" effect of crossing edges and improving the overall readability of the layout.
Experimental Results
The algorithm was evaluated on the London Tube network (307 stations) and the Arxiv General Relativity collaboration network (over 4,000 nodes).
Smoothness and Visual Clarity
In the London Tube example, the smoothness parameter lambda proved critical for visual clarity. As shown in the figure below, increasing lambda from 0 to 10,000 significantly reduces edge crossings. At high regularization values, the layout becomes visually organized in fewer iterations, demonstrating that the penalty term aids both aesthetics and computational efficiency.
Convergence and Scalability
A key advantage of this method is its mathematical guarantee of convergence. Unlike heuristic-based radial layouts, the BCD-based solver consistently reaches a KKT point. The following figure illustrates the typical convergence behavior, where the stress objective decreases monotonically and stabilizes.
The approach also scales effectively to larger networks. For the Arxiv collaboration network, the algorithm successfully embedded thousands of nodes within 30 outer iterations, clearly clustering core researchers at the center of the radial plot.
Conclusion
This paper presents a robust framework for centrality-constrained graph embedding. By mapping hierarchy to radial distance, it provides an intuitive visualization of network structure. While the current work focuses on 2D embeddings and requires user-defined centrality mapping functions, the guaranteed convergence and scalability make it a powerful tool for analyzing complex networks. Future work may explore automated mapping functions and higher-dimensional visualizations.
Summary updated