Inferring partial orders of nodes for hierarchical network layout

階層ネットワークデータレイアウトにおけるノード間半順序関係の推定

Wu, H.-Y.*; 高橋 成雄*; 宮村 浩子  ; 大坐畠 智*; 中尾 彰宏*

Wu, H.-Y.*; Takahashi, Shigeo*; Miyamura, Hiroko; Ozahata, Satoshi*; Nakao, Akihiro*

複雑なネットワークデータから階層構造を抜き出すのは、例えばネットワークトラフィックや分散の解析に有用である。本論文では山なりのパスに従ってノードを配置するようにノードの半順序関係を推定する手法を提案する。提案手法の有効性を検証するために、コース依存状態チャート、鉄道ネットワーク、およびピアツーピア(P2P)ネットワークに適用した例を示す。

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. This paper presents an algorithm for inferring such partial orders by optimizing the network hierarchies along flow paths that are given as input. We study several network examples to demonstrate the feasibility of the proposed approach including course dependency charts, railway networks, and P2P networks.