Inferring Partial Orders of Nodes for Hierarchical Network Layout
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.
Document Type: Research Article
Publication date: 01 November 2016
This article was made available online on 05 December 2016 as a Fast Track article with title: "Inferring Partial Orders of Nodes for Hierarchical Network Layout".
The Journal of Imaging Science and Technology (JIST) is dedicated to the advancement of imaging science knowledge, the practical applications of such knowledge, and how imaging science relates to other fields of study. The pages of this journal are open to reports of new theoretical or experimental results, and to comprehensive reviews. Only original manuscripts that have not been previously published, nor currently submitted for publication elsewhere, should be submitted.
IS&T's JIST-first publication option allows authors wishing to present their work at conferences, but have a journal citation for their paper, to submit a paper to JIST that follows the same rigorous peer-review vetting and publication process as traditional JIST articles, but with the benefit of a condensed time-to-publication time frame and guaranteed conference presentation slot.
Please note: For purposes of its Digital Library content, IS&T defines Open Access as papers that will be downloadable in their entirety for free in perpetuity. Copyright restrictions on papers vary; see individual paper for details.
- Editorial Board
- Information for Authors
- Submit a Paper
- Subscribe to this Title
- Membership Information
- Information for Advertisers
- Terms & Conditions
- Information for JIST-First Authors
- Ingenta Connect is not responsible for the content or availability of external websites