(57)【要約】【課題】Ｇｏｏｇｌｅ検索エンジンでは不可能な一般化されたネットワーク構造からネットワークシステムの基本特性すなわち情報流や物流の分布パターンを求めることを可能とすること。【解決手段】ネットワーク構造を表現するネットワークグラフからユークリッドノルムの新遷移行列を考案して、その複数の固有ベクトルからネットワークの情報流や物流のパターンを算定することで、構造改革での効果を分析可能とする。【選択図】図１
2008130067.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの接続関係を表すネットワークグラフを求める機能、これを散乱行列に変換しその固有ベクトルを求める機能、これをネットワーク図形に表示する機能を有するネットワーク分析器。
【請求項２】
散乱行列Ｓがネットワークグラフ（その要素Ｎｉ，ｊとする）をユークリッドノル
2008130067.tif 000009
項１で記載されるネットワーク分析器。
【請求項３】
請求項２を満たすネットワーク分析器において、複数の固有モードの固有ベクトルを用いて、ネットワーク機能特性を分析することを特徴とするネットワーク分析器。
【請求項４】
上記複数の固有モードの固有ベクトルから、検索リストに複数のランク付けをすることを特徴とする請求項２を満たすネットワーク分析器。
【発明の詳細な説明】
【技術分野】
【０００１】ネットワークは通信、鉄道をはじめ社会インフラとして実生活に不可欠なものになっているが、その最適化設計や分析の普遍的手法の開拓は複雑系科学の最先端のひとつである。本特許は、ネットワークでの情報・物流の集中などを分析する新ネットワーク分析器の技術に関する。
【背景技術】
【０００２】  従来、ネットワークの分析は、高速道路網での渋滞の分析のように、交通量のサンプリング調査などを用いて交通量を計算モデルを設定してシミュレートしている。グーグル検索エンジンの新規性は、ネットワーク構造のみのデータからＷｅｂページの人気度を推定するなどのネットワーク基本特性を分析する点にある。
すなわち、グーグル検索エンジンでは、従来Ｗｅｂの検索すなわちウェブサーフィンをマルコフ過程として捉え、その定常解を人気度とするモデルを考案した。ウェブサーファは次のページへ飛ぶとき、今いるページからリンクしているページのどれかに、遷移行列の与える確率にしたがって遷移する。これまでの遷移の経緯を忘れて、現時点のページから遷移行列にしたがって遷移するモデルはマルコフ過程と呼ばれる。このマルコフ過程を無限回続けたとして行き着いくページ毎の確率が遷移行列の固有ベクトルとして与えられることが知られている。グーグル検索エンジンではこのマルコフ過程で人気度あるいは重要度を求め、一致リストに重み付けして表示順を決めている。これら詳細は公表されていないので、Ｍｅｙｅｒらの解説書（Ｇｏｏｇｌｅ’ｓ  ＰａｇｅＲａｎｋ  ａｎｄ  Ｂｅｙｏｎｄ，Ｐｒｉｎｓｔｏｎ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２００６）によっている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】先行技術であるグーグル検索エンジンが、不可能な一般化されたネットワークグラフに対して、新遷移行列を発見しその複数の固有ベクトルの与えるネットワーク人気度など活性度を示すパターンにより、一般化されたネットワーク分析解析設計を可能とする手段を提供する。
解説書により推定するグーグル検索エンジンはユークリッドノルムでなく１−ｎｏｒｍを用いているため、対称なネットワークグラフに対しては、無限回のマルコフ過程で到達するノードの確率分布は、ノードの持つリンク数に比例した結果となり、現実と整合しない。
【解決するための手段】
【０００４】本発明は、ネットワークグラフで記述されるネットワーク構造のみから、ネットワークに内在する基本特性を分析できるネットワーク分析器に関する。前述の問題を生じる遷移行列をやめて、物理学で一般的なユークリッドノルムをもつ散乱行列的な新遷移行列Ｓを発見した。すなわち、ネットワークグラフ｛Ｎｉ，ｊ｝はノードｉがノードｊに接続されていれば１、そうでなければ０で、ネットワーク構造を記述する。新遷移行列｛Ｓｉ，ｊ｝を次のように定義した。
2008130067.tif 000003
ここで、Ｍはネットワークのノード数である。
2008130067.tif 000004
ある。新遷移行列Ｓの固有方程式は
ＳＴ・ｆｋ＝λｋ・ｆｋ
で与えられる。ここにＳＴはＳの転置行列、λｋはｋ番目の固有値、ｆｋはｋ番目の固有値に対応する固有ベクトルである。マルコフ過程における定常確率分布状態はｆｋで与えられ、
2008130067.tif 000005
すこし数学的準備をすると、
この新遷移行列は実数行列でネットワークの任意の初期状態から無限回のマルコフ過程を
2008130067.tif 000006
またｍ個の初期状態ベクトルから互いに直交するように無限回のマルコフ過程を繰り返すと異なるｍ個の固有ベクトルに収束することも知られている。
以上の基本部を有するネットワーク分析器では以下の機能を提供する。
▲１▼ネットワークグラフによるネットワーク構造から、ネットワークの動作や活性度などの状態の複数のモードをネットワーク上にそれぞれ図示して情報流や物流のパターンを提供する。
▲２▼ネットワークグラフを改造して、特定ノードへの情報流や物流を集中ないし排除など、ネットワーク動作行動状態の予測分析を提供する。
▲３▼ネットワーク上の情報・物流の他のリストと上記固有ベクトルとの相関によりランキングを提供する。
【０００５】  特許の新奇性のポイントは、前述の問題を生じる遷移行列をやめて、物理学で一般的なユークリッドノルムをもつ散乱行列的な新遷移行列Ｓを発明・導入した点に発する。
従来、散乱行列として、マイクロ波解析などで定義されるものは、ユニタリ行列で
2008130067.tif 000007
など厳密な条件が付与されている。したがって、ここでは前例のない新遷移行列Ｓを発明しているし、それの有効性が確認されている。
すなわち、
特許請求範囲：
請求項１．ネットワークの接続関係を表すネットワークグラフを求める機能、これを散乱行列に変換しその固有ベクトルを求める機能、これをネットワーク図形に表示する機能を有するネットワーク分析器。
請求項２．散乱行列Ｓがネットワークグラフ（その要素Ｎｉ，ｊとする）をユークリッドノル
2008130067.tif 000008
項１で記載されるネットワーク分析器。
請求項３．請求項２を満たすネットワーク分析器において、複数の固有モードの固有ベクトルを用いて、ネットワーク機能特性を分析することを特徴とするネットワーク分析器。
請求項４．上記複数の固有モードの固有ベクトルから、検索リストに複数のランク付けをすることを特徴とする請求項２を満たすネットワーク分析器。
【発明の効果】
【０００６】解説書により推定するグーグル検索エンジンはユークリッドノルムでなく１−ｎｏｒｍを用いているため、対称なネットワークグラフに対しては、無限回のマルコフ過程で到達するノードの確率分布は、ノードの持つリンク数に比例した結果となり、現実と整合しない。
すなわち図１は本発明の成果をグーグル的検索エンジンと比較した。東京鉄道地下鉄網に適用して利用者数の上位３駅の抽出を試みた。鉄道地下鉄網のに乗る人は、鉄道地下鉄網の与える遷移行列に従ってマルコフ過程を繰り返すとして駅ごとの到達確率が利用者数を与えるというモデルである。すると結果は新宿、池袋、新橋となり、実際の利用者数データ（Ｗｉｋｉｐｅｄｅａによる）新宿３２０万人／日、池袋２７０万人／日、渋谷２２０万人／日と異なった。図１ａはグーグル的検索エンジンでリンク数の多き駅順に比例して到達確率分布が与えられる。図１ｂは本発明によるネット分析エンジンの結果で、リンク数７の小さな渋谷がちゃんと第三の大利用者数駅に抽出される。
また本エンジンでは多様なネットワーク特性モードの表示がはじめて可能となりかつその有用性が期待できる。
図２は２００番目のモードパターンで、横浜線（新横浜）、東横線（菊名）、田園都市線（あざみ野、長津田）のコヒレントな励起が見られる。この路線の囲む中に、港北ニュータウン計画が実施されたことは、鉄道網が地域活性度と密接な相互作用していることを考慮すると偶然とは思えない。このような都市計画など広範囲なネットワーク分析器の提供が可能となる。
【発明を実施するための最良の形態】
【０００７】ネットワーク分析器の構成には、大規模新遷移行列の固有ベクトルを求める演算ツール（１０００ノード未満のネットワークに対しては標準的数学ソフトで十分）を準備して、構成要素を展開すればよい。
【実施例】
【０００８】首都高速道路網の場合の実施例を示す。
ノードの定義をインターチェンジとして分岐はそれを囲むノード間のリンク接続で表現する。ライトマップル東京都道路地図ＩＳＢＮ４−３９８−６２９６３−７  Ｃ０３２６のＰ．３１掲載の首都圏高速道路網図を用いた。そこから２１０ノードを抽出してネットグラフを作り、新遷移行列Ｓの固有モードベクトルをマップに図示する。到達確率振幅を２例示す。図３ａは固有モード＃５であり５番目に大きな固有値に対応する。ここには、扇大橋から千住新橋、小菅、四つ木、平井大橋にいたる中央環状線と加平、小菅、堤通、向島、駒形にいたる高速６号線の交差する代表的混雑領域を表している。その他は省略するが、有名な混雑領域はちゃんと固有モードに含まれている。示唆的な第二の例は東京湾アクアラインでが、南千葉地区と川崎地区をつなぐ動脈として混雑地区として抽出されている。これは、アクアラインの設計意義を裏付ける結果であり、ネットワークグラフで考慮されていない料金問題を示唆する。
このように、ネットワーク機能を特定領域で活性化する手法評価など有用性が期待できる。
【産業上の利用可能性】
【０００９】現在、通信や交通の社会インフラをなすネットワークの効率と安全性を確保しながら如何に有用な新サービスを実現するか経済活動の基盤になろうとしている。
本発明はそんなネットワーク構築の基本手法を提供するもので、Ｇｏｏｇｌｅとは違った領域を含み大発展する可能性を秘める。
具体例は特許請求範囲３に述べるように、特定のＷｅｂサイトへの情報流集中のコンサルタント業は具体化している。すなわち、Ｗｅｂサイトアクセスをマルコフ過程と仮定して、Ｗｅｂリンクの張り方を変えて特定サイトへの情報流集中をシミュレートして最適化を図る。これはＷｅｂサイトコンサルティングのコア構造を本発明が与えることを意味する。
【図面の簡単な説明】
【００１０】
【図１】本発明により世界３大利用者数駅を初めて東京鉄道地下鉄網構造だけから抽出
【図２】Ｇｏｏｇｌｅ的検索エンジンでは図１の正解は得られない
【図３】図１のネットワークの＃２００番目の固有モードの確率振幅分布図
【図４】図３で囲まれた地域で実施された港北ニュータウン計画（中央暗部）Ａｚ：あざみ野、Ｎａ：長津田、Ｓｙ：新横浜、Ｋｉ：菊名
【図５】実施例の首都高速道路網での６番目の固有モード：有名な混雑地区の抽出例
【図６】図５と同じく７番目の固有モード：アクアライン地区が混雑地区として抽出され、料金課題を抽出
【図１】
2008130067.tif 000010
【図２】
2008130067.tif 000011
【図３】
2008130067.tif 000012
【図４】
2008130067.tif 000013
【図５】
2008130067.tif 000014
【図６】
2008130067.tif 000015