(57)【要約】【課題】第１対象と第２対象との関係を含む原関係ネットワークを二重化関係ネットワークに変換する関係ネットワーク変換装置を提供する。【解決手段】関係ネットワーク変換装置は、第1対象を表す第1対象点と、第2対象を表す第2対象点と、第1対象点から第2対象点へ向かう有向辺とを含む原関係ネットワークから、第1対象点に対応する超頂点321、322を設定し、第2対象点に対応する超頂点323、324を設定し、制御点325、326を設定し、制御点325と326とを結合する制御辺333を設定し、超頂点321から制御点325への制御辺341、超頂点324から制御点326への制御辺343、制御点325から超頂点322への制御辺344、制御点326から超頂点323への制御辺342を設定し、二重化関係ネットワークを生成する。【選択図】図１５
2010287155.tif 000002
【特許請求の範囲】
【請求項１】
第１対象と第２対象との関係を含む原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換する関係ネットワーク変換装置であって、
第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得手段と、
取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成手段と、
生成した二重化関係ネットワークを出力する出力手段と
を備えることを特徴とする関係ネットワーク変換装置。
【請求項２】
前記生成手段は、前記第１有向経路に対して、第１減衰率を設定し、前記第２有向経路に対して、前記第１減衰率とは異なる第２減衰率を設定し、
前記第１減衰率は、第１有向経路を経ることにより、第１対象から第２対象への関係度合いが減衰する率を示し、前記第２減衰率は、第２有向経路を経ることにより、第２対象から第１対象への関係度合いが減衰する率を示す
ことを特徴とする請求項１に記載の関係ネットワーク変換装置。
【請求項３】
前記生成手段は、前記第１有向経路及び前記第２有向経路の両方の有向経路上に、２個以上の制御点を設ける
ことを特徴とする請求項２に記載の関係ネットワーク変換装置。
【請求項４】
前記生成手段は、前記第１有向経路及び前記第２有向経路の両方の有向経路上に、第１制御点及び第２制御点を設け、前記第１制御点と前記第２制御点とを連結し、向きが無く、第１制御点と第２制御点との間を経ることにより、第１制御点と第２制御点との間の関係度合いが減衰すること無く、前記有向辺が有するフロー容量と同一のフロー容量を有する非減衰制御辺を生成する
ことを特徴とする請求項３に記載の関係ネットワーク変換装置。
【請求項５】
前記生成手段は、前記第１対象点に対応して、第１超頂点及び第２超頂点を生成し、第１超頂点及び第２超頂点を連結し、向きが無く、第１超頂点と第２超頂点との間を経ることにより、第１超頂点と第２超頂点との間の関係度合いが減衰することが無く、所定のフロー容量を有する超頂点間辺を生成する
ことを特徴とする請求項４に記載の関係ネットワーク変換装置。
【請求項６】
前記生成手段は、前記第２対象点に対応して、第３超頂点及び第４超頂点を生成し、第３超頂点及び第４超頂点を連結し、向きが無く、第３超頂点と第４超頂点との間を経ることにより、第３超頂点と第４超頂点との間の関係度合いが減衰することが無く、所定のフロー容量を有する超頂点間辺を生成する
ことを特徴とする請求項５に記載の関係ネットワーク変換装置。
【請求項７】
前記生成手段は、第１超頂点から第１制御点へ向かう第１減衰制御辺、第１制御点から第２超頂点へ向かう第２減衰制御辺、第２制御点から第３超頂点へ向かう第３減衰制御辺及び第４超頂点から第２制御点へ向かう第４減衰制御辺を生成し、
各減衰制御辺は、減衰率を有し、前記有向辺が有するフロー容量と同一のフロー容量を有し、
第１減衰制御辺が有する減衰率と第３減衰制御辺が有する減衰率とを乗じて、前記第１減衰率が得られ、第２減衰制御辺が有する減衰率と第４減衰制御辺が有する減衰率とを乗じて、前記第２減衰率が得られる
ことを特徴とする請求項６に記載の関係ネットワーク変換装置。
【請求項８】
第１対象と第２対象とを関連付ける縁を検索する縁検索システムであって、
第１対象と第２対象との関係を含む原関係ネットワークを生成する関係ネットワーク生成装置と、
前記原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換する関係ネットワーク変換装置と、
前記二重化関係ネットワークを用いて、第１対象と第２対象とを関連付ける縁を検索する縁検索装置とから構成され、
前記関係ネットワーク変換装置は、
第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得手段と、
取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成手段と、
生成した二重化関係ネットワークを出力する出力手段と
を備えることを特徴とする縁検索システム。
【請求項９】
第１対象と第２対象との関係を含む原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換する関係ネットワーク変換装置で用いられる関係ネットワーク変換方法であって、
第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得ステップと、
取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成ステップと、
生成した二重化関係ネットワークを出力する出力ステップと
を含むことを特徴とする関係ネットワーク変換方法。
【請求項１０】
第１対象と第２対象との関係を含む原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換するコンピュータである関係ネットワーク変換装置で用いられる関係ネットワーク変換のためのコンピュータプログラムであって、
前記コンピュータに対して、
第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得ステップと、
取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成ステップと、
生成した二重化関係ネットワークを出力する出力ステップと
を実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一の対象と他の対象との関係を含む関係ネットワークから、一の対象と他の対象との間を仲介し、関連付ける縁（えん、えにし）を発見する技術に関し、特に、関係ネットワークを、縁を発見するために計算効率のよい関係ネットワークに変換する技術に関する。
【背景技術】
【０００２】
商品を販売する際に、商品の販売者と購入者と間の人的関係、つまり人脈が重要であり、その人脈が商品の売上に影響することがある。このような場合に備えて、特許文献１は、人物同士の関係を自動収集して、人脈マップなどの形で直感的に分かりやすく表示する技術を開示している。また、特許文献２は、ある人物が他の人物を高く評価する場合に、その状況を表現するために、当該人物による他の人物に対する向きのある関連を検出し、その関連に基づいて、人物と人物との間の関連性を評価する技術を開示している。このような人脈や人的関係は、一般に、縁（えん、えにし）と呼ばれる。
【０００３】
人と人との関係に限らず、物と物との関係や、情報と情報との関係などを表現する場合には、人、物、情報を点で表し、その関係を辺で表し、点（頂点、ノードなどとも呼ばれる。）と辺（枝、エッジなどとも呼ばれる。）から構成されるグラフを用いる。ここでは、インターネットや通信のネットワークと区別するために、人と人との関係、物と物との関係、情報と情報との関係など、対象と対象との関係を、関係ネットワークを呼ぶことにする。
【０００４】
関係ネットワークから一の対象と他の対象とを関連付ける縁を発見することは、関係ネットワークの減衰流最大化問題を解くことに帰着させることができる。ここで、減衰流最大化問題(generalized maximum flow problem)は、最大フロー問題の一般化であり、各辺にフローの減衰率が与えられている。減衰流最大化問題の解法としては、Wayneのアルゴリズムなどが知られている。
【０００５】
次に、関係ネットワークから一の対象と他の対象とを関連付ける縁を発見する場合において、減衰流最大化問題の解決手法をどのように適用するかについて、以下に簡単に説明する。
上記のように、対象を点で表し、対象と対象との直接の関係を向きのある辺で表し、点と辺とから構成されるグラフ（有向グラフと呼ぶこともある。）に、一の始点から一の終点に向けて、できる限り多くのフローを流すものとする。ここで、始点は、上記の一の対象に対応し、終点は、上記の他の対象に対応する。各辺には、そのフローを流すための容量が設定されており、例えば、全ての辺の容量は、「１」であるとする。このように想定したときに、このグラフにおいて、始点から終点への１本以上のパスであって、辺を共有しないものをできるだけ多く求めることができれば、これらのパスを、関係ネットワークにおいて一の対象と他の対象とを関連付ける縁とすることができる。ここで、グラフにおいて、始点から終点への、辺を共有しない短いパスが、できるだけ多い方が、関係ネットワークにおいて、一の対象と他の対象とを関連付ける縁が強いと言える。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１０８１２３号公報
【特許文献２】特開２００７−１２８１６３号公報
【非特許文献】
【０００７】
【非特許文献１】Kevin Daniel Wayne, Generalized Maximum Flow Algorithm. PhD Thesis, Cornell University,1999.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献２に開示されているように、人物（第１人物と呼ぶ。）と他の人物（第２人物と呼ぶ。）との関係には、向きが存在するので、このような場合に関係ネットワークを、向きのある辺を含む有向グラフにより表現することにより、減衰流最大化問題の解決手法を適用することができる。
しかし、第１人物と第２人物との関係は、第１人物から第２人物への一方向だけでなく、第２人物から第１人物への向きの関係も存在しうる。
【０００９】
このため、関係ネットワークから一の対象と他の対象とを関連付ける縁を発見する場合、特許文献２における開示において、第１人物と第２人物との関係の両方向の向きを考慮すると、第１人物から第２人物への向きの辺を含む第１有向グラフと、第２人物から第１人物への向きの辺を含む第２有向グラフとの両方について、減衰流最大化問題の解決手法の対象としなければならない。さらに、有向グラフに含まれる全ての辺について、両方向の向きを考慮すると、２の［有向グラフに含まれる辺の数］乗個のグラフについて、減衰流最大化問題の解決手法の対象としなければならない。このため、考慮すべき有向グラフの数が多すぎ、実時間においてこの問題を解くには、計算量的に困難であるという問題がある。
【課題を解決するための手段】
【００１０】
本発明は、上記の問題点を解決するために、関係ネットワークから第１の対象と第２の対象とを関連付ける縁を発見する際に、関係ネットワークを表す有向グラフにおいて、各辺について、両方向の向きを考慮した上で、実時間においてこの問題を解くことができるように、関係ネットワークを変換して二重化関係ネットワークを生成する関係ネットワーク変換装置、関係ネットワーク変換方法及びコンピュータプログラム並びに縁検索システムを提供することを目的とする。
【００１１】
上記目的を達成するために、本発明は、第１対象と第２対象との関係を含む原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換する関係ネットワーク変換装置であって、第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得手段と、取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成手段と、生成した二重化関係ネットワークを出力する出力手段とを備えることを特徴とする。
【発明の効果】
【００１２】
この構成によると、生成された二重化関係ネットワークは、原関係ネットワークの有向辺に代えて、前記有向辺と同一方向の第１有向経路と、前記有向辺と反対方向で、前記第１有向経路と排他的に作用する第２有向経路とを含むので、生成された二重化関係ネットワークに対して、減衰流最大化問題の解決手法を適用することにより、検索対象となる関係ネットワークの数を増やすことなく、両方向の向きを考慮して縁検索を行うことができるという優れた効果を奏する。
【００１３】
ここで、前記生成手段は、前記第１有向経路に対して、第１減衰率を設定し、前記第２有向経路に対して、前記第１減衰率とは異なる第２減衰率を設定し、前記第１減衰率は、第１有向経路を経ることにより、第１対象から第２対象への関係度合いが減衰する率を示し、前記第２減衰率は、第２有向経路を経ることにより、第２対象から第１対象への関係度合いが減衰する率を示すとしてもよい。
【００１４】
この構成によると、第２有向経路に対して設定される減衰率は、第１有向経路に対して設定される減衰率と異なっている。第１対象から第２対象への関係の度合いと、第２対象から第１対象への関係の度合いは、現実の場面では、異なることが普通であると考えられ、このようなケースに対しても適切に対応することができる。
ここで、前記生成手段は、前記第１有向経路及び前記第２有向経路の両方の有向経路上に、２個以上の制御点を設けるとしてもよい。
【００１５】
ここで、前記生成手段は、前記第１有向経路及び前記第２有向経路の両方の有向経路上に、第１制御点及び第２制御点を設け、前記第１制御点と前記第２制御点とを連結し、向きが無く、第１制御点と第２制御点との間を経ることにより、第１制御点と第２制御点との間の関係度合いが減衰すること無く、前記有向辺が有するフロー容量と同一のフロー容量を有する非減衰制御辺を生成するとしてもよい。
【００１６】
この構成によると、第１有向経路と第２有効経路の両方に重複して、ただ一つの非減衰制御辺が生成されるので、この一つの非減衰制御辺の存在により、第１有向経路と第２有向経路とを、排他的に作用させることができる。
ここで、前記生成手段は、前記第１対象点に対応して、第１超頂点及び第２超頂点を生成し、第１超頂点及び第２超頂点を連結し、向きが無く、第１超頂点と第２超頂点との間を経ることにより、第１超頂点と第２超頂点との間の関係度合いが減衰することが無く、所定のフロー容量を有する超頂点間辺を生成するとしてもよい。また、前記生成手段は、前記第２対象点に対応して、第３超頂点及び第４超頂点を生成し、第３超頂点及び第４超頂点を連結し、向きが無く、第３超頂点と第４超頂点との間を経ることにより、第３超頂点と第４超頂点との間の関係度合いが減衰することが無く、所定のフロー容量を有する超頂点間辺を生成するとしてもよい。
【００１７】
この構成によると、原関係ネットワークの有向辺の一端の対象点に対して、２個の超頂点を生成するので、前記有向辺への入力と、前記有向辺からの出力とを、それぞれの２個の超頂点に担わせることができる。こうして、両方向の経路を実現することができる。
ここで、前記生成手段は、第１超頂点から第１制御点へ向かう第１減衰制御辺、第１制御点から第２超頂点へ向かう第２減衰制御辺、第２制御点から第３超頂点へ向かう第３減衰制御辺及び第４超頂点から第２制御点へ向かう第４減衰制御辺を生成し、各減衰制御辺は、減衰率を有し、前記有向辺が有するフロー容量と同一のフロー容量を有し、第１減衰制御辺が有する減衰率と第３減衰制御辺が有する減衰率とを乗じて、前記第１減衰率が得られ、第２減衰制御辺が有する減衰率と第４減衰制御辺が有する減衰率とを乗じて、前記第２減衰率が得られるとしてもよい。
【００１８】
この構成によると、第１超頂点から第１制御点へ向かう第１減衰制御辺、第１制御点から第２超頂点へ向かう第２減衰制御辺、第２制御点から第３超頂点へ向かう第３減衰制御辺及び第４超頂点から第２制御点へ向かう第４減衰制御辺が生成されるので、各減衰制御辺に一方向の経路を担わせ、これにより、両方向の経路を実現することができる。
また、本発明は、第１対象と第２対象とを関連付ける縁を検索する縁検索システムであって、第１対象と第２対象との関係を含む原関係ネットワークを生成する関係ネットワーク生成装置と、前記原関係ネットワークを、第１対象と第２対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークに変換する関係ネットワーク変換装置と、前記二重化関係ネットワークを用いて、第１対象と第２対象とを関連付ける縁を検索する縁検索装置とから構成され、前記関係ネットワーク変換装置は、第１対象を表す第１対象点と、第２対象を表す第２対象点と、第１対象点から第２対象点へ向かう有向辺とを含む原関係ネットワークを取得する取得手段と、取得した原関係ネットワークに含まれる第１対象点、第２対象点及び有向辺を用いて、第１対象点から第２対象点へ向かい、前記有向辺に対応する第１有向経路と、第２対象点から第１対象点へ向かい、前記第１有向経路と排他的に作用する第２有向経路とを生成し、原関係ネットワークの前記有向辺に代えて、前記第１有向経路及び前記第２有向経路を含む二重化関係ネットワークを生成する生成手段と、生成した二重化関係ネットワークを出力する出力手段とを備えることを特徴とする。
【００１９】
この構成によると、生成された二重化関係ネットワークは、原関係ネットワークの有向辺に代えて、前記有向辺と同一方向の第１有向経路と、前記有向辺と反対方向で、前記第１有向経路と排他的に作用する第２有向経路とを含むので、縁検索装置によって、生成された二重化関係ネットワークに対して、減衰流最大化問題の解決手法を適用することにより、検索対象となる関係ネットワークの数を増やすことなく、両方向の向きを考慮して縁検索を行うことができるという優れた効果を奏する。
【図面の簡単な説明】
【００２０】
【図１】縁検索システム１０の構成を示す全体構成図である。
【図２】Ｗｅｂサーバ装置１００の構成を示すブロック図である。
【図３】各ＰＣ５０ａ、５０ｂ、・・・、５０ｃにおいて表示されるべき画面画像の一例を示す。
【図４】関係ネットワーク収集生成装置２００の構成を示すブロック図である。
【図５】収集された複数のマークアップ言語間のリンクを示す。
【図６】オリジナル対応テーブル７３１のデータ構造を示す。
【図７】関係ネットワークの一例を示す。
【図８】オリジナル辺テーブル７４１のデータ構造を示す。
【図９】オリジナル点テーブル７５１のデータ構造を示す。
【図１０】オリジナル関係ネットワーク２４１の構成を示す。
【図１１】オリジナル関係ネットワーク２４１に対応するオリジナル辺テーブル２７１のデータ構造を示す。
【図１２】オリジナル関係ネットワーク２４１に対応するオリジナル点テーブル２８１のデータ構造を示す。
【図１３】関係ネットワーク変換装置３００の構成を示すブロック図である。
【図１４】オリジナル関係ネットワーク内に含まれる部分ネットワーク３１０の構成を示す。
【図１５】図１４に示す部分ネットワーク３１０を含むオリジナル関係ネットワークを変換して、得られた二重化関係ネットワークの一部である部分ネットワーク３２０の構成を示す。
【図１６】超頂点対テーブル３６１のデータ構造を示す。
【図１７】制御点対テーブル３７１のデータ構造を示す。
【図１８】source-destinationテーブル３８１のデータ構造を示す。
【図１９】超頂点間辺テーブル３９１のデータ構造を示す。
【図２０】二重化辺テーブル５０１のデータ構造を示す。
【図２１】縁検索装置４００の構成を示すブロック図である。
【図２２】二重化縁情報テーブル４２１のデータ構造を示す。
【図２３】二重化点連鎖情報テーブル４３１のデータ構造を示す。
【図２４】目的縁情報テーブル４４１のデータ構造を示す。
【図２５】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の超頂点を含む。
【図２６】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の制御点を含む。
【図２７】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。始点及び終点を含む。
【図２８】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の超頂点間辺を含む。
【図２９】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の非減衰制御辺を含む。
【図３０】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。減衰制御辺を含む。
【図３１】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。減衰制御辺を含む。
【図３２】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の減衰制御辺及び非減衰制御辺を含む。
【図３３】二重化関係ネットワークが生成されるまでの過程におけるネットワーク図である。複数の減衰制御辺及び非減衰制御辺を含む。
【図３４】最終的に生成された二重化関係ネットワークを示すネットワーク図である。始点からの辺及び終点への辺を含む。
【図３５】縁検索システム１０の全体の動作を示すフローチャートである。
【図３６】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図３７へ続く。
【図３７】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図３８へ続く。
【図３８】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図３９へ続く。
【図３９】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図４０へ続く。
【図４０】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図４１へ続く。
【図４１】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図４２へ続く。
【図４２】関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作を示すフローチャートである。図４１から続く。
【図４３】縁検索装置４００の縁検索部４０４及び描画部４０５による関係ネットワーク図の生成の動作を示すフローチャートである。図４４へ続く。
【図４４】縁検索装置４００の縁検索部４０４及び描画部４０５による関係ネットワーク図の生成の動作を示すフローチャートである。図４３から続く。
【図４５】縁検索部４０４による二重化点連鎖情報の処理を示すフローチャートである。
【図４６】流量最大の減衰流を示すグラフである。
【図４７】（ａ）オリジナルの有向ネットワークを示すグラフである。（ｂ）オリジナルの有向ネットワークの２個の部分反転ネットワークを示すグラフである。（ｃ）二重化ネットワークを示すグラフである。
【図４８】（ａ）オリジナルの有向ネットワークの一つの辺を示すグラフである。（ｂ）オリジナルの有向ネットワークの一つの辺に対応し、その二重化辺集合を示すグラフである。
【図４９】原初正則なフローと、反転正則なフローを示す図である。
【図５０】変形例としての二重化関係ネットワークの構成を示す。
【発明を実施するための形態】
【００２１】
本発明に係る一の実施の形態としての縁検索システム１０について説明する。
１．縁検索システム１０
１．１  縁検索システム１０の全体構成
縁検索システム１０は、対象と対象との関係の集合である関係ネットワークから、一の対象（以下、始点対象と呼ぶ。またこの始点対象を示す情報を始点情報と呼ぶ。）と他の対象（以下、終点対象と呼ぶ。またこの終点対象を示す情報を終点情報と呼ぶ。）との間を仲介し、関連付ける縁を検索するための複数の装置の集合体である。
【００２２】
縁検索システム１０は、図１に示すように、Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、関係ネットワーク変換装置３００、縁検索装置４００、パーソナルコンピュータ（以下、ＰＣ）５０ａ、５０ｂ、・・・、５０ｃ、及びＷｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから構成されている。ここで、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃは、一般的なＷｅｂサーバ装置であり、各種の情報を開示する。また、ＰＣ５０ａ、５０ｂ、・・・、５０ｃは、インターネット２０へ接続して他の装置と通信を行う機能を備え、またＷｅｂブラウザ機能を備えている。
【００２３】
Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、ＰＣ５０ａ、５０ｂ、・・・、５０ｃ、及びＷｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃは、インターネット２０に接続されている。また、Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、関係ネットワーク変換装置３００及び縁検索装置４００は、ＬＡＮ（ローカルエリアネットワーク）３０に接続されている。
【００２４】
ＰＣ５０ａは、ＰＣ５０ａの利用者の操作により、始点情報と終点情報の入力を受け付け、Ｗｅｂサーバ装置１００に対して、始点対象と終点対象との間を仲介し、関連付ける縁を検索するよう要求する。関係ネットワーク収集生成装置２００は、Ｗｅｂサーバ装置１００の指示により、始点情報に関する開示情報及び終点情報に関する開示情報を、インターネット２０を介して、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから収集し、収集した開示情報を用いて、オリジナル関係ネットワークを生成する。関係ネットワーク変換装置３００は、関係ネットワーク収集生成装置２００により生成されたオリジナル関係ネットワークを変換して、始点対象と終点対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークを生成する。縁検索装置４００は、生成された二重化関係ネットワークを用いて、始点情報と終点情報との間を仲介し、関連付ける縁を検索し、また、得られた縁を基にして、始点対象と終点対象との間を仲介し、関連付ける縁を示す関係ネットワーク図を描画する。Ｗｅｂサーバ装置１００は、関係ネットワーク図を表す関係ネットワーク図データを受信し、関係ネットワーク図データを要求元のＰＣへ送信する。要求元のＰＣは、関係ネットワーク図を表示する。ＰＣ５０ｂ、・・・、ＰＣ５０ｃも、ＰＣ５０ａと同様に動作する。
【００２５】
１．２  Ｗｅｂサーバ装置１００
Ｗｅｂサーバ装置１００は、図２に示すように、制御部１０１、情報記憶部１０２、第１通信部１０３及び第２通信部１０４から構成されている。Ｗｅｂサーバ装置１００は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、通信ユニットなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、Ｗｅｂサーバ装置１００は、その機能を達成する。
【００２６】
（１）情報記憶部１０２
情報記憶部１０２は、図３に示すように、ＰＣ５０ａ、５０ｂ、・・・、５０ｃにおいて表示されるべき画面画像１１１を構成するよう定義された画面フォーマット情報を記憶している。画面フォーマット情報は、例えば、ＨＴＭＬ（HyperText Markup Language）を用いて記載されている。画面フォーマット情報は、始点情報入力部１１３、終点情報入力部１１４、関係ネットワーク図表示部１１２及び操作ボタン１１５を含んでいる。
【００２７】
始点情報入力部１１３は、ＰＣの利用者による始点情報の入力を受け付けるための入力部であり、終点情報入力部１１４は、ＰＣの利用者による終点情報の入力を受け付けるための入力部である。また、関係ネットワーク図表示部１１２は、縁検索装置４００から受信した関係ネットワーク図を表示するための表示部である。関係ネットワーク図表示部１１２に表示される関係ネットワーク図については、後述する。さらに、操作ボタン１１５は、ＰＣの利用者により操作を受け付けるための操作部である。操作ボタン１１５に対する利用者の操作により、始点情報と終点情報との間を仲介し、関連付ける縁の検索の指示が出力される。
【００２８】
関係ネットワーク図表示部１１２に表示される関係ネットワーク図は、一例して、図３に示すように、対象表示情報１２１、１２２、１２３、１２４及び１２５を含んでいる。対象表示情報１２１、１２２、１２３、１２４及び１２５は、それぞれ、文字列「織田信長」、「明智光秀」、「豊臣秀吉」、「徳川家康」及び「前田利家」を表している。
図３においては、対象表示情報１２１「織田信長」と対象表示情報１２５「前田利家」とは、対象表示情報１２２「明智光秀」を介する縁表示情報１３１により、対象表示情報１２３「豊臣秀吉」を介する縁表示情報１３２により、また、対象表示情報１２４「徳川家康」を介する縁表示情報１３３により、関連付けられていることを示している。
【００２９】
（２）制御部１０１
制御部１０１は、ＰＣ５０ａ、５０ｂ、・・・、又は５０ｃの要求により、情報記憶部１０２から画面フォーマット情報を読み出し、読み出した画面フォーマット情報を、第１通信部１０３及びインターネット２０を介して、要求元のＰＣへ送信する。次に、制御部１０１は、要求元のＰＣから、インターネット２０及び第１通信部１０３を介して、始点情報、終点情報及び縁の検索の指示を受け取る。始点情報、終点情報及び縁の検索の指示を受け取ると、制御部１０１は、始点情報、終点情報及び縁の検索の指示を、第２通信部１０４及びＬＡＮ３０を介して、関係ネットワーク収集生成装置２００へ送信する。
【００３０】
制御部１０１は、縁検索装置４００から、ＬＡＮ３０及び第２通信部１０４を介して、始点情報と終点情報との間を仲介し、関連付ける縁を示す関係ネットワーク図を受信し、受信した関係ネットワーク図を、画面フォーマット情報の関係ネットワーク図表示部１１２に埋め込み、関係ネットワーク図が埋め込まれた画面情報を、第１通信部１０３及びインターネット２０を介して、要求元のＰＣへ送信する。
【００３１】
（３）第１通信部１０３及び第２通信部１０４
第１通信部１０３は、インターネット２０を介して、ＰＣ５０ａ、５０ｂ、・・・、５０ｃに接続されており、制御部１０１とＰＣ５０ａ、５０ｂ、・・・又は５０ｃとの間で情報の送受信を行う。
第２通信部１０４は、ＬＡＮ３０を介して、関係ネットワーク収集生成装置２００及び縁検索装置４００と接続されており、制御部１０１と関係ネットワーク収集生成装置２００との間で、及び制御部１０１と縁検索装置４００との間で、情報の送受信を行う。
【００３２】
１．３  関係ネットワーク収集生成装置２００
関係ネットワーク収集生成装置２００は、図４に示すように、制御部２０１、情報記憶部２０２、第１通信部２０３、第２通信部２０４、関係ネットワーク生成部２０５及び情報収集部２０６から構成されている。関係ネットワーク収集生成装置２００は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、通信ユニットなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、関係ネットワーク収集生成装置２００は、その機能を達成する。
【００３３】
（１）制御部２０１
制御部２０１は、Ｗｅｂサーバ装置１００から、ＬＡＮ３０及び第２通信部２０４を介して、始点情報、終点情報及び縁の検索の指示を受け取る。始点情報、終点情報及び縁の検索の指示を受け取ると、情報収集部２０６へ、情報の収集指示、始点情報及び終点情報を出力する。
【００３４】
また、制御部２０１は、情報記憶部２０２、第１通信部２０３、第２通信部２０４、関係ネットワーク生成部２０５及び情報収集部２０６を制御する。
（２）情報収集部２０６及び関係ネットワーク生成部２０５
情報収集部２０６は、制御部２０１から情報の収集指示、始点情報及び終点情報を受け取る。情報の収集指示、始点情報及び終点情報を受け取ると、第１通信部２０３及びインターネット２０を介して、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから、マークアップ言語を収集する。収集の対象となるマークアップ言語は、他のマークアップ言語等へのリンクを示すタグ内に、受け取った始点情報を含むものである。
【００３５】
例えば、始点情報が「織田信長」である場合に、情報収集部２０６は、「織田信長」を含むマークアップ言語を収集する。ここで、図５に示すように、マークアップ言語２２１「織田信長.html」が収集されたとする。マークアップ言語２２１は、「明智光秀」、「豊臣秀吉」、「徳川家康」についての記述をそれぞれ含むマークアップ言語２２２「明智光秀.html」、マークアップ言語２２３「豊臣秀吉.html」、マークアップ言語２２４「徳川家康.html」へのリンクを含むものとする。さらに、具体的には、マークアップ言語２２１「織田信長.html」は、次のようなタグを含む。
<a href="http://www.rekisi.jp/mituhide.html"> 明智光秀</a>
<a href="http://www.rekisi.jp/hideyosi.html"> 豊臣秀吉</a>
<a href="http://www.rekisi.jp/ieyasu.html"> 徳川家康</a>
次に、情報収集部２０６は、収集したマークアップ言語の中から、リンクタグを検索し、つまり、<a> 及び</a>のセットを検索し、リンク先のマークアップ言語を示す文字列及び、<a> 及び</a>により囲まれる表示文字を抽出し、始点情報に関連付けて、抽出した表示文字を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込む。
【００３６】
具体的には、情報収集部２０６は、収集したマークアップ言語２２１から、「<a href="http://www.rekisi.jp/mituhide.html"> 明智光秀</a>」が検出された場合には、「http://www.rekisi.jp/mituhide.html」及び「明智光秀」を抽出し、始点情報「織田信長」に関連付けて、抽出した表示文字「明智光秀」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込む。
【００３７】
また、収集したマークアップ言語２２１には、
「<a href="http://www.rekisi.jp/hideyosi.html"> 豊臣秀吉</a>」及び
「<a href="http://www.rekisi.jp/ieyasu.html"> 徳川家康</a>」が含まれているので、上記と同様に、情報収集部２０６は、「http://www.rekisi.jp/hideyosi.html」及び「 豊臣秀吉」並びに、「http://www.rekisi.jp/ieyasu.html」及び「徳川家康」を抽出し、始点情報「織田信長」に関連付けて、抽出した表示文字「豊臣秀吉」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込み、また、始点情報「織田信長」に関連付けて、抽出した表示文字「豊臣秀吉」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込む。
【００３８】
次に、情報収集部２０６は、リンク先のマークアップ言語を取得する。ここで、図５に示すように、例えば、マークアップ言語２２２、２２３、２２４が取得される。情報収集部２０６は、取得したリンク先のマークアップ言語について、上記と同様に、リンクタグの検索、リンク先のマークアップ言語を示す文字列及び<a> 及び</a>により囲まれる表示文字の抽出を行い、前に抽出した表示文字に関連付けて、抽出した表示文字を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込む。
【００３９】
具体的には、情報収集部２０６は、表示文字「明智光秀」に関連付けて、抽出した表示文字「前田利家」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込み、表示文字「豊臣秀吉」に関連付けて、抽出した表示文字「前田利家」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込み、表示文字「徳川家康」に関連付けて、抽出した表示文字「前田利家」を情報記憶部２０２のオリジナル対応テーブル７３１へ書き込む。
【００４０】
次に、情報収集部２０６は、<a> 及び</a>により囲まれる表示文字として、終点情報が抽出されるまで、上記の処理を繰り返す。具体的には、<a> 及び</a>により囲まれる表示文字として、「前田利家」が抽出されるまで、上記の処理を繰り返す。
このようにして、一例として図５に示すように、マークアップ言語２２１、２２２、２２３、２２４及び２２５が取得されたものとする。
【００４１】
マークアップ言語２２１は、「織田信長」に関する記述を含み、マークアップ言語２２２、２２３及び２２４へのそれぞれのリンクを含む。また、マークアップ言語２２２は、「明智光秀」に関する記述を含み、マークアップ言語２２５へのリンクを含み、マークアップ言語２２３は、「豊臣秀吉」に関する記述を含み、マークアップ言語２２５へのリンクを含み、マークアップ言語２２４は、「徳川家康」に関する記述を含み、マークアップ言語２２５へのリンクを含む。さらに、マークアップ言語２２５は、「前田利家」に関する記述を含む。
【００４２】
以上説明したように、情報収集部２０６は、一例として、図６に示すように、情報記憶部２０２のオリジナル対応テーブル７３１に、「織田信長」及び「明智光秀」の組、「織田信長」及び「豊臣秀吉」の組、「織田信長」及び「徳川家康」の組、「明智光秀」及び「前田利家」の組、「豊臣秀吉」及び「前田利家」の組、及び、「徳川家康」及び「前田利家」の組を書き込む。
【００４３】
次に、関係ネットワーク生成部２０５は、上記のそれぞれの組に対して、辺番号「１」、「２」、「３」、「４」、「５」及び「６」を割り当て、「織田信長」、「明智光秀」、「豊臣秀吉」、「徳川家康」、及び「前田利家」に、それぞれ、点番号「１」、「２」、「３」、「４」及び「５」を割り当てることにより、オリジナル対応テーブル７３１を基にして、図８に示すオリジナル辺テーブル７４１を生成して情報記憶部２０２へ書き込む。
【００４４】
この時点で、オリジナル辺テーブル７４１は、６個の辺情報から構成され、各辺情報は、オリジナル対応テーブル７３１の各組に対応している。また、各辺情報は、辺番号、始点番号及び終点番号を含む。各辺番号は、オリジナル対応テーブル７３１の各組に割り当てられた辺番号であり、始点番号及び終点番号は、オリジナル対応テーブル７３１の各組に含まれる２個の表示文字に割り当てられた点番号である。
【００４５】
具体的には、オリジナル辺テーブル７４１の第１の辺情報は、辺番号「１」、始点番号「１」及び終点番号「２」を含む。ここで、辺番号「１」は、オリジナル対応テーブル７３１の「織田信長」及び「明智光秀」の組を示し、始点番号「１」及び終点番号「２」は、それぞれ、「織田信長」及び「明智光秀」を示している。
次に、関係ネットワーク生成部２０５は、オリジナル辺テーブル７４１の各辺情報に対して、容量、減衰率及び向きの有無を設定する。関係ネットワーク生成部２０５は、各容量を固定的に「１」と設定する。また、６個の減衰率を、ｇ1 、ｇ2 、・・・ 、ｇ6 と設定し、各向きの有無には、向きがあることを示すフラグを設定する。ここで、減衰率とは、当該減衰率の設定された辺を経ることにより、辺の両端の２点の対象の関係度合いが減衰する率を示す。
【００４６】
なお、図８のオリジナル辺テーブル７４１において、向きの有無「○」は、当該辺に向きが存在することを示す。また、図８のオリジナル辺テーブル７４１において例示していないが、向きの有無「×」は、当該辺に向きが存在しないことを示す。
次に、関係ネットワーク生成部２０５は、点番号「１」をsource点とし、点番号「５」をdestination点とするオリジナル点テーブル７５１を生成して情報記憶部２０２へ書き込む。
【００４７】
オリジナル点テーブル７５１は、図９に示すように、５個の点情報から構成され、各点情報は、点番号及び点属性を含む。オリジナル点テーブル７５１に含まれる点番号「１」、「２」、「３」、「４」及び「５」は、それぞれ、「織田信長」、「明智光秀」、「豊臣秀吉」、「徳川家康」、及び「前田利家」に、対して割り当てられたものである。ここで、点番号「１」は、点属性「source」とともに、点情報に含まれ、点番号「５」は、点属性「destination」とともに、点情報に含まれる。点属性「source」は、点番号「１」により示される点が、source点であることを示し、点属性「destination」は、点番号「５」により示される点が、destination点であることを示している。
【００４８】
オリジナル辺テーブル７４１及びオリジナル点テーブル７５１により示される関係ネットワークを図７に示している。この図に示すように、「織田信長」７１１は、「明智光秀」７１２、「豊臣秀吉」７１３及び「徳川家康」７１４を介して、「前田利家」７１５と関係付けられている。
次に、関係ネットワーク生成部２０５は、関係ネットワークとして、生成したオリジナル辺テーブル及びオリジナル点テーブルを、第２通信部２０４及びＬＡＮ３０を介して、関係ネットワーク変換装置３００へ送信する。
【００４９】
説明を簡略化するために、以降においては、関係ネットワークとして、図１０に示すオリジナル関係ネットワーク２４１を用いるものとする。
オリジナル関係ネットワーク２４１は、図１０に示すように、３個の点２５１、２５２及び２５３、並びに３個の辺２６１、２６２及び２６３から構成されている。辺２６１は、点２５１を始点とし、点２５２を終点とする。辺２６２は、点２５１を始点とし、点２５３を終点とする。辺２６３は、点２５３を始点とし、点２５２を終点とする。辺２６１、２６２及び２６３は、それぞれ、向きを有している。
【００５０】
オリジナル関係ネットワーク２４１に対応するオリジナル辺テーブル２７１を図１１に示し、オリジナル関係ネットワーク２４１に対応するオリジナル点テーブル２８１を図１２に示す。
オリジナル辺テーブル２７１は、図１１に示すように、複数のオリジナル辺情報から構成され、各オリジナル辺情報は、図１０に示すオリジナル関係ネットワーク２４１の各辺に対応している。各オリジナル辺情報は、辺番号、始点番号、終点番号、容量、減衰率及び向きの有無を含む。辺番号、始点番号、終点番号、容量、減衰率及び向きの有無については、図８のオリジナル辺テーブル７４１の説明において述べた通りである。
【００５１】
オリジナル点テーブル２８１は、図１２に示すように、複数の点情報から構成され、各点情報は、図１０に示すオリジナル関係ネットワーク２４１の各点に対応している。各点情報は、点番号及び点属性を含む。点番号は、図１０に示すオリジナル関係ネットワーク２４１の各点を識別する番号である。点属性は、対応する点番号により識別される点が、source点であるか、又はdestination点であるかを示す。source点は、関係ネットワークにおけるフローの起点であり、destination点は、フローの終点である。
【００５２】
（３）情報記憶部２０２、第１通信部２０３及び第２通信部２０４
情報記憶部２０２は、情報収集部２０６により収集された１個又は複数個のマークアップ言語を記憶するための領域を備えている。図４に一例として示すように、情報記憶部２０２は、マークアップ言語２２１、２２２、２２３、２２４及び２５５を記憶する。
また、情報記憶部２０２は、オリジナル対応テーブル、オリジナル辺テーブル及びオリジナル点テーブルを記憶するための領域を備えている。
【００５３】
第１通信部２０３は、インターネット２０を介して、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃに接続されており、情報収集部２０６とＷｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃとの間で情報の送受信を行う。
第２通信部２０４は、ＬＡＮ３０を介して、関係ネットワーク変換装置３００と接続されており、関係ネットワーク生成部２０５と関係ネットワーク変換装置３００との間で、情報の送受信を行う。
【００５４】
１．４  関係ネットワーク変換装置３００
関係ネットワーク変換装置３００は、図１３に示すように、制御部３０１、情報記憶部３０２、通信部３０３及び関係ネットワーク変換部３０４から構成されている。関係ネットワーク変換装置３００は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、通信ユニットなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、関係ネットワーク変換装置３００は、その機能を達成する。
【００５５】
（１）制御部３０１
制御部３０１は、関係ネットワーク収集生成装置２００から、ＬＡＮ３０及び通信部３０３を介して、オリジナル対応テーブル及びオリジナル関係ネットワークとしてのオリジナル辺テーブル及びオリジナル点テーブルを受信する。オリジナル対応テーブル、オリジナル辺テーブル及びオリジナル点テーブルを受信すると、制御部３０１は、関係ネットワーク変換部３０４に対して、オリジナル関係ネットワークを変換する旨の指示を出力する。次に、受信したオリジナル対応テーブル、オリジナル辺テーブル及びオリジナル点テーブルを情報記憶部３０２へ書き込む。
【００５６】
ここでは、一例として、図１１及び図１２に示すオリジナル辺テーブル２７１及びオリジナル点テーブル２８１を受信し、オリジナル辺テーブル２７１及びオリジナル点テーブル２８１を情報記憶部３０２へ書き込むものとする。
また、制御部３０１は、情報記憶部３０２、通信部３０３及び関係ネットワーク変換部３０４を制御する。
【００５７】
（２）関係ネットワーク変換部３０４
関係ネットワーク変換部３０４は、制御部３０１から関係ネットワークを変換する旨の指示を受け取る。この指示を受け取ると、情報記憶部３０２に記憶されているオリジナル関係ネットワークとしてのオリジナル辺テーブル及びオリジナル点テーブルを用いて、後述するようにして、二重化関係ネットワークを生成する。この生成の過程において、後述する超頂点対テーブル３６１、制御点対テーブル３７１、source-destinationテーブル３８１、超頂点間辺テーブル３９１、二重化辺テーブル５０１を情報記憶部３０２へ書き込む。
【００５８】
ここでは、説明を簡略化するため、オリジナル関係ネットワークの一部分について、具体的には、図１４に示すように、オリジナル関係ネットワーク内に含まれる部分ネットワーク３１０について、関係ネットワーク変換部３０４がどのようにして、二重化関係ネットワークを生成するかを説明する。ここで、部分ネットワーク３１０は、１個の辺３１３、及び、この辺３１３の両端の２個の点ｕ（３１１）及び点ｖ（３１２）から構成され、辺３１３の容量は、Ｃであり、減衰率は、αであるとする。部分ネットワーク３１０を含むオリジナル関係ネットワークに基づいて生成された二重化関係ネットワークの部分である部分ネットワーク３２０を図１５に示す。
【００５９】
なお、０＜減衰率≦１である。ここで、減衰率が「０．５」である場合、当該減衰率が設定された辺の両端の２点間を経ることにより、２点間の関係度合いが半減することを示す。また、減衰率が「１」である場合、当該減衰率が設定された辺の両端の２点間を経ることにより、２点間の関係度合いが減衰しないことを示す。
ここで、減衰率αは、例えば、「０．５」である。
【００６０】
関係ネットワーク変換部３０４は、オリジナル関係ネットワーク内の点ｕ（３１１）に対応して、二重化関係ネットワーク上において、２個の超頂点ｕ１（３２１）及び超頂点ｕ２（３２２）を設定する。また、同様に、オリジナル関係ネットワーク内の点ｖ（３１２）に対して、二重化関係ネットワーク上において、２個の超頂点ｖ１（３２３）及び超頂点ｖ２（３２４）を設定する。
【００６１】
次に、関係ネットワーク変換部３０４は、オリジナル関係ネットワーク内の辺３１３に対して、二重化関係ネットワーク上に、２個の制御点３２５及び制御点３２６を設定する。
次に、関係ネットワーク変換部３０４は、二重化関係ネットワーク上において、超頂点ｕ１（３２１）と超頂点ｕ２（３２２）とを接続し、向きの無い超頂点間辺３３１を設定する。ここで、超超頂間辺３３１の減衰率は、「１」であり、その容量は、無限大であるとする。また、二重化関係ネットワーク上において、超頂点ｖ１（３２３）と超頂点ｖ２（３２４）とを接続し、向きの無い超頂点間辺３３２を設定する。超頂点間辺３３２の減衰率は、「１」であり、その容量は、無限大であるとする。
【００６２】
次に、関係ネットワーク変換部３０４は、二重化関係ネットワーク上において、制御点３２５と制御点３２６とを接続する非減衰制御辺３３３を設定する。非減衰制御辺３３３の減衰率は、「１」であり、その容量は、Ｃであるとする。また、非減衰制御辺３３３は、方向を有しない。
次に、関係ネットワーク変換部３０４は、二重化関係ネットワーク上に、超頂点３２１から制御点３２５へ向かう有向の減衰制御辺３４１を設定する。減衰制御辺３４１の減衰率は、α＾（１／２）であり、その容量は、Ｃであるとする。ここで、Ｘ＾Ｙは、Ｘy を意味する。つまり、α＾（１／２）は、αの平方根を意味する。また、二重化関係ネットワーク上に、制御点３２６から超頂点３２３へ向かう有向の減衰制御辺３４２を設定する。減衰制御辺３４２の減衰率は、α＾（１／２）であり、その容量は、Ｃであるとする。
【００６３】
また、関係ネットワーク変換部３０４は、二重化関係ネットワーク上に、超頂点３２４から制御点３２６へ向かう有向の減衰制御辺３４３を設定する。減衰制御辺３４３の減衰率は、（β×α）＾（１／２）であり、その容量は、Ｃであるとする。また、二重化関係ネットワーク上に、制御点３２５から超頂点３２２へ向かう有向の減衰制御辺３４４を設定する。減衰制御辺３４４の減衰率は、（β×α）＾（１／２）であり、その容量は、Ｃであるとする。
【００６４】
ここで、βは、一定の係数であり、０＜係数＜１である。ここで、一例として、βは、「０．８」である。
このようにして、関係ネットワーク変換部３０４は、図１４に示す部分ネットワーク３１０を含むオリジナル関係ネットワークを変換して、図１５に示す部分ネットワーク３２０を含む二重化関係ネットワークを生成する。
【００６５】
図１５に示すように、部分ネットワーク３２０は、減衰制御辺３４１、非減衰制御辺３３３及び減衰制御辺３４２から構成される有向経路３３６を含み、減衰制御辺３４３、非減衰制御辺３３３及び減衰制御辺３４４から構成される有向経路３３７を含んでいる。有向経路３３６と有向経路３３７とは、非減衰制御辺３３３を共有しているので、有向経路３３６と有向経路３３７とは、排他的に又は交代的に作用し機能する。
【００６６】
有向経路３３６を構成する減衰制御辺３４１、非減衰制御辺３３３及び減衰制御辺３４２にそれぞれ設定された減衰率は、「（α）＾（１／２）」、「１」及び「（α）＾（１／２）」である。有向経路３３６の減衰率は、これらの積（α）＾（１／２）×１×（α）＾（１／２）により得られ、その値は、αである。これは、図１４に示す辺３１３に設定された減衰率αに等しい。
【００６７】
また、有向経路３３７を構成する減衰制御辺３４３、非減衰制御辺３３３及び減衰制御辺３４４にそれぞれ設定された減衰率は、「（β×α）＾（１／２）」、「１」及び「（β×α）＾（１／２）」である。有向経路３３７の減衰率は、これらの積（β×α）＾（１／２）×１×（β×α）＾（１／２）により得られ、その値は、β×αである。これは、図１４に示す辺３１３に設定された減衰率αに係数βを乗じて得られたものに等しい。
【００６８】
このように、有向経路３３６上の辺（非減衰制御辺を除く）に設定される減衰率は、有向経路３３７上の辺（非減衰制御辺を除く）に設定される減衰率とは異なるものである。
以上、関係ネットワーク変換部３０４による二重化関係ネットワークの生成について説明した。なお、図１０に示すオリジナル関係ネットワーク２４１を変換して、二重化関係ネットワークを生成する場合における具体例について、またオリジナル関係ネットワークを変換して、二重化関係ネットワークを生成する手順について、後述する。
【００６９】
次に、関係ネットワーク変換部３０４は、情報記憶部３０２に記憶しているオリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブル、制御点対テーブル、二重化辺テーブル及びsource-destinationテーブルを、通信部３０３及びＬＡＮ３０を介して、縁検索装置４００へ送信する。
（３）情報記憶部３０２
情報記憶部３０２は、オリジナル対応テーブル、オリジナル辺テーブル２７１、オリジナル点テーブル２８１、超頂点対テーブル３６１、制御点対テーブル３７１、source-destinationテーブル３８１、超頂点間辺テーブル３９１、二重化辺テーブル５０１を記憶するための領域を備えている。
【００７０】
二重化辺テーブル５０１は、二重化関係ネットワークを表すテーブルであり、関係ネットワーク変換部３０４により、オリジナル辺テーブル２７１及びオリジナル点テーブル２８１を基にして、生成される。超頂点対テーブル３６１、制御点対テーブル３７１、source-destinationテーブル３８１、超頂点間辺テーブル３９１は、二重化辺テーブル５０１の生成の過程において生成される作業用のテーブルである。
（オリジナル対応テーブル、オリジナル辺テーブル２７１及びオリジナル点テーブル２８１）
オリジナル対応テーブル、オリジナル辺テーブル２７１及びオリジナル点テーブル２８１については、上述した通りである。
（超頂点対テーブル３６１）
超頂点対テーブル３６１は、オリジナル関係ネットワークにおける点と、この点に対して生成される二重化関係ネットワークにおける２個の超頂点との対応関係を示すテーブルである。超頂点対テーブル３６１は、図１６に示すように、１個又は複数個の超頂点情報を含む。各超頂点情報は、オリジナル関係ネットワークにおける各点に対応している。各超頂点情報は、点番号、第１超頂点番号及び第２頂点番号を含む。点番号は、オリジナル関係ネットワークにおける点を識別する番号であり、第１超頂点番号及び第２超頂点番号は、それぞれ、オリジナル関係ネットワークにおける点に対応して生成された２個の超頂点を識別する番号である。
（制御点対テーブル３７１）
制御点対テーブル３７１は、オリジナル関係ネットワークにおける辺と、この辺に対して生成される２個の制御点との対応関係を示すテーブルである。制御点対テーブル３７１は、図１７に示すように、１個又は複数個の制御点情報を含む。各制御点情報は、オリジナル関係ネットワークにおける各辺に対応している。各制御点情報は、辺番号、第１制御点番号及び第２制御点番号を含む。辺番号は、オリジナル関係ネットワークにおける辺を識別する番号であり、第１制御点番号及び第２制御点番号は、それぞれ、オリジナル関係ネットワークにおける辺に対応して生成された２個の制御点を識別する番号である。
（source-destinationテーブル３８１）
source-destinationテーブル３８１は、図１８に示すように、source点番号及びdestination点番号を含む。source点番号は、二重化関係ネットワークにおけるsource点（始点）を識別する番号であり、destination点番号は、二重化関係ネットワークにおけるdestination点（終点）を識別する番号である。
（超頂点間辺テーブル３９１）
超頂点間辺テーブル３９１は、オリジナル関係ネットワークにおける点と、二重化関係ネットワークにおける超頂点間辺との対応関係を示すテーブルである。超頂点間辺は、オリジナル関係ネットワークにおける点に対して生成される２個の超頂点を接続する辺である。超頂点間辺テーブル３９１は、図１９に示すように、複数の超頂点間辺情報を含む。各超頂点間辺情報は、オリジナル関係ネットワークにおける各点に対応している。各超頂点間辺情報は、点番号、辺番号、始点番号、終点番号、容量、減衰率及び向きの有無を含む。点番号は、オリジナル関係ネットワークにおける点を識別する番号であり、辺番号は、超頂点間辺を識別する番号であり、始点番号及び終点番号は、二重化関係ネットワークにおける点を識別する番号であって、それぞれ超頂点間辺の始点及び終点を示す。容量は、超頂点間辺の容量を示し、減衰率は、超頂点間辺の減衰率を示し、向きの有無は、超頂点間辺の向きの有無を示す。
（二重化辺テーブル５０１）
二重化辺テーブル５０１は、二重化関係ネットワークを表すテーブルであり、図２０に示すように、複数個の二重化辺情報を含んで構成されている。各二重化辺情報は、二重化関係ネットワークの各辺に対応している。各二重化辺情報は、辺番号、始点番号、終点番号、容量、減衰率及び向きの有無を含む。
【００７１】
辺番号は、二重化関係ネットワークにおける辺を識別する番号である。始点番号及び終点番号は、二重化関係ネットワークにおける点を識別する番号であって、それぞれ二重化関係ネットワークにおける辺の始点及び終点を示す。容量は、当該辺の容量を示し、減衰率は、当該辺の減衰率を示し、向きの有無は、当該辺の向きの有無を示す。
（４）通信部３０３
通信部３０３は、ＬＡＮ３０を介して、関係ネットワーク収集生成装置２００との間で、また、ＬＡＮ３０を介して、縁検索装置４００との間で、情報の送受信を行う。
【００７２】
１．５  縁検索装置４００
縁検索装置４００は、図２１に示すように、制御部４０１、情報記憶部４０２、通信部４０３、縁検索部４０４及び描画部４０５から構成されている。縁検索装置４００は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、通信ユニットなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、縁検索装置４００は、その機能を達成する。
【００７３】
（１）情報記憶部４０２
情報記憶部４０２は、オリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブル、二重化辺テーブル、制御点対テーブル及びsource-destinationテーブルを記憶するための領域を備えており、制御部４０１の制御により、関係ネットワーク変換装置３００からオリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブル、二重化辺テーブル、制御点対テーブル及びsource-destinationテーブルを、ＬＡＮ３０及び通信部４０３を介して、受信し、受信したオリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブル、二重化辺テーブル、制御点対テーブル及びsource-destinationテーブルを記憶する。
【００７４】
また、縁検索部４０４により生成される二重化縁情報テーブル４２１、二重化点連鎖情報テーブル４３１及び目的縁情報テーブル４４１を記憶するための領域を備えている。
さらに、描画部４０５により生成される関係ネットワーク図データを記憶するための領域を備えている。
二重化縁情報テーブル４２１は、図２２に示すように、１又は複数の二重化縁情報から構成される。二重化縁情報テーブル４２１は、二重化関係ネットワークにおいて、始点から終点に向けて、できる限り多くのフローを流すものとする場合に、減衰流最大化問題の解決手法であるWayneのアルゴリズムを適用して得られた結果であり、１個又は複数の二重化縁情報は、求められた始点から終点への１個又は複数のパスに対応している。各二重化縁情報は、複数の辺情報を含む。各辺情報は、二重化関係ネットワークにおける前記パスを構成する複数の辺を識別する識別情報である。
【００７５】
図２２に一例として示す二重化縁情報テーブル４２１は、二重化縁情報４２２及び４２３を含む。二重化縁情報４２２は、「１９−５−４−６−２−１７−１４−１８−３−２０」であり、これは、図３４に示す二重化関係ネットワーク６００ｊ（後述する）における辺１９、辺５、辺４、辺６、辺２、辺１７、辺１４、辺１８、辺３及び辺２０から構成されるパスを示している。また、二重化縁情報４２３は、「１９−１０−９−１１−２０」であり、これは、図３４に示す二重化関係ネットワーク６００ｊにおける辺１９、辺１０、辺９、辺１１及び辺２０から構成されるパスを示している。
【００７６】
二重化点連鎖情報テーブル４３１は、図２３に示すように、１又は複数の二重化点連鎖情報を含んで構成されている。各二重化点連鎖情報は、二重化関係ネットワークにおける前記パスに対応し、当該パスを、二重化関係ネットワークに含まれる点により示す。
各二重化点連鎖情報は、前記パス上において並びを構成する複数の点の順に従って、配列される複数の点情報から構成される。各点情報は、二重化関係ネットワークに含まれる点を示す。
【００７７】
図２３に一例として示す二重化点連鎖情報テーブル４３１は、二重化点連鎖情報４３２及び４３３を含む。二重化点連鎖情報４３２は、「１３−１−７−８−３−４−１２−１１−６−５−１４」であり、これは、図３４に示す二重化関係ネットワーク６００ｊにおける点１３、点１、点７、点８、点３、点４、点１２、点１１、点６、点５及び点１４をこの順序で連結して構成されるパスを示している。また、二重化点連鎖情報４３３は、「１３−１−９−１０−５−１４」であり、これは、図３４に示す二重化関係ネットワーク６００ｊにおける点１３、点１、点９、点１０、点５及び点１４をこの順序で連結して構成されるパスを示している。
【００７８】
目的縁情報テーブル４４１は、図２４に示すように、１又は複数の目的縁情報から構成される。目的縁情報テーブル４４１は、オリジナル関係ネットワークにおいて、始点から終点に向けて、できる限り多くのフローを流すものとする場合に、得られた結果であり、１個又は複数の目的縁情報は、求められた始点から終点への１個又は複数のパスに対応している。各目的縁情報は、複数の辺情報を含む。各辺情報は、オリジナル関係ネットワークにおける前記パスを構成する複数の辺を識別する識別情報である。
【００７９】
図２４に一例として示す目的縁情報テーブル４４１は、目的縁情報４４２及び４４３を含む。目的縁情報４４２は、「１−３」であり、これは、図１０に示すオリジナル関係ネットワーク２４１における辺１及び辺３から構成されるパスを示している。また、目的縁情報４４３は、「２」であり、これは、図１０に示すオリジナル関係ネットワーク２４１における辺２から構成されるパスを示している。
【００８０】
（２）縁検索部４０４
縁検索部４０４は、制御部４０１の指示により、情報記憶部４０２に記憶されている二重化辺テーブル５０１及びsource-destinationテーブル３８１を用いて、減衰流最大化問題の解決手法であるWayneのアルゴリズムを適用して、source-destinationテーブル３８１のsource点番号により示される始点と、destination点番号により示される終点とを関連付ける二重化縁情報テーブル４２１を生成し、生成した二重化縁情報テーブル４２１を情報記憶部４０２へ書き込む。
【００８１】
次に、縁検索部４０４は、情報記憶部４０２に記憶されている二重化縁情報テーブル４２１の各二重化縁情報について、情報記憶部４０２に記憶されている二重化辺テーブル５０１を用いて、二重化点連鎖情報テーブル４３１を生成し、生成した二重化点連鎖情報テーブル４３１を情報記憶部４０２に書き込む。つまり、縁検索部４０４は、上記のWayneのアルゴリズムを適用して求められた各パスを、辺の集合による表現（二重化縁情報テーブル４２１）から、点の集合による表現（二重化点連鎖情報テーブル４３１）に変換する。
【００８２】
縁検索部４０４は、次のようにして二重化点連鎖情報テーブル４３１を生成する。
縁検索部４０４は、二重化縁情報テーブル４２１の各二重化縁情報に対応して、二重化点連鎖情報テーブルの各二重化点連鎖情報を生成する。縁検索部４０４は、二重化縁情報テーブル４２１の二重化縁情報に含まれる複数の辺番号を順に読み出し、読み出した辺番号と同一の辺番号を含む二重化辺情報を、二重化辺テーブル５０１から読み出し、読み出した二重化辺情報に含まれる始点番号を抽出し、抽出した始点番号を二重化点連鎖情報テーブル４３１の二重化点連鎖情報に追加して書き込む。最後に読み出す辺番号については、読み出した辺番号と同一の辺番号を含む二重化辺情報を、二重化辺テーブル５０１から読み出し、読み出した二重化辺情報に含まれる始点番号及び終点番号を抽出し、抽出した始点番号及び終点番号を二重化点連鎖情報テーブル４３１の二重化点連鎖情報に追加して書き込む。
【００８３】
次に、縁検索部４０４は、二重化点連鎖情報テーブル４３１を基にして、目的縁情報テーブル４４１を生成し、生成した目的縁情報テーブル４４１を情報記憶部４０２に書き込む。つまり、縁検索部４０４は、二重化関係ネットワークにおけるパスを、オリジナル関係ネットワークにおけるパスに置き換える。なお、目的縁情報テーブル４４１の生成の詳細については、後述する。
【００８４】
次に、縁検索部４０４は、目的縁情報テーブル４４１の情報記憶部４０２への書き込みを完了すると、描画部４０５に対して、関係ネットワーク図を描画するように指示する。
（３）描画部４０５
描画部４０５は、縁検索部４０４から関係ネットワーク図の描画の指示を受け取る。この指示を受け取ると、描画部４０５は、情報記憶部４０２からオリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブルを読み出し、読み出したオリジナル対応テーブル、オリジナル辺テーブル、オリジナル点テーブルを用いて、オリジナル関係ネットワークを表す関係ネットワーク図を描画し、目的縁情報テーブルを読み出し、読み出した目的縁情報テーブルを用いて、すでに描画した関係ネットワーク図に重ねて、上記のWayneのアルゴリズムを適用して求められた各パスを表す縁ネットワーク図を描き、関係ネットワーク図データを生成する。
【００８５】
次に、描画部４０５は、関係ネットワーク図データを通信部４０３及びＬＡＮ３０を介して、Ｗｅｂサーバ装置１００へ送信する。
（４）通信部４０３及び制御部４０１
通信部４０３は、ＬＡＮ３０を介して、関係ネットワーク変換装置３００との間で、また、ＬＡＮ３０を介して、Ｗｅｂサーバ装置１００との間で、情報の送受信を行う。
【００８６】
制御部４０１は、情報記憶部４０２、通信部４０３、縁検索部４０４及び描画部４０５を制御する。
２．二重化関係ネットワークの生成例
関係ネットワーク変換装置３００による二重化関係ネットワークの生成の一例を説明する。ここでは、図１０に示すオリジナル関係ネットワーク２４１を基にして、二重化関係ネットワークを生成するものとする。
【００８７】
関係ネットワーク変換装置３００の関係ネットワーク変換部３０４は、図２５に示すように、オリジナル関係ネットワーク２４１の点２５１に対応して、超頂点６０１及び６０２を設定し、オリジナル関係ネットワーク２４１の点２５２に対応して、超頂点６０３及び６０４を設定し、オリジナル関係ネットワーク２４１の点２５３に対応して、超頂点６０５及び６０６を設定する。
【００８８】
次に、関係ネットワーク変換部３０４は、図２６に示すように、オリジナル関係ネットワーク２４１の辺２６１に対応して、制御点６０７及び６０８を設定し、オリジナル関係ネットワーク２４１の辺２６２に対応して、制御点６０９及び６１０を設定し、オリジナル関係ネットワーク２４１の辺２６３に対応して、制御点６１１及び６１２を設定する。
次に、関係ネットワーク変換部３０４は、図２７に示すように、オリジナル関係ネットワーク２４１の始点である点２５１に対応して、始点である点６１３（source）を設定し、オリジナル関係ネットワーク２４１の終点である点２５３に対応して、終点である点６１４（destination）を設定する。
【００８９】
次に、関係ネットワーク変換部３０４は、図２８に示すように、超頂点６０１及び６０２を連結する超頂点間辺６２１を設定し、超頂点６０３及び６０４を連結する超頂点間辺６２２を設定し、超頂点６０５及び６０６を連結する超頂点間辺６２３を設定する。
次に、関係ネットワーク変換部３０４は、図２９に示すように、制御点６０７及び６０８を連結する非減衰制御辺６２４を設定する。
【００９０】
次に、関係ネットワーク変換部３０４は、図３０に示すように、超頂点６０１及び制御点６０７を連結する減衰制御辺６２５を設定し、超頂点６０３及び制御点６０８を連結する減衰制御辺６２６を設定する。
次に、関係ネットワーク変換部３０４は、図３１に示すように、超頂点６０４及び制御点６０８を連結する減衰制御辺６２７を設定し、超頂点６０２及び制御点６０７を連結する減衰制御辺６２８を設定する。
【００９１】
次に、関係ネットワーク変換部３０４は、図３２に示すように、超頂点６２５及び制御点６０９を連結する減衰制御辺６３０を設定し、超頂点６０２及び制御点６０９を連結する減衰制御辺６３２を設定する。また、制御点６０９及び制御点６１０を連結する非減衰制御辺６２９を設定する。さらに、超頂点６０５及び制御点６１０を連結する減衰制御辺６３１を設定し、超頂点６０６及び制御点６１０を連結する減衰制御辺６３３を設定する。
【００９２】
次に、関係ネットワーク変換部３０４は、図３３に示すように、超頂点６０３及び制御点６１２を連結する減衰制御辺６３６を設定し、超頂点６０４及び制御点６１２を連結する減衰制御辺６３７を設定する。また、制御点６１１及び制御点６１２を連結する非減衰制御辺６３４を設定する。さらに、超頂点６０５及び制御点６１１を連結する減衰制御辺６３５を設定し、超頂点６０６及び制御点６１１を連結する減衰制御辺６３８を設定する。
【００９３】
次に、関係ネットワーク変換部３０４は、図３４に示すように、点６１３（source)及び超頂点６０１を連結するsource点からの辺６３９を設定し、超頂点６０５及び点６１４（destination）を連結するdestination点への辺６４０を設定する。
このようにして、関係ネットワーク変換部３０４は、図３４に示す二重化関係ネットワーク６００ｊを生成する。
【００９４】
なお、以上に示す順序により辺及び点が生成されて二重化関係ネットワークが構成されるが、二重化関係ネットワークを構成する辺及び点を生成する順序は、上記の順序には限定されない。他の順序により生成するとしてもよい。
３．縁検索システム１０の動作
縁検索システム１０の動作について説明する。
【００９５】
３．１  縁検索システム１０の全体の動作
ここでは、縁検索システム１０の全体の動作について、図３５に示すフローチャートを用いて説明する。
ＰＣ５０ａは、ＰＣ５０ａの利用者から検索のための条件、つまり、始点情報と終点情報の入力を受け付け（ステップＳ１０１）、受け付けた条件をＷｅｂサーバ装置１００へ送信し、Ｗｅｂサーバ装置１００に対して、始点対象と終点対象との間を仲介し、関連付ける縁を検索するよう要求する（ステップＳ１０２）。Ｗｅｂサーバ装置１００は、受け付けた条件を関係ネットワーク収集生成装置２００へ送信し、関係ネットワーク収集生成装置２００に対して、関連付ける縁を検索するよう要求する（ステップＳ１０３）。
【００９６】
関係ネットワーク収集生成装置２００は、Ｗｅｂサーバ装置１００の指示により、始点情報に関する開示情報及び終点情報に関する開示情報を、インターネット２０を介して、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから収集し（ステップＳ１０４）、収集した開示情報を用いて、オリジナル関係ネットワークを生成し（ステップＳ１０５）、生成したオリジナル関係ネットワークを関係ネットワーク変換装置３００へ送信する（ステップＳ１０６）。
【００９７】
関係ネットワーク変換装置３００は、関係ネットワーク収集生成装置２００により生成されたオリジナル関係ネットワークを変換して、始点対象と終点対象とを関連付ける縁を発見するために効率的に構成された二重化関係ネットワークを生成し（ステップＳ１０７）、生成した二重化関係ネットワークを縁検索装置４００へ送信する（ステップＳ１０８）。
【００９８】
縁検索装置４００は、受信した二重化関係ネットワークを用いて、始点情報と終点情報との間を仲介し、関連付ける縁を検索し（ステップＳ１０９）、得られた縁を基にして、始点対象と終点対象との間を仲介し、関連付ける縁を示す関係ネットワーク図を描画し（ステップＳ１１０）、Ｗｅｂサーバ装置１００へ関係ネットワーク図を送信する（ステップＳ１１１）。
【００９９】
Ｗｅｂサーバ装置１００は、受信した関係ネットワーク図を要求元のＰＣへ送信する（ステップＳ１１２）。要求元のＰＣは、図３に示すように、関係ネットワーク図を表示する（ステップＳ１１３）。
３．２  二重化関係ネットワークの生成の動作
ここでは、関係ネットワーク変換装置３００の関係ネットワーク変換部３０４による二重化関係ネットワークの生成の動作について、図３６〜図４２に示すフローチャートを用いて説明する。
【０１００】
関係ネットワーク変換部３０４は、ステップＳ２０１〜Ｓ２０４において、オリジナル点テーブル内の各点情報に含まれる点番号ｉ（ｉ＝１、２、・・・、ｎ）の各々について、２個の超頂点を生成するために、次のステップＳ２０２〜Ｓ２０３を繰り返す。ここで、ｎは、オリジナル関係ネットワークに含まれる点の数である。
関係ネットワーク変換部３０４は、点番号ｉについて、二重化関係ネットワークの超頂点対である第１超頂点番号２ｉ−１及び第２超頂点番号２ｉを生成し（ステップＳ２０２）、オリジナル関係ネットワークの点番号ｉ、第１超頂点番号２ｉ−１及び第２超頂点番号２ｉを、超頂点情報として、超頂点対テーブル３６１に書き込む（ステップＳ２０３）。
【０１０１】
こうして、オリジナル関係ネットワークに含まれる各点について、二重化関係ネットワークにおける２個の超頂点が設定される。
次に、関係ネットワーク変換部３０４は、ステップＳ２０５〜Ｓ２０８において、オリジナル辺テーブルのオリジナル辺情報に含まれる辺番号ｊ（ｊ＝１、２、・・・、ｍ）について、２個の制御点を生成するために、次のステップＳ２０６〜Ｓ２０７を繰り返す。ここで、ｍは、オリジナル関係ネットワークに含まれる辺の数である。
【０１０２】
関係ネットワーク変換部３０４は、辺番号ｊについて、二重化関係ネットワークの制御点対である第１制御点番号２ｎ＋２ｊ−１及び第２制御点番号２ｎ＋２ｊを生成し（ステップＳ２０６）、オリジナル関係ネットワークの辺番号ｊ、第１制御点番号２ｎ＋２ｊ−１及び第２制御点番号２ｎ＋２ｊを、制御点情報として、制御点対テーブル３７１へ書き込む（ステップＳ２０７）。
【０１０３】
こうして、オリジナル関係ネットワークに含まれる各辺について、二重化関係ネットワークにおける２個の制御点が設定される。
次に、関係ネットワーク変換部３０４は、二重化関係ネットワークのsource点２ｎ＋２ｍ＋１及びdestination点２ｎ＋２ｍ＋２を生成し（ステップＳ２２１）、生成したsource点２ｎ＋２ｍ＋１及びdestination点２ｎ＋２ｍ＋２を、それぞれ、source点番号及びdestination点番号として、source-destinationテーブル３８１へ書き込む（ステップＳ２２２）。
【０１０４】
次に、関係ネットワーク変換部３０４は、変数Ｗを値「０」により初期化する（ステップＳ２２３）。ここで、変数Ｗは、二重化関係ネットワークにおける辺を識別する辺番号を記憶するためのものである。
次に、関係ネットワーク変換部３０４は、ステップＳ２２４〜Ｓ２２８において、超頂点対テーブル３６１に含まれる全ての超頂点情報について、超頂点間辺を生成するために、ステップＳ２２５、Ｓ２２６及びＳ２２７を繰り返す。
【０１０５】
関係ネットワーク変換部３０４は、超頂点対テーブル３６１から順に超頂点情報を読み出し（ステップＳ２２５）、変数Ｗに値「１」を加算し（ステップＳ２２６）、読み出した超頂点情報に含まれる第１超頂点番号を始点番号とし、第２超頂点番号を終点番号とし、辺番号＝Ｗとし、辺番号、始点番号、終点番号、容量「∞」、減衰率「１」、辺の向き「向き無し」を含む二重化辺情報（超頂点間辺に対するもの）を二重化辺テーブル５０１へ書き込む（ステップＳ２２７）。
【０１０６】
こうして、二重化関係ネットワークにおける全ての超頂点間辺が設定される。
次に、関係ネットワーク変換部３０４は、ステップＳ２４１〜Ｓ２４５、Ｓ２６１〜Ｓ２７０及びＳ２８１〜Ｓ２８９において、オリジナル辺テーブル２７１に含まれる全てのオリジナル辺情報の各々について、１本の非減衰制御辺と、４本の減衰制御辺とを生成するために、ステップＳ２４２〜Ｓ２４５、Ｓ２６１〜Ｓ２７０及びＳ２８１〜Ｓ２８８を繰り返す。
【０１０７】
関係ネットワーク変換部３０４は、オリジナル辺テーブル２７１から、順に、オリジナル辺情報を読み出し、読み出したオリジナル辺情報から辺番号を抽出し（ステップＳ２４２）、抽出した辺番号と同一の辺番号を含む制御点情報を制御点対テーブル３７１から読み出し、読み出した制御点情報から第１制御点番号及び第２制御点番号を抽出し（ステップＳ２４３）、変数Ｗに値「１」を加算し（ステップＳ２４４）、辺番号＝Ｗとし、抽出した２個の第１制御点番号及び第２制御点番号をそれぞれ始点番号及び終点番号とし、辺番号、始点番号、終点番号、容量「１」、減衰率「１」及び辺の向き「向き無し」を含む二重化辺情報（非減衰制御辺）を二重化辺テーブル５０１へ書き込む（ステップＳ２４５）。
【０１０８】
こうして、二重化関係ネットワークにおいて、対である２個の制御点を連結する非減衰制御辺が設定される。このようにして設定された非減衰制御辺の一例は、図１５に示す辺３３３である。この場合に、第１制御点番号及び第２制御点番号は、図１５の点３２５及び点３２６に相当する。
次に、関係ネットワーク変換部３０４は、読み出したオリジナル辺情報から減衰率ｇを抽出し（ステップＳ２６１）、抽出した減衰率ｇの平方根ｇ＾（１／２）を算出し（ステップＳ２６２）、読み出したオリジナル辺情報から始点番号を抽出し（ステップＳ２６３）、抽出した始点番号と同一の点番号を含む超頂点情報を超頂点対テーブル３６１から読み出し、読み出した超頂点情報から第１超頂点番号及び第２超頂点番号を抽出し（ステップＳ２６４）、変数Ｗに値「１」を加算し（ステップＳ２６５）、辺番号＝Ｗとし、第１超頂点番号を始点番号とし、第１制御点番号を終点番号とし、辺番号、始点番号、終点番号、容量「１」、減衰率＝ｇ＾（１／２）、辺の向き「向き有り」を含む二重化辺情報（減衰制御辺）を二重化辺テーブル５０１へ書き込む（ステップＳ２６６）。
【０１０９】
こうして、二重化関係ネットワークにおいて、超頂点と制御点を連結する減衰制御辺が設定される。このようにして設定された減衰制御辺の一例は、図１５に示す辺３４１である。この場合に、第１超頂点番号及び第１制御点番号は、図１５の点３２１及び点３２５に相当する。
次に、関係ネットワーク変換部３０４は、読み出したオリジナル辺情報から終点番号を抽出し（ステップＳ２６７）、抽出した終点番号と同一の点番号を含む超頂点情報を超頂点対テーブル３６１から読み出し、読み出した超頂点情報から第１超頂点番号及び第２超頂点番号を抽出し（ステップＳ２６８）、変数Ｗに値「１」を加算し（ステップＳ２６９）、辺番号＝Ｗとし、第２制御点番号を始点番号とし、第１超頂点番号を終点番号とし、辺番号、始点番号、終点番号、容量「１」、減衰率＝ｇ＾（１／２）、辺の向き「向き有り」を含む二重化辺情報（減衰制御辺）を二重化辺テーブル５０１へ書き込む（ステップＳ２７０）。
【０１１０】
こうして、二重化関係ネットワークにおいて、超頂点と制御点を連結する減衰制御辺が設定される。このようにして設定された減衰制御辺の一例は、図１５に示す辺３４２である。この場合に、第２制御点番号及び第１超頂点番号は、図１５の点３２６及び点３２３に相当する。
次に、関係ネットワーク変換部３０４は、読み出したオリジナル辺情報から終点番号を抽出し（ステップＳ２８１）、抽出した終点番号と同一の点番号を含む超頂点情報を超頂点対テーブル３６１から読み出し、読み出した超頂点情報から第１超頂点番号及び第２超頂点番号を抽出し（ステップＳ２８２）、変数Ｗに値「１」を加算し（ステップＳ２８３）、辺番号＝Ｗとし、第２超頂点番号を始点番号とし、第２制御点番号を終点番号とし、辺番号、始点番号、終点番号、容量「１」、減衰率＝（β×ｇ）＾（１／２）、辺の向き「向き有り」を含む二重化辺情報（減衰制御辺）を二重化辺テーブル５０１へ書き込む（ステップＳ２８４）。ここで、βは、係数であり、０＜β＜１である。
【０１１１】
こうして、二重化関係ネットワークにおいて、超頂点と制御点を連結する減衰制御辺が設定される。このようにして設定された減衰制御辺の一例は、図１５に示す辺３４３である。この場合に、第２超頂点番号及び第２制御点番号は、図１５の点３２４及び点３２６に相当する。
次に、関係ネットワーク変換部３０４は、読み出したオリジナル辺情報から始点番号を抽出し（ステップＳ２８５）、抽出した始点番号と同一の点番号を含む超頂点情報を、超頂点対テーブル３６１から読み出し、読み出した超頂点情報から第１超頂点番号及び第２超頂点番号を抽出し（ステップＳ２８６）、変数Ｗに値「１」を加算し（ステップＳ２８７）、辺番号＝Ｗとし、第１制御点番号を始点番号とし、第２超頂点番号を終点番号とし、辺番号、始点番号、終点番号、容量「１」、減衰率＝（β×ｇ）＾（１／２）、辺の向き「向き有り」を含む二重化辺情報（減衰制御辺）を二重化辺テーブル５０１へ書き込む（ステップＳ２８８）。
【０１１２】
こうして、二重化関係ネットワークにおいて、超頂点と制御点を連結する減衰制御辺が設定される。このようにして設定された減衰制御辺の一例は、図１５に示す辺３４４である。この場合に、第１制御点番号及び第２超頂点番号は、図１５の点３２５及び点３２２に相当する。
次に、関係ネットワーク変換部３０４は、source-destinationテーブル３８１からsource点番号を読み出し（ステップＳ３０１）、オリジナル点テーブル２８１から点情報「source」に対応する点番号を読み出し（ステップＳ３０２）、超頂点対テーブル３６１から、読み出した点番号と同一の点番号を含む超頂点情報を読み出し（ステップＳ３０３）、読み出した超頂点情報から第１超頂点番号を抽出し（ステップＳ３０４）、変数Ｗに値「１」を加算し（ステップＳ３０５）、辺番号＝Ｗとし、source点番号を始点番号とし、第１超頂点番号を終点番号とし、辺番号、始点番号、終点番号、容量「∞」、減衰率「１」、辺の向き「向きあり」を含む二重化辺情報（source辺）を二重化辺テーブル５０１へ書き込む（ステップＳ３０６）。
【０１１３】
こうして、二重化関係ネットワークにおいて、source点から超頂点への辺が設定される。このようにして設定されたsource点からの辺の一例は、図３４に示す辺６３９である。
次に、関係ネットワーク変換部３０４は、オリジナル点テーブル２８１から点情報「destination」に対応する点番号を読み出し（ステップＳ３２１）、超頂点対テーブル３６１から、読み出した点番号と同一の点番号を含む超頂点情報を読み出し（ステップＳ３２２）、読み出した超頂点情報から第１超頂点番号を抽出し（ステップＳ３２３）、source-destinationテーブル３８１からdestination点番号を読み出し（ステップＳ３２４）、変数Ｗに値「１」を加算し（ステップＳ３２５）、辺番号＝Ｗとし、第１超頂点番号を始点番号とし、destination点番号を終点番号とし、辺番号、始点番号、終点番号、容量「∞」、減衰率「１」、辺の向き「向きあり」を含む二重化辺情報（destination辺）を二重化辺テーブル５０１へ書き込む（ステップＳ３２６）。
【０１１４】
こうして、二重化関係ネットワークにおいて、超頂点からdestination点への辺が設定される。このようにして設定されたdestination点への辺の一例は、図３４に示す辺６４０である。
以上により、二重化関係ネットワークに対応する二重化辺テーブルが生成される。
３．３  関係ネットワーク図の生成の動作
ここでは、縁検索装置４００の縁検索部４０４及び描画部４０５による関係ネットワーク図の生成の動作について、図４３〜図４４及び図４５に示すフローチャートを用いて説明する。
【０１１５】
縁検索部４０４は、ステップＳ４０１〜Ｓ４０３において、二重化縁情報テーブル４２１に含まれる全ての二重化縁情報の各々について、次のステップＳ４０２を繰り返す。
縁検索部４０４は、二重化縁情報テーブル４２１から二重化縁情報を読み出し、読み出した二重化縁情報に対応して、二重化点連鎖情報テーブル４３１に、二重化点連鎖情報を記憶するための領域を確保する。次に、読み出した二重化縁情報から辺番号を順に読み出し、読み出した辺番号と同一の辺番号を含む二重化辺情報を、二重化辺テーブル５０１から読み出し、読み出した二重化辺情報に含まれる始点番号を抽出し、抽出した始点番号を二重化点連鎖情報テーブル４３１の二重化点連鎖情報（上記で確保した領域）に追加して書き込む。最後に読み出す辺番号については、読み出した辺番号と同一の辺番号を含む二重化辺情報を、二重化辺テーブル５０１から読み出し、読み出した二重化辺情報に含まれる始点番号及び終点番号を抽出し、抽出した始点番号及び終点番号を二重化点連鎖情報テーブル４３１の二重化点連鎖情報に追加して書き込む（ステップＳ４０２）。
【０１１６】
このようにして、一例として図２３に示す二重化点連鎖情報テーブル４３１が生成される。
次に、縁検索部４０４は、ステップＳ４０４〜Ｓ４０６において、二重化点連鎖情報テーブル４３１に含まれる全ての二重化点連鎖情報の各々について、次のステップＳ４０５を繰り返す。
【０１１７】
縁検索部４０４は、二重化点連鎖情報の処理を行う（ステップＳ４０５）。なお、この詳細については、後述する。
次に、描画部４０５は、情報記憶部４０２からオリジナル対応テーブル、オリジナル辺テーブル及びオリジナル点テーブルを読み出し（ステップＳ４０７）、読み出したオリジナル対応テーブル、オリジナル辺テーブル及びオリジナル点テーブルを用いて、オリジナル関係ネットワークを表す関係ネットワーク図を描画する（ステップＳ４０８）。
【０１１８】
次に、描画部４０５は、情報記憶部４０２から目的縁情報テーブル４４１を読み出し（ステップＳ４０９）、読み出した目的縁情報テーブル４４１を用いて、描画した関係ネットワーク図上に、縁ネットワーク図を上書きし、縁ネットワーク図の上書きされた関係ネットワーク図を表した関係ネットワーク図データを情報記憶部４０２に書き込む（ステップＳ４１０）。
【０１１９】
このようして、縁ネットワーク図の上書きされた関係ネットワーク図が生成される。縁ネットワーク図の上書きされた関係ネットワーク図の一例を図３に示している。
次に、図４３に示すステップＳ４０５の詳細について、図４５に示すフローチャートを用いて、説明する。
縁検索部４０４は、二重化点連鎖情報テーブル４３１から二重化点連鎖情報を読み出し、目的縁情報テーブル４４１に目的縁情報を記憶するための領域を確保する（ステップＳ４２１）。
【０１２０】
次に、縁検索部４０４は、二重化点連鎖情報から、点情報を順に読み出す（ステップＳ４２２）。
読み出した点情報が、destination点であるなら（ステップＳ４２３）、処理を終了する。
読み出した点情報が超頂点又はsource点であるなら（ステップＳ４２４）、ステップＳ４２２へ戻って処理を繰り返す。
【０１２１】
読み出した点情報が制御点であり（ステップＳ４２４）、一つ前に読み出した点情報が超頂点であるか又は、一つ前に読み出す点情報が存在しないとき（ステップＳ４２５）、ステップＳ４２２へ戻って処理を繰り返す。
一つ前に読み出した点情報が制御点であるとき（ステップＳ４２５）、制御点対テーブル３７１から、当該制御点を第１制御点又は第２制御点として含む制御点情報を読み出し、読み出した制御点情報から辺番号を抽出し（ステップＳ４２６）、抽出した辺番号を目的縁情報へ追加して書き込む（ステップＳ４２７）。次に、ステップＳ４２２へ戻って処理を繰り返す。
【０１２２】
以上のようにして、縁検索部４０４は、二重化関係ネットワークにおけるパスを、オリジナル関係ネットワークにおけるパスに置き換える。
４．減衰流と二重化ネットワークに関する定理の証明
ここでは、減衰流と二重化ネットワークに関する定理について証明する。
４．１  減衰流と二重化ネットワーク
４．１．１  流量最大の減衰流
点集合がＶ，辺集合がＥ，ソースがｓ∈Ｖ，デスティネーションがｔ∈Ｖ，各辺ｅの容量（capacity）がμ（ｅ）≧０，各辺の減衰率（gain）がγ(e)＞０であるような有向ネットワークＧ＝(V,E,s,t,μ,vc,γ)が与えられたとする。フローｆの各辺ｅでの流量をf(e)≧０で表し、ｆの値をｔに流れ込むフローの総量と定義する。このとき、減衰流最大化問題（generalized maximum flow problem）とは、容量制約f(e)≦μ(e)をすべての辺ｅで満たすような、最大のｆ（流量最大の減衰流）を求める問題である。
【０１２３】
図４６は、流量最大の減衰流の例である。ソースｓからｖ1 へ１単位のフローが流れている、すなわちf(s,v1)＝１であるが、フローがｖ1 に到達したときにはその流量はγ(s,v1)倍となるため、0.8単位のみが到達することになる。同様に、デスティネーションｔには0.512単位のみが到達する。各辺の容量制約は、その辺の減衰率がかけられる前に満たされていなければならないことに注意する。たとえば、f(s,v1)＝１≦μ(s,v1)が満たされていなければならない。
【０１２４】
４．１．２  二重化ネットワーク
まず、いくつかの記号を導入する。
（表記法１）Ｇ＝(V,E,s,t,μ,γ)を有向ネットワークとする。あるフローｆに対して、各点ｖについて、exf(v)をｖに流れ込む流量とｖから流れ出る流量の差、すなわち
【０１２５】
【数１】
2010287155.tif 000003
とする。exf(v)＞０ならばｖは超過（excess）を持つといい、exf(v)＜０ならばｖは不足（deficit）を持つという。フローｆの値は、exf (t)の値で定義される。
次に、元の減衰流問題のネットワークの任意の辺を反転させてできるネットワークを「部分反転ネットワーク」（partially reversed network）と名付ける。反転された辺の減衰率は、もともとその辺に与えられた減衰率と異なっても良いので、反転された辺の減衰率を「反転辺減衰率」(reversed edge gain) と呼んで、もともとその辺に与えられた減衰率と区別する。
（定義１）rev：Ｅ→（０，１］を与えられた反転辺減衰率とし、Ｅr ⊆ＥをＥの与えられた部分集合とする。このとき、元のネットワークＧとＥr とrevに対する部分反転ネットワークＧEr,revとは、以下の２点を除いてＧと同じネットワークである。（１）ｅ∈Ｅr である各辺ｅの向きは逆になる。（２）ＧEr,revの各辺に対して、「反転辺」（reversed edge）すなわちＧの中ではｅ∈Ｅr となっていた辺の減衰率γ’(e)はrev(e)となる。そうでない辺「原初辺」（original edge）に対しては、γ’(e)＝γ(e)となる。
【０１２６】
図４７（ｂ）は、図４７（ａ）のネットワークＧに対する２つの部分反転ネットワーク      
【０１２７】
【数２】
2010287155.tif 000004
を描いている。
ここで、「二重化ネットワーク」(doubled network) を定義する。
（定義２）Ｇ＝(V,E,s,t,μ,γ)を有向ネットワーク，rev：Ｅ→（0,1］をＧの各辺の反転辺減衰率とする。Ｇのrevに対する二重化ネットワークＧ’rev ＝(V' ,E',s',t',μ',γ')を以下のように定義する。Ｖ’はＧの各点に対応する「超頂点対」（super vertices pair）と各辺に対応する「制御点対」（control vertices pair）、「仮想ソース」（virtual source）、「仮想デスティネーション」（virtual destination）で構成される。
【０１２８】
（１）Ｇの点ｖ∈Ｖに対応する超頂点対はＧ’rev の２つの点ｖ1 ，ｖ2 で表す。
（２）辺（ｕ，ｖ）∈Ｅに対応する制御点対はＧ’rev の２つの点ｌu,v ，ｒu,v で表す。
（３）仮想ソースをｓ’で表す。
（４）仮想デスティネーションをｔ’で表す。
【０１２９】
Ｅ’は以下の５種類の辺で構成される。
（１）２本の有向辺ｅ1 ＝(s',s1)，ｅ2 ＝(t1 ,t')．容量はμ’(e1)＝μ’(e2)＝∞とし、減衰率はγ’(e1)＝γ’(e2)＝１とする。
（２）Ｇの各点ｖ∈Ｖにつき、それに対応する超頂点対ｖ1 ，ｖ2 を結ぶ１本の無向辺ｅ＝｛v1，v2 ｝．容量はμ’(e)＝∞とし、減衰率はγ’(e)＝１とする。
【０１３０】
（３）Ｇの各辺(u,v)∈Ｅにつき、それに対応する制御点対を結ぶ１本の無向辺ｅ＝｛ｌu,v ，ｒu,v｝．容量はμ’(e)＝μ(u,v)とし、γ’(e)＝１とする。
（４）Ｇの各辺(u,v)∈Ｅにつき２本の有向辺e1＝(u1,ｌu,v），e2＝(ru,v ,v1)．  容量はμ’(e1)＝μ’(e2)＝μ(u,v)とし、減衰率はγ’(e1)＝γ’(e2)＝（γ(u,v))^(1/2)とする。
【０１３１】
（５）Ｇの各辺（ｕ，ｖ）∈Ｅにつき２本の有向辺e1＝(v2，ru,v） ，e2 ＝(lu,v ，ｕ2 ）．容量はμ’(e1）＝μ’(e2）＝μ(u,v)とし、減衰率はγ’(e1）＝γ’(e2）＝(rev(u,v))^(1/2)とする。
元のネットワークの辺（ｕ，ｖ）は、（３）−（５）の５本の辺に対応している。これらの辺の集合を（ｕ，ｖ）の「二重化辺集合」（doubled edge set）  と呼び、Ｄ（ｕ，ｖ）で表す。
【０１３２】
図４８は有向ネットワークの辺と、その二重化辺集合を描いている。なお、{u1，u2 }と{v1 ，v2 }の２本の辺も一緒に描いている。
Ｇのrevに対するすべての部分反転ネットワークについて流量最大の減衰流を求めるには指数時間かかってしまうが、二重化ネットワーク上の流量最大の減衰流は多項式時間で求めることができる。次に述べるのが、本稿の主たる定理である。
（定理１）Ｅのすべての部分集合の族を｛Ｅ1 ，Ｅ2 ，  ．．．，Ｅ2m ｝で表す。与えられた反転辺減衰率revと各部分集合Ｅｉ（１≦ｉ≦２m ）に対するＧの部分反転ネットワークをＧEi,revとする。revに対するＧの二重化ネットワークをＧ’rev とする。有向ネットワークＧに対する減衰流最大化問題の解（流量最大の減衰流の流量）をgenmax(G)で表し、さらにＧに対する減衰流最大化問題の解をgenmax(G)で表す。このとき、以下の等式が成立する。
【０１３３】
【数３】
2010287155.tif 000005
定理１を証明するために、二重化辺集合について「原初正則」（original regular）  と「反転正則」（reversed regular）という２つの概念を導入する。Ｇの辺(u,v)と、それに対応するＧ’rev の二重化辺集合Ｄ(u,v)について、原初正則なフローをＤ(u,v)に流すことは、(u,v)に（元の向きで）フローを流すことに対応する。反転正則なフローをＤ(u,v)に流すことは、反転辺(v,u)にフローを流すことに対応する。これらの例を図４９に示す。厳密な定義は以下の通り。
（定義３）G'revを二重化ネットワークとし、その上での任意の減衰流をｆ’とする。ある二重化辺集合Ｄ(u,v)において、その制御点対ｌu,v ，ｒu,v で超過ないし不足が生じていないときに、
・f'(u1,lu,v ）＞０∧f'(lu,v,ru,v ）＞０∧f'(ru,v,v1 ）＞０∧f'(v2,ru,v ）＝０∧f'(lu,v,u2 ）＝０であるならば、ｆ’はその二重化辺集合の上で原初正則であるという。
・f'(v2 ,ru,v ）＞０∧f'(ru,v ,lu,v ）＞０∧f'(lu,v ,u2 ）＞０∧f'(u1 ,lu,v ）＝０∧f'(ru,v ,v1 ）＝０であるならば、ｆ’はその二重化辺集合の上で反転正則であるという。
・f'(u1 ，lu,v ）＝f'{lu,v ,ru,v ｝＝f'(ru,v,v1 )＝f'(lu,v，u2 )＝f'(v2 ,ru,v）＝０であるならば、ｆ’はその二重化辺集合の上で空であるという。
【０１３４】
すべての二重化辺集合に対して、f'が原初正則または反転正則または空のいずれかであるならば、f'は正則であるという。
この定義から直ちに次の命題が得られる。
（命題１）G'revを二重化ネットワークとし、その上での任意の減衰流をf'とする。f'が正則であるための必要十分条件は、すべての制御点対が超過も不足も持たず、かつf'(u1 ，lu,v)f'(lu,v，u2)＝０かつf'(ru,v，v1 )f'(v2 ,ru,v)＝０を満たすことである。
【０１３５】
定理１を証明するための鍵となるアイディアは、二重化ネットワークG'revと部分反転ネットワークGEi,revとの「減衰流の等価性」である。
（定義４）fを部分反転ネットワークGEi,revにおける減衰流とし、f'を二重化ネットワークＧ’revにおける減衰流とする。このとき、fとf'が等価（equivalent）であるとは、次の条件（１）−（４）を満たすことである。
【０１３６】
（１）辺e＝(u,v)でf(e)＞０を満たすものについて、もしｅが原初辺であるならば、f'は二重化辺集合Ｄ(u,v)の上で原初正則であり、かつf(u1,lu,v）＝f(e)となる；もしeが反転辺であるならば、f'はＤ(u,v)の上で反転正則であり、かつf(v2 ,ru,v）＝f(e)となる；
（２）辺e＝(u,v)でf(e)＝０を満たすものについて、ｆ’はＤ(u,v)上で空である；
【０１３７】
【数４】
2010287155.tif 000006
（１）と（２）を満たすフローは正則である。したがって、fとf'が等価であるならば、f'は正則である。
G'revとGEi,revにおける減衰流の等価性を用いれば、定理１の証明の概略を組み立てることができる。
【０１３８】
（１）点に対する容量vcの付いた部分反転ネットワークGEi,rev上の減衰流に対して、それと等価なG'rev上の正則な減衰流が存在する。これから、以下が得られる。
【０１３９】
【数５】
2010287155.tif 000007
（２）G'rev上の正則な減衰流に対して、それと等価な、ある１≦ｉ≦２m に対する部分反転ネットワークGEi,rev上の減衰流が存在する。これから、以下が得られる。
【０１４０】
【数６】
2010287155.tif 000008
（３）G'revには、流量最大となる減衰流で、正則なものが存在する。
下の補題１が（１）に対応し、補題２が（２）に対応し、補題３が（３）に対応している。
（補題１）Gを有向ネットワーク，revをGの反転辺減衰率、vcをGの点の容量とし、EiをEの部分集合とする。G'revをGのrevに対する二重化ネットワークとし、Gi,revをGのrevとEi に対する部分反転ネットワークとする。fをGi,revにおける減衰流で、デスティネーション以外は超過を持っていないものとする。このとき、fと等価なG'rev上の減衰流f'が存在する。
［証明］fと等価で正則な減衰流f'を構築することで、この補題を証明する。Gi,revの辺集合をRとする。まず、すべての超頂点対間の辺｛ｖin,vout｝について、f'の流量を次のように定める。なお、
【０１４１】
【数７】
2010287155.tif 000009
とおく。
１．もしｘ＝０ならば、辺｛v1 ,v2 ｝でのf'の流量は０とする。
２．そうではなく、ｘ＞０ならば、f'(v1 ,v2)＝ｘとする。
【０１４２】
３．そうではなく、ｘ＜０ならば、f'(v2 ,v1)＝ｘとする。
これは、容量制約を満たしているから、可能である。次に、f'が定義４の条件（１）−（４）をすべて満たすように、他の辺の流量を定める。このようにしてできたｆ’が正則な減衰流であると示せれば、証明は完了する。そのためには、以下の性質（ａ）−（ｃ）が満たされることを示せばよい：（ａ）f'は容量制約を満たす；（ｂ）仮想ソースと仮想デスティネーション以外の点は、超過も不足も持たない；（ｃ）仮想ソースは超過を持たず、仮想デスティネーションは不足を持たない。二重化ネットワークの容量の設定方法から、f'が容量制約を満たすことは容易にわかる。また、f'は定義４の（１）−（４）を満たすから、仮想ソースs'は不足はあっても超過はなく、仮想デスティネーションt'は超過はあっても不足はない。また、どの制御点対も超過や不足を持たない。各超頂点対v1 ,v2 に対しては、f'の構成から、v1 に制御点対から入ってくるf'の流量とv1 から制御点対へ出て行くf'の流量の差は、上のｘに等しい。上のように辺｛v1,v2 ｝の流量を設定したから、v1 では超過も不足もない。さらに、v2 に制御点対から入ってくるf'の流量とv2 から制御点対へ出て行くf'の流量の差は、
【０１４３】
【数８】
2010287155.tif 000010
であるが、Gi,revにおいてvではfは超過も不足もないので、ｙ＝−ｘである。したがって、辺｛v1,v2 ｝の流量の設定から、v2 では超過も不足もない。従って、f'は、G'i,revにおける、fと等価な減衰流である。［証明終了］
よって、
【０１４４】
【数９】
2010287155.tif 000011
から、vinとvoutは超過も不足も持たない。
（補題２）Gを有向ネットワーク，revをGの反転辺減衰率とする。G'revをGのrevに対する二重化ネットワークとし、f'をG'revにおける減衰流で、仮想デスティネーション以外は超過を持っていないものとする。このとき、Gi,revがf'と等価な減衰流が存在するような、あるEi⊆Eが存在する。
［証明］f'が反転正則となっているようなすべての二重化辺集合D(u,v)に対応する辺(u,v)を集めた集合をEi⊆Eとする。そして、f'と等価なGi,revにおける減衰流fを構築することで、この補題を証明する。G'revの各二重化辺集合D(u,v)に対して、もしf'が空であれば、f(u,v)＝０とする；f'が原初正則ならば、辺(u,v)はGi,revに存在しているから、f(u,v)＝f'(u1,lu,v)とする；もしf'が反転正則ならば、辺(v,u)がGi,revに存在しているから、f(v,u)＝f'(v2,ru,v)とする。定義４より、fが減衰流であれば、f'とfは等価となる。上記の構築方法から、fはGi,revにおける容量制約を満たし、ソースのみが不足を持ち得、デスティネーションのみが超過を持ち得る。G'revの各超頂点対v1，v2について、隣接する制御点対からのみ入ってくる（つまり辺｛v1,v2｝や辺（s',v）によるものを無視した）流量の合計をそれぞれIn(v1），In(v2）とし、隣接する制御点対に出て行く流量の合計をそれぞれOut(v1），Out(v2）とする。Gi,revの任意の点vについて、vに入ってくるfの流量はIn(v)＝In(v1）＋In(ｖ2）であり、vから出て行く流量はOut(v)＝Out(v1）＋Out(ｖ2）である。すると、終点tについては、In(t)−Out(t)＝f'(t1，t')≧０であり、超過の可能性はあるが、不足はない。始点ｓについては、In(s)−Out(s)＝f'（s',s1）≦０であり、不足の可能性はあるが超過はない。それ以外の点vについては、In(v)−Out(v)＝０となり、超過も不足もない。よって、fはGi,rev上の減衰流であり、しかもf'と等価である。［証明終了］
したがって、Gi,revにおけるソースとデスティネーション以外のすべての点について、ｆのその点に流れ込む流量とその点から流れ出る流量は等しい。
【０１４５】
補題３を証明する前に、以下の命題を記しておく。
（命題２）G上の任意の減衰流fに対して、fと同じ値を持つ、終点以外に超過のない減衰流gで、任意の辺eに対してf(e)≧g(e)を満たすものが存在する。
この命題は既知である。
（補題３）二重化ネットワークG'revについて、流量最大の減衰流fの値がM＞０であるとき、流量Mでデスティネーション以外の点が超過を持たないような正則な減衰流f'が存在する。
［証明］命題２から、G'revには値がMでデスティネーション以外の点が超過を持たないような減衰流gが存在する。gが命題１における正則性の十分条件であるf'(u1,lu,v）f'(lu,v，u2）＝０とf'(ru,v,v1）f'(v2,ru,v）＝０のどちらかを満足していないような任意の二重化辺集合D(u,v)について考えよう。g(u1,lu,v）g(lu,v,u2）＞０である場合、
【０１４６】
【数１０】
2010287155.tif 000012
【０１４７】
【数１１】
2010287155.tif 000013
f'(ru,v,v1 ）f'(v2 ,ru,v）＞０の場合も同様である。これらの操作はすべてG'revの容量制約に違反しない。さらに、この操作によって、各制御点対に対してg'は正則となる。したがって、各制御点対は超過も不足も持たない。また、各超頂点対の超過は増える可能性はあるが、減ることはない。ここでt1 の超過が増えたとすると、流量をM'より大きくできてしまうことになり、gが流量最大の減衰流であるという仮定に反する。また、他の点で増えた超過を流すことによって流量を増やせたとしても、同様に仮定に反する。よって、g'は流量M'であり、正則な流量最大の減衰流であるから、命題によって、流量M'で終点以外に超過のない、正則な減衰流f'が存在する。［証明終了］
補題１，補題２，補題３を組み合わせることで、以下の系が得られる。
［系１］任意の部分反転ネットワークGi,revの流量最大の減衰流fに対して、それと等価なG'revにおける流量最大の減衰流f'が存在し、genmax（Gi,rev）＝genmax（G'rev）となる。一方で、G'revにおける流量最大の減衰流g'に対して、それと等価で値がgenmax（G'rev）である流量最大の減衰流gが存在するような部分反転ネットワークGj,revが存在する。
【０１４８】
系１は定理１より真に強い。したがって、定理１は証明された。  
５．その他の変形例
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）上記の実施の形態では、２個の超頂点を連結する超頂点間辺は、無向であるとしているが、図５０に示すように、超頂点間辺は、有向であるとしてもよい。
【０１４９】
図５０に示す二重化関係ネットワーク７００は、始点７０１、終点７０８、超頂点７０２、７０３、超頂点７０４、７０５、超頂点７０６、７０７、制御点７１１、７１２、制御点７１３、７１４、及び制御点７１５、７１６を含み、超頂点間辺７２１、７２２、７２３及びその他の辺を含む。
超頂点間辺７２１は、超頂点７０２から７０３への向きを有し、超頂点間辺７２２は、超頂点７０４から７０５への向きを有し、超頂点間辺７２３は、超頂点７０６から７０７への向きを有する。
【０１５０】
（２）上記の実施の形態では、超頂点間辺のフロー容量を無限大であるとしているが、これには、限定されない。超頂点間辺のフロー容量は、所定の値であるとしてもよい。
オリジナル関係ネットワークの各辺の容量をＣとすると、超頂点間辺のフロー容量は、Ｃより十分大きい所定の値であるとしてもよい。
例えば、Ｃ＝１であるなら、超頂点間辺のフロー容量＝１０００であるとしてもよい。
【０１５１】
（３）上記の実施の形態では、オリジナル関係ネットワークの各辺に対応して２個の制御点を生成するとしているが、これには限定されない。オリジナル関係ネットワークの各辺に対応して３個以上の制御点を生成してもよい。
３個以上の制御点を生成する場合には、一例として、図１５に示す非減衰制御辺３３３上に、これらの３個以上の制御点が設定される。
【０１５２】
（４）上記の実施の形態では、図１５に示すように、有向経路３３６を構成する減衰制御辺３４１及び減衰制御辺３４２に設定された減衰率は、それぞれ、「（α）＾（１／２）」及び「（α）＾（１／２）」である。しかし、これには限定されない。
有向経路３３６を構成する複数の制御辺に設定された減衰率の積がαとなるように、各辺（非減衰制御辺を除く）に減衰率が設定されればよい。
【０１５３】
例えば、有向経路３３６を構成する減衰制御辺３４１及び減衰制御辺３４２に設定される減衰率は、それぞれ、「（α）＾（１／４）」及び「（α）＾（３／４）」であるとしてもよいし、またそれぞれ、「（α）＾（１／３）」及び「（α）＾（２／３）」であるとしてもよい。
（５）上記の実施の形態では、図１５に示すように、有向経路３３７を構成する減衰制御辺３４３及び減衰制御辺３４４に設定された係数は、それぞれ、「（β）＾（１／２）」及び「（β）＾（１／２）」である。しかし、これには限定されない。
【０１５４】
有向経路３３７を構成する複数の制御辺に設定された係数の積がβとなるように、各辺（非減衰制御辺を除く）に係数が設定されればよい。
例えば、有向経路３３７を構成する減衰制御辺３４３及び減衰制御辺３４４に設定された係数は、それぞれ、「（β）＾（１／４）」及び「（β）＾（３／４）」であるとしてもよいし、「（β）＾（１／３）」及び「（β）＾（２／３）」であるとしてもよい。
【０１５５】
この結果及び上記の（４）の結果、有向経路３３７を構成する減衰制御辺３４３及び減衰制御辺３４４に設定される減衰率は、これらの組合せに依存して定まる。
（６）上記の実施の形態では、関係ネットワーク収集生成装置２００は、Ｗｅｂサーバ装置１００の指示により、始点情報に関する開示情報及び終点情報に関する開示情報を、インターネット２０を介して、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから収集し、収集した開示情報を用いて、オリジナル関係ネットワークを生成するとしているが、これには限定されない。
【０１５６】
関係ネットワーク収集生成装置２００は、あらかじめ、Ｗｅｂサーバ装置６０ａ、６０ｂ、・・・、６０ｃから開示されている全ての開示情報を収集しておき、収集した開示情報を記憶しておく。関係ネットワーク収集生成装置２００は、記憶している開示情報の中から、Ｗｅｂサーバ装置１００から受け付けた条件に基づいて、オリジナル関係ネットワークを生成するとしてもよい。
【０１５７】
（７）上記の実施の形態では、縁検索システム１０は、Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、関係ネットワーク変換装置３００及び縁検索装置４００を含み、Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、関係ネットワーク変換装置３００及び縁検索装置４００は、ＬＡＮ３０により接続されているとしているが、これには限定されない。
【０１５８】
Ｗｅｂサーバ装置１００、関係ネットワーク収集生成装置２００、関係ネットワーク変換装置３００及び縁検索装置４００は、一台の装置から構成されているとしてもよい。
（８）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。前記マイクロプロセッサは、前記コンピュータプログラムに含まれる各命令を１個ずつ読み出し、読み出した命令を解読し、解読結果に従って動作する。ここで、コンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。
【０１５９】
（９）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１６０】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０１６１】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（１０）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１６２】
本発明を構成する各装置は、関係ネットワークから一の対象と他の対象とを関連付ける縁を発見する場合に有用である。また、本発明を構成する各装置は、例えば、インターネット上に開示されている情報を検索する検索エンジンを製造し、提供する産業分野において、経営的に、また継続的及び反復的に、製造され、提供される。
【符号の説明】
【０１６３】
１０    縁検索システム
２０    インターネット
３０    ＬＡＮ
５０ａ〜５０ｃ    ＰＣ
６０ａ〜６０ｃ    Ｗｅｂサーバ装置
１００              Ｗｅｂサーバ装置
１０１    制御部
１０２    情報記憶部
１０３    第１通信部
１０４    第２通信部
２００    関係ネットワーク収集生成装置
２０１    制御部
２０２    情報記憶部
２０３    第１通信部
２０４    第２通信部
２０５    関係ネットワーク生成部
２０６    情報収集部
３００    関係ネットワーク変換装置
３０１    制御部
３０２    情報記憶部
３０３    通信部
３０４    関係ネットワーク変換部
４００    縁検索装置
４０１    制御部
４０２    情報記憶部
４０３    通信部
４０４    縁検索部
４０５    描画部
【図１】
2010287155.tif 000014
【図２】
2010287155.tif 000015
【図３】
2010287155.tif 000016
【図４】
2010287155.tif 000017
【図５】
2010287155.tif 000018
【図６】
2010287155.tif 000019
【図７】
2010287155.tif 000020
【図８】
2010287155.tif 000021
【図９】
2010287155.tif 000022
【図１０】
2010287155.tif 000023
【図１１】
2010287155.tif 000024
【図１２】
2010287155.tif 000025
【図１３】
2010287155.tif 000026
【図１４】
2010287155.tif 000027
【図１５】
2010287155.tif 000028
【図１６】
2010287155.tif 000029
【図１７】
2010287155.tif 000030
【図１８】
2010287155.tif 000031
【図１９】
2010287155.tif 000032
【図２０】
2010287155.tif 000033
【図２１】
2010287155.tif 000034
【図２２】
2010287155.tif 000035
【図２３】
2010287155.tif 000036
【図２４】
2010287155.tif 000037
【図２５】
2010287155.tif 000038
【図２６】
2010287155.tif 000039
【図２７】
2010287155.tif 000040
【図２８】
2010287155.tif 000041
【図２９】
2010287155.tif 000042
【図３０】
2010287155.tif 000043
【図３１】
2010287155.tif 000044
【図３２】
2010287155.tif 000045
【図３３】
2010287155.tif 000046
【図３４】
2010287155.tif 000047
【図３５】
2010287155.tif 000048
【図３６】
2010287155.tif 000049
【図３７】
2010287155.tif 000050
【図３８】
2010287155.tif 000051
【図３９】
2010287155.tif 000052
【図４０】
2010287155.tif 000053
【図４１】
2010287155.tif 000054
【図４２】
2010287155.tif 000055
【図４３】
2010287155.tif 000056
【図４４】
2010287155.tif 000057
【図４５】
2010287155.tif 000058
【図４６】
2010287155.tif 000059
【図４７】
2010287155.tif 000060
【図４８】
2010287155.tif 000061
【図４９】
2010287155.tif 000062
【図５０】
2010287155.tif 000063