Extracting hierarchical structures from networks provides us with an effective means of visualizing them, especially when they contain complicated node connectivities such as those in traffic and distributed networks. Although many techniques have been developed for such purposes, they often deterministically break unwanted cycles that may arise from inconsistencies in the network hierarchies, and thus never seek the best compromise among possible partial orders of nodes inherent in the cycle. This article presents an algorithm for inferring such partial orders by optimizing the network hierarchies along flow paths that are given as input. Our idea is to extract network hierarchies from round-trip paths as well as one-way ones by deriving reasonably consistent multi-layered structures even from possibly inconsistent flow data over the networks. This problem is formulated as mixed-integer programming where we incorporate additional constraints into fundamental layout criteria according to the type and/or expected use of the network. For better visual readability of the network layout, the nodes in individual layers are clustered and reordered for minimizing edge crossings, which is followed by fine adjustment of intervals between neighboring nodes. We study several network examples to demonstrate the feasibility of the proposed approach including course dependency charts, railway networks, and peer-to-peer (P2P) networks. © 2016 Society for Imaging Science and Technology.
Hsiang-Yun Wu, Shigeo Takahashi, Hiroko Nakamura Miyamura, Satoshi Ohzahata, Akihiro Nakao, "Inferring Partial Orders of Nodes for Hierarchical Network Layout" in Proc. IS&T Int’l. Symp. on Electronic Imaging: Visualization and Data Analysis, 2017, pp 118 - 130, https://doi.org/10.2352/ISSN.2470-1173.2017.1.VDA-395