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.