(57)【要約】【課題】本発明は、よりブラウジングに適したネットワークデータの低次元空間への埋め込みを実現する新たな技術の提供を目的とする。【解決手段】各ノードについて直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置される場合に最適な配置であるとして、その最適な配置に近づく程ある値に近づく性質を持つ目的関数を用い、順次更新される各ノードの埋め込み位置を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する過程と、改善指標に基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断する過程と、打ち切りを判断しない場合に、目的関数から導出される値を使って、最適な配置に向かうようにとノードの埋め込み位置を更新する過程とを備える。この構成に従って、接続関係を忠実に保存する形で埋め込みを実現できるようになる。【選択図】          図１
2004318739.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実行されて、複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを低次元の空間に埋め込み配置するネットワークデータ低次元埋込方法であって、
各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置されるようにと、各ノードの埋め込み位置を決定することを、
特徴とするネットワークデータ低次元埋込方法。
【請求項２】
コンピュータにより実行されて、複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを低次元の空間に埋め込み配置するネットワークデータ低次元埋込方法であって、
全ノードの埋め込み位置の初期値をランダムに設定する過程と、
各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置される場合に最適な配置であるとして、その最適な配置に近づく程ある値に近づく性質を持つ目的関数を用い、上記初期値を起点として順次更新される各ノードの埋め込み位置を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する過程と、
上記改善指標に基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断する過程と、
上記打ち切りを判断しない場合に、上記目的関数から導出される値を使って、最適な配置に向かうようにとノードの埋め込み位置を更新する過程とを備えることを、
特徴とするネットワークデータ低次元埋込方法。
【請求項３】
請求項２記載のネットワークデータ低次元埋込方法において、
上記算出する過程では、各ノードについて、他のノードを固定してそのノードを移動させたときの勾配ベクトルの大きさを上記改善指標として算出することを、
特徴とするネットワークデータ低次元埋込方法。
【請求項４】
請求項３記載のネットワークデータ低次元埋込方法において、
上記算出する過程では、前回算出した勾配ベクトルと上記埋め込み位置の更新量とに基づいて今回算出する勾配ベクトルを算出できることになるノードについては、それらに基づいて今回算出する勾配ベクトルを算出し、その大きさを算出することにより上記改善指標を算出することを、
特徴とするネットワークデータ低次元埋込方法。
【請求項５】
請求項２ないし４のいずれか１項に記載のネットワークデータ低次元埋込方法において、
上記改善指標が最も大きな値を示すノードを選択することで、埋め込み位置の更新対象となるノードを１つ選択する過程を備えることを、
特徴とするネットワークデータ低次元埋込方法。
【請求項６】
請求項５記載のネットワークデータ低次元埋込方法において、
上記判断する過程では、上記選択したノードについての上記改善指標の大きさに基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断することを、
特徴とするネットワークデータ低次元埋込方法。
【請求項７】
複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを低次元の空間に埋め込み配置するネットワークデータ低次元埋込装置であって、
各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置されるようにと、各ノードの埋め込み位置を決定する手段を備えることを、
特徴とするネットワークデータ低次元埋込装置。
【請求項８】
複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを低次元の空間に埋め込み配置するネットワークデータ低次元埋込装置であって、
全ノードの埋め込み位置の初期値をランダムに設定する手段と、
各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置される場合に最適な配置であるとして、その最適な配置に近づく程ある値に近づく性質を持つ目的関数を用い、上記初期値を起点として順次更新される各ノードの埋め込み位置を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する手段と、
上記改善指標に基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断する手段と、
上記打ち切りを判断しない場合に、上記目的関数から導出される値を使って、最適な配置に向かうようにとノードの埋め込み位置を更新する手段とを備えることを、
特徴とするネットワークデータ低次元埋込装置。
【請求項９】
請求項８記載のネットワークデータ低次元埋込装置において、
上記算出する手段は、各ノードについて、他のノードを固定してそのノードを移動させたときの勾配ベクトルの大きさを上記改善指標として算出することを、
特徴とするネットワークデータ低次元埋込装置。
【請求項１０】
請求項９記載のネットワークデータ低次元埋込装置において、
上記算出する手段は、前回算出した勾配ベクトルと上記埋め込み位置の更新量とに基づいて今回算出する勾配ベクトルを算出できることになるノードについては、それらに基づいて今回算出する勾配ベクトルを算出し、その大きさを算出することにより上記改善指標を算出することを、
特徴とするネットワークデータ低次元埋込装置。
【請求項１１】
請求項８ないし１０のいずれか１項に記載のネットワークデータ低次元埋込装置において、
上記改善指標が最も大きな値を示すノードを選択することで、埋め込み位置の更新対象となるノードを１つ選択する手段を備えることを、
特徴とするネットワークデータ低次元埋込装置。
【請求項１２】
請求項１１記載のネットワークデータ低次元埋込装置において、
上記判断する手段は、上記選択したノードについての上記改善指標の大きさに基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断することを、
特徴とするネットワークデータ低次元埋込装置。
【請求項１３】
請求項１ないし６のいずれか１項に記載のネットワークデータ低次元埋込方法の実現に用いられる処理をコンピュータに実行させるためのネットワークデータ低次元埋込プログラム。
【請求項１４】
請求項１ないし６のいずれか１項に記載のネットワークデータ低次元埋込方法の実現に用いられる処理をコンピュータに実行させるためのネットワークデータ低次元埋込プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複雑なネットワークを低次元空間に配置することで、コンピュータのディスプレイ上で容易に閲覧できるようにするネットワークデータ低次元埋込方法及びその装置と、そのネットワークデータ低次元埋込方法の実現に用いられるネットワークデータ低次元埋込プログラム及びそのプログラムを記録した記録媒体とに関する。
【０００２】
【従来の技術】
多くの研究分野において、複雑なリレーショナルデータの表現手段としてネットワーク又はグラフが良く用いられる。ここで述べるネットワークとは、複数のノードとノード間を結ぶリンクとからなる集合であると定義する。
【０００３】
例えばＷｅｂを対象とする場合、各Ｗｅｂページをノード、ページ間のハイパーリンクをノード間のリンクとするハイパーリンクネットワークが良く用いられているし、生物学においては、遺伝子やたんぱく質、代謝物質などの相互作用を遺伝子制御ネットワークを用いて表現することが行われている。また、人間どうし、あるいは企業などの社会的存在どうしの関係の解析にはソーシャルネットワークが用いられる。
【０００４】
一般にネットワーク表現によって、グラフ理論などを駆使した数学的な解析が可能になると同時に、低次元空間に埋め込んで実際に表示させることで、内在するデータの構造的特徴を浮彫りにし、その結果、研究者にとって重要な洞察を得ることが可能になる。
【０００５】
このようにネットワークの埋め込み法の研究は、ネットワークに内在する知識を獲得し構造的原理を明らかにするという、発見科学および機械学習の立場からみても極めて重要である。しかるに、ネットワークのサイズが増加し複雑になるとネットワークの埋め込みはより困難となり、より効率的な埋め込みアルゴリズムが必要となる。
【０００６】
ネットワークの構造を直感的に理解し解析する基本的な方法の一つとして、「ブラウジング」が挙げられる。ブラウジングとは、ネットワークを低次元の空間に埋め込み、その配置上でノードからノードへのリンクをたどったり、ノードごとの接続関係を相互に比較するなど低次元の配置を直接調べることである。効率的な埋め込みアルゴリズムとは、ブラウジングに最も適したネットワークの低次元ユークリッド空間への埋め込みを生成することが出来るアルゴリズムであると考えられる。
【０００７】
ネットワーク又はグラフを２次元や３次元のような低次元ユークリッド空間に埋め込んで可視化する方法はいくつか知られている。
【０００８】
古典的な多次元尺度法（例えば、非特許文献１参照）を用いることも可能であるし、また、もっとも代表的な方法として、バネモデル（例えば、非特許文献２参照）が知られている。また、球面上に配置する方法として、スペクトラルクラスタリング（例えば、非特許文献３参照）が知られている。
【０００９】
これら従来の方法では、ネットワークの任意のノードのペア間に距離が存在することを仮定している。例えば上述のバネモデルでは、任意のノードペアに対してグラフ距離（ｇｒａｐｈ−ｔｈｅｏｒｅｔｉｃ  ｄｉｓｔａｎｃｅ）を計算し、この距離がもつとも忠実に保存されるような低次元への埋め込みを考えている。
【００１０】
ここでグラフ距離とは、２ノード間のグラフ上の最短経路長（すなわち最小リンク数）のことであり、例えば  Ｆｌｏｙｄアルゴリズム（Ｆｌｏｙｄ，Ｒ．Ｗ．”Ａｌｇｏｒｉｔｈｍ  ９７（Ｓｈｏｒｔｅｓｔ  ｐａｔｈ）”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，５（６），３４５，１９６２．）によって計算される。
【００１１】
まとめると、従来法はどれも、以下のような〔原則Ｂ〕をなるべく満足する配置を求める手法であると言える。
【００１２】
〔原則Ｂ〕（ｄｉｓｔａｎｃｅ  ｐｒｅｓｅｒｖｉｎｇ  ｐｒｉｎｃｉｐｌｅ）各ノードペアは、相互のグラフ距離が低次元ユークリッド空間においてもっとも忠実に復元されるように相互の配置を決める。
【００１３】
【非特許文献１】
Ｔｏｒｇｅｒｓｏｎ，Ｗ．Ｓ．，”Ｔｈｅｏｒｙ  ａｎｄ  Ｍｅｔｈｏｄｓ  ｏｆ  Ｓｃａｌｉｎｇ”，Ｗｉｌｅｙ，Ｎｅｗ  Ｙｏｒｋ，１９５８．
【非特許文献２】
Ｋａｍａｄａ，Ｔ．，＆  Ｋａｗａｉ，Ｓ．”Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｄｒａｗｉｎｇ  Ｇｅｎｅｒａｌ  Ｕｎｄｉｒｅｃｔｅｄ  Ｇｒａｐｈ”，Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｌｅｔｔｅｒｓ，３２，７−１５，１９８９．
【非特許文献３】
Ｎｇ，Ａ．，Ｊｏｒｄａｎ，Ｍ．  ＆  Ｗｅｉｓｓ，Ｙ．”Ｏｎ  ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ：  Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  ａｌｇｏｒｉｔｈｍ”  Ｐｒｏｃ．  ｏｆ  ＮＩＰＳ  １４，２００１．
【００１４】
【発明が解決しようとする課題】
しかしながら、特に埋め込みの次元が低く、かつ大規模で複雑なネットワークの場合、埋め込みの自由度が少ないため、従来法のような距離を忠実に保存する埋め込みでは破綻をきたすことになる。
【００１５】
その結果、従来技術に従っていると、ブラウジングに不向きな、片寄った配置しか得られないことが多い。
【００１６】
本発明はかかる事情に鑑みてなされたものであって、従来法のような「距離を忠実に保存する」というアプローチをとるのではなく、もっと直接的に「接続関係を忠実に保存する」というアプローチをとることによって、よりブラウジングに適したネットワークデータの低次元空間への埋め込みを実現する新たなネットワークデータ低次元埋込技術の提供を目的とする。
【００１７】
【課題を解決するための手段】
今、Ｎ個のノードからなるネットワークを考え、その隣接行列をＡ＝（ａｉ，ｊ  ）とする。
【００１８】
説明を簡単にするために無向ネットワークのみを扱うこととする。すなわち、ａｉ，ｊ  ∈｛０，１｝、ａｉ，ｉ  ＝１、かつａｉ，ｊ  ＝ａｊ，ｉ  と仮定する。ただし、本発明は有向ネットワークにも容易に拡張できる。
【００１９】
ここで、ａｉ，ｊ  ∈｛０，１｝は、ａｉ，ｊ  の値が１か０であることを示し、ｉとｊとが繋がっている場合にはａｉ，ｊ  ＝１となり、ｉとｊとが繋がっていない場合にはａｉ，ｊ  ＝０となる。
【００２０】
与えられたネットワークに対して、本発明の目的は、次に述べるＫ次元ユークリッド距離の意味で、下記の〔原則Ａ〕を実現するＮ個のノードのＫ次元空間への埋め込みを求めることである。
【００２１】
〔原則Ａ〕（ｃｏｎｎｅｃｔｉｖｉｔｙ  ｐｒｅｓｅｒｖｉｎｇ  ｐｒｉｎｃｉｐｌｅ）  各ノードは、それと隣接するノード（すなわち、直接リンクで繋がっているノード）を、隣接しないノードより相対的により近くに配置する。
【００２２】
そこで、本発明では、以下で説明するようにクロスエントロピーに基づく目的関数を考えることによって、より最適な埋め込みを求める。
【００２３】
Ｋ次元空間におけるＮ個のノードの座標をｘ１，ｘ２，・・・  ，ｘＮ  （本来はベクトル表記すべきものであるが記載の便宜上ベクトル表記していない）とする。ここで、ｘｉ  とｘｊ  との間のユークリッド距離は下記の式（１）のように定義される。
【００２４】
【数１】
2004318739.tif 000003
【００２５】
次に、ｕ≧０に関する単調減少関数ρ（ｕ）∈［０，１］を考え、ρ（０）＝１，ρ（∞）＝０とする。このとき、ρ（ｄｉ，ｊ  ）は、ｘｉ  ，  ｘｊ  間の（連続値をとる）類似度関数と見なすことができる。
【００２６】
本発明の基本的な技術思想は、実際の最適化がより扱いやすくなるように〔原則Ａ〕を言い換えることである。
【００２７】
まず、この類似度を用いると、〔原則Ａ〕は、「各ノードは隣接するノードと自分との類似度が、隣接しないノードとの類似度よりも大きくなるように配置する」と言い換えられる。
【００２８】
さらに、ａｉ，ｊ  とρ（ｄｉ，ｊ  ）を用いることによって、〔原則Ａ〕は、「各ノードは連続値をとる類似度関数ρ（ｄｉ，ｊ  ）が離散類似度ａｉ，ｊ  のもっとも良い近似となるように配置する」という、多少条件が緩和された形に言い換えられる。
【００２９】
そこで、ρ（ｄｉ，ｊ  ）によってａｉ，ｊ  を近似するために、ａｉ，ｊ  とρ（ｄｉ，ｊ  ）に関する下記の式（２）に示すような負のクロスエントロピーを考える。
【００３０】
【数２】
2004318739.tif 000004
【００３１】
この式（２）は、ｘｉ  ，ｘｊ  に関しρ（ｄｉ，ｊ  ）＝ａｉ，ｊ  のとき、すなわち、連続値類似度関数が離散類似度と完全に一致するときに最小となる。Ｅｉ，ｊ  が対称であることに注意すると、ｘ１，ｘ２，・・・  ，ｘＮ  に関し最小化すべき全エネルギー関数は下記の式（３）となる。
【００３２】
【数３】
2004318739.tif 000005
【００３３】
ここで、ノードｉを固定してみる。するとａｉ，ｊ  はノードｊの２値クラスラベルと解釈することができる。すなわち、ａｉ，ｊ  ＝１の場合、ｊが属するクラスのラベルは１であり、ａｉ，ｉ  ＝１に注意すると、ｊはｉと同じクラスに属する。一方、ａｉ，ｊ  ＝０の場合、ノードｊが属するクラスのラベルは０であり、ｊはｉとは異なるクラスに属する。
【００３４】
従って、この問題は、式（３）を分類問題としては標準的な目的関数として、ｘ１，ｘ２，・・・  ，ｘＮ  をパラメータするＮ個の２値分類問題を同時に解くことであると解釈できる。
【００３５】
ここでは、類似度関数として常にρ（ｕ）＝ｅｘｐ（−ｕ／２）を用いる（他の関数を用いることも可能）。これを用いると、式（２）のエネルギー関数は下記の式（４）で与えられる。
【００３６】
【数４】
2004318739.tif 000006
【００３７】
この式（４）を使い、最終的な目的関数は正則化項を付加して下記の式（５）のように定義される。
【００３８】
【数５】
2004318739.tif 000007
【００３９】
ここで、μは正則化係数であり、事前に決めておく。このような正則化項を導入することによって、アルゴリズムは安定すると同時に、埋め込まれた配置のサイズを制御することができる。
【００４０】
この目的関数は、各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置される場合に最適な配置であるとして、その最適な配置に近づく程、その値が小さくなってある値に近づくという性質を持つ。
【００４１】
本発明のネットワークデータ低次元埋込装置は、複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを低次元の空間に埋め込み配置する処理を行うために、▲１▼全ノードの埋め込み位置の初期値をランダムに設定する設定手段と、▲２▼上述の性質を持つ目的関数を用い、設定手段の設定した初期値を起点として順次更新される各ノードの埋め込み位置を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する算出手段と、▲３▼算出手段の算出した改善指標に基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断する判断手段と、▲４▼判断手段が打ち切りを判断しない場合に、上述の性質を持つ目的関数から導出される値を使って、最適な配置に向かうようにとノードの埋め込み位置を更新する更新手段とを備える。
【００４２】
このように構成されるときにあって、算出手段は、各ノードについて、他のノードを固定してそのノードを移動させたときの勾配ベクトルの大きさを改善指標として算出することがある。
【００４３】
このとき、算出手段は、前回算出した勾配ベクトルと更新手段による埋め込み位置の更新量とに基づいて今回算出する勾配ベクトルを算出できることになるノードについては、それらに基づいて今回算出する勾配ベクトルを算出し、その大きさを算出することにより改善指標を算出することがある。
【００４４】
また、このように構成されるときにあって、算出手段の算出した改善指標が最も大きな値を示すノードを選択することで、埋め込み位置の更新対象となるノードを１つ選択する選択手段を備えることがある。
【００４５】
この選択手段を備えるときには、判断手段は、選択手段の選択したノードについての改善指標の大きさに基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断することがある。
【００４６】
以上の各処理手段が動作することで実現される本発明のネットワークデータ低次元埋込方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどの記録媒体に記録して提供したり、ネットワークを介して提供することができる。
【００４７】
このように構成される本発明のネットワークデータ低次元埋込装置では、全ノードの埋め込み位置の初期値をランダムに設定すると、上述の性質を持つ目的関数を用い、その設定した初期値を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する。
【００４８】
そして、その算出した改善指標に基づいて、ノードの埋め込み位置の更新を打ち切るのか否かを判断して、打ち切りを判断しない場合には、上述の性質を持つ目的関数から導出される値を使って最適な配置に向かうノードの埋め込み位置を算出し、それに基づいて、最適な配置に向かうようにとノードの埋め込み位置を更新する。
【００４９】
そして、上述の性質を持つ目的関数を用い、その更新したノードの埋め込み位置の処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出する。
【００５０】
このようにして、上述の性質を持つ目的関数を用い、初期値を起点として順次更新される各ノードの埋め込み位置を処理対象として、最適な配置に向けての各ノードの埋め込み位置の改善指標を算出することを繰り返していくことで、最適な配置に向かうようにとノードの埋め込み位置を更新していくときに、算出した改善指標に基づいて、ノードの埋め込み位置の更新を打ち切ることを判断する場合には、その時点で得られた各ノードの埋め込み位置を最終結果として出力する。
【００５１】
このように、本発明では、各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置されるようにと、各ノードの埋め込み位置を決定することから、よりブラウジングに適したネットワークデータの低次元空間への埋め込みを実現できるようになる。
【００５２】
【発明の実施の形態】
次に、本発明の実施の形態について、図面を参照して説明する。
【００５３】
図１に、本発明を具備するネットワークデータ低次元埋込装置１の一実施形態例を図示する。
【００５４】
この図に示すように、本発明のネットワークデータ低次元埋込装置１は、ネットワークデータ・データベース２に格納されるネットワークデータを処理対象として、処理対象のネットワークデータを低次元のユークリッド空間に埋め込むという処理を行うものであって、この埋め込み処理を実現するために、埋め込み配置初期化部１０と、勾配ベクトル初期化部１１と、移動ノード選択部１２と、変分ベクトル計算部１３と、勾配ベクトル更新部１４と、埋め込み配置更新部１５と、作業用メモリ部１６とを備える。
【００５５】
ここで、作業用メモリ部１６は、各ノードの配置座標ｘ１，ｘ２，・・・  ，ｘＮ  の途中結果や最終結果などを一時的に格納するために用意される。
【００５６】
図２に、このように構成される本発明のネットワークデータ低次元埋込装置１の動作を示すフローチャートを図示する。
【００５７】
次に、このフローチャートに従って、このように構成される本発明のネットワークデータ低次元埋込装置１の処理について詳細に説明する。
【００５８】
本発明のネットワークデータ低次元埋込装置１では、まず、ネットワークデータ・データベース２から、ノード数Ｎ、Ｎ×Ｎの大きさを持つ隣接行列Ａ＝（ａｉ，ｊ  ）、埋め込みの次元Ｋ、正則化のための定数μ、終了条件を決めるための収束精度定数εを埋め込み配置初期化部１０に入力する（ステップ２０）。
【００５９】
ここで、μ，εについては、例えばμ，εともに、μ，ε∈［１０−８，１０−４］の範囲に設定すればよい。
【００６０】
次に、埋め込み配置初期化部１０において、ｔ＝１とするとともに、全てのノードについての埋め込み配置、すなわち各ノードの配置座標ｘ１，ｘ２，・・・  ，ｘＮ  の初期値をランダムに設定する（ステップ２１）。
【００６１】
次に、勾配ベクトル初期化部１１において、各ノードｉについて、上述の式（５）で定義される目的関数Ｊのｘｉ  に関する勾配ベクトルＪｘｉを下記の式（６）によって計算する（ステップ２２）。
【００６２】
【数６】
2004318739.tif 000008
【００６３】
但し、上述の式（４）を微分することによって、Ｅｉ，ｊ  の微分∂Ｅｉ，ｊ  は下記の式（７）で計算できる。
【００６４】
【数７】
2004318739.tif 000009
【００６５】
次に、移動ノード選択部１２において、下記の式（８）に従って、勾配ベクトルの二乗ノルム‖Ｊｘｊ（ｔ）  ‖２  が最大となるノードｉを選択する（ステップ２３）。なお、以下では、勾配ベクトルの二乗ノルムを勾配ノルムと呼ぶことがある。
【００６６】
【数８】
2004318739.tif 000010
【００６７】
次に、ステップ２３で選ばれたノードｉに関する勾配ノルム‖Ｊｘｉ（ｔ）  ‖２  が収束精度定数εより小さいかどうかをチェックして（ステップ２４）、勾配ノルム‖Ｊｘｉ（ｔ）  ‖２  が収束精度定数εより小さい場合には、すでに収束したと見なして、現在の埋め込み配置ｘ１，ｘ２，・・・  ，ｘＮ  を出力して（ステップ２８）、処理を終了する。
【００６８】
一方、勾配ノルム‖Ｊｘｉ（ｔ）  ‖２  が収束精度定数εより小さくない場合には、ステップ２５に進んで、変分ベクトル計算部１３において、ノードｉの新たな配置座標を求めるべく、ノードｉの変分ベクトルΔｘｉ  をヘッシアン行列Ｈを用いて下記の式（９）により計算する（但し、ｘの転置行列をｘ’で表す）。
【００６９】
【数９】
2004318739.tif 000011
【００７０】
しかし、Ｈは必ずしも正定値とは限らないため、「Ｊ（ｔ＋１）  ＜Ｊ（ｔ）  」が常に成り立つとは限らない。
【００７１】
そこで、式（９）を適用した結果、「ΔＪ＝Ｊ（ｔ＋１）  −Ｊ（ｔ）  ＞０」となったのか否かを検査して、「ΔＪ＝Ｊ（ｔ＋１）  −Ｊ（ｔ）  ＞０」となった場合には、式（９）の適用をやめ、その代りに下記の式（１０）を用いる。
【００７２】
【数１０】
2004318739.tif 000012
【００７３】
但し、ステップ長λは「Ｊ（ｔ＋１）  ＜Ｊ（ｔ）  」となるように選ぶ。Ｊｘｉ（ｔ）  は勾配方向であるので、十分小さいλを選べば目的関数であるＪが常に減少するようにできる。こうすることによってアルゴリズムは収束が保証される。
【００７４】
ここで、式（９）を式（１０）よりも優先させる形でノードｉの変分ベクトルΔｘｉ  を計算するのは、式（９）で得られる変分ベクトルΔｘｉ  の方が大きい値をとることで、計算効率を上げることができるからである。
【００７５】
また、ノードｉの配置座標のみが変更し、それ以外のノードについては配置座標が変更しないことで、それ以外のノード間に係る（ｔ＋１）におけるＪの値とｔにおけるＪの値との間に変化がないことを考慮して、ΔＪについては、下記の式（１１）に従って、ノードｉに関連する差分だけ計算することによってＯ（Ｎ）（Ｎのオーダの計算量）で計算できることになる。なお、式（９）の代りに式（１０）を用いるという状況はたまにしか起らないため、あまり計算上の負担にはならない。
【００７６】
【数１１】
2004318739.tif 000013
【００７７】
次に、勾配ベクトル更新部１４において、Ｊｘｊ（ｔ）  を用いてＪｘｊ（ｔ＋１）  を更新する（ステップ２６）。
【００７８】
この更新処理について説明するならば、目的関数Ｊのｘｊ  に関する勾配ベクトルＪｘｊは、式（５）に基づいて下記の式（１２）により計算される。
【００７９】
【数１２】
2004318739.tif 000014
【００８０】
一方、Ｊｘｊ（ｔ＋１）  とＪｘｊ（ｔ）  との間には、
Ｊｘｊ（ｔ＋１）  ＝Ｊｘｊ（ｔ）  ＋ΔＪｘｊ
という関係式が成り立つことから、この式（１２）に基づいて下記の式（１３）の関係式が成り立つ。
【００８１】
【数１３】
2004318739.tif 000015
【００８２】
ここで、ノードｉの配置座標のみが変更し、それ以外のノードについては配置座標が変更しないことから、ｈ≠ｉ，ｊとして、下記の式（１４）という関係式が成り立つ。
【００８３】
【数１４】
2004318739.tif 000016
【００８４】
従って、Ｊｘｊ（ｔ＋１）  とＪｘｊ（ｔ）  との間には、この式（１４）と式（１３）とに基づいて下記の式（１５）の関係式が成り立つ。
【００８５】
【数１５】
2004318739.tif 000017
【００８６】
ここで、式（４）と式（７）とから分かるように、下記の式（１６）という関係式が成り立つ。
【００８７】
【数１６】
2004318739.tif 000018
【００８８】
従って、この式（１６）と式（１５）とに基づいて、Ｊｘｊ（ｔ＋１）  とＪｘｊ（ｔ）  との間には下記の式（１７）が成り立つ。
【００８９】
【数１７】
2004318739.tif 000019
【００９０】
これから、ステップ２６では、この式（１７）基づいて、Ｊｘｊ（ｔ）  を用いてＪｘｊ（ｔ＋１）  を更新するのである。従って、Ｊｘｊの更新はＯ（Ｎ）（Ｎのオーダの計算量）で計算できることになる。
【００９１】
なお、Ｊｘｉ（ｔ＋１）  については、ノードｉの配置座標が変更することでＪｘｉ（ｔ）  から求めることができないので、式（６）に従って最初から計算することになる。
【００９２】
次に、ステップ２７で、埋め込み配置更新部１５において、変分ベクトル計算部１３で計算したノードｉの変分ベクトルΔｘｉ  に基づいて、各ノードの配置座標ｘ１，ｘ２，・・・  ，ｘＮ  の更新するとともに、ｔ＝ｔ＋１としてから、移動ノード選択部１２（ステップ２３）の処理に戻る。
【００９３】
このようにして、本発明のネットワークデータ低次元埋込装置１は、式（２）に示すようなクロスエントロピーに基づく目的関数を最小化するという方法を用いることによって、各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置されるようにと、各ノードの埋め込み位置を決定するように処理するのである。
【００９４】
次に、実データを利用した実験によって本発明の有効性を示す。
【００９５】
（イ）実験に用いたデータ
本発明の有効性を検証すべく、実データから構成した３種類の異なるタイプのネットワークを用いた実験を行った。
【００９６】
生物学に由来する第一のネットワークは、大腸菌（Ｅｓｃｈｅｒｉｃｈｉａ  ｃｏｌｉ）の遺伝子制御ネットワークであり、文献「Ｓｈｅｎ−Ｏｒｒ，Ｓ．Ｓ．，  Ｍｉｌｏ，Ｒ．，  Ｍａｎｇａｎ，Ｓ．  ＆  Ａｌｏｎ，Ｕ．”Ｎｅｔｗｏｒｋ  ｍｏｔｉｆｓ  ｉｎ  ｔｈｅ  Ｔｒａｎｓｃｒｉｐｔｉｏｎａｌ  Ｒｅｇｕｌａｔｉｏｎ  Ｎｅｔｗｏｒｋ  ｏｆ  Ｅｓｃｈｅｒｉｃｈｉａ  Ｃｏｌｉ”，Ｎａｔｕｒｅ  Ｇｅｎｅｔｉｃｓ  Ｖｏｌｕｍｅ，３１，Ｎｏ．１，６４−６８，２００２．  」に由来する。
【００９７】
第二のネットワークは、国際会議ＮＩＰＳ（Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ）の第１回から第１２回までに発表された論文の共著者ネットワークであり、「Ｒｏｗｅｉｓ，Ｓ．Ｔ．”Ｄａｔａ  ｆｏｒ  ＭＡＴＬＡＢ  ｈａｃｋｅｒｓ：  ＮＩＰＳ  ｃｏｎｆｅｒｅｎｃｅ  ｐａｐｅｒｓ  Ｖｏｌｓ  ０−１２．”，ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｔｏｒｏｎｔｏ．ｅｄｕ／ｒｏｗｅｉｓ／ｄａｔａ．ｈｔｍｌ，２００２．」より入手した。この第二のネットワークでは、各著者をノードとし、二人の著者が少なくとも一つの共著論文を発表すればその著者間にリンクを張ることで構成される。
【００９８】
第三のネットワークは、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）のハイパーリンクネットワークであり、本出願人のサイトに属するＷＷＷページをすべて収集して構成した。
【００９９】
本発明の有効性を検証するために、これらのネットワークをまず無向ネットワークに変換し、さらに最大連結成分のみを抜き出したものを用いた。通常このように各連結成分を別々に計算するのが自然である。
【０１００】
図３に、これら抜き出したネットワークに関する統計量を示す。ここで、ノード数をＮとし、ＬＴ  、ＬＡ  、ＬＭ  は、それぞれ各ネットワークの合計リンク数、平均リンク数、最大リンク数を表す。Ｌｉ  をノードｉと直接繋がっているリンク数とすると、これらの間には、下記の式（１８）の関係式が成り立つ。
【０１０１】
【数１８】
2004318739.tif 000020
【０１０２】
次に、ＧＡ  およびＧＭ  を定義する。ＧＡ  、ＧＭ  は、各ネットワークにおける任意の２ノード間のグラフ距離のそれぞれ平均値、最大値を表す。ｇｉ，ｊ  をノードｉとｊとの間のグラフ論的距離とすると、下記の式（１９）の関係式が成り立つ。
【０１０３】
【数１９】
2004318739.tif 000021
【０１０４】
これらのネットワークの隣接行列はすべて疎行列という点では共通しているが、各統計量についてはそれぞれ異なる特徴を持つことがわかる。また、第三のネットワークは、第一のネットワーク、第二のネットワークに比べてサイズが特に大きく複雑なネットワークである。
【０１０５】
（ロ）評価尺度
本発明の有効性をはかるためには、以下のような適切な評価尺度が必要である。
【０１０６】
今、ＮノードからなるＫ次元ユークリッド空間への埋め込みが得られたとし、その配置座標をｘ１，ｘ２，・・・  ，ｘＮ  とする。
【０１０７】
そこで、各ｘｉ  を中心とし、半径ｒｉ  のＫ次元球体Ｂｉ  （ｒｉ  ）を考える。〔原則Ａ〕を完全に実現する理想的な埋め込みでは、各ノードｉにおいて適切な半径ｒｉ  を選ぶことによって、ｉに隣接する（直接リンクで繋がっている）ノードをすべて含み、逆に、ｉに隣接しないノードについては全く含まないようなＢｉ  （ｒｉ  ）を構成できるはずである。
【０１０８】
しかしながら、実際の埋め込みでは、特に次元Ｋが小さく複雑なネットワークの場合には、すべてのノードｉでそのようなｒｉ  を選ぶことは一般に不可能である。しかるに、適切な尺度のもとで最適なｒｉ  を考えることはできるはずである。
【０１０９】
特に、疎なネットワークの場合には、隣接するノードに比べて隣接しないノード数が圧倒的に多いため、Ｂｉ  （ｒｉ  ）に正しく含まれるノードの個数およびＢｉ  （ｒｉ  ）から正しく除外されるノードの個数の合計を考える通常の「精度」（ａｃｃｕｒａｃｙ）を尺度として用いるのは適切ではない。何故なら、隣接するかどうかに関わらず、すべてのノードが全くＢｉ  （ｒｉ  ）に含まれない場合でも、精度は高くなるからである。このような場合では、Ｆ−尺度を用いるのが適切である。Ｆ−尺度は情報検索やテキスト分類などの分野で広く用いられる尺度である。
【０１１０】
Ｆ−尺度は、「適合率」（ｐｒｅｃｉｓｉｏｎ）と「再現率」（ｒｅｃａｌｌ）との調和平均で定義される。今、＃Ｘで集合Ｘの要素の個数を表すことにすると、ｘｉ  とｒｉ  に対応するｉ番目の球体Ｂｉ  （ｒｉ  ）の適合率Ｐｉ  （ｒｉ  ）は下記の式（２０）のように定義される。
【０１１１】
【数２０】
2004318739.tif 000022
【０１１２】
同様にして、ｘｉ  とｒｉ  に対応するｉ番目の球体Ｂｉ  （ｒｉ  ）の再現率Ｒｉ  （ｒｉ  ）は下記の式（２１）のように定義される。
【０１１３】
【数２１】
2004318739.tif 000023
【０１１４】
おおざっぱに言うと、適合率を高くするためにはｒｉ  を小さくする必要があり、逆に、再現率を高くするためにはｒｉ  を大きくする必要があるので、最適なｒｉ  は両者のバランスで決まる。より厳密には、最適な半径＜ｒｉ  ＞は、下記の式（２２）で定義されるＦ−尺度を最大にするものとして定義できる。但し、実験では常にα＝１／２を用いる。
【０１１５】
【数２２】
2004318739.tif 000024
【０１１６】
この式（２２）をすべてのノードについて平均することによって、低次元に埋め込まれたネットワークの配置を定量的に評価する尺度である「接続Ｆ−尺度」（ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｆ−ｍｅａｓｕｒｅ）を下記の式（２３）のように定義する。
【０１１７】
【数２３】
2004318739.tif 000025
【０１１８】
本発明の有効性を検証するために行って実験では、この式（２３）で定義される「接続Ｆ−尺度」を評価尺度として用いた。
【０１１９】
（ハ）接続Ｆ−尺度を用いた比較
本発明の提案法ならびに、古典的な多次元尺度法、バネモデル、スペクトラルクラスタリングの３つの既存法を上に述べた３種類のネットワークにそれぞれ適用し、Ｋ次元空間への埋め込みを得た。さらに、その結果を接続Ｆ−尺度を用いて評価した。Ｋの値については、第一のネットワークについては２から２５まで、第二のネットワークと第三のネットワークとについては２から９までそれぞれ変化させて実験した。
【０１２０】
図４に、評価結果のグラフを示す。ここで、縦軸は接続Ｆ−尺度の値を表し、横軸は埋め込んだ次元Ｋを表す。図中の記号はそれぞれ、ＣＥ：本発明の提案法、ＣＭＤＳ：古典的な多次元尺度法、ＫＫ：バネモデル、ＳＣ：スペクトラルクラスタリングを意味する。
【０１２１】
接続Ｆ−尺度が高いほうがより優れた解法である。なお、本発明の提案法およびバネモデルについては、局所解の問題があるため乱数の初期値を変えて５回行った結果を表示しているが、結果を見る限り、結果のばらつきはほとんどなく、局所解の影響は無視できることがわかる。各手法とも、次元数Ｋを増加し、埋め込みの自由度が増すと単調に性能が向上することがわかる。
【０１２２】
この図４から分かるように、期待どおり、本発明の提案法が他の手法に比べて、特に配置が難しい低次元において、優れていることが分かる。中でも、もつともサイズの大きい第三のネットワークを用いた実験において、本発明の提案法と従来法の性能差が際立っていることが分かる。
【０１２３】
（ニ）２次元への埋め込み結果
図５（ａ）〜（ｃ）のそれぞれ左側に、古典ＭＤＳ（ＣＭＤＳ）、バネモデル（ＫＫ）、本発明の提案法（ＣＥ）による第三のネットワークの実際の２次元への埋め込み結果を示す。スペクトラククラスタリングについては３次元球面上の配置となるため省略した。
【０１２４】
図５（ａ）に示す古典的な多次元尺度法の結果は、多くのノードが一点に縮退してしまっているため、可視化、特にブラウジングの観点では問題がある。これは線型手法の限界と考えられる。
【０１２５】
一方、図５（ｂ）に示すバネモデルと、図５（ｃ）に示す本発明の提案法とは、このノード縮退が少ない。さらにこれらを注意深く見ると、前者では多くのノードが半円状にかたまって配置されているのに対し、後者ではより一様に放射状に広がっている。本発明の提案法のほうが空間をより効率的に活用していることがわかり、ここに両者の接続Ｆ−尺度の性能差が現れているとも言える。これは、前者のバネモデルが復元しようとするグラフ距離が、離散的な値のみをとるからと考えられる。バネモデルの結果は、特にノードが密集した領域において、ブラウジングを難しくしている。
【０１２６】
図５（ａ）〜（ｃ）のそれぞれの左側の図において、点線で囲まれた領域を切り出し、この部分のみ再計算して埋め込んだのがそれぞれの右側の図である。切り出し前後を含む、合計６つの点線で囲まれた領域は、すべて同一のサブネットワークに対応している。
【０１２７】
この図から容易に分かるように、古典的な多次元尺度法、バネモデルにおいては、この切り出しの前後において、配置がかなり変化しているのに対し、本発明の提案法では比較的変化が少ない。従って、より切り出し安定性が高い、と考えられる。このことから考えても、本発明の提案法はよりブラウジングに適した埋め込み方法である、と言うことができる。
【０１２８】
【発明の効果】
以上説明したように、本発明は、複数のノードとノード間を結ぶリンクとからなるネットワークで表現されたデータを２次元や３次元の低次元ユークリッド空間に埋め込むことにより視覚的に表現できるようにするときにあって、クロスエントロピーに基づく目的関数を最小化するという方法を用いることによって、各ノードについて自ノードと直接リンクで繋がっているノードの方が直接リンクで繋がっていないノードよりも近くに配置されるようにと、各ノードの埋め込み位置を決定するように処理することから、従来法に比べてより空間効率を生かしたブラウジングに適した埋め込みを実現できるようになる。
【図面の簡単な説明】
【図１】本発明のネットワークデータ低次元埋込装置の一実施形態例である。
【図２】本発明のネットワークデータ低次元埋込装置の動作を示すフローチャートである。
【図３】本発明の有効性を検証するために行った実験に用いたネットワークに関する統計量の説明図である。
【図４】本発明の有効性を検証するために行った実験の評価結果を示すグラフである。
【図５】本発明の有効性を検証するために行った実験における２次元空間への埋め込み結果の説明図である。
【符号の説明】
１    ネットワークデータ低次元埋込装置
２    ネットワークデータ・データベース
１０  埋め込み配置初期化部
１１  勾配ベクトル初期化部
１２  移動ノード選択部
１３  変分ベクトル計算部
１４  勾配ベクトル更新部
１５  埋め込み配置更新部
【図１】
2004318739.tif 000026
【図２】
2004318739.tif 000027
【図３】
2004318739.tif 000028
【図４】
2004318739.tif 000029
【図５】
2004318739.tif 000030