(57)【要約】      （修正有）【課題】複雑ネットワークに対するグラフトラバーサルに要する時間を短縮する。【解決手段】本情報処理方法は、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。【選択図】図４
2019091257.tif 000002
【特許請求の範囲】
【請求項１】
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出された前記ハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納するグループ化部と、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部と、
を有する情報処理装置。
【請求項２】
前記グループ化部は、
前記ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行する、
請求項１記載の情報処理装置。
【請求項３】
前記所定数は、前記記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、前記複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数である、
請求項１又は２記載の情報処理装置。
【請求項４】
前記トラバーサル処理部は、
前記グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された前記複数の経路のうち所定の条件を満たす経路を特定する、
請求項１乃至３のいずれか１つ記載の情報処理装置。
【請求項５】
前記トラバーサル処理部は、
前記グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路について前記グラフトラバーサルを実行することで前記複数の経路を生成する、
請求項１乃至３のいずれか１つ記載の情報処理装置。
【請求項６】
コンピュータに、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行させるプログラム。
【請求項７】
コンピュータが、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行する情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ処理技術に関する。
【背景技術】
【０００２】
複雑ネットワークは、頂点間の接続パターンが純粋な規則性を有するわけではなく且つ純粋なランダム性を有するわけでもないネットワークである。図１は、複雑ネットワークの一例を示す図である。図１において、円は頂点を表し、頂点間の線分はエッジを表す。例えばソーシャルネットワークやナレッジグラフなど、現実世界における巨大で複雑なネットワークの中には複雑ネットワークの性質を有するネットワークがある。
【０００３】
複雑ネットワークはスケールフリーネットワークであることが知られている。スケールフリーネットワークとは次数分布がべき乗則に従うネットワークであり、次数とは頂点のエッジ数のことである。スケールフリーネットワークには、ハブ或いはハブノードと呼ばれる、極めて次数が大きい頂点がごく少数（例えば１％程度）存在する。一方で、多くの（例えば５０％程度の）頂点は１又は２といったごく少数のエッジを有する。ハブのエッジ数の合計が複雑ネットワークにおける全エッジ数のおよそ半数に達することがあり、このような場合、或る頂点の次に到達する頂点はおおよそ５０％の確率でハブである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１６−１８９２１４号公報
【特許文献２】特開平２−２５３４７８号公報
【特許文献３】特表２０１３−５１９１４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
グラフトラバーサルとはグラフ処理の一種であり、経路の探索等を目的としてグラフにおける頂点を辿る処理である。ハブに関する上記のような性質から、複雑ネットワークに対してグラフトラバーサルを実行すると経路がハブを経由する確率が高い。経路がハブを経由する場合、経路の組合せ爆発により記憶装置に対するランダムアクセス（具体的には、ランダムリード）の回数が増大するため処理時間が長くなるという問題が有る。上で述べたように、複雑ネットワークによってはおよそ半数のエッジが１つのハブに接続することがあるため、特に、ハブから出た複数の経路が再びハブを経由するパターンが原因となり処理時間が長くなりやすい。グラフ処理に関する従来技術は、このような問題の解決には適していない。
【０００６】
本発明の目的は、１つの側面では、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮するための技術を提供することである。
【課題を解決するための手段】
【０００７】
一態様に係る情報処理方法は、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。
【発明の効果】
【０００８】
１つの側面では、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮できるようになる。
【図面の簡単な説明】
【０００９】
【図１】図１は、複雑ネットワークの一例を示す図である。
【図２】図２は、情報処理装置の機能ブロック図である。
【図３】図３は、本実施の形態におけるグループ化について説明するための図である。
【図４】図４は、本実施の形態におけるグループ化について説明するための図である。
【図５】図５は、本実施の形態におけるグループ化について説明するための図である。
【図６】図６は、本実施の形態におけるグループ化について説明するための図である。
【図７】図７は、第１ＫＶＳに格納されるデータの一例を示す図である。
【図８Ａ】図８Ａは、第２ＫＶＳに格納されるデータの一例を示す図である。
【図８Ｂ】図８Ｂは、第２ＫＶＳに格納されるデータの一例を示す図である。
【図９】図９は、グループ化部が実行する処理の処理フローを示す図である。
【図１０】図１０は、第１の実施の形態におけるトラバーサル処理部が実行する処理の処理フローを示す図である。
【図１１】図１１は、第１の実施の形態におけるトラバーサル処理部が実行する処理の処理フローを示す図である。
【図１２】図１２は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１３】図１３は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１４】図１４は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１５】図１５は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１６】図１６は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１７】図１７は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１８】図１８は、第１の実施の形態のグラフトラバーサルについて説明するための図である。
【図１９】図１９は、本実施の形態におけるグループ化について説明するための図である。
【図２０】図２０は、本実施の形態におけるグループ化について説明するための図である。
【図２１】図２１は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。
【図２２】図２２は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。
【図２３】図２３は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。
【図２４】図２４は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。
【図２５】図２５は、第２の実施の形態のトラバーサル処理部が実行する処理の処理フローを示す図である。
【図２６】図２６は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。
【図２７】図２７は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。
【図２８】図２８は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１０】
［実施の形態１］
本実施の形態における情報処理装置１は、複雑ネットワークについてのグラフ処理を実行するパーソナルコンピュータ或いはサーバ等の装置である。情報処理装置１は、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介してグラフトラバーサルのクエリ（以下、トラバーサルクエリと呼ぶ）を受信し、受信したトラバーサルクエリに応じてグラフトラバーサルを実行し、グラフトラバーサルの結果を出力する。
【００１１】
図２は、情報処理装置１の機能ブロック図である。情報処理装置１は、ネットワーク管理部１０１と、グループ化部１０３と、トラバーサル処理部１０５と、第１ＫＶＳ（Key-Value Store）１１１と、第２ＫＶＳ１１３と、出力データ格納部１１５とを含む。
【００１２】
ネットワーク管理部１０１、グループ化部１０３及びトラバーサル処理部１０５は、例えば図２８におけるＳＳＤ（Solid State Drive）２５０５に格納されたプログラムがメモリ２５０１に読み出されてＣＰＵ（Central Processing Unit）２５０３により実行されることで実現される。第１ＫＶＳ１１１、第２ＫＶＳ１１３及び出力データ格納部１１５は、例えばＳＳＤ２５０５に設けられる。
【００１３】
ネットワーク管理部１０１は、複雑ネットワークにおける各頂点に隣接する頂点の情報を第１ＫＶＳ１１１において管理する。複雑ネットワークのトポロジが変更された場合、ネットワーク管理部１０１は第１ＫＶＳ１１１に格納されているデータを更新する。なお、「隣接」とは頂点が他の頂点に１ホップで接続されることを意味する。以下では、或る頂点又はグループに隣接する頂点のことを「隣接頂点」とも呼ぶ。また、或る頂点に隣接するグループのことを「隣接グループ」とも呼ぶ。
【００１４】
グループ化部１０３は、第１ＫＶＳ１１１に格納されたデータに基づきハブを抽出し、抽出されたハブの隣接頂点をグループ化する。グループ化部１０３は、グループ化の結果を第２ＫＶＳ１１３に格納する。
【００１５】
トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されたデータ及び第２ＫＶＳ１１３に格納されたデータに基づき、複雑ネットワークに対するグラフトラバーサルを実行し、グラフトラバーサルの結果を出力データ格納部１１５に格納する。
【００１６】
ここで、本実施の形態におけるグループ化の概要を説明する。一例として、図３に示すような複雑ネットワークを考える。図３には無向グラフが示されており、円は頂点を表し、頂点間の線分はエッジを表す。図３においては次数が５以上である頂点がハブであるので、頂点Ａ、頂点Ｂ及び頂点Ｃがハブである。頂点Ａ、頂点Ｂ及び頂点Ｃはハッチングされている。なお、実際の複雑ネットワークは図３に示すようなネットワークより複雑である場合が多いが、説明を簡単にするためここでは単純な例が示されている。
【００１７】
図４は、ハブＡの隣接頂点をグループ分けした結果を示す図である。ハブＡの隣接頂点は頂点ａ、頂点ｂ、頂点ｃ、頂点ｄ、頂点ｅ、頂点ｌ、頂点ｍ、頂点ｎ、頂点ｏ及びハブである頂点Ｂである。本実施の形態においては、（１）隣接するハブの組み合わせが同じである頂点が同じグループに属するという条件、及び（２）ハブはグループには属さないという条件が満たされるようにグループ化が実行される。これらのルールに従うと、図４に示すようにグループ化が行われる。頂点ａ、頂点ｂ及び頂点ｃはハブＡに隣接するのでグループＧＡ１に属し、頂点ｄ及び頂点ｅはハブＡ及びハブＢに隣接するのでグループＧＡ２に属し、頂点ｌ及び頂点ｍはハブＡ及びハブＣに隣接するのでグループＧＡ３に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでＧＡ４に属する。ハブである頂点Ｂはいずれのグループにも属さない。
【００１８】
図５は、ハブＢの隣接頂点をグループ分けした結果を示す図である。ハブＢの隣接頂点はハブである頂点Ａ、ハブである頂点Ｃ、頂点ｇ、頂点ｑ、頂点ｄ、頂点ｅ、頂点ｎ及び頂点ｏである。上記のルールに従うと、図５に示すようにグループ化が行われる。頂点ｇ及び頂点ｑはハブＢに隣接するのでグループＧＢ１に属し、頂点ｄ及び頂点ｅはハブＡ及びハブＢに隣接するのでグループＧＢ２に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでＧＢ３に属する。ハブである頂点Ａ及びハブである頂点Ｃはいずれのグループにも属さない。
【００１９】
図６は、ハブＣの隣接頂点をグループ分けした結果を示す図である。ハブＣの隣接頂点は、ハブである頂点Ｂ、頂点ｆ、頂点ｒ、頂点ｌ、頂点ｍ、頂点ｎ及び頂点ｏである。上記のルールに従うと、図６に示すようにグループ化が行われる。頂点ｆ及び頂点ｒはハブＣに隣接するのでグループＧＣ１に属し、頂点ｌ及び頂点ｍはハブＡ及びハブＣに隣接するのでＧＣ２に属し、頂点ｎ及び頂点ｏはハブＡ、ハブＢ及びハブＣに隣接するのでグループＧＣ３に属する。ハブである頂点Ｂはいずれのグループにも属さない。
【００２０】
図７は、第１ＫＶＳ１１１に格納されるデータの一例を示す図である。図７の例では、頂点の識別情報（キー）と、その頂点の隣接頂点の識別情報（バリュー）とが格納される。エントリは、複雑ネットワークにおける全頂点（ハブを含む）について生成される。
【００２１】
図８Ａ及び図８Ｂは、第２ＫＶＳ１１３に格納されるデータの一例を示す図である。図８Ａ及び図８Ｂには、図４に示したハブＡについて格納されるデータの一例が示されている。図８Ａの例では、ハブの識別情報（キー）と、当該ハブの隣接グループの識別情報及び隣接頂点の識別情報（バリュー）とが格納される。図８Ｂの例では、グループの識別情報（キー）と、当該グループ内の頂点の識別情報及びその隣接頂点の識別情報並びにグループ内の全頂点が隣接するハブの識別情報（バリュー）とが格納される。
【００２２】
なお、図８Ａ及び図８Ｂに示したデータは、全ハブについて生成される。
【００２３】
次に、情報処理装置１が実行する処理を詳細に説明する。
【００２４】
図９は、情報処理装置１のグループ化部１０３が実行する処理の処理フローを示す図である。本処理は、例えば、第１ＫＶＳ１１１に格納されているデータが更新された場合、又は、ユーザからの指示に応じて実行される。
【００２５】
グループ化部１０３は、第１ＫＶＳ１１１に格納されているデータに基づき、所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出する（図９：ステップＳ１）。
【００２６】
ステップＳ１における所定数は、例えば、（１）ＳＳＤ２５０５に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、（２）複雑ネットワークにおける頂点のうちエッジ数の多さが第Ｎ位（Ｎは自然数）である頂点のエッジ数である。（１）については、例えば１回のランダムアクセスに要する時間が１０マイクロ秒であり且つ１の頂点につき許容される処理時間が１秒（＝１００００００マイクロ秒）である場合、１０００００（＝１００００００／１０）が所定数である。（２）については、例えばＮが１３であり且つ第１３位の頂点のエッジ数が５００００００である場合、所定数は５００００００である。但し、（１）又は（２）以外の数を所定数としてもよい。
【００２７】
グループ化部１０３は、ステップＳ１において抽出されたハブのうち未処理のハブを１つ特定する（ステップＳ３）。以下では、ステップＳ３において特定されたハブをハブｈと呼ぶ。
【００２８】
グループ化部１０３は、第１ＫＶＳ１１１から、ハブｈに対応付けられている隣接頂点を抽出する。（ステップＳ５）。
【００２９】
グループ化部１０３は、ステップＳ５において抽出された隣接頂点を、当該隣接頂点に隣接するハブの組み合わせに基づきグループ化する（ステップＳ７）。グループ化の方法については、図３乃至図６を用いて説明したとおりである。
【００３０】
グループ化部１０３は、ハブｈの識別情報に対応付けて、隣接グループの識別情報及び隣接頂点の識別情報を第２ＫＶＳ１１３に格納する（ステップＳ９）。
【００３１】
グループ化部１０３は、ハブｈの各隣接グループの識別情報に対応付けて、当該グループに属する頂点の識別情報と当該頂点の隣接頂点の識別情報と当該グループ内の全頂点が隣接するハブの識別情報とを第２ＫＶＳ１１３に格納する（ステップＳ１１）。
【００３２】
グループ化部１０３は、ステップＳ１において抽出されたハブのうち未処理のハブが有るか判定する（ステップＳ１３）。
【００３３】
未処理のハブが有る場合（ステップＳ１３：Ｙｅｓルート）、処理はステップＳ３に戻る。一方、未処理のハブが無い場合（ステップＳ１３：Ｎｏルート）、処理は終了する。
【００３４】
以上のような処理を実行すれば、本実施の形態のグラフトラバーサルにおいて使用される第２ＫＶＳ１１３のデータを用意できるようになる。
【００３５】
図１０は、第１の実施の形態におけるトラバーサル処理部１０５が実行する処理の処理フローを示す図である。本処理は、トラバーサルクエリを受信又は受け付けた場合に実行される。
【００３６】
トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図１０：ステップＳ２１）。
【００３７】
本実施の形態において、グラフトラバーサルの経路はリストで表現される。例えば頂点ａ、頂点ｂ、頂点ｃの順に探索された場合、経路は［ａ，ｂ，ｃ］と表現される。Ｑは一時的に使用されるキューであり、Ｒは結果を格納するためのキューである。Ｑ及びＲは、例えばメモリ２５０１に格納される。また、グラフトラバーサルの始点である頂点をｎ０とする。ｎ０のみで構成される経路をＴ０とする。つまりＴ０＝［ｎ０］である。
【００３８】
トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ２３）。
【００３９】
経路集合Ｑが空である場合（ステップＳ２３：Ｙｅｓルート）、処理はステップＳ２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ２５）。探索終了条件はトラバーサルクエリに含まれており、経路が所定個以上見つかったという条件やグラフトラバーサルのホップ数が所定の閾値を超えたという条件等である。
【００４０】
探索終了条件が満たされない場合（ステップＳ２５：Ｎｏルート）、処理は端子Ａを介して図１１のステップＳ３３の処理に移行する。
【００４１】
図１１の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図１１：ステップＳ３３）。以下では、ステップＳ３３において取り出された経路を経路Ｔと呼ぶ。
【００４２】
トラバーサル処理部１０５は、経路Ｔが探索条件を満たさないか判定する（ステップＳ３５）。ステップＳ３５の処理時点においてはグループが展開されていないため、経路Ｔにはグループが含まれる可能性がある。但し、たとえ経路Ｔにグループが含まれていたとしても経路Ｔが明らかに探索条件を満たさないと判定可能なことがあり、このような場合には経路Ｔは選択肢から除外される。なお、探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件等である。
【００４３】
経路Ｔが探索条件を満たさない場合（ステップＳ３５：Ｙｅｓルート）、処理はステップＳ４１に移行する。
【００４４】
一方、経路Ｔが探索条件を満たす場合（ステップＳ３５：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔがフィルタ条件Ｆを満たさないか判定する（ステップＳ３７）。ステップＳ３７の処理時点においてはグループが展開されていないため、経路Ｔにはグループが含まれる可能性がある。但し、たとえ経路Ｔにグループが含まれていたとしても経路Ｔが明らかにフィルタ条件Ｆを満たさないと判定可能なことがあり、このような場合には経路Ｔは選択肢から除外される。フィルタ条件Ｆはトラバーサルクエリに含まれており、例えば、ホップ数が所定値以上であるという条件や或る頂点を経由するという条件等である。
【００４５】
経路Ｔがフィルタ条件Ｆを満たさない場合（ステップＳ３７：Ｙｅｓルート）、処理はステップＳ４１に移行する。一方、経路Ｔがフィルタ条件Ｆを満たす場合（ステップＳ３７：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ３９）。
【００４６】
トラバーサル処理部１０５は、経路Ｔの最後の要素ｅを特定する（ステップＳ４１）。要素ｅは、頂点又はグループである。例えば経路Ｔが［Ａ，Ｂ，ｃ］である場合、ステップＳ４１において特定される要素ｅは頂点ｃである。
【００４７】
トラバーサル処理部１０５は、要素ｅがグループであるか判定する（ステップＳ４３）。
【００４８】
要素ｅがグループである場合（ステップＳ４３：Ｙｅｓルート）、トラバーサル処理部１０５は、グループｅに隣接するハブのうち未訪問のハブの集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］を特定する（ステップＳ４５）。そして処理はステップＳ４９に移行する。ここで、未訪問であるハブとは経路Ｔに含まれないハブを意味する。以下においても同様とする。
【００４９】
上で述べたように、同じグループに属する頂点は同じハブに接続される。ステップＳ４５においては、ＳＳＤ２５０５に対する１回のランダムアクセスによってグループ内の各頂点に隣接するハブが一括して特定されることになるので、各頂点についてランダムアクセスを行わなくて済むようになる。これにより、ランダムアクセスの回数を減らし、グラフトラバーサルにかかる時間を短縮できるようになる。
【００５０】
一方、要素ｅがグループではない場合（ステップＳ４３：Ｎｏルート）、トラバーサル処理部１０５は、以下の処理を実行する。具体的には、トラバーサル処理部１０５は、頂点ｅの隣接頂点のうち未訪問の隣接頂点、及び、頂点ｅの隣接グループのうち未訪問のグループの集合を、Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］として特定する（ステップＳ４７）。
【００５１】
トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・のうちフィルタ条件Ｆを満たす経路を経路集合Ｑに追加する（ステップＳ４９）。そして処理は端子Ｂを介して図１０のステップＳ２３に戻る。
【００５２】
図１０の説明に戻り、探索終了条件が満たされる場合（ステップＳ２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路の各々について、当該経路に含まれるグループを第２ＫＶＳ１１３に格納されているデータを用いて展開することで経路集合Ｒｘを生成する（ステップＳ２７）。例えば経路が［ａ，Ａ，ＧＡ２］であり且つグループＧＡ２に頂点ｄ及び頂点ｅが含まれる場合、グループの展開により経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が生成される。ここで、展開により同じ頂点が２度以上訪問されることになった場合、経路は削除される。例えば展開により経路［ａ，Ａ，ｏ，Ｃ，ｏ］が生成された場合、頂点ｏが２回訪問されるので経路［ａ，Ａ，ｏ，Ｃ，ｏ］は削除される。
【００５３】
トラバーサル処理部１０５は、経路集合Ｒｘに含まれる経路のうち探索条件を満たし且つフィルタ条件Ｆを満たす経路を特定する（ステップＳ２９）。
【００５４】
トラバーサル処理部１０５は、ステップＳ２９において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ３１）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。
【００５５】
通常のグラフトラバーサルには、探索される頂点の数とランダムアクセスの回数とがほぼ一致するという特徴がある。これに対し、本実施の形態の方法においては、ハブに基づいて頂点がグループ化されており、複数の頂点に対して１回のランダムアクセスが実行される。これにより、経路がハブを経由する場合であっても、ランダムアクセスの回数の増加が原因となり処理時間が増大することを抑制できるようになる。複雑ネットワークによっては、処理時間の桁数を大幅に減らすことができる。
【００５６】
なお、通常のグラフトラバーサルの詳細については、付録を参照されたい。
【００５７】
また、第１の実施の形態においては、フィルタ条件Ｆを明らかに満たさない経路はステップＳ４９において経路集合Ｑに追加されない。従って、特にフィルタ条件Ｆの条件が厳しい場合には、フィルタ条件Ｆによって多くの経路が探索の対象から外されるようになるのでグラフトラバーサルにかかる時間を短縮できるようになる。
【００５８】
複雑ネットワークは疎な部分が占める割合が大きいにもかかわらず、疎な部分での処理によっては性能問題が発生しないため、複雑ネットワーク全体に対して前処理を実行すること及びインデックスを生成することは効率的ではない。本実施の形態においては、性能問題の原因であるハブに限定してグループ化を実行しており、効率的な対策が実現されている。
【００５９】
また、本実施の形態の方法は、オンメモリでの処理が困難である大規模グラフに対しても有効である。
【００６０】
ここで、本実施の形態の処理について具体例を用いて説明する。
【００６１】
第１の例として、探索条件が「ａを始点とし且つｋを終点とする経路」という条件であり、且つ、フィルタ条件Ｆが「ホップ数が３以下である」という条件であるケースについて説明する。
【００６２】
図１２は、経路集合Ｑに含まれる経路をホップ数毎に示す図である。
【００６３】
ホップ数が０である経路［ａ］は経路集合Ｑに追加される。但し、経路［ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が１である経路［ａ，Ａ］は経路集合Ｑに追加される。但し、経路［ａ，Ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が２である経路［ａ，Ａ，ＧＡ１］、経路［ａ，Ａ，ＧＡ２］、経路［ａ，Ａ，ＧＡ３］、経路［ａ，Ａ，ＧＡ４］及び経路［ａ，Ａ，Ｂ］は経路集合Ｑに追加される。これらの経路のうち経路［ａ，Ａ，Ｂ］は明らかに探索条件を満たさないので、経路［ａ，Ａ，Ｂ］以外の経路が経路集合Ｒに追加される。ホップ数が３である経路［ａ，Ａ，ＧＡ２，Ｂ］、経路［ａ，Ａ，ＧＡ３，Ｃ］、経路［ａ，Ａ，ＧＡ４，Ｂ］、経路［ａ，Ａ，ＧＡ４，Ｃ］、経路［ａ，Ａ，Ｂ，ＧＢ１］、経路［ａ，Ａ，Ｂ，ＧＢ２］、経路［ａ，Ａ，Ｂ，ＧＢ３］及び経路［ａ，Ａ，Ｂ，Ｃ］は経路集合Ｑに追加される。これらの経路のうち経路［ａ，Ａ，Ｂ，Ｃ］は明らかに探索条件を満たさないので、経路［ａ，Ａ，Ｂ，Ｃ］以外の経路が経路集合Ｒに追加される。
【００６４】
図１３は、経路集合Ｑに含まれる経路及び経路集合Ｒに含まれる経路のうちグループを含むものについて展開を実行した場合の結果を示す図である。なお、ホップ数が３以下であるという条件の下で展開後にさらに探索が実行されている。
【００６５】
経路［ａ，Ａ，ＧＡ１］におけるグループＧＡ１の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｃ］、経路［ａ，Ａ，ｃ，ｐ］、経路［ａ，Ａ，ｂ］、経路［ａ，Ａ，ｂ，ｊ］及び経路［ａ，Ａ，ｂ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ２］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が得られる。経路［ａ，Ａ，ＧＡ３］におけるグループＧＡ３の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｍ］、経路［ａ，Ａ，ｌ］及び経路［ａ，Ａ，ｌ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ４］におけるグループＧＡ４の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｎ］、経路［ａ，Ａ，ｏ］及び経路［ａ，Ａ，ｏ，ｋ］が得られる。
【００６６】
経路［ａ，Ａ，ＧＡ２，Ｂ］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ，Ｂ］及び経路［ａ，Ａ，ｅ，Ｂ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ］及び経路［ａ，Ａ，ｍ，Ｃ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｂ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｂ］及び経路［ａ，Ａ，ｏ，Ｂ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ］及び経路［ａ，Ａ，ｏ，Ｃ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ１］におけるグループＧＢ１の展開を実行すると、経路［ａ，Ａ，Ｂ，ｑ］及び経路［ａ，Ａ，Ｂ，ｇ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ２］におけるグループＧＢ２の展開を実行すると、経路［ａ，Ａ，Ｂ，ｄ］及び経路［ａ，Ａ，Ｂ，ｅ］が得られる。経路［ａ，Ａ，Ｂ，ＧＢ３］におけるグループＧＢ３の展開を実行すると、経路［ａ，Ａ，Ｂ，ｎ］及び経路［ａ，Ａ，Ｂ，ｏ］が得られる。
【００６７】
なお、（※）は、隣接頂点が存在するためさらなる探索が可能であるがフィルタ条件Ｆに基づき処理が打ち切られた経路を表している。
【００６８】
以上から、探索条件及びフィルタ条件Ｆを満たす経路として経路［ａ，Ａ，ｏ，ｋ］が得られる。
【００６９】
第２の例として、探索条件が「ａを始点とし且つｋを終点とする経路」という条件であり、且つ、フィルタ条件Ｆが「ホップ数が４以下であり且つ頂点Ｂを経由しない」という条件であるケースについて説明する。
【００７０】
図１４は、経路集合Ｑに含まれる経路をホップ数毎に示す図である。
【００７１】
ホップ数が０である経路［ａ］は経路集合Ｑに追加される。但し、経路［ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が１である経路［ａ，Ａ］は経路集合Ｑに追加される。但し、経路［ａ，Ａ］は明らかに探索条件を満たさないので、経路集合Ｒには追加されない。ホップ数が２である経路［ａ，Ａ，ＧＡ１］、経路［ａ，Ａ，ＧＡ２］、経路［ａ，Ａ，ＧＡ３］及び経路［ａ，Ａ，ＧＡ４］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。ホップ数が３である経路［ａ，Ａ，ＧＡ３，Ｃ］及び経路［ａ，Ａ，ＧＡ４，Ｃ］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。ホップ数が４である経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ１］、経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ２］、経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ３］、経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ１］、経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ２］及び経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ３］は経路集合Ｑに追加される。これらの経路は経路集合Ｒにも追加される。
【００７２】
図１５は、経路集合Ｑに含まれる経路及び経路集合Ｒに含まれる経路のうちグループを含むものについて展開を実行した場合の結果を示す図である。なお、ホップ数が４以下である条件の下で展開後にさらに探索が実行されている。
【００７３】
経路［ａ，Ａ，ＧＡ１］におけるグループＧＡ１の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｃ］、経路［ａ，Ａ，ｃ，ｐ］、経路［ａ，Ａ，ｂ］、経路［ａ，Ａ，ｂ，ｊ］及び経路［ａ，Ａ，ｂ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ２］におけるグループＧＡ２の展開を実行すると、経路［ａ，Ａ，ｄ］及び経路［ａ，Ａ，ｅ］が得られる。経路［ａ，Ａ，ＧＡ３］におけるグループＧＡ３の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｍ］、経路［ａ，Ａ，ｌ］及び経路［ａ，Ａ，ｌ，ｉ］が得られる。経路［ａ，Ａ，ＧＡ４］におけるグループＧＡ４の展開及び展開後の探索を実行すると、経路［ａ，Ａ，ｎ］、経路［ａ，Ａ，ｏ］及び経路［ａ，Ａ，ｏ，ｋ］が得られる。
【００７４】
経路［ａ，Ａ，ＧＡ３，Ｃ］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ］及び経路［ａ，Ａ，ｍ，Ｃ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ］におけるグループＧＡ４の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ］及び経路［ａ，Ａ，ｏ，Ｃ］が得られる。
【００７５】
経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ１］におけるグループＧＡ３及びグループＧＣ１の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ，ｆ］、経路［ａ，Ａ，ｌ，Ｃ，ｒ］、経路［ａ，Ａ，ｍ，Ｃ，ｆ］及び経路［ａ，Ａ，ｍ，Ｃ，ｒ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ２］におけるグループＧＡ３及びグループＧＣ２の展開を実行すると、経路［ａ，Ａ，ｍ，Ｃ，ｌ］及び経路［ａ，Ａ，ｌ，Ｃ，ｍ］が得られる。経路［ａ，Ａ，ＧＡ３，Ｃ，ＧＣ３］におけるグループＧＡ３の展開を実行すると、経路［ａ，Ａ，ｌ，Ｃ，ｎ］、経路［ａ，Ａ，ｍ，Ｃ，ｎ］、経路［ａ，Ａ，ｌ，Ｃ，ｏ］及び経路［ａ，Ａ，ｍ，Ｃ，ｏ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ１］におけるグループＧＡ４及びグループＧＣ１の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｎ，Ｃ，ｒ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］及び経路［ａ，Ａ，ｏ，Ｃ，ｒ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ２］におけるグループＧＡ４及びグループＧＣ２の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｌ］、経路［ａ，Ａ，ｎ，Ｃ，ｍ］、経路［ａ，Ａ，ｏ，Ｃ，ｌ］及び経路［ａ，Ａ，ｏ，Ｃ，ｍ］が得られる。経路［ａ，Ａ，ＧＡ４，Ｃ，ＧＣ３］におけるグループＧＡ４及びグループＧＣ３の展開を実行すると、経路［ａ，Ａ，ｎ，Ｃ，ｏ］及び経路［ａ，Ａ，ｏ，Ｃ，ｎ］が得られる。
【００７６】
（※）は、隣接頂点が存在するためさらなる探索が可能な経路である。
【００７７】
図１６は、図１５に示された経路のうち一部の経路についてさらなる探索を実行した場合の結果を示す図である。経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］、経路［ａ，Ａ，ｍ，Ｃ，ｌ］、経路［ａ，Ａ，ｎ，Ｃ，ｆ］、経路［ａ，Ａ，ｏ，Ｃ，ｆ］及び経路［ａ，Ａ，ｎ，Ｃ，ｌ］は、フィルタ条件Ｆを満たさない。
【００７８】
経路［ａ，Ａ，ｂ，ｉ］からは経路［ａ，Ａ，ｂ，ｉ，ｌ］が得られる。経路［ａ，Ａ，ｌ，ｉ］からは経路［ａ，Ａ，ｌ，ｉ，ｂ］が得られる。経路［ａ，Ａ，ｏ，ｋ］からは経路［ａ，Ａ，ｏ，ｋ，ｇ］及び経路［ａ，Ａ，ｏ，ｋ，ｆ］が得られる。
【００７９】
以上から、探索条件及びフィルタ条件Ｆを満たす経路として経路［ａ，Ａ，ｏ，ｋ］が得られる。
【００８０】
図１７は、第１の例について本実施の形態のグラフトラバーサルを実行した場合のランダムアクセスを示す図である。例えば第１行目の情報は、経路［ａ］における最後の要素である頂点ａの隣接頂点を第１ＫＶＳ１１１から特定するためのランダムアクセスを表す。また、例えば第８行目の情報は、経路［ａ，Ａ，ＧＡ１］における最後の要素であるグループＧＡ１に属する頂点を第２ＫＶＳ１１３から特定するためのランダムアクセスを表す。このように、合計で１５回のランダムアクセスが発生する。一方、図１８は、第１の例について通常のグラフトラバーサルを実行した場合のランダムアクセスを示す図である。このように、合計で３０回のランダムアクセスが発生する。
【００８１】
このように、本実施の形態のグラフトラバーサルを実行すれば、ランダムアクセスの回数を減らすことができるので、最終的にグラフトラバーサルを完了するまでの時間を短縮することができるようになる。
【００８２】
なお、本実施の形態の方法は、図３乃至図６に示したような無向グラフだけではなく、例えば図１９に示すような、或る頂点（図１９においては頂点ａ）を始点とする有向グラフに対しても適用可能である。図１９においてはエッジの数が４以上である頂点がハブであり、ハブは頂点Ａ、頂点Ｂ、頂点Ｃ、頂点Ｄ及び頂点Ｅである。ハブＡには、頂点ａ、頂点ｂ、頂点ｃ、頂点ｄ、頂点ｅ、頂点ｆ、頂点ｇ及び頂点Ｅが接続されている。
【００８３】
このようなケースにおいては、例えば図２０に示すようにグループ化が実行される。図２０の例においては、ハブＡ及びハブＢに接続されている頂点ｂ及び頂点ｃはグループＧＡ１に属し、ハブＡにのみ接続されている頂点ｄ及び頂点ｅはグループＧＡ２に属し、ハブＡ、ハブＣ及びハブＤに接続されている頂点ｆ及び頂点ｇはグループＧＡ３に属し、ハブＥはいずれのグループにも属さない。
【００８４】
［実施の形態２］
第１の実施の形態においては、フィルタ条件Ｆを満たさない経路が経路探索が完了した後に一括して除外される。これに対して、第２の実施の形態においては、フィルタ条件Ｆを満たさない経路が経路探索中に除外される。そのため、複雑ネットワークの形態及びフィルタ条件Ｆの内容によっては、グラフトラバーサルに要する時間がさらに短縮される。
【００８５】
図２１は、第２の実施の形態のトラバーサル処理部１０５が実行する処理の処理フローを示す図である。本処理は、トラバーサルクエリを受信又は受け付けた場合に実行される。
【００８６】
トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図２１：ステップＳ１２１）。
【００８７】
本実施の形態において、グラフトラバーサルの経路はリストで表現される。例えば頂点ａ、頂点ｂ、頂点ｃの順に探索された場合、経路は［ａ，ｂ，ｃ］と表現される。Ｑは一時的に使用されるキューであり、Ｒは結果を格納するためのキューである。
【００８８】
グラフトラバーサルの始点である頂点をｎ０とする。ｎ０のみで構成される経路をＴ０とする。つまりＴ０＝［ｎ０］である。
【００８９】
トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ１２３）。
【００９０】
経路集合Ｑが空である場合（ステップＳ１２３：Ｙｅｓルート）、処理はステップＳ１２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ１２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ１２５）。探索終了条件はトラバーサルクエリに含まれており、経路が所定個以上見つかったという条件やグラフトラバーサルのホップ数が所定の閾値を超えたという条件等である。
【００９１】
探索終了条件が満たされない場合（ステップＳ１２５：Ｎｏルート）、処理は端子Ｃを介して図２２のステップＳ１３１の処理に移行する。
【００９２】
図２２の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図２２：ステップＳ１３１）。以下では、ステップＳ１３１において取り出された経路を経路Ｔと呼ぶ。
【００９３】
トラバーサル処理部１０５は、経路Ｔの最後の要素を特定する（ステップＳ１３３）。以下では、ステップＳ１３３において特定された要素を要素ｅと呼ぶ。要素ｅは、頂点又はグループである。例えば経路Ｔが［Ａ，Ｂ，ｃ］である場合、要素ｅは頂点ｃである。
【００９４】
トラバーサル処理部１０５は、ステップＳ１３３において特定された要素ｅがグループであるか判定する（ステップＳ１３５）。
【００９５】
要素ｅがグループである場合（ステップＳ１３５：Ｙｅｓルート）、処理は端子Ｄを介して図２３のステップＳ１４７に移行する。
【００９６】
一方、要素ｅがグループではない場合（ステップＳ１３５：Ｎｏルート）、トラバーサル処理部１０５は、経路Ｔが探索条件を満たすか判定する（ステップＳ１３７）。探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件等である。
【００９７】
経路Ｔが探索条件を満たさない場合（ステップＳ１３７：Ｎｏルート）、処理はステップＳ１４１に移行する。一方、経路Ｔが探索条件を満たす場合（ステップＳ１３７：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ１３９）。
【００９８】
トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータ及び第２ＫＶＳ１１３に格納されているデータに基づき、要素ｅの隣接頂点のうち未訪問の隣接頂点の集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］、及び、要素ｅの隣接グループの集合Ｇ＝［ｇ１，ｇ２，ｇ３，．．．］を特定する（ステップＳ１４１）。ここで、未訪問である頂点とは経路Ｔに含まれない頂点を意味する。以下においても同様とする。
【００９９】
トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］及び経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１、経路ＴＭ２、経路ＴＭ３、・・・のうちフィルタ条件Ｆを満たす経路を経路集合Ｑに追加する（ステップＳ１４３）。フィルタ条件Ｆはトラバーサルクエリに含まれており、例えば、ホップ数が所定値以上であるという条件や或る頂点を経由するという条件等である。
【０１００】
トラバーサル処理部１０５は、経路ＴＧ１＝Ｔ＋［ｇ１］、経路ＴＧ２＝Ｔ＋［ｇ２］、経路ＴＧ３＝Ｔ＋［ｇ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＧ１、経路ＴＧ２及び経路ＴＧ３、・・・を経路集合Ｑに追加する（ステップＳ１４５）。但し、Ｇが空集合である場合にはステップＳ１４５の処理はスキップされる。そして処理は端子Ｅを介して図２１のステップＳ１２３に戻る。
【０１０１】
端子Ｄを介して図２３の説明に移行し、トラバーサル処理部１０５は、経路Ｔからグループｅを取り除いた経路である経路Ｔｘを生成する（図２３：ステップＳ１４７）。
【０１０２】
トラバーサル処理部１０５は、第２ＫＶＳ１１３に格納されているデータに基づき、グループｅに隣接するハブのうち未訪問のハブの集合Ｈ＝［ｈ１，ｈ２，ｈ３，．．．］を特定する（ステップＳ１４９）。上で述べたように、同じグループに属する頂点は同じハブに接続される。ステップＳ１４９においては、１回のランダムアクセスによってグループ内の各頂点に隣接するハブが一括して特定されることになるので、各頂点についてランダムアクセスを行わなくて済むようになる。これにより、ランダムアクセスの回数を減らし、グラフトラバーサルにかかる時間を短縮できるようになる。
【０１０３】
トラバーサル処理部１０５は、グループｅに未処理の頂点が有るか判定する（ステップＳ１５０）。未処理の頂点が無い場合（ステップＳ１５０：Ｎｏルート）、処理は端子Ｅを介して図２１のステップＳ１２３に戻る。
【０１０４】
一方、グループｅに未処理の頂点が有る場合（ステップＳ１５０：Ｙｅｓルート）、トラバーサル処理部１０５は、グループｅに属する頂点のうち未処理の頂点を１つ特定する（ステップＳ１５１）。以下では、ステップＳ１５１において特定された頂点を頂点ｐと呼ぶ。
【０１０５】
トラバーサル処理部１０５は、経路Ｔｐ＝Ｔｘ＋［ｐ］を生成する（ステップＳ１５３）。例えばＴｘ＝［ａ，ｂ］である場合にはＴｐ＝［ａ，ｂ，ｐ］である。
【０１０６】
トラバーサル処理部１０５は、経路Ｔｐがフィルタ条件Ｆを満たすか判定する（ステップＳ１５５）。
【０１０７】
経路Ｔｐがフィルタ条件Ｆを満たさない場合（ステップＳ１５５：Ｎｏルート）、処理はステップＳ１５０に戻る。一方、経路Ｔｐがフィルタ条件Ｆを満たす場合（ステップＳ１５５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｐが探索条件を満たすか判定する（ステップＳ１５７）。
【０１０８】
経路Ｔｐが探索条件を満たさない場合（ステップＳ１５７：Ｎｏルート）、処理は端子Ｆを介して図２４のステップＳ１６１に移行する。一方、経路Ｔｐが探索条件を満たす場合（ステップＳ１５７：Ｙｅｓルート）、経路Ｔｐを経路集合Ｒに追加する（ステップＳ１５９）。そして処理は端子Ｆを介して図２４のステップＳ１６１に移行する。
【０１０９】
図２４の説明に移行し、トラバーサル処理部１０５は、ハブの集合Ｈに含まれるハブのうち未処理のハブを１つ特定する（図２４：ステップＳ１６１）。以下では、ステップＳ１６１において特定されたハブをハブｈと呼ぶ。
【０１１０】
トラバーサル処理部１０５は、経路Ｔｈ＝Ｔｐ＋［ｈ］を生成する（ステップＳ１６３）。
【０１１１】
トラバーサル処理部１０５は、経路Ｔｈがフィルタ条件Ｆを満たすか判定する（ステップＳ１６５）。
【０１１２】
経路Ｔｈがフィルタ条件Ｆを満たさない場合（ステップＳ１６５：Ｎｏルート）、処理はステップＳ１６９に移行する。一方、経路Ｔｈがフィルタ条件Ｆを満たす場合（ステップＳ１６５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｈを経路集合Ｑに追加する（ステップＳ１６７）。
【０１１３】
トラバーサル処理部１０５は、ハブの集合Ｈに含まれるハブのうち未処理のハブが有るか判定する（ステップＳ１６９）。未処理のハブが有る場合（ステップＳ１６９：Ｙｅｓルート）、処理はステップＳ１６１に戻る。一方、未処理のハブが無い場合（ステップＳ１６９：Ｎｏルート）、処理は端子Ｇを介して図２５のステップＳ１７１に移行する。
【０１１４】
図２５の説明に移行し、トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータに基づき、頂点ｐの隣接頂点（ここでは、ハブ以外の頂点）のうち未訪問の隣接頂点の集合Ｖから、未処理の頂点を１つ特定する（図２５：ステップＳ１７１）。以下では、ステップＳ１７１において特定された頂点を頂点ｖと呼ぶ。
【０１１５】
トラバーサル処理部１０５は、経路Ｔｖ＝Ｔｐ＋［ｖ］を生成する（ステップＳ１７３）。
【０１１６】
トラバーサル処理部１０５は、経路Ｔｖがフィルタ条件Ｆを満たすか判定する（ステップＳ１７５）。
【０１１７】
経路Ｔｖがフィルタ条件Ｆを満たさない場合（ステップＳ１７５：Ｎｏルート）、処理はステップＳ１７９に移行する。一方、経路Ｔｖがフィルタ条件Ｆを満たす場合（ステップＳ１７５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔｖを経路集合Ｑに追加する（ステップＳ１７７）。
【０１１８】
トラバーサル処理部１０５は、未処理の頂点が有るか判定する（ステップＳ１７９）。
【０１１９】
未処理の頂点が有る場合（ステップＳ１７９：Ｙｅｓルート）、処理はステップＳ１７１に戻る。一方、未処理の頂点が無い場合（ステップＳ１７９：Ｎｏルート）、処理は端子Ｈを介してステップＳ１５０の処理に戻る。
【０１２０】
図２１の説明に戻り、探索終了条件が満たされる場合（ステップＳ１２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路のうち、フィルタ条件Ｆを満たす経路を特定する（ステップＳ１２７）。
【０１２１】
トラバーサル処理部１０５は、ステップＳ１２７において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ１２９）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。
【０１２２】
通常のグラフトラバーサルには、探索される頂点の数とランダムアクセスの回数とがほぼ一致するという特徴がある。これに対して、本実施の形態の方法においては、ハブに基づいて頂点がグループ化されており、複数の頂点に対して１回のランダムアクセスが実行される。これにより、経路がハブを経由する場合であっても、ランダムアクセスの回数の増加が原因となり処理時間が増大することを抑制できるようになる。複雑ネットワークによっては、処理時間の桁数を大幅に減らすことができる。
【０１２３】
また、第２の実施の形態においては、フィルタ条件Ｆを満たさない経路はステップＳ１４３において経路集合Ｑに追加されない。従って、特にフィルタ条件Ｆの条件が厳しい場合には、フィルタ条件Ｆによって多くの経路が探索の対象から外されるようになるのでグラフトラバーサルにかかる時間を短縮できるようになる。
【０１２４】
複雑ネットワークは疎な部分が占める割合が大きいにもかかわらず、疎な部分での処理によっては性能問題が発生しないため、複雑ネットワーク全体に対して前処理を実行すること及びインデックスを生成することは効率的ではない。本実施の形態においては、性能問題の原因であるハブに限定してグループ化を実行しており、効率的な対策が実現されている。
【０１２５】
また、本実施の形態の方法は、オンメモリでの処理が困難である大規模グラフに対しても有効である。
【０１２６】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した情報処理装置１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【０１２７】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【０１２８】
例えば、グラフトラバーサルと展開とを並行して実行することで処理時間を短縮してもよい。
【０１２９】
［付録］
本付録においては、通常のグラフトラバーサルにおいて実行される処理について説明する。図２６は、通常のグラフトラバーサルにおいて実行される処理の処理フローを示す図である。
【０１３０】
トラバーサル処理部１０５は、トラバーサル処理についての初期化を実行する。具体的には、トラバーサル処理部１０５は、経路集合ＱをＱ＝［Ｔ０］と設定し且つ経路集合ＲをＲ＝［］と設定する（図２６：ステップＳ２２１）。
【０１３１】
トラバーサル処理部１０５は、経路集合Ｑが空であるか判定する（ステップＳ２２３）。
【０１３２】
経路集合Ｑが空である場合（ステップＳ２２３：Ｙｅｓルート）、処理はステップＳ２２７に移行する。一方、経路集合Ｑが空ではない場合（ステップＳ２２３：Ｎｏルート）、トラバーサル処理部１０５は、探索終了条件が満たされるか判定する（ステップＳ２２５）。
【０１３３】
探索終了条件が満たされない場合（ステップＳ２２５：Ｎｏルート）、処理は端子Ｉを介して図２７のステップＳ２３１の処理に移行する。
【０１３４】
図２７の説明に移行し、トラバーサル処理部１０５は、経路集合Ｑにおける経路を１つ取り出す（図２７：ステップＳ２３１）。以下では、ステップＳ２３１において取り出された経路を経路Ｔと呼ぶ。
【０１３５】
トラバーサル処理部１０５は、経路Ｔが探索条件を満たすか判定する（ステップＳ２３３）。探索条件はトラバーサルクエリに含まれており、例えば、頂点ａを始点とし且つ頂点ｋを終点とする経路であるという条件、といった条件である。
【０１３６】
経路Ｔが探索条件を満たさない場合（ステップＳ２３３：Ｎｏルート）、処理はステップＳ２３７に移行する。
【０１３７】
一方、経路Ｔが探索条件を満たす場合（ステップＳ２３３：Ｙｅｓルート）、トラバーサル処理部１０５は、経路Ｔを経路集合Ｒに追加する（ステップＳ２３５）。
【０１３８】
トラバーサル処理部１０５は、経路Ｔの最後の頂点である頂点ｎを特定する（ステップＳ２３７）。
【０１３９】
トラバーサル処理部１０５は、第１ＫＶＳ１１１に格納されているデータに基づき、頂点ｎの隣接頂点を特定する。そして、トラバーサル処理部１０５は、頂点ｎの隣接頂点のうち未処理の隣接頂点の集合Ｍ＝［ｍ１，ｍ２，ｍ３，．．．］を特定する（ステップＳ２３９）。
【０１４０】
トラバーサル処理部１０５は、経路ＴＭ１＝Ｔ＋［ｍ１］、経路ＴＭ２＝Ｔ＋［ｍ２］、経路ＴＭ３＝Ｔ＋［ｍ３］、・・・を生成する。そして、トラバーサル処理部１０５は、経路ＴＭ１、経路ＴＭ２、経路ＴＭ３、・・・を経路集合Ｑに追加する（ステップＳ２４１）。そして処理は端子Ｊを介して図２６のステップＳ２２３に戻る。
【０１４１】
図２６の説明に戻り、探索終了条件が満たされる場合（ステップＳ２２５：Ｙｅｓルート）、トラバーサル処理部１０５は、経路集合Ｑにおける経路及び経路集合Ｒにおける経路のうち、フィルタ条件Ｆを満たす経路を特定する（ステップＳ２２７）。
【０１４２】
トラバーサル処理部１０５は、ステップＳ２２７において特定された経路の情報（例えば、経路に含まれる頂点の識別情報が順序通りに並んだ情報）を出力データ格納部１１５に格納する（ステップＳ２２９）。そして処理は終了する。なお、トラバーサル処理部１０５は出力データ格納部１１５に格納された経路の情報を出力（例えば、表示部への表示又はトラバーサルクエリの送信元への送信）してもよい。
【０１４３】
このように、通常のグラフトラバーサルは、頂点をキーとし且つ隣接頂点をバリューとする第１ＫＶＳ１１１を繰り返し参照することにより進行する。
【０１４４】
なお、ここでは単純な幅優先探索に基づくグラフトラバーサルの例を示したが、例えば、深さ優先探索に基づくグラフトラバーサルや訪問済みの頂点には再訪問しないグラフトラバーサルなど、グラフトラバーサルには種々のバリエーションがある。
【０１４５】
以上で付録を終了する。
【０１４６】
なお、上で述べた情報処理装置１は、コンピュータ装置であって、図２８に示すように、メモリ２５０１とＣＰＵ２５０３とソリッドステートドライブ２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＳＳＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＳＳＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＳＳＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＳＳＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＳＳＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１４７】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１４８】
本実施の形態の第１の態様に係る情報処理装置は、（Ａ）所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出されたハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部（実施の形態における第２ＫＶＳ１１３は上記記憶部の一例である）に格納するグループ化部（実施の形態におけるグループ化部１０３は上記グループ化部の一例である）と、（Ｂ）複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部（実施の形態におけるトラバーサル処理部１０５は上記トラバーサル処理部の一例である）とを有する。
【０１４９】
複雑ネットワークに対するグラフトラバーサルにおいては、多数のエッジを有するハブが原因となり、ランダムアクセスの回数が増加して処理時間が長くなる。そこで、上で述べたような処理を実行すれば、頂点単位ではなくグループ単位でランダムアクセスが行われるので、複雑ネットワークに対するグラフトラバーサルに要する時間を短縮できるようになる。
【０１５０】
また、上記グループ化部は、（ａ１）ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行してもよい。
【０１５１】
ランダムアクセスの回数が少なくなるようにグループ化することができるようになる。
【０１５２】
また、上記所定数は、記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数であってもよい。
【０１５３】
処理時間の増加をもたらすハブを適切に抽出できるようになる。
【０１５４】
また、上記トラバーサル処理部は、（ｂ１）グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された複数の経路のうち所定の条件を満たす経路を特定してもよい。
【０１５５】
展開を一括して実行することができるようになる。
【０１５６】
また、上記トラバーサル処理部は、（ｂ２）グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路についてグラフトラバーサルを実行することで複数の経路を生成してもよい。
【０１５７】
所定の条件を満たさない経路を途中で除外することができるようになる。
【０１５８】
また、上記所定の条件は、グラフトラバーサルのクエリに含まれてもよい。
【０１５９】
本実施の形態の第２の態様に係る情報処理方法は、（Ｃ）所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、（Ｄ）抽出されたハブに隣接する頂点をグループ化し、（Ｅ）グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、（Ｆ）複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして記憶部から特定し、（Ｇ）グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する処理を含む。
【０１６０】
なお、上記方法による処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１６１】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１６２】
（付記１）
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、抽出された前記ハブに隣接する頂点をグループ化し、グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納するグループ化部と、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成するトラバーサル処理部と、
を有する情報処理装置。
【０１６３】
（付記２）
前記グループ化部は、
前記ハブが複数抽出された場合、隣接するハブの組み合わせが同じである頂点が同じグループに属するようにグループ化を実行する、
付記１記載の情報処理装置。
【０１６４】
（付記３）
前記所定数は、前記記憶部に対する１回のランダムアクセスに要する時間と１の頂点につき許容される処理時間とに基づき決定される数、又は、前記複雑ネットワークにおける頂点のうちエッジ数の多さが所定順位である頂点のエッジ数である、
付記１又は２記載の情報処理装置。
【０１６５】
（付記４）
前記トラバーサル処理部は、
前記グラフトラバーサルにより生成される経路上のグループを、当該経路の生成が完了した後に展開し、生成された前記複数の経路のうち所定の条件を満たす経路を特定する、
付記１乃至３のいずれか１つ記載の情報処理装置。
【０１６６】
（付記５）
前記トラバーサル処理部は、
前記グラフトラバーサルにより経路を生成中に当該経路上にグループを検出した場合、当該グループを展開し、展開により生成された経路のうち所定の条件を満たす経路について前記グラフトラバーサルを実行することで前記複数の経路を生成する、
付記１乃至３のいずれか１つ記載の情報処理装置。
【０１６７】
（付記６）
前記所定の条件は、前記グラフトラバーサルのクエリに含まれる、
付記４又は５記載の情報処理装置。
【０１６８】
（付記７）
コンピュータに、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行させるプログラム。
【０１６９】
（付記８）
コンピュータが、
所定数以上のエッジを有する頂点であるハブを複雑ネットワークから抽出し、
抽出された前記ハブに隣接する頂点をグループ化し、
グループに属する複数の頂点の識別情報と当該複数の頂点に隣接する頂点の識別情報とを含むグループ情報を当該グループの識別情報に対応付けて記憶部に格納し、
前記複雑ネットワークに対するグラフトラバーサルにおいて、各グループに属する複数の頂点に隣接する頂点を、当該グループの識別情報をキーとして前記記憶部から特定し、
前記グラフトラバーサルにより生成される経路上のグループを当該グループのグループ情報に基づき展開して複数の経路を生成する、
処理を実行する情報処理方法。
【符号の説明】
【０１７０】
１  情報処理装置    １０１  ネットワーク管理部
１０３  グループ化部    １０５  トラバーサル処理部
１１１  第１ＫＶＳ    １１３  第２ＫＶＳ
１１５  出力データ格納部
【図１】
2019091257.tif 000003
【図２】
2019091257.tif 000004
【図３】
2019091257.tif 000005
【図４】
2019091257.tif 000006
【図５】
2019091257.tif 000007
【図６】
2019091257.tif 000008
【図７】
2019091257.tif 000009
【図８Ａ】
2019091257.tif 000010
【図８Ｂ】
2019091257.tif 000011
【図９】
2019091257.tif 000012
【図１０】
2019091257.tif 000013
【図１１】
2019091257.tif 000014
【図１２】
2019091257.tif 000015
【図１３】
2019091257.tif 000016
【図１４】
2019091257.tif 000017
【図１５】
2019091257.tif 000018
【図１６】
2019091257.tif 000019
【図１７】
2019091257.tif 000020
【図１８】
2019091257.tif 000021
【図１９】
2019091257.tif 000022
【図２０】
2019091257.tif 000023
【図２１】
2019091257.tif 000024
【図２２】
2019091257.tif 000025
【図２３】
2019091257.tif 000026
【図２４】
2019091257.tif 000027
【図２５】
2019091257.tif 000028
【図２６】
2019091257.tif 000029
【図２７】
2019091257.tif 000030
【図２８】
2019091257.tif 000031