特別小特集 5. 複雑ネットワーク解析における非バックトラック

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.105 No.1 (2022/1) 目次へ

前の記事へ次の記事へ


特別小特集 5. 複雑ネットワーク解析における非バックトラック A Brief Introduction to Non-backtracking in Network Analysis 小蔵正輝

小蔵正輝 正員 大阪大学大学院情報科学研究科バイオ情報工学専攻

Masaki OGURA, Member (Graduate School of Information Science and Technology, Osaka University, Suita-shi, 565-0871 Japan).

電子情報通信学会誌 Vol.105 No.1 pp.27-32 2022年1月

©電子情報通信学会2022

1.は じ め に

 慣れない土地での移動は難しい.例えば車で移動するときには,カーナビゲーションが指示する交差点で曲がりそびれたりする.Uターンをして元の交差点まで戻らなければいけない.また,筆者は梅田の地下街でよく迷う.気がつけば同じ道を何度も行き来していることがある.国際学会などの旅先でも同様である.迷っている最中に意外な発見をすることもあるが,やはりそれでも無用な行き戻りは減らせるに越したことはない.

 近年,ネットワーク解析においても行き戻り防止の有用性が注目されている.本稿ではバックトラックと呼ばれる行き戻りに焦点を当てる.大雑把に言うとバックトラックとは,図1に示すパスが含む行き戻りmathのことである.このようなバックトラックを防ぐことにより可能となるネットワーク解析を紹介したい.本稿ではネットワーク科学において代表的な研究テーマである酔歩,伝搬,中心性における以下の題材を扱う:

・バックトラックの禁止による酔歩の効率化(2.

・非バックトラック性を考慮した感染症伝搬の漸近解析(4.

・非バックトラック性の導入による中心性局在の緩和(5.

図1 バックトラックを持つパス  行き戻り5→6→5が生じている.

 また,途中の3.ではバックトラックを排除したネットワーク解析を行う際に便利な道具である非バックトラック行列を紹介する.

 本稿で用いる記法と用語について述べる.mathmath個の頂点mathを持つ無向グラフとする.mathが持つ無向辺の数をmathと書く.辺は重みを持たないと仮定する.またmathは連結である,つまり任意の二頂点の間にはパスが存在すると仮定する.隣接行列math

math

(1)

により定める.図2に無向グラフと隣接行列の例を示す.頂点mathに隣接する頂点の集合をmathと書く.慣習と文脈に応じてグラフをネットワークと呼ぶことがあるが,意味に大きな違いはない.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録

  

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。