著者

日野 滋樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CST, コンカレント工学 (ISSN:09135685)

巻号頁・発行日

vol.105, no.389, pp.35-40, 2005-11-03

---

インターネットサービスの内部でグラフアルゴリズムが応用されることが増えているが、その殆どが階層構造など特別なグラフ構造に依存して高速化されたものである。ここでは、特定の構造に依存しない一般グラフ上のアルゴリズムが応用できないかを考える。例題として、ノード間の直接的関係の強さを枝重みで表すグラフにおいて、他ノードを経由して伝搬される関係強度を加味したノード間の関係強度を求める問題を取り上げ、計算方法の簡略化と適用場面を想定した妥当性の関係について考察した。計算対象経路を、起点に近いノードに発する枝優先で選択した有向木を基準として順方向の枝のみを加えた部分グラフ上の経路に絞り込むことで、一般グラフを対象とするアルゴリズムが伴いやすい組み合わせ爆発を抑止しつつ、関係強度のランキングを提示する。隣接相手が少ないノードを起点とするとき、全経路を計算したときとほぼ同じ結果を得た。これをネット上の人間関係や企業間の依存関係のモデルに当てはめると妥当な結果になる。