JP2019091257A - 情報処理装置、情報処理方法及びプログラム - Google Patents

Abstract

【課題】複雑ネットワークに対するグラフトラバーサルに要する時間を短縮する。【解決手段】本情報処理方法は、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。【選択図】図４

Description

本発明は、グラフ処理技術に関する。

複雑ネットワークは、頂点間の接続パターンが純粋な規則性を有するわけではなく且つ純粋なランダム性を有するわけでもないネットワークである。図１は、複雑ネットワークの一例を示す図である。図１において、円は頂点を表し、頂点間の線分はエッジを表す。例えばソーシャルネットワークやナレッジグラフなど、現実世界における巨大で複雑なネットワークの中には複雑ネットワークの性質を有するネットワークがある。

複雑ネットワークはスケールフリーネットワークであることが知られている。スケールフリーネットワークとは次数分布がべき乗則に従うネットワークであり、次数とは頂点のエッジ数のことである。スケールフリーネットワークには、ハブ或いはハブノードと呼ばれる、極めて次数が大きい頂点がごく少数（例えば１％程度）存在する。一方で、多くの（例えば５０％程度の）頂点は１又は２といったごく少数のエッジを有する。ハブのエッジ数の合計が複雑ネットワークにおける全エッジ数のおよそ半数に達することがあり、このような場合、或る頂点の次に到達する頂点はおおよそ５０％の確率でハブである。

特開２０１６−１８９２１４号公報 特開平２−２５３４７８号公報 特表２０１３−５１９１４０号公報

グラフトラバーサルとはグラフ処理の一種であり、経路の探索等を目的としてグラフにおける頂点を辿る処理である。ハブに関する上記のような性質から、複雑ネットワークに対してグラフトラバーサルを実行すると経路がハブを経由する確率が高い。経路がハブを経由する場合、経路の組合せ爆発により記憶装置に対するランダムアクセス（具体的には、ランダムリード）の回数が増大するため処理時間が長くなるという問題が有る。上で述べたように、複雑ネットワークによってはおよそ半数のエッジが１つのハブに接続することがあるため、特に、ハブから出た複数の経路が再びハブを経由するパターンが原因となり処理時間が長くなりやすい。グラフ処理に関する従来技術は、このような問題の解決には適していない。

本発明の目的は、１つの側面では、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮するための技術を提供することである。

一態様に係る情報処理方法は、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。

１つの側面では、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮できるようになる。

図１は、複雑ネットワークの一例を示す図である。 図２は、情報処理装置の機能ブロック図である。 図３は、本実施の形態におけるグループ化について説明するための図である。 図４は、本実施の形態におけるグループ化について説明するための図である。 図５は、本実施の形態におけるグループ化について説明するための図である。 図６は、本実施の形態におけるグループ化について説明するための図である。 図７は、第１ＫＶＳに格納されるデータの一例を示す図である。 図８Ａは、第２ＫＶＳに格納されるデータの一例を示す図である。 図８Ｂは、第２ＫＶＳに格納されるデータの一例を示す図である。 図９は、グループ化部が実行する処理の処理フローを示す図である。 図１０は、第１の実施の形態におけるトラバーサル処理部が実行する処理の処理フローを示す図である。 図１１は、第１の実施の形態におけるトラバーサル処理部が実行する処理の処理フローを示す図である。 図１２は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１３は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１４は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１５は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１６は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１７は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１８は、第１の実施の形態のグラフトラバーサルについて説明するための図である。 図１９は、本実施の形態におけるグループ化について説明するための図である。 図２０は、本実施の形態におけるグループ化について説明するための図である。 図２１は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。 図２２は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。 図２３は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。 図２４は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。 図２５は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。 図２６は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。 図２７は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。 図２８は、コンピュータの機能ブロック図である。

［実施の形態１］
本実施の形態における情報処理装置１は、複雑ネットワークについてのグラフ処理を実行するパーソナルコンピュータ或いはサーバ等の装置である。情報処理装置１は、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介してグラフトラバーサルのクエリ（以下、トラバーサルクエリと呼ぶ）を受信し、受信したトラバーサルクエリに応じてグラフトラバーサルを実行し、グラフトラバーサルの結果を出力する。

図２は、情報処理装置１の機能ブロック図である。情報処理装置１は、ネットワーク管理部１０１と、グループ化部１０３と、トラバーサル処理部１０５と、第１ＫＶＳ（Key-Value Store）１１１と、第２ＫＶＳ１１３と、出力データ格納部１１５とを含む。

ネットワーク管理部１０１、グループ化部１０３及びトラバーサル処理部１０５は、例えば図２８におけるＳＳＤ（Solid State Drive）２５０５に格納されたプログラムがメモリ２５０１に読み出されてＣＰＵ（Central Processing Unit）２５０３により実行されることで実現される。第１ＫＶＳ１１１、第２ＫＶＳ１１３及び出力データ格納部１１５は、例えばＳＳＤ２５０５に設けられる。

ネットワーク管理部１０１は、複雑ネットワークにおける各頂点に隣接する頂点の情報を第１ＫＶＳ１１１において管理する。複雑ネットワークのトポロジが変更された場合、ネットワーク管理部１０１は第１ＫＶＳ１１１に格納されているデータを更新する。なお、「隣接」とは頂点が他の頂点に１ホップで接続されることを意味する。以下では、或る頂点又はグループに隣接する頂点のことを「隣接頂点」とも呼ぶ。また、或る頂点に隣接するグループのことを「隣接グループ」とも呼ぶ。

グループ化部１０３は、第１ＫＶＳ１１１に格納されたデータに基づきハブを抽出し、抽出されたハブの隣接頂点をグループ化する。グループ化部１０３は、グループ化の結果を第２ＫＶＳ１１３に格納する。

トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されたデータ及び第２ＫＶＳ１１３に格納されたデータに基づき、複雑ネットワークに対するグラフトラバーサルを実行し、グラフトラバーサルの結果を出力データ格納部１１５に格納する。

ここで、本実施の形態におけるグループ化の概要を説明する。一例として、図３に示すような複雑ネットワークを考える。図３には無向グラフが示されており、円は頂点を表し、頂点間の線分はエッジを表す。図３においては次数が５以上である頂点がハブであるので、頂点Ａ、頂点Ｂ及び頂点Ｃがハブである。頂点Ａ、頂点Ｂ及び頂点Ｃはハッチングされている。なお、実際の複雑ネットワークは図３に示すようなネットワークより複雑である場合が多いが、説明を簡単にするためここでは単純な例が示されている。

図４は、ハブＡの隣接頂点をグループ分けした結果を示す図である。ハブＡの隣接頂点は頂点ａ、頂点ｂ、頂点ｃ、頂点ｄ、頂点ｅ、頂点ｌ、頂点ｍ、頂点ｎ、頂点ｏ及びハブである頂点Ｂである。本実施の形態においては、（１）隣接するハブの組み合わせが同じである頂点が同じグループに属するという条件、及び（２）ハブはグループには属さないという条件が満たされるようにグループ化が実行される。これらのルールに従うと、図４に示すようにグループ化が行われる。頂点ａ、頂点ｂ及び頂点ｃはハブＡに隣接するのでグループＧＡ１に属し、頂点ｄ及び頂点ｅはハブＡ及びハブＢに隣接するのでグループＧＡ２に属し、頂点ｌ及び頂点ｍはハブＡ及びハブＣに隣接するのでグループＧＡ３に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでＧＡ４に属する。ハブである頂点Ｂはいずれのグループにも属さない。

図５は、ハブＢの隣接頂点をグループ分けした結果を示す図である。ハブＢの隣接頂点はハブである頂点Ａ、ハブである頂点Ｃ、頂点ｇ、頂点ｑ、頂点ｄ、頂点ｅ、頂点ｎ及び頂点ｏである。上記のルールに従うと、図５に示すようにグループ化が行われる。頂点ｇ及び頂点ｑはハブＢに隣接するのでグループＧＢ１に属し、頂点ｄ及び頂点ｅはハブＡ及びハブＢに隣接するのでグループＧＢ２に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでＧＢ３に属する。ハブである頂点Ａ及びハブである頂点Ｃはいずれのグループにも属さない。

図６は、ハブＣの隣接頂点をグループ分けした結果を示す図である。ハブＣの隣接頂点は、ハブである頂点Ｂ、頂点ｆ、頂点ｒ、頂点ｌ、頂点ｍ、頂点ｎ及び頂点ｏである。上記のルールに従うと、図６に示すようにグループ化が行われる。頂点ｆ及び頂点ｒはハブＣに隣接するのでグループＧＣ１に属し、頂点ｌ及び頂点ｍはハブＡ及びハブＣに隣接するのでＧＣ２に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでグループＧＣ３に属する。ハブである頂点Ｂはいずれのグループにも属さない。

図７は、第１ＫＶＳ１１１に格納されるデータの一例を示す図である。図７の例では、頂点の識別情報（キー）と、その頂点の隣接頂点の識別情報（バリュー）とが格納される。エントリは、複雑ネットワークにおける全頂点（ハブを含む）について生成される。

図８Ａ及び図８Ｂは、第２ＫＶＳ１１３に格納されるデータの一例を示す図である。図８Ａ及び図８Ｂには、図４に示したハブＡについて格納されるデータの一例が示されている。図８Ａの例では、ハブの識別情報（キー）と、当該ハブの隣接グループの識別情報及び隣接頂点の識別情報（バリュー）とが格納される。図８Ｂの例では、グループの識別情報（キー）と、当該グループ内の頂点の識別情報及びその隣接頂点の識別情報並びにグループ内の全頂点が隣接するハブの識別情報（バリュー）とが格納される。

なお、図８Ａ及び図８Ｂに示したデータは、全ハブについて生成される。

次に、情報処理装置１が実行する処理を詳細に説明する。

図９は、情報処理装置１のグループ化部１０３が実行する処理の処理フローを示す図である。本処理は、例えば、第１ＫＶＳ１１１に格納されているデータが更新された場合、又は、ユーザからの指示に応じて実行される。

グループ化部１０３は、第１ＫＶＳ１１１に格納されているデータに基づき、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出する（図９：ステップＳ１）。

ステップＳ１における所定数は、例えば、（１）ＳＳＤ２５０５に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、（２）複雑ネットワークにおける頂点のうちエッジ数の多さが第Ｎ位（Ｎは自然数）である頂点のエッジ数である。（１）については、例えば１回のランダムアクセスに要する時間が１０マイクロ秒であり且つ１の頂点につき許容される処理時間が１秒（＝１００００００マイクロ秒）である場合、１０００００（＝１００００００／１０）が所定数である。（２）については、例えばＮが１３であり且つ第１３位の頂点のエッジ数が５００００００である場合、所定数は５００００００である。但し、（１）又は（２）以外の数を所定数としてもよい。

グループ化部１０３は、ステップＳ１において抽出されたハブのうち未処理のハブを１つ特定する（ステップＳ３）。以下では、ステップＳ３において特定されたハブをハブｈと呼ぶ。

グループ化部１０３は、第１ＫＶＳ１１１から、ハブｈに対応付けられている隣接頂点を抽出する。（ステップＳ５）。

グループ化部１０３は、ステップＳ５において抽出された隣接頂点を、当該隣接頂点に隣接するハブの組み合わせに基づきグループ化する（ステップＳ７）。グループ化の方法については、図３乃至図６を用いて説明したとおりである。

グループ化部１０３は、ハブｈの識別情報に対応付けて、隣接グループの識別情報及び隣接頂点の識別情報を第２ＫＶＳ１１３に格納する（ステップＳ９）。

グループ化部１０３は、ハブｈの各隣接グループの識別情報に対応付けて、当該グループに属する頂点の識別情報と当該頂点の隣接頂点の識別情報と当該グループ内の全頂点が隣接するハブの識別情報とを第２ＫＶＳ１１３に格納する（ステップＳ１１）。

グループ化部１０３は、ステップＳ１において抽出されたハブのうち未処理のハブが有るか判定する（ステップＳ１３）。

未処理のハブが有る場合（ステップＳ１３：Ｙｅｓルート）、処理はステップＳ３に戻る。一方、未処理のハブが無い場合（ステップＳ１３：Ｎｏルート）、処理は終了する。

以上のような処理を実行すれば、本実施の形態のグラフトラバーサルにおいて使用される第２ＫＶＳ１１３のデータを用意できるようになる。

図１０は、第１の実施の形態におけるトラバーサル処理部１０５が実行する処理の処理フローを示す図である。本処理は、トラバーサルクエリを受信又は受け付けた場合に実行される。

トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図１０：ステップＳ２１）。

本実施の形態において、グラフトラバーサルの経路はリストで表現される。例えば頂点ａ、頂点ｂ、頂点ｃの順に探索された場合、経路は［ａ，ｂ，ｃ］と表現される。Ｑは一時的に使用されるキューであり、Ｒは結果を格納するためのキューである。Ｑ及びＲは、例えばメモリ２５０１に格納される。また、グラフトラバーサルの始点である頂点をｎ０とする。ｎ０のみで構成される経路をＴ０とする。つまりＴ０＝［ｎ０］である。

トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ２３）。

経路集合Ｑが空である場合（ステップＳ２３：Ｙｅｓルート）、処理はステップＳ２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ２５）。探索終了条件はトラバーサルクエリに含まれており、経路が所定個以上見つかったという条件やグラフトラバーサルのホップ数が所定の閾値を超えたという条件等である。

探索終了条件が満たされない場合（ステップＳ２５：Ｎｏルート）、処理は端子Ａを介して図１１のステップＳ３３の処理に移行する。

図１１の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図１１：ステップＳ３３）。以下では、ステップＳ３３において取り出された経路を経路Ｔと呼ぶ。

トラバーサル処理部１０５は、経路Ｔが探索条件を満たさないか判定する（ステップＳ３５）。ステップＳ３５の処理時点においてはグループが展開されていないため、経路Ｔにはグループが含まれる可能性がある。但し、たとえ経路Ｔにグループが含まれていたとしても経路Ｔが明らかに探索条件を満たさないと判定可能なことがあり、このような場合には経路Ｔは選択肢から除外される。なお、探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件等である。

経路Ｔが探索条件を満たさない場合（ステップＳ３５：Ｙｅｓルート）、処理はステップＳ４１に移行する。

一方、経路Ｔが探索条件を満たす場合（ステップＳ３５：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔがフィルタ条件Ｆを満たさないか判定する（ステップＳ３７）。ステップＳ３７の処理時点においてはグループが展開されていないため、経路Ｔにはグループが含まれる可能性がある。但し、たとえ経路Ｔにグループが含まれていたとしても経路Ｔが明らかにフィルタ条件Ｆを満たさないと判定可能なことがあり、このような場合には経路Ｔは選択肢から除外される。フィルタ条件Ｆはトラバーサルクエリに含まれており、例えば、ホップ数が所定値以上であるという条件や或る頂点を経由するという条件等である。

経路Ｔがフィルタ条件Ｆを満たさない場合（ステップＳ３７：Ｙｅｓルート）、処理はステップＳ４１に移行する。一方、経路Ｔがフィルタ条件Ｆを満たす場合（ステップＳ３７：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ３９）。

トラバーサル処理部１０５は、経路Ｔの最後の要素ｅを特定する（ステップＳ４１）。要素ｅは、頂点又はグループである。例えば経路Ｔが［Ａ，Ｂ，ｃ］である場合、ステップＳ４１において特定される要素ｅは頂点ｃである。

トラバーサル処理部１０５は、要素ｅがグループであるか判定する（ステップＳ４３）。

要素ｅがグループである場合（ステップＳ４３：Ｙｅｓルート）、トラバーサル処理部１０５は、グループｅに隣接するハブのうち未訪問のハブの集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］を特定する（ステップＳ４５）。そして処理はステップＳ４９に移行する。ここで、未訪問であるハブとは経路Ｔに含まれないハブを意味する。以下においても同様とする。

上で述べたように、同じグループに属する頂点は同じハブに接続される。ステップＳ４５においては、ＳＳＤ２５０５に対する１回のランダムアクセスによってグループ内の各頂点に隣接するハブが一括して特定されることになるので、各頂点についてランダムアクセスを行わなくて済むようになる。これにより、ランダムアクセスの回数を減らし、グラフトラバーサルにかかる時間を短縮できるようになる。

一方、要素ｅがグループではない場合（ステップＳ４３：Ｎｏルート）、トラバーサル処理部１０５は、以下の処理を実行する。具体的には、トラバーサル処理部１０５は、頂点ｅの隣接頂点のうち未訪問の隣接頂点、及び、頂点ｅの隣接グループのうち未訪問のグループの集合を、Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］として特定する（ステップＳ４７）。

トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・のうちフィルタ条件Ｆを満たす経路を経路集合Ｑに追加する（ステップＳ４９）。そして処理は端子Ｂを介して図１０のステップＳ２３に戻る。

図１０の説明に戻り、探索終了条件が満たされる場合（ステップＳ２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路の各々について、当該経路に含まれるグループを第２ＫＶＳ１１３に格納されているデータを用いて展開することで経路集合Ｒｘを生成する（ステップＳ２７）。例えば経路が［ａ，Ａ，ＧＡ２］であり且つグループＧＡ２に頂点ｄ及び頂点ｅが含まれる場合、グループの展開により経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が生成される。ここで、展開により同じ頂点が２度以上訪問されることになった場合、経路は削除される。例えば展開により経路［ａ，Ａ，ｏ，Ｃ，ｏ］が生成された場合、頂点ｏが２回訪問されるので経路［ａ，Ａ，ｏ，Ｃ，ｏ］は削除される。

トラバーサル処理部１０５は、経路集合Ｒｘに含まれる経路のうち探索条件を満たし且つフィルタ条件Ｆを満たす経路を特定する（ステップＳ２９）。

トラバーサル処理部１０５は、ステップＳ２９において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ３１）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。

通常のグラフトラバーサルには、探索される頂点の数とランダムアクセスの回数とがほぼ一致するという特徴がある。これに対し、本実施の形態の方法においては、ハブに基づいて頂点がグループ化されており、複数の頂点に対して１回のランダムアクセスが実行される。これにより、経路がハブを経由する場合であっても、ランダムアクセスの回数の増加が原因となり処理時間が増大することを抑制できるようになる。複雑ネットワークによっては、処理時間の桁数を大幅に減らすことができる。

なお、通常のグラフトラバーサルの詳細については、付録を参照されたい。

また、第１の実施の形態においては、フィルタ条件Ｆを明らかに満たさない経路はステップＳ４９において経路集合Ｑに追加されない。従って、特にフィルタ条件Ｆの条件が厳しい場合には、フィルタ条件Ｆによって多くの経路が探索の対象から外されるようになるのでグラフトラバーサルにかかる時間を短縮できるようになる。

複雑ネットワークは疎な部分が占める割合が大きいにもかかわらず、疎な部分での処理によっては性能問題が発生しないため、複雑ネットワーク全体に対して前処理を実行すること及びインデックスを生成することは効率的ではない。本実施の形態においては、性能問題の原因であるハブに限定してグループ化を実行しており、効率的な対策が実現されている。

また、本実施の形態の方法は、オンメモリでの処理が困難である大規模グラフに対しても有効である。

ここで、本実施の形態の処理について具体例を用いて説明する。

第１の例として、探索条件が「ａを始点とし且つｋを終点とする経路」という条件であり、且つ、フィルタ条件Ｆが「ホップ数が３以下である」という条件であるケースについて説明する。

図１２は、経路集合Ｑに含まれる経路をホップ数毎に示す図である。

ホップ数が０である経路［ａ］は経路集合Ｑに追加される。但し、経路［ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が１である経路［ａ，Ａ］は経路集合Ｑに追加される。但し、経路［ａ，Ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が２である経路［ａ，Ａ，ＧＡ１］、経路［ａ，Ａ，ＧＡ２］、経路［ａ，Ａ，ＧＡ３］、経路［ａ，Ａ，ＧＡ４］及び経路［ａ，Ａ，Ｂ］は経路集合Ｑに追加される。これらの経路のうち経路［ａ，Ａ，Ｂ］は明らかに探索条件を満たさないので、経路［ａ，Ａ，Ｂ］以外の経路が経路集合Ｒに追加される。ホップ数が３である経路［ａ，Ａ，ＧＡ２，Ｂ］、経路［ａ，Ａ，ＧＡ３，Ｃ］、経路［ａ，Ａ，ＧＡ４，Ｂ］、経路［ａ，Ａ，ＧＡ４，Ｃ］、経路［ａ，Ａ，Ｂ，ＧＢ１］、経路［ａ，Ａ，Ｂ，ＧＢ２］、経路［ａ，Ａ，Ｂ，ＧＢ３］及び経路［ａ，Ａ，Ｂ，Ｃ］は経路集合Ｑに追加される。これらの経路のうち経路［ａ，Ａ，Ｂ，Ｃ］は明らかに探索条件を満たさないので、経路［ａ，Ａ，Ｂ，Ｃ］以外の経路が経路集合Ｒに追加される。

図１３は、経路集合Ｑに含まれる経路及び経路集合Ｒに含まれる経路のうちグループを含むものについて展開を実行した場合の結果を示す図である。なお、ホップ数が３以下であるという条件の下で展開後にさらに探索が実行されている。

経路［ａ，Ａ，ＧＡ１］におけるグループＧＡ１の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｃ］、経路［ａ，Ａ，ｃ，ｐ］、経路［ａ，Ａ，ｂ］、経路［ａ，Ａ，ｂ，ｊ］及び経路［ａ，Ａ，ｂ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ２］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が得られる。経路［ａ，Ａ，ＧＡ３］におけるグループＧＡ３の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｍ］、経路［ａ，Ａ，ｌ］及び経路［ａ，Ａ，ｌ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ４］におけるグループＧＡ４の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｎ］、経路［ａ，Ａ，ｏ］及び経路［ａ，Ａ，ｏ，ｋ］が得られる。

経路［ａ，Ａ，ＧＡ２，Ｂ］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ，Ｂ］及び経路［ａ，Ａ，ｅ，Ｂ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ］及び経路［ａ，Ａ，ｍ，Ｃ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｂ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｂ］及び経路［ａ，Ａ，ｏ，Ｂ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ］及び経路［ａ，Ａ，ｏ，Ｃ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ１］におけるグループＧＢ１の展開を実行すると、経路［ａ，Ａ，Ｂ，ｑ］及び経路［ａ，Ａ，Ｂ，ｇ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ２］におけるグループＧＢ２の展開を実行すると、経路［ａ，Ａ，Ｂ，ｄ］及び経路［ａ，Ａ，Ｂ，ｅ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ３］におけるグループＧＢ３の展開を実行すると、経路［ａ，Ａ，Ｂ，ｎ］及び経路［ａ，Ａ，Ｂ，ｏ］が得られる。

なお、（※）は、隣接頂点が存在するためさらなる探索が可能であるがフィルタ条件Ｆに基づき処理が打ち切られた経路を表している。

以上から、探索条件及びフィルタ条件Ｆを満たす経路として経路［ａ，Ａ，ｏ，ｋ］が得られる。

第２の例として、探索条件が「ａを始点とし且つｋを終点とする経路」という条件であり、且つ、フィルタ条件Ｆが「ホップ数が４以下であり且つ頂点Ｂを経由しない」という条件であるケースについて説明する。

図１４は、経路集合Ｑに含まれる経路をホップ数毎に示す図である。

ホップ数が０である経路［ａ］は経路集合Ｑに追加される。但し、経路［ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が１である経路［ａ，Ａ］は経路集合Ｑに追加される。但し、経路［ａ，Ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が２である経路［ａ，Ａ，ＧＡ１］、経路［ａ，Ａ，ＧＡ２］、経路［ａ，Ａ，ＧＡ３］及び経路［ａ，Ａ，ＧＡ４］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。ホップ数が３である経路［ａ，Ａ，ＧＡ３，Ｃ］及び経路［ａ，Ａ，ＧＡ４，Ｃ］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。ホップ数が４である経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ１］、経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ２］、経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ３］、経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ１］、経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ２］及び経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ３］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。

図１５は、経路集合Ｑに含まれる経路及び経路集合Ｒに含まれる経路のうちグループを含むものについて展開を実行した場合の結果を示す図である。なお、ホップ数が４以下である条件の下で展開後にさらに探索が実行されている。

経路［ａ，Ａ，ＧＡ１］におけるグループＧＡ１の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｃ］、経路［ａ，Ａ，ｃ，ｐ］、経路［ａ，Ａ，ｂ］、経路［ａ，Ａ，ｂ，ｊ］及び経路［ａ，Ａ，ｂ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ２］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が得られる。経路［ａ，Ａ，ＧＡ３］におけるグループＧＡ３の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｍ］、経路［ａ，Ａ，ｌ］及び経路［ａ，Ａ，ｌ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ４］におけるグループＧＡ４の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｎ］、経路［ａ，Ａ，ｏ］及び経路［ａ，Ａ，ｏ，ｋ］が得られる。

経路［ａ，Ａ，ＧＡ３，Ｃ］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ］及び経路［ａ，Ａ，ｍ，Ｃ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ］及び経路［ａ，Ａ，ｏ，Ｃ］が得られる。

経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ１］におけるグループＧＡ３及びグループＧＣ１の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ，ｆ］、経路［ａ，Ａ，ｌ，Ｃ，ｒ］、経路［ａ，Ａ，ｍ，Ｃ，ｆ］及び経路［ａ，Ａ，ｍ，Ｃ，ｒ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ２］におけるグループＧＡ３及びグループＧＣ２の展開を実行すると、経路［ａ，Ａ，ｍ，Ｃ，ｌ］及び経路［ａ，Ａ，ｌ，Ｃ，ｍ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ３］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ，ｎ］、経路［ａ，Ａ，ｍ，Ｃ，ｎ］、経路［ａ，Ａ，ｌ，Ｃ，ｏ］及び経路［ａ，Ａ，ｍ，Ｃ，ｏ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ１］におけるグループＧＡ４及びグループＧＣ１の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｎ，Ｃ，ｒ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］及び経路［ａ，Ａ，ｏ，Ｃ，ｒ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ２］におけるグループＧＡ４及びグループＧＣ２の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｌ］、経路［ａ，Ａ，ｎ，Ｃ，ｍ］、経路［ａ，Ａ，ｏ，Ｃ，ｌ］及び経路［ａ，Ａ，ｏ，Ｃ，ｍ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ３］におけるグループＧＡ４及びグループＧＣ３の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｏ］及び経路［ａ，Ａ，ｏ，Ｃ，ｎ］が得られる。

（※）は、隣接頂点が存在するためさらなる探索が可能な経路である。

図１６は、図１５に示された経路のうち一部の経路についてさらなる探索を実行した場合の結果を示す図である。経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］、経路［ａ，Ａ，ｍ，Ｃ，ｌ］、経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］及び経路［ａ，Ａ，ｎ，Ｃ，ｌ］は、フィルタ条件Ｆを満たさない。

経路［ａ，Ａ，ｂ，ｉ］からは経路［ａ，Ａ，ｂ，ｉ，ｌ］が得られる。経路［ａ，Ａ，ｌ，ｉ］からは経路［ａ，Ａ，ｌ，ｉ，ｂ］が得られる。経路［ａ，Ａ，ｏ，ｋ］からは経路［ａ，Ａ，ｏ，ｋ，ｇ］及び経路［ａ，Ａ，ｏ，ｋ，ｆ］が得られる。

以上から、探索条件及びフィルタ条件Ｆを満たす経路として経路［ａ，Ａ，ｏ，ｋ］が得られる。

図１７は、第１の例について本実施の形態のグラフトラバーサルを実行した場合のランダムアクセスを示す図である。例えば第１行目の情報は、経路［ａ］における最後の要素である頂点ａの隣接頂点を第１ＫＶＳ１１１から特定するためのランダムアクセスを表す。また、例えば第８行目の情報は、経路［ａ，Ａ，ＧＡ１］における最後の要素であるグループＧＡ１に属する頂点を第２ＫＶＳ１１３から特定するためのランダムアクセスを表す。このように、合計で１５回のランダムアクセスが発生する。一方、図１８は、第１の例について通常のグラフトラバーサルを実行した場合のランダムアクセスを示す図である。このように、合計で３０回のランダムアクセスが発生する。

このように、本実施の形態のグラフトラバーサルを実行すれば、ランダムアクセスの回数を減らすことができるので、最終的にグラフトラバーサルを完了するまでの時間を短縮することができるようになる。

なお、本実施の形態の方法は、図３乃至図６に示したような無向グラフだけではなく、例えば図１９に示すような、或る頂点（図１９においては頂点ａ）を始点とする有向グラフに対しても適用可能である。図１９においてはエッジの数が４以上である頂点がハブであり、ハブは頂点Ａ、頂点Ｂ、頂点Ｃ、頂点Ｄ及び頂点Ｅである。ハブＡには、頂点ａ、頂点ｂ、頂点ｃ、頂点ｄ、頂点ｅ、頂点ｆ、頂点ｇ及び頂点Ｅが接続されている。

このようなケースにおいては、例えば図２０に示すようにグループ化が実行される。図２０の例においては、ハブＡ及びハブＢに接続されている頂点ｂ及び頂点ｃはグループＧＡ１に属し、ハブＡにのみ接続されている頂点ｄ及び頂点ｅはグループＧＡ２に属し、ハブＡ、ハブＣ及びハブＤに接続されている頂点ｆ及び頂点ｇはグループＧＡ３に属し、ハブＥはいずれのグループにも属さない。

［実施の形態２］
第１の実施の形態においては、フィルタ条件Ｆを満たさない経路が経路探索が完了した後に一括して除外される。これに対して、第２の実施の形態においては、フィルタ条件Ｆを満たさない経路が経路探索中に除外される。そのため、複雑ネットワークの形態及びフィルタ条件Ｆの内容によっては、グラフトラバーサルに要する時間がさらに短縮される。

図２１は、第２の実施の形態のトラバーサル処理部１０５が実行する処理の処理フローを示す図である。本処理は、トラバーサルクエリを受信又は受け付けた場合に実行される。

トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図２１：ステップＳ１２１）。

本実施の形態において、グラフトラバーサルの経路はリストで表現される。例えば頂点ａ、頂点ｂ、頂点ｃの順に探索された場合、経路は［ａ，ｂ，ｃ］と表現される。Ｑは一時的に使用されるキューであり、Ｒは結果を格納するためのキューである。

グラフトラバーサルの始点である頂点をｎ０とする。ｎ０のみで構成される経路をＴ０とする。つまりＴ０＝［ｎ０］である。

トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ１２３）。

経路集合Ｑが空である場合（ステップＳ１２３：Ｙｅｓルート）、処理はステップＳ１２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ１２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ１２５）。探索終了条件はトラバーサルクエリに含まれており、経路が所定個以上見つかったという条件やグラフトラバーサルのホップ数が所定の閾値を超えたという条件等である。

探索終了条件が満たされない場合（ステップＳ１２５：Ｎｏルート）、処理は端子Ｃを介して図２２のステップＳ１３１の処理に移行する。

図２２の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図２２：ステップＳ１３１）。以下では、ステップＳ１３１において取り出された経路を経路Ｔと呼ぶ。

トラバーサル処理部１０５は、経路Ｔの最後の要素を特定する（ステップＳ１３３）。以下では、ステップＳ１３３において特定された要素を要素ｅと呼ぶ。要素ｅは、頂点又はグループである。例えば経路Ｔが［Ａ，Ｂ，ｃ］である場合、要素ｅは頂点ｃである。

トラバーサル処理部１０５は、ステップＳ１３３において特定された要素ｅがグループであるか判定する（ステップＳ１３５）。

要素ｅがグループである場合（ステップＳ１３５：Ｙｅｓルート）、処理は端子Ｄを介して図２３のステップＳ１４７に移行する。

一方、要素ｅがグループではない場合（ステップＳ１３５：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔが探索条件を満たすか判定する（ステップＳ１３７）。探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件等である。

経路Ｔが探索条件を満たさない場合（ステップＳ１３７：Ｎｏルート）、処理はステップＳ１４１に移行する。一方、経路Ｔが探索条件を満たす場合（ステップＳ１３７：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ１３９）。

トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータ及び第２ＫＶＳ１１３に格納されているデータに基づき、要素ｅの隣接頂点のうち未訪問の隣接頂点の集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］、及び、要素ｅの隣接グループの集合Ｇ＝［ｇ１，ｇ２，ｇ３，．．．］を特定する（ステップＳ１４１）。ここで、未訪問である頂点とは経路Ｔに含まれない頂点を意味する。以下においても同様とする。

トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］及び経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１、経路ＴＭ２、経路ＴＭ３、・・・のうちフィルタ条件Ｆを満たす経路を経路集合Ｑに追加する（ステップＳ１４３）。フィルタ条件Ｆはトラバーサルクエリに含まれており、例えば、ホップ数が所定値以上であるという条件や或る頂点を経由するという条件等である。

トラバーサル処理部１０５は、経路ＴＧ１＝Ｔ＋［ｇ１］、経路ＴＧ２＝Ｔ＋［ｇ２］、経路ＴＧ３＝Ｔ＋［ｇ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＧ１、経路ＴＧ２及び経路ＴＧ３、・・・を経路集合Ｑに追加する（ステップＳ１４５）。但し、Ｇが空集合である場合にはステップＳ１４５の処理はスキップされる。そして処理は端子Ｅを介して図２１のステップＳ１２３に戻る。

端子Ｄを介して図２３の説明に移行し、トラバーサル処理部１０５は、経路Ｔからグループｅを取り除いた経路である経路Ｔｘを生成する（図２３：ステップＳ１４７）。

トラバーサル処理部１０５は、第２ＫＶＳ１１３に格納されているデータに基づき、グループｅに隣接するハブのうち未訪問のハブの集合Ｈ＝［ｈ１，ｈ２，ｈ３，．．．］を特定する（ステップＳ１４９）。上で述べたように、同じグループに属する頂点は同じハブに接続される。ステップＳ１４９においては、１回のランダムアクセスによってグループ内の各頂点に隣接するハブが一括して特定されることになるので、各頂点についてランダムアクセスを行わなくて済むようになる。これにより、ランダムアクセスの回数を減らし、グラフトラバーサルにかかる時間を短縮できるようになる。

トラバーサル処理部１０５は、グループｅに未処理の頂点が有るか判定する（ステップＳ１５０）。未処理の頂点が無い場合（ステップＳ１５０：Ｎｏルート）、処理は端子Ｅを介して図２１のステップＳ１２３に戻る。

一方、グループｅに未処理の頂点が有る場合（ステップＳ１５０：Ｙｅｓルート）、トラバーサル処理部１０５は、グループｅに属する頂点のうち未処理の頂点を１つ特定する（ステップＳ１５１）。以下では、ステップＳ１５１において特定された頂点を頂点ｐと呼ぶ。

トラバーサル処理部１０５は、経路Ｔｐ＝Ｔｘ＋［ｐ］を生成する（ステップＳ１５３）。例えばＴｘ＝［ａ，ｂ］である場合にはＴｐ＝［ａ，ｂ，ｐ］である。

トラバーサル処理部１０５は、経路Ｔｐがフィルタ条件Ｆを満たすか判定する（ステップＳ１５５）。

経路Ｔｐがフィルタ条件Ｆを満たさない場合（ステップＳ１５５：Ｎｏルート）、処理はステップＳ１５０に戻る。一方、経路Ｔｐがフィルタ条件Ｆを満たす場合（ステップＳ１５５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｐが探索条件を満たすか判定する（ステップＳ１５７）。

経路Ｔｐが探索条件を満たさない場合（ステップＳ１５７：Ｎｏルート）、処理は端子Ｆを介して図２４のステップＳ１６１に移行する。一方、経路Ｔｐが探索条件を満たす場合（ステップＳ１５７：Ｙｅｓルート）、経路Ｔｐを経路集合Ｒに追加する（ステップＳ１５９）。そして処理は端子Ｆを介して図２４のステップＳ１６１に移行する。

図２４の説明に移行し、トラバーサル処理部１０５は、ハブの集合Ｈに含まれるハブのうち未処理のハブを１つ特定する（図２４：ステップＳ１６１）。以下では、ステップＳ１６１において特定されたハブをハブｈと呼ぶ。

トラバーサル処理部１０５は、経路Ｔｈ＝Ｔｐ＋［ｈ］を生成する（ステップＳ１６３）。

トラバーサル処理部１０５は、経路Ｔｈがフィルタ条件Ｆを満たすか判定する（ステップＳ１６５）。

経路Ｔｈがフィルタ条件Ｆを満たさない場合（ステップＳ１６５：Ｎｏルート）、処理はステップＳ１６９に移行する。一方、経路Ｔｈがフィルタ条件Ｆを満たす場合（ステップＳ１６５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｈを経路集合Ｑに追加する（ステップＳ１６７）。

トラバーサル処理部１０５は、ハブの集合Ｈに含まれるハブのうち未処理のハブが有るか判定する（ステップＳ１６９）。未処理のハブが有る場合（ステップＳ１６９：Ｙｅｓルート）、処理はステップＳ１６１に戻る。一方、未処理のハブが無い場合（ステップＳ１６９：Ｎｏルート）、処理は端子Ｇを介して図２５のステップＳ１７１に移行する。

図２５の説明に移行し、トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータに基づき、頂点ｐの隣接頂点（ここでは、ハブ以外の頂点）のうち未訪問の隣接頂点の集合Ｖから、未処理の頂点を１つ特定する（図２５：ステップＳ１７１）。以下では、ステップＳ１７１において特定された頂点を頂点ｖと呼ぶ。

トラバーサル処理部１０５は、経路Ｔｖ＝Ｔｐ＋［ｖ］を生成する（ステップＳ１７３）。

トラバーサル処理部１０５は、経路Ｔｖがフィルタ条件Ｆを満たすか判定する（ステップＳ１７５）。

経路Ｔｖがフィルタ条件Ｆを満たさない場合（ステップＳ１７５：Ｎｏルート）、処理はステップＳ１７９に移行する。一方、経路Ｔｖがフィルタ条件Ｆを満たす場合（ステップＳ１７５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｖを経路集合Ｑに追加する（ステップＳ１７７）。

トラバーサル処理部１０５は、未処理の頂点が有るか判定する（ステップＳ１７９）。

未処理の頂点が有る場合（ステップＳ１７９：Ｙｅｓルート）、処理はステップＳ１７１に戻る。一方、未処理の頂点が無い場合（ステップＳ１７９：Ｎｏルート）、処理は端子Ｈを介してステップＳ１５０の処理に戻る。

図２１の説明に戻り、探索終了条件が満たされる場合（ステップＳ１２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路のうち、フィルタ条件Ｆを満たす経路を特定する（ステップＳ１２７）。

トラバーサル処理部１０５は、ステップＳ１２７において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ１２９）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。

通常のグラフトラバーサルには、探索される頂点の数とランダムアクセスの回数とがほぼ一致するという特徴がある。これに対して、本実施の形態の方法においては、ハブに基づいて頂点がグループ化されており、複数の頂点に対して１回のランダムアクセスが実行される。これにより、経路がハブを経由する場合であっても、ランダムアクセスの回数の増加が原因となり処理時間が増大することを抑制できるようになる。複雑ネットワークによっては、処理時間の桁数を大幅に減らすことができる。

また、第２の実施の形態においては、フィルタ条件Ｆを満たさない経路はステップＳ１４３において経路集合Ｑに追加されない。従って、特にフィルタ条件Ｆの条件が厳しい場合には、フィルタ条件Ｆによって多くの経路が探索の対象から外されるようになるのでグラフトラバーサルにかかる時間を短縮できるようになる。

複雑ネットワークは疎な部分が占める割合が大きいにもかかわらず、疎な部分での処理によっては性能問題が発生しないため、複雑ネットワーク全体に対して前処理を実行すること及びインデックスを生成することは効率的ではない。本実施の形態においては、性能問題の原因であるハブに限定してグループ化を実行しており、効率的な対策が実現されている。

また、本実施の形態の方法は、オンメモリでの処理が困難である大規模グラフに対しても有効である。

以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した情報処理装置１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。

また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。

例えば、グラフトラバーサルと展開とを並行して実行することで処理時間を短縮してもよい。

［付録］
本付録においては、通常のグラフトラバーサルにおいて実行される処理について説明する。図２６は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。

トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図２６：ステップＳ２２１）。

トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ２２３）。

経路集合Ｑが空である場合（ステップＳ２２３：Ｙｅｓルート）、処理はステップＳ２２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ２２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ２２５）。

探索終了条件が満たされない場合（ステップＳ２２５：Ｎｏルート）、処理は端子Ｉを介して図２７のステップＳ２３１の処理に移行する。

図２７の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図２７：ステップＳ２３１）。以下では、ステップＳ２３１において取り出された経路を経路Ｔと呼ぶ。

トラバーサル処理部１０５は、経路Ｔが探索条件を満たすか判定する（ステップＳ２３３）。探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件、といった条件である。

経路Ｔが探索条件を満たさない場合（ステップＳ２３３：Ｎｏルート）、処理はステップＳ２３７に移行する。

一方、経路Ｔが探索条件を満たす場合（ステップＳ２３３：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ２３５）。

トラバーサル処理部１０５は、経路Ｔの最後の頂点である頂点ｎを特定する（ステップＳ２３７）。

トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータに基づき、頂点ｎの隣接頂点を特定する。そして、トラバーサル処理部１０５は、頂点ｎの隣接頂点のうち未処理の隣接頂点の集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］を特定する（ステップＳ２３９）。

トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１、経路ＴＭ２、経路ＴＭ３、・・・を経路集合Ｑに追加する（ステップＳ２４１）。そして処理は端子Ｊを介して図２６のステップＳ２２３に戻る。

図２６の説明に戻り、探索終了条件が満たされる場合（ステップＳ２２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路のうち、フィルタ条件Ｆを満たす経路を特定する（ステップＳ２２７）。

トラバーサル処理部１０５は、ステップＳ２２７において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ２２９）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。

このように、通常のグラフトラバーサルは、頂点をキーとし且つ隣接頂点をバリューとする第１ＫＶＳ１１１を繰り返し参照することにより進行する。

なお、ここでは単純な幅優先探索に基づくグラフトラバーサルの例を示したが、例えば、深さ優先探索に基づくグラフトラバーサルや訪問済みの頂点には再訪問しないグラフトラバーサルなど、グラフトラバーサルには種々のバリエーションがある。

以上で付録を終了する。

なお、上で述べた情報処理装置１は、コンピュータ装置であって、図２８に示すように、メモリ２５０１とＣＰＵ２５０３とソリッドステートドライブ２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＳＳＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＳＳＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＳＳＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＳＳＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＳＳＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。

以上述べた本発明の実施の形態をまとめると、以下のようになる。

本実施の形態の第１の態様に係る情報処理装置は、（Ａ）所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部（実施の形態における第２ＫＶＳ１１３は上記記憶部の一例である）に格納するグループ化部（実施の形態におけるグループ化部１０３は上記グループ化部の一例である）と、（Ｂ）複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部（実施の形態におけるトラバーサル処理部１０５は上記トラバーサル処理部の一例である）とを有する。

複雑ネットワークに対するグラフトラバーサルにおいては、多数のエッジを有するハブが原因となり、ランダムアクセスの回数が増加して処理時間が長くなる。そこで、上で述べたような処理を実行すれば、頂点単位ではなくグループ単位でランダムアクセスが行われるので、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮できるようになる。

また、上記グループ化部は、（ａ１）ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行してもよい。

ランダムアクセスの回数が少なくなるようにグループ化することができるようになる。

また、上記所定数は、記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数であってもよい。

処理時間の増加をもたらすハブを適切に抽出できるようになる。

また、上記トラバーサル処理部は、（ｂ１）グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された複数の経路のうち所定の条件を満たす経路を特定してもよい。

展開を一括して実行することができるようになる。

また、上記トラバーサル処理部は、（ｂ２）グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路についてグラフトラバーサルを実行することで複数の経路を生成してもよい。

所定の条件を満たさない経路を途中で除外することができるようになる。

また、上記所定の条件は、グラフトラバーサルのクエリに含まれてもよい。

本実施の形態の第２の態様に係る情報処理方法は、（Ｃ）所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、（Ｄ）抽出されたハブに隣接する頂点をグループ化し、（Ｅ）グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、（Ｆ）複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、（Ｇ）グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。

なお、上記方法による処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。

以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。

（付記１）
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出された前記ハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納するグループ化部と、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部と、
を有する情報処理装置。

（付記２）
前記グループ化部は、
前記ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行する、
付記１記載の情報処理装置。

（付記３）
前記所定数は、前記記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、前記複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数である、
付記１又は２記載の情報処理装置。

（付記４）
前記トラバーサル処理部は、
前記グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された前記複数の経路のうち所定の条件を満たす経路を特定する、
付記１乃至３のいずれか１つ記載の情報処理装置。

（付記５）
前記トラバーサル処理部は、
前記グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路について前記グラフトラバーサルを実行することで前記複数の経路を生成する、
付記１乃至３のいずれか１つ記載の情報処理装置。

（付記６）
前記所定の条件は、前記グラフトラバーサルのクエリに含まれる、
付記４又は５記載の情報処理装置。

（付記７）
コンピュータに、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行させるプログラム。

（付記８）
コンピュータが、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行する情報処理方法。

１ 情報処理装置 １０１ ネットワーク管理部
１０３ グループ化部 １０５ トラバーサル処理部
１１１ 第１ＫＶＳ １１３ 第２ＫＶＳ
１１５ 出力データ格納部

Claims (7)

1. 所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出された前記ハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納するグループ化部と、
   前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部と、
   を有する情報処理装置。
2. 前記グループ化部は、
   前記ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行する、
   請求項１記載の情報処理装置。
3. 前記所定数は、前記記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、前記複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数である、
   請求項１又は２記載の情報処理装置。
4. 前記トラバーサル処理部は、
   前記グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された前記複数の経路のうち所定の条件を満たす経路を特定する、
   請求項１乃至３のいずれか１つ記載の情報処理装置。
5. 前記トラバーサル処理部は、
   前記グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路について前記グラフトラバーサルを実行することで前記複数の経路を生成する、
   請求項１乃至３のいずれか１つ記載の情報処理装置。
6. コンピュータに、
   所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
   抽出された前記ハブに隣接する頂点をグループ化し、
   グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
   前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
   前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
   処理を実行させるプログラム。
7. コンピュータが、
   所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
   抽出された前記ハブに隣接する頂点をグループ化し、
   グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
   前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
   前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
   処理を実行する情報処理方法。

Images