(57)【要約】コミュニティの社会的な定義と浸透理論に関連した、複雑ネットワークにおけるコミュニティ発見問題に対する新しいアプローチのための方法と装置を提示する。グラフを上から下に別々のサブグラフに分割するのではなく、コミュニティの重複を許容する、各頂点のコミュニティを発見する局所アルゴリズムを提案する。ランダムに合成したグラフおよび現実世界のネットワークに対するアルゴリズムの実行を利用して、他の方法との比較を行う。局所コミュニティ発見アルゴリズムを用いてネットワークのコミュニティのリストを作成する発見的解決法を提供する。拡散に基づくアルゴリズムとは異なり、本発明が提案するアルゴリズムは、重複するコミュニティを発見し、コミュニティ構造における信頼性を測る手段を提供する。グラフ全体を探索する必要がなく、ネットワークのノード部分集合に関するコミュニティを探索する局所性と低複雑度を特徴とする。
2008545178.tif 000002
【特許請求の範囲】
【請求項１】
リンクしたデータを潜在的に重複したコミュニティにグループ化するコンピュータで実現する方法において、ノードに対して局所コミュニティを決定するステップと、対象となるオブジェクトの性質を知るために前記局所コミュニティを適用するステップとを具えていることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、さらに、少なくとも２つの局所コミュニティを生成するステップと、少なくとも２つの局所コミュニティをコミュニティ構造に統合するステップを具えている方法。
【請求項３】
請求項１に記載の方法において、前記の決定ステップが、コミュニティにノードが属する強度を量化するステップを具えている方法。
【請求項４】
請求項１に記載の方法において、前記の決定ステップが、局所コミュニティを探しているノードからのボンド浸透（ボンドパーコレーション）を採用するステップを具えている方法。
【請求項５】
請求項２に記載の方法において、前記の決定ステップが、局所コミュニティを探しているノードの集合からのボンド浸透（ボンドパーコレーション）を採用するステップを具えている方法。
【請求項６】
請求項５に記載の方法において、前記の採用ステップが、ノードからの浸透メッセージの初期化をするステップと、送信したメッセージを受信したノードからなり、浸透確率が増加する場合にコミュニティサイズが拡大しない連結成分としてコミュニティを識別するステップとを具えている方法。
【請求項７】
請求項６に記載の方法において、前記の初期化ステップが、ノードの集合から個々の浸透メッセージを送信するステップと、送信したメッセージを受信したノードからなり、浸透確率が増加する場合にコミュニティサイズが拡大しない連結成分としてコミュニティを識別するステップとを具えている方法。
【請求項８】
請求項１に記載の方法において、前記の決定ステップが、各リンクに対して重みを指定し、重み付けした局所コミュニティを決定するステップを具えている方法。
【請求項９】
請求項１に記載の方法において、前記の決定ステップが、各ノードに対して重みを指定し、重み付けした局所コミュニティを決定するステップを具えている方法。
【請求項１０】
請求項８に記載の方法において、前記の重みの指定ステップが、ユーザーのクエリーに従って重みを指定するステップを具えている方法。
【請求項１１】
請求項８に記載の方法において、前記の重みの指定ステップが、ユーザーのクエリーに影響されずに重みを指定するステップを具えている方法。
【請求項１２】
請求項９に記載の方法において、前記の重みの指定ステップが、ユーザーのクエリーに従って重みを指定するステップを具えている方法。
【請求項１３】
請求項９に記載の方法において、前記の重みの指定ステップが、ユーザーのクエリーに影響されずに重みを指定するステップを具えている方法。
【請求項１４】
請求項４に記載の方法において、初期クエリーから初期ノードの集合を生成するステップを具えている方法。
【請求項１５】
請求項６に記載の方法において、初期クエリーから初期ノードの集合を生成するステップを具えている方法。
【請求項１６】
請求項１に記載の方法において、前記の決定ステップの結果として発見したコミュニティに従ってリンクしたデータを改変するステップを具えている方法。
【請求項１７】
請求項５に記載の方法において、前記の採用ステップが、繰り返してグラフ全体のボンド浸透（ボンドパーコレーション）を初期化するステップと、ボンド浸透のステップを数多く繰り返すことにより同一の連結成分で発生するノードを決定することで大域コミュニティを識別するステップを具えている方法。
【請求項１８】
リンクしたデータをコミュニティにグループ化する装置であって、本発明による浸透型アルゴリズムをエンコーディングしたソフトウェアを搭載した計算ハードウェアを具えている装置。
【請求項１９】
リンクしたデータをコミュニティにグループ化する装置であって、本発明による浸透型アルゴリズムをエンコーディングしたファームウェアを具えている装置。
【請求項２０】
リンクしたノードをコミュニティにグループ化するコンピュータで実現する方法において、
・各リンクに対して重みを指定するステップと、
・各ノードに対して重みを割り当てるステップと、
・ある特定のノードからの浸透メッセージを初期化するステップと、
・メッセージを繰り返し受信するノードからなる連結成分を決定するステップと、
・浸透確率を増加させるにつれ集合のサイズを拡大しない集合としてコミュニティを識別するステップとを具えている方法。
【請求項２１】
リンクしたノードをコミュニティにグループ化するコンピュータで実現する方法において、
・各リンクに対して重みを指定するステップと、
・各ノードに対して重みを割り当てるステップと、
・ある特定のノードの集合からの浸透メッセージを初期化するステップと、
・メッセージを繰り返し受信するノードからなる連結成分を決定するステップと、
・浸透確率を増加させるにつれ集合のサイズを拡大しない集合としてコミュニティを識別するステップとを具えている方法。
【請求項２２】
請求項２０に記載の方法において、前記の識別ステップが、識別したコミュニティのリンクとノードを表示するステップを具えている方法。
【請求項２３】
請求項２０に記載の方法において、前記の識別ステップが、識別したコミュニティのリンクとノードに対するメタ情報を示す注釈を表示するステップを具えている方法。
【請求項２４】
請求項２３に記載の方法において、前記の識別し注釈を加えられたコミュニティを、この注釈の特定の情報のみによりノードとリンクを保持することで、サブコミュニティに分割する方法。
【請求項２５】
請求項２０に記載の方法において、
・重みを変化するステップと、
・前記の初期化ステップと決定ステップを繰り返すステップとを具えている方法。
【請求項２６】
請求項２５に記載の方法において、前記の変化ステップと繰り返しステップとを繰り返すステップを具えている方法。
【請求項２７】
請求項２０に記載の方法において、
・付加的なリンクしたデータを供給するステップと、
・前記の初期化ステップと決定ステップを繰り返す繰り返しステップと、
・前記の繰り返しステップの結果をユーザーに警告するステップとを具えている方法。
【請求項２８】
請求項２０に記載の方法において、コミュニティ内の強度を得て、コミュニティ感の関係を表示するステップを具えている方法。
【請求項２９】
請求項２０に記載の方法において、前記の初期化ステップと決定ステップを、一定時間繰り返し、識別したコミュニティを比較するステップを具えている方法。
【請求項３０】
請求項２３に記載の方法において、前記の識別し注釈を加えたコミュニティを、ノードとリンクの注釈で利用可能なタイムスタンプ情報を用いて時間で発展する動的な対象として、表示するステップを具えている方法。
【請求項３１】
請求項２９に記載の方法において、前記の繰り返しステップが、繰り返しステップを実行する前の情報を保持するステップを具えている方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は概して、ノードが局所的な相互作用またはリンクを持つ関係システムを解析するための方法に関するものであり、特に、リンクしたデータベースの解析に関するものである。
【背景技術】
【０００２】
ほとんどの情報データベースと知識レポジトリは、異なる関係性により相互に作用するオブジェクトのクラス（分類）を具えているものとして見ることができる。また、オブジェクトおよびこれらオブジェクトの相互作用のクラスは、時間によって変化し、それにより相互作用パターンが動的な様相を呈する。従って、これらオブジェクトおよびその関係性に関する利用可能なメタ情報に基づくことで、動的で複雑なネットワークについての全体の情報を捉えることができる。このネットワークにおいては、ノードが、異なるオブジェクトクラスに属するエンティティまたはオブジェクトを表し、リンクが、結びついたノードがある特定の関係性で関係することを表す。例えば、友人関係の情報データベースでは、ノードは個人に対応し、リンクは２人の個人がお互いに知っていることに対応する。ほとんど全ての情報レポジトリでは、この情報レポジトリの複雑な性質や固有の意味合いを捉えるために、リンクしたデータベースまたはネットワーク表現には、適切に注釈を加えなければならない。例えば、友人関係の情報の例では、各ノードは、例えば、年齢、性別、人種、住所、趣味、職業等の個人に関連する情報を持ち、各リンクには、関係性の性質（例えば、恋愛関連、仕事関連、趣味関連、ファミリー、同じ学校に通っていた等）、および関係性の強度（例えば、どれくらいの頻度で連絡するか等）といった属性で格付けしなければならない。
【０００３】
上述のリンクしたデータベースまたは情報ネットワークは、簡単に、数百万ものノードやリンクを具える非常に大規模なものになり得る。例えば、ワールドワイドウェブ（ｗｗｗ）は、この種のネットワークであり、数十億のノードやリンクを潜在的に有しており、ノードすなわちＵＲＬを連結するリンクという複雑な関係性を有している。このようなネットワークの大規模でかつ時間変動する性質により、ネットワークは動的で複雑なネットワークになり、このネットワークの大きさによって、ネットワークの直接的で包括的なデータマイニングやクエリーが妨げられている。最も一般的な戦略は、深層的なネットワークから構造化データベースを構築し、従来のツールを用いてこの構造化データベースから効率的にクエリーを行うことである。しかし、このインデックス化したデータベースは、深層的なネットワークのある特定の断層や写像を捉えているのにすぎず、データベースを構築する際に抽出した断層に直接的に収まらないクエリーに対して答えることができない。この良い例が、グーグル（Ｇｏｏｇｌｅ）が提供するサービスである。キーワードを与えると、その特定のキーワードを持ち、関連性や重要性に応じて評価されたウェブページを返す。ウェブページの関連性や重要性は、大域的なワールドワイドウェブにおけるウェブページの位置により決まる。すなわち、どれほどの他の「重要」なウェブページが、そのウェブページを示しているか等によって決まる。しかし、例えば、ある会社のウェブでの存在感がどれほどであるか、またはどのような種類の個人やニュース組織がその会社について報告しているか、またはそのような個人やニュース組織が誰についての報告をして、その人が会社にとって関係が深いまたは重要であるかということを訊ねる場合、このような情報を得るための簡単なキーワードは存在しない。そして、様々なキーワードによって徹底的な検索をし、その後で多くの後処理をし、このような情報を推論しなければならない。それでも、その会社に対して直接的に報告した個人や組織のみしか見つけることができないかも知れず、この直接的な報告に非常に関連している他の個人や組織を見つけることは困難であろう。このような情報が、深層的なネットワークに埋まっていることは明らかであるが、キーワードに基づく検索では利用できない。どのようにこの問題に取り組み、このような情報を効率的に抽出するかについては、明らかにされてこなかった。
【０００４】
近年、この方面での、いくつかの発展がなされており、複雑ネットワークまたはグラフ中のいわゆる「コミュニティ」が調査され始めている。この基礎となる動機（モチベーション）は、しばしば我々が、個人が属するコミュニティを調べることによって、その個人の多く知るということから由来する。今まで、この「コミュニティ」の概念は、単に構造的なものであって、様々な研究者が、文献において、コミュニティの様々な概念を使用してきた。しかし、共通の論旨は、構造的なコミュニティは、ネットワーク中の他のノードに比べて、ノード同士でより強く相互連結しているノードの集合であるというものである。
【０００５】
近年まで、複雑ネットワークおけるコミュニティ発見の問題は、グラフの分割という背景（文脈）においてのみ研究されてきた。参考文献９，１２，１５，２１に示す近年のアプローチでは、ネットワークのモジュラリティの分割を最適化することによって、コミュニティがどのように識別され探索され得るかについての新たな洞察を行っている。これらの方法は拡散理論に影響を受けており、高い辺間隔度（betweenness）を持つ辺を剪定し、グラフを上から下に分割し、凝集性のあるコミュニティを得る。
【０００６】
ネットワークのコミュニティ構造を見つけ、深く関係した頂点の組を識別することには、様々な分野において多くの応用が存在する。並列コンピューティング、ＶＬＳＩ  ＣＡＤ、調節ネットワーク、デジタルライブラリおよび交友関係の社会的ネットワークという背景の中で、異なる方法が用いられてきた。グラフ分割の問題は長い間、関心がもたれてきた。ＶＬＳＩの配置が負荷バランスを取るようにグラフを２分割するためのＫ‐Ｌ（Kernighnan-Lin）アルゴリズムが、１９７０年に初めて提案された。散在するマトリクスを分割するためにスペクトル分割が使用された（参考文献１４）。また、凝集性のある社会的コミュニティを見つけるために、階層的クラスタリングが提案された（参考文献１８）。これらのアルゴリズムは、特定の分割されたグラフに対しては良く機能するものの、一般的な複雑ネットワークのコミュニティ構造の探索と識別には機能しない。特に、これらのアルゴリズムでは、通常、コミュニティの数とサイズが入力として必要になる。
【０００７】
分枝型（divisive）と凝集型（agglomerative）のクラスタリングアルゴリズムが多く提案されている。これらのアルゴリズムは、ほとんどが拡散理論の影響を受けており、コミュニティの境界を、高い辺間隔度を持つ辺またはノードとして識別する。ネットワーク中のコミュニティまたはグループに関する標準的な定義は存在しない一方、これらのアルゴリズムでは、グループの社会的な形成と相互作用に基づく提案した定義を用いている（参考文献１９）。参考文献９と同様に、ラディッチ（Radicchi）らは、強い意味と弱い意味でのコミュニティを定義した（参考文献１５）。各ノードが、コミュニティ内でグラフの他の部分より、より連結している場合、サブグラフは、強い意味でコミュニティであるとした。同様に、サブグラフ内の全ての等級の和が、ネットワークの他の部分への全て等級の和より大きいとき、このサブグラフは、弱い意味でのコミュニティであるとした。同様の定義が参考文献７において用いられており、ウェブのコミュニティをウェブページの集まりとして定義し、メンバーとなる各ページがコミュニティ内でこのコミュニティの外側より、より多くのハイパーリンクをどちらかの方向で持つような集まりとして定義した。グループの社会的な定義に影響を受けて、ガーバン（Girvan）とニューマン（Newman）は、辺間隔度の複数の定義を用い、ネットワークの辺を剪定し、ネットワークをいくつかのコミュニティに分割する分枝型のアルゴリズムを提案した（参考文献９）。このアルゴリズムは、ｍ本の辺とｎ個の頂点を持つ任意のネットワークで、計算量Ｏ（ｍ２ ｎ）という大きな計算量になる。参考文献１２，１５，２１のより早いアルゴリズムでは、辺間隔度や同様の考えに基づいており、参考文献１２では、コミュニティの質を評価するためにモジュラリティ手法が提案されている。参考文献４では、参考文献１２をより早く実現する方法が提案されており、ネットワークのコミュニティ構造を記述する系統樹（デンドログラム）の深さをｄとしたとき、計算量はＯ（ｍｄ ｌｏｇ ｎ）となる。
【０００８】
局所アルゴリズムを用いた、コミュニティ発見の高速アルゴリズムは、極めて大規模なネットワークの解析に有用で、複雑ネットワークの識別や解析の応用に有用であることがわかっている。このような方法は、社会的ネットワーク（参考文献１３）、生物学的ネットワーク（参考文献３，１７）および、ソフトウェアネットワーク（参考文献１１）を含めた多数の様々な応用例に適用されている。
【０００９】
しかし、これらの提案された方法は、重複したコミュニティを識別することや、ノードがコミュニティに属する程度を識別することができない。また、これらの方法は、ネットワークの部分集合からコミュニティを生成するのに、ネットワークの大域的な情報を必要とする。ヒューバーマン（Hueberman）らは、ＧＮアルゴリズムがネットワーク構造に非常に影響を受けやすく、ネットワーク構造中の小さな摂動により、異なる解が得られる可能性があることを指摘した（参考文献２１）。解決策として、ヒューバーマンらは、このようなアルゴリズムを確率化したものを提案し、コミュニティ構造のロバストネス（エラー耐性）と信頼性を得た。しかし、このアルゴリズムはまだ、中央処理的なもので、ネットワークの大域的な情報を必要とする。非中央処理的なアルゴリズムの多くは、ランダムウォーク（参考文献１０）またはｌ‐ｓｈｅｌｌ法（参考文献１）に基づく。これらのアルゴリズムは、複雑ネットワークのコミュニティ構造を識別する局所的な方法を提案している。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
以上の提案されているアプローチは、以下のような欠点を持つ。
【００１１】
大域の情報が必要となること。
提案されているアプローチでは、ネットワーク構造の大域の情報が必要である。すなわち、これらのアプローチでは、ノードのある特定の部分集合とその回りのコミュニティ構造を発見するために、ネットワークの大域的な構造を知る必要がある。これは、通常、ある特定のノードやノードの集合に関するコミュニティに関心を持つ大規模ネットワークにとって、特に重要なことである。
【００１２】
重複するコミュニティを扱うことができないこと。
提案されているコミュニティ発見アルゴリズムでは、まだ、凝集性のあるサブグループを発見しているだけである（参考文献１９）。すなわち、ネットワークをコミュニティに分割し、コミュニティ構造のデンドログラムを得ているだけである。ＬＳやλ集合のような凝集性なあるサブグループは、メンバー全てではなくいくつかのメンバーを共有することにより、重複することがないことに留意されたい（参考文献１９，２３）。これらの集合がグラフ内の包含関係により関係し、集合には階層が存在する。現実世界のネットワークではしばしば、凝集的で独立した集合を持たず、むしろ提携ネットワーク（affiliation network）のように重複するコミュニティを持つ。このようなネットワークは、イベントまたはコミュニティの集合と共に、参加者の集合の提携に注目した２つの方式のネットワークであり、各イベントは、重複する可能性のあるコミュニティの部分集合からなる。コミュニティの重複部分を捉える新たなアルゴリズムが必要である。
【００１３】
計算量が大きいこと。
ニューマン（Newman）の高速コミュニティ発見法（参考文献４）の実行には、計算量Ｏ（ｍｄ ｌｏｇ ｎ）がかかることが報告されており、ここで、ｄは、コミュニティ構造を記述するデンドログラムの深さである。多くの応用例では、ノードの部分集合に関係する特定のサイズのコミュニティを発見することが求められているに過ぎない。提案されている拡散型のアルゴリズムは、局所構造を捉えるためにネットワーク全体の処理が必要であるという意味では、規模を測っていない。下から上への局所アルゴリズムにより、検索の制約に対する柔軟性を得ることができ得る。
【００１４】
信頼性に欠けること。
あるＧＮ法では、コミュニティのノードに対する信頼性は得られない。このことは、参考文献２１において言及されているが、未だ、コミュニティに属するノードの信頼性を測るための完全なフレームワークはない。
【００１５】
構造的コミュニティ対情報的コミュニティ。
従来のコミュニティ発見アルゴリズムでは、密集するノードすなわち、ネットワークの残りのノードより、よりリンクしたノードから成るコミュニティを発見する。しかし、リンクしたデータベースにおいては、異なるタイプの辺とノードがあり、コミュニティには、異なる関係性に関して関心を持ち得る。例えば、友好関係のネットワークでは、恋愛関係や家族関係に基づくコミュニティにのみ関心が持たれる。このような例では、このような関係を表現する辺だけを保持し、残りを削除した関心に基づくサブネットワークを処理する。同様に、ある期間にのみ固有のコミュニティまたは、地理的な場所の集合に制限されたコミュニティに関して訊ねることがあり得る。このようなコミュニティは、情報的コミュニティと呼ぶことができる。このような情報的なコミュニティおよびその組み合わせ、これらの和集合や積集合を各ノードに対して計算すると、すぐに、組み合わせの爆発的増大の壁にぶつかることは明らかである。さらに、このことから、検索要求に基づいて情報的コミュニティを発見する必要性が強調される。その上、上述したように、ある特定のノードやノードの集合に対する情報的コミュニティに関心が持たれる可能性もある。
【課題を解決するための手段】
【００１６】
本発明は、コミュニティがネットワーク中でどのように形成されるかという局所的な性質を利用し、また、浸透理論によって、局所的で分散的な方法で重複するコミュニティを探索し識別する手段を得るということを利用する。詳述すると、ここでは、ノードまたはノードの集合の局所的な構造的コミュニティを定義するが、以下のように定義する。固定した浸透確率において試行を繰り返したとき、「高い」時間的割合で、ある特定のノードからメッセージが浸透を介して到着するノードまたはノードの集合からなり（この「高い」時間的割合を定義する閾値の精密な値は、調整し得るパラメータである）、また集合のサイズが、浸透確率の範囲で固定されたままであるノードまたはノードの集合として局所的な構造的コミュニティを定義する。このような構造的コミュニティのノードの強度は、浸透メッセージが何回届いたかの測定値、およびコミュニティを得るために用いた浸透確率を基準とする。例えば、浸透確率を１と設定する場合、ネットワーク全体にメッセージが届き、単一の連結成分を形成していると過程する。よって、あるノードに届くために必要な確率が高ければ高いほど、そのノードのコミュニティ内での強度は低くなる。異なる確率でノードの集合から浸透をさせ、ノードの相互作用と重複を決めることにより、本発明によるノードの集合に対する局所的な構造的コミュニティを決めることができる。
【００１７】
局所的コミュニティの上述した定義の妥当性は、後述する浸透理論および浸透閾値により支持される。さらに、我々の結果に示すように、この定義は、文献においてコミュニティを定義するために一般的に用いられる判定条件を包含している。関心を持たれる特別な話題の１つは、ここで定義したコミュニティと、与えられたノードに対するｋ最近傍の概念との関係である。後述において、あるノードに対してｋホップで到着する全てのノードを決定する。局所的コミュニティのこのような定義に潜在的に存在する問題は、ほとんどの複雑ネットワークにおいて、数ホップでほぼ全てのノードに到着し、例えば２、３ホップで到着するノードの数が非常に大きいことである。これらのノードの全てが、対象とするノードと関係しているわけではない。メッセージの浸透によってコミュニティを定義する方法が、ロバストな（エラー耐性のある）方法であり、自然科学、工学および社会科学の様々な分野のコミュニティの概念と関係し得ることを後述において示す。
【００１８】
ここで、局所的な構造的コミュニティの概念を一般化し、局所的な情報的コミュニティの解釈を含めるようにする。情報的コミュニティには、関心のある関係性のみを包含させ、目立たせたい。重み付けした浸透確率を用いることで、これを本発明によるフレームワークに組み込む。すなわち、メッセージを浸透させるとき、このメッセージが辺に送られる確率を、重みにより改変し、この重みは、リンクに対して割り当てると同時に、メッセージのあるノードに関連して決める。これにより、ある特定の特性値に関してノードまたはノードの集合が属するコミュニティを抽出することができる。例えば、ある一定期間における他のノードとの相互関係という観点から、あるノードのコミュニティを得たい場合、１つの方法では、その期間に属さない全てのノードと辺に０の重みを割り当てる。すなわち、対象とする期間の間、これらのノードと辺が作られず、また存在していないということになる。また、局所的な構造的コミュニティの概念は、局所的な情報的コミュニティの特別な事例であることに留意されたい。すなわち、情報的コミュニティにおいて、全てのノードと辺を、同じ重みで扱う場合と等価である。このため、本発明の特許請求の範囲および、この他の文章では、上述の局所的な情報的コミュニティを示す用語として局所コミュニティという用語を用いる。
【００１９】
データベースから始め、メタ情報を識別することでネットワークを構築する。このメタ情報としては、例えば、生成されるネットワークのノードを定めるために用いるデータ特性、関係性、およびノード（頂点）を連結するリンク（辺）を定める関係性の重みがある。
【００２０】
本発明によると、クエリーによってリンクしたデータベースを処理し、種となるノードを１つ以上識別し、いくつかの種類の辺とノードに対して１つ以上の重みを与える。この重みは、各辺および各ノードで異なり得る。浸透型アルゴリズムを適用することによって、特に、後述のボンド浸透型（ボンドパーコレーション）アルゴリズムを適用することによって、ネットワーク内の頂点の構造的近傍を探索し、構造的近傍を構築するコミュニティを識別する。さらに、ノードのコミュニティに対する関係性の強度を決定する。
【００２１】
更に本発明によると、本発明による処理の結果を、様々な側面で解析することができる。
例えば、構文解析によってコミュニティを調べることができ、コミュニティにおけるノードまたはリンクの特性を定める、または、コミュニティのメンバー間での共通性を決定するための概念を定める。さらに、コミュニティの中心に位置することから強度を判別し強度の強いノードからのキーワードに高い重みを与えることで、この解析を改良することができる。こうして、リンクおよびノードの両者の重みを調整することが可能である。
本発明による更なる処理により、ノードとリンクに割り当てた重みを用いる概念と関連したサブコミュニティを作成する。このさらなる処理を、コミュニティ構造を改善するために求められるだけ繰り返し、または所要に応じた異なる観点でコミュニティを解析することができる。
【００２２】
本発明による装置は、本発明による浸透型アルゴリズムをエンコードしたファームウェアと、本発明による浸透型アルゴリズムをエンコードしたソフトウェアを搭載したハードウェアとを具える。
【００２３】
また、本発明による装置は、本発明による浸透型アルゴリズムをエンコードしたコンピュータの可読メディアを具える。
【００２４】
本発明の利点の１つは、ユーザーが、ノードやリンクの重みを含むクエリーを行うことで、ユーザーの目的に対して処理の結果を調整することが可能であることである。
【００２５】
本発明の利点の１つは、隙間部分（ＧＡＰ  ｐａｒｔ）であるコミュニティ間のリンクと強度を識別し、コミュニティ間の重要な関係を探索することができることである。
【００２６】
本発明のさらなる利点は、特定の応用に対して調整した予め特定した概念と重みをパッケージで提供できることにある。
【００２７】
本発明のさらに別の利点は、ユーザーの選択したパラメータに関連するデータベースの更新を監視し、関連する新しい情報をユーザーに警告する監視役機能を実現できることにある。
【発明を実施するための最良の形態】
【００２８】
本明細書において、本発明による浸透理論に基づく局所アルゴリズムを説明する。そして、局所コミュニティの発見方法を、複雑ネットワークのコミュニティ構造の検出および探索のアルゴリズムに法則化する。その後、文献においてコミュニティ発見アルゴリズムの性能を評価するために採用されたランダムに生成したネットワークおよび現実世界でのネットワークを様々用いて行った本アルゴリズムのベンチマークを説明する。
【００２９】
事例１
浸透型のコミュニティ発見のアプローチ
ここでは、コミュニティの社会的定義を採用し、従来の拡散に基づくアルゴリズムと比較して、浸透によりある特定の頂点のコミュニティを識別することを示す。次に、ＥＲランダムグラフに対する本アルゴリズムの要点および性能を示す。
【００３０】
Ａ．再訪した社会的コミュニティ
種々の定義により、グラフの分割における重要な洞察は得られているが、ここではより局所的なアプローチを選択する。凝集性コミュニティの定義とは異なり、ガートン（Garton）らは、以下のようにコミュニティを定義した（参考文献８参照）。社会的ネットワークの解析の文脈において、グループは、経験的に発見される構造であると。母集団のメンバー間における関係の傾向を調べることで、参加者間同士が強く相互連結した集合としてグループが生じ、これはクリーク（clique）やクラスタ（cluster）として知られる。ネットワーク解析の用語では、これらは、密に織り込まれているとか（densely-knit）、厳しく囲まれている（tightly-bounded）という。すなわち、ほとんどの重要な結びつきが、画定したネットワーク内でなされている（参考文献１８〜２０）。そして、社会ネットワークの分析者は、グループを画定し維持する関係の種類や傾向と並んで、誰がグループに属しているかを知ろうと欲する。この定義は、ニューマンやその他の人物が用いた、ほとんどの重要な結びつきがコミュニティ内でなされるだけでなくノードが高度に相互連結しているという凝集性による前述の定義とは異なることを記しておく（参考文献１９）。また、この定義は、コミュニティ間の重複を許容する。
【００３１】
この定義は、機能または関心に近い頂点が極めて密集したコミュニティを形成する多くの生物学的ネットワーク、社会ネットワークまたはＷｅｂネットワークにおいて、自然に生ずるものである。ある１つの頂点はコミュニティ内の多くの他の頂点と連結する。
【００３２】
Ｂ．浸透理論：背景
本発明の実施例において、ある頂点に対する構造的に近傍の頂点を探索し識別するためのツールとして、ボンド浸透（ボンドパーコレーション）を用いる。浸透理論は最初、多孔性の媒体中における流体の流れを研究するために用いられたが、拡散理論が通常支配されていた問題に対する新しいアプローチとして導入された。浸透理論は媒体の構造内のランダム性や無秩序性を説明するために用いられており、一方拡散プロセスは、決定論的構造内のエージェントのランダムな動きを説明するために用いられている。同様の概念が、複雑ネットワークの文献に広く用いられてきており、ランダムウォークやノードおよび辺の故障に対するネットワークのロバストネスといった、ネットワークにおける様々な現象をモデル化し解析している。非線形の動的特性を持つ複雑ネットワークの多くは、システムの構造およびエージェントの移動の相互作用に影響を与える様々な要因に従い、相転移する。
【００３３】
他のコミュニティ発見アルゴリズムでは、拡散プロセスおよびランダムウォークを使用して、隔度（betweenness）を定め、ネットワークを様々なコミュニティに識別することが広く行われている。本発明では、異なるアプローチである浸透理論を用い、お互いに強く結びつく頂点の高度に密集したグループを識別する。拡散に基づくアルゴリズムでは、コミュニティの境界線にあるエッジの辺間隔度（参考文献２４）が高いとの観察に基づいており、これは、コミュニティの境界線のエッジにより別々のコミュニティにおけるノード間の連絡（コミュニケーション）が可能になるからである。図１は、この概念を示しており、エッジの太さが、ネットワークの全ての頂点間における最短経路の辺間隔度に比例している。凝集的なコミュニティの境界は簡単に識別できる一方、重複しているコミュニティに対しては良く機能していないことが簡単に見て取れる。ランダムウォークを実行する代わりに、あるノードから浸透メッセージを送り、連結部分の集合を構築し、そして、図２に示すように浸透確率が増加するにつれてサイズが拡大しない連結部分を観察する。図１Ｄおよび図１Ｅに、分散的な浸透型の探索により、ノードに対して非常に密集した集合を得ていることを示す。ここで、ノードのサイズは浸透メッセージの返答される割合に比例している。ランダムウォークに基づくアルゴリズムは、幅優先探索をランダム化したものである一方、浸透型の方法は、深さ優先探索をランダム化したものと見ることができる。
【００３４】
Ｃ．ランダムグラフに対する性能
ランダムグラフにおける単純なコミュニティモデルを見ることで、経験に基づく社会的定義と複雑ネットワーク解析との間の関係を示す。コミュニティ発見アルゴリズムの単純な性能を解析した文献では、非常に密集したＥＲグラフの組が広く用いられてきた（参考文献９，１２，１５）。ランダムグラフは、グラフの頂点や辺およびこれら接続の数のような特性が、何らかのランダム手法により決定されるグラフである（参考文献２）。ランダムグラフの多くの単調増加特性に関して、ある閾値より若干小さいサイズのグラフは、この特性を持つことはほとんどあり得ないが、一方、グラフの辺を少し増やすだけでほぼ確実に、グラフがこの特性を持つ。これは、相転移または閾値現象として知られている。グラフにおける最大の連結成分のサイズが、特に重要である。ＥＲグラフＧ（Ｎ；ｐ）は、ｎ個の頂点を持つランダムグラフで、頂点の各対が、この対間に確率ｐで辺を持つ（参考文献５，６）。任意な２個の辺の存在は、独立事象である。
【００３５】
サイズＮのランダムＥＲグラフを考えると、各頂点対は、確率ｐ０（Ｎ）で連結する。このことは、グラフ全体で、浸透確率ｐ０（Ｎ）による（結合）浸透（ボンドパーコレーション）として見ることができる。エルディッシュ（Erdos）とレーニイ（Reneyi）は、ｐ０（Ｎ） がｐ０（Ｎ） ∝ ｃ／Ｎのときに、連結成分が興味深い特性を持つことを示している（参考文献５，６）。ｃに基づいて、十分大きなＮに対して確率１で以下の特性が表れる。
Ｉ．ｃ＜１の場合、最大の連結成分のサイズがΘ（ｌｏｇ（Ｎ））である。
II．相転移時においてｃ＝１の場合、Θ（Ｎ２／３）
III．ｃ＞１の場合、巨大連結成分が現れ、サイズがΘ（Ｎ）である。
【００３６】
所見１：ＥＲグラフＧ（Ｎ；ｐ０） において、結合浸透（bond percolation）を確率ｐｐとするとき、ＥＲグラフは、Ｇ（Ｎ；ｐ０・ｐｐ） となる。
【００３７】
こうして、確率ｐ０でランダムに発生させたグラフに対する臨界浸透確率は、ｃ＞１として、ｐｃ＝ｃ／（ｐ０Ｎ）により与えられる。この確率より小さい場合、頂点ｉは最大サイズΘ（ｌｏｇ（Ｎ））の連結成分に属し、この閾値より大きい場合は、ほぼ全ての頂点が巨大連結成分に属する確率が一定になる。すなわち、Ｎが十分大きいときは、ランダムに選んだ頂点対間経路が、消えない一定確率で存在する。
【００３８】
確率ｐで（結合）浸透するとき、頂点ｉに関して、この頂点ｉを含む連結成分ｉとして集合ＳｉＰを定義する。強度ｐの頂点ｉに対してコミュニティを、（ｊ，ｍ） の組としてＣｉＰで定義し、ここでｋ回繰り返し中ｍ回繰り返しｍ＞ｋｔｈとして、ｊ∈ＳｉＰである。
【００３９】
残った問題は、どのように頂点ｉが、自分のコミュニティを識別するかという問題で、
すなわち、浸透の強度ｐがどのような値をとるときに、コミュニティが識別可能になるかという問題である。似たような関心または話題を持つ頂点の集合としてのコミュニティの定義に一旦戻ると、浸透確率が変動するときに、連結成分としてコミュニティが出現することを観察することができる。これをより詳細に説明するために、サイズＮ、確率ｐ０のＥＲグラフＧ（Ｎ；ｐ０） の単純な例を考える。ノードの部分集合Γが、サイズＭの局所コミュニティを形成する。すなわち、図３に示すように、頂点の各対が確率ｐｒ ＞＞ｐ０で連結する。
【００４０】
所見２：十分大きなＭ、Ｎ、および浸透の閾値ｃ／（ｐ０Ｎ） ＞＞ｐｃ＞＞ｃ／（ｐｒ Ｍ） に対して、連結成分に属する任意な２個の頂点ｉおよびｊの確率は、この２個の頂点が部分集合Γに属する場合１であり、その他の場合は、無視できるくらい小さい。
【００４１】
証明：証明は、上述の特性IIに従う。これは、浸透（パーコレーション）の閾値が、部分集合ΓのＥＲグラフに対する閾値を上回り、全体ＥＲグラフの浸透（パーコレーション）の閾値を下回るからである。
【００４２】
このことは、部分集合Γの任意の頂点ｉに対して、ＣｉＰが、ｃ／（ｐ０Ｎ）＞ｐ＞ｃ／（ｐｒ Ｍ）に対してほぼ部分集合Γになり、ｐ＞ｃ／（ｐ０Ｎ） に対してＥＲグラフＧのほぼ全ての頂点となることを意味している。
【００４３】
ここで、重複するおよび重複しない複数のコミュニティに対して定義を法則化し、様々な例におけるＣｉＰの挙動を検証する。サイズＮ、確率ｐ０のＥＲグラフと、それぞれ、サイズＭ１，Ｍ２で、連結確率ｐ１＞＞ｐ０，ｐ２＞＞ｐ０の２個のサブグラフΓ１，Γ２を考える。臨界浸透確率ｐｃｉ＝ｃ／（ｐｉＭｉ），ｉ＝１，２を定義する。浸透確率を図示せず、連結成分を、重複する場合と重複しない場合の両方に対して図４Ａおよび図４Ｂに示す。
【００４４】
ｃ／（ｐ０Ｎ）＞ｐｐ＞ｍａｘ（ｐｃ１，ｐｃ２） に対して、浸透確率はサブグラフの浸透確率より大きいので、所見２より、各コミュニティのほぼ全ての頂点を連結する。ここで、２つの場合を考える。
【００４５】
１．Γ１ とΓ２ が重複部分を持つとき、同一のサブグラフ中の任意な２個の頂点は、ほぼ確実に連結する。よって、双方のコミュニティに属する任意な２個の頂点は、ほぼ確実に連結する。Γｋ のあるノードから、浸透を開始すると、Γｋ のノードからｑｋの割合の繰り返しで戻り、他のコミュニティからｑ１ｑ２の割合の繰り返しで戻る。
【００４６】
２．Γ１ とΓ２ が重複部分を持たないとき、浸透時にΓｋ の任意のノードから、任意の他のノードへ移動する確率は、消えない定数ｑｋである。そして、あるコミュニティのノードｉから、別のコミュニティのノードｊへ移動する確率は、１−（１−ｑ１ｑ２）αであり、αは２個のコミュニティ間における辺の期待数で、このモデルではおおよそ、α＝Ｍ１Ｍ２Ｐ０である。よって、コミュニティ間で強く連結していても２個のコミュニティ間では弱い連結になり、その連結の強さは、  おおよそ、コミュニティ間の辺の数に依存する。
【００４７】
上述の解析により、ＣｉＰが、コミュニティに対応する臨界確率において、相転移することが予測でき、この解析により、全体的な情報がなくても、局所的な方法でコミュニティの識別が可能になる。
【００４８】
局所コミュニティ発見
Ａ．アルゴリズム
各頂点に対してコミュニティを発見するアルゴリズムでは、浸透確率ｐｐで浸透メッセージを送り、ｐｐの範囲でＣｉＰｐを形成し、コミュニティの大きさの急激な変化を見つける。
１．頂点ｉは、繰り返し（イテレーション）を識別する固有の識別子（ＩＤ）をつけて浸透確率ｐｐでメッセージを送る。
２．返答を記録し、返答した頂点からなる集合ＳｉＰｐを作る。
３．上記のタスクを、ｋ回行い、ｋｔｈより多く返答した全ての頂点からなる集合ＣｉＰｐを作る。
４．ある範囲のｐｐでＣｉＰｐを算出し、浸透確率ｐｐｌにおいてＣｉＰｐの急激な変化を確認し、ＣｉＰｐｌとして強度Ｐｐｌのコミュニティ層ｌを定義する。
【００４９】
上述のアルゴリズムは、通常、送信元ノードに対して極めて密集して強く結びついているノードを発見するが、拡散アルゴリズムでは、高い辺間隔度を持つ辺や、ランダムウォークにおいて流れの多い辺を見つけ、コミュニティ間の境界を見つけようとする。図１では、拡散に基づくアルゴリズムと浸透に基づくアルゴリズムとを比較する。
【００５０】
Ｂ．利点
浸透に基づくアルゴリズムを用いることで、文献にある、分枝型（divisive）および凝集型（agglomerative）のアルゴリズムを凌ぐ利点を多く得る。浸透に基づく検索の分散的で並列的な性質によって、参考文献１６で「構造近傍(structure neighborhood)」と称するある特定のノードに関して、コミュニティを局所的に探索する手段を得る。しばしば、現実世界のネットワークにおいて、コミュニティは、凝集性のものではなく、重複部分を持つ。このような場合は、拡散に基づくアプローチでは、コミュニティ間を区分けする境界が存在しないので、コミュニティを発見することができない。本発明によるアルゴリズムでは、コミュニティを探索し、コミュニティの重複部分にある頂点を識別する。コミュニティ構造におけるもう１つの関心のある特性は、頂点がどれほど強くコミュニティに属しているかということと、コミュニティ構造の信頼性の程度である。浸透による検索では、ある頂点からの返答メッセージの割合を見ることで、これらの統計値を簡単に得ることができる。図１は、拡散と浸透に基づくアプローチの基本的な違いを示す。ｎ個の頂点とｍ本の辺を持つネットワークに対して、他の種類のコミュニティ発見アルゴリズムでは、コミュニティ構造を計算量Ｏ（ｍｄｌｏｇ（ｎ））で見出す（［参考文献４］参照）。ここでｄは、コミュニティの系統樹（デンドログラム）の深さである。しかし、ある特定のノードのコミュニティ構造を発見するのにグラフ全体を処理する必要がある。
【００５１】
コミュニティの発見
上述のセクションにおいて、単一の頂点のコミュニティを発見するための局所的で分散的なアルゴリズムに関して説明した。ここでは、この方法を一般化（法則化）し、通常、コミュニティの系統樹（デンドログラム）と呼ばれるグラフのコミュニティ構造を見つける。本例では、系統樹（デンドログラム）は、コミュニティが重複し得るために単純な樹形図ではない。
【００５２】
コミュニティ構造を作るための最初のアプローチとして、頂点間で、非対称な距離ｄ（ｉ，ｊ）を次式ように定義する。
【数１】
2008545178.tif 000003
【００５３】
古典的なクラスタリング手法を用い、この距離マトリクスに対して、ノードを分割しコミュニティを見つけることが可能である（［参考文献２５］参照）。
【００５４】
局所コミュニティ発見アルゴリズムでは、主要なコミュニティを発見するので、これを利用し、本発明は、個々の頂点におけるコミュニティの発見結果を組み合わせた大域コミュニティ発見アルゴリズムを含む。このアルゴリズムは、既に提案されたアルゴリズムに対して、いくつかの利点がある。このアルゴリズムは、複数の頂点に対するコミュニティを統合しているので、ロバスト性（エラー耐性）がより高い。コミュニティの重複を許容し、弱くて重要でないコミュニティは自動的に削除される。
【００５５】
コミュニティ発見アルゴリズム
【数２】
2008545178.tif 000004
各コミュニティ対（Ｃ１，Ｃ２）に対して、以下の処理をする。ここで、ｍ１は、コミュニティｉを統合した回数である。類似度Ψ１，２を、（ｎ１，２−（ｎ１＋ｎ２））／ （ｎ１，２ −（ｎ１＋ｎ２））として定義する。
１．ネットワークの各頂点ｉに対して、局所コミュニティ発見アルゴリズムを実行し、浸透確率Ｐｐｌに対応する異なるレベルのコミュニティＣｉＰｌを得る。
Ｍ ＝ｍａｘ（ｍ）∀（ｊ，ｍ）∈ＣｉＰｐｌ，ｊ≠ｉとして正規化し、
集合（ｉ，ｍ）＝ｊ（ｉ，１）とする。
２．最大の類似度Ψｍａｘ＝ｍａｘｉ，ｊΨｉ，ｊを持つコミュニティの対ＣｌとＣｋを見つける。
Ψｍａｘ＜１／３のとき３に進む。
３．ＣｋにＣｌを統合し、ｍｋ＝ｍｋ＋ｍｌとする。
４．各残りのコミュニティＣｋを、次式により正規化する。
【数３】
2008545178.tif 000005
【００５６】
結果
本発明によるアルゴリズムの性能をさらに測るために、従来のコミュニティ発見アルゴリズム（参考文献９，１２，１５）の性能を測るために用いられるランダムに生成したグラフと社会的ネットワークおよび生物学的ネットワークとに対する結果を比較する。
【００５７】
Ａ．ランダムに生成したグラフ
本発明によるアルゴリズムを、２組のランダムに生成したグラフに適用する。本発明のアルゴリズムの性能を測るために、参考文献９に提案されている従来のＥＲグラフを用いる。その後、ランダムに生成したグラフの重複モデルを用いて、分割アルゴリズムと特に参考文献９に提案されている高速コミュニティ発見アルゴリズムとに対する、本アルゴリズムの利点を示す。
【００５８】
１．ランダムに生成し、重複部分を持たないコミュニティ
サイズＮ＝１２８のグラフを多数生成し、３２個の頂点からなる４個の同サイズのコミュニティに分割する。同一のコミュニティ内の任意な２個の頂点は、確率ｐ１で連結し、異なるコミュニティ間の任意な２個の頂点はｐ０で連結する。頂点の次数の期待値は１６となる。本コミュニティ発見アルゴリズムのコミュニティを発見する性能を、コミュニティ内の辺の様々な値に対して調べる。図５は、コミュニティ間の辺の集まりに対して、正しく分類した頂点の比率を示す。この結果を、他のアルゴリズムでの同様の実験に対して評価する。図５からは、提案したアルゴリズムが、コミュニティ間の辺の１頂点に対する平均数が小さいときに、ＧＮアルゴリズムと同様に機能し、コミュニティ間の辺の平均数が大きいときに、顕著に高い性能を発揮することがわかる。コミュニティ内での辺の数と、コミュニティの外側の辺の数とが近いので、ＧＮアルゴリズムはコミュニティの検出に失敗する。本発明によるアルゴリズムは、精度が低くなるがコミュニティの検出を行っている。これは、コミュニティの外側への辺が、ネットワーク中でランダムに配置され、一方内部の辺が、より相互に結びつく頂点から集合を形成するからである。
【００５９】
２．ランダムな重複部分を持たないコミュニティ
前述の例では、ランダムグラフに対するコミュニティ発見アルゴリズムの性能を評価したが、実際のネットワークではしばしば、コミュニティが前述でのモデル化のようにうまく分離されているわけではなく、むしろ、現実世界のコミュニティは、重複部分を持つ。すなわち、２個以上のコミュニティに対して強く結びつくノードが存在する。提案したアルゴリズムの局所的なアプローチによる利点の１つに、重複するコミュニティを正しく識別することがあり、一方、従来の分割アルゴリズムでは、重複する頂点を１つのコミュニティとして分割してしまう。改良型のＧＮアルゴリズムでは、分割のステップをランダムにすることで、この挙動を捉えることが提案されている（参考文献２１）。
【００６０】
１２８個の頂点を持つランダムに生成したグラフを考える。ランダムな各頂点は、２個のランダムな辺を平均して持つ。サイズ３７の２個のコミュニティが存在し、コミュニティ内では各ノードが１４本のランダムな辺を持つ。また、図６Ａに示すように、２つのコミュニティは、５個の共通のノードを持つ。高速ＧＮコミュニティ発見アルゴリズムと、浸透コミュニティ発見アルゴリズムの双方を適用した。ＧＮ法は、図６Ｂに示すように、共通の頂点を１つのコミュニティに分割する一方、本発明による方法は、図６Ｃに示すように、コミュニティを識別し、双方のコミュニティに対しても重複した頂点を含めた。本発明による方法を用いることで、７個のノード｛４４，６０，６１，７７，８８，９０，１０２｝の分類に失敗したが一方、ＧＮ法では、２８個のノードの分類に失敗した。
【００６１】
Ｂ．ザチャリー（Zachary）の空手クラブ
本発明による局所コミュニティ発見アルゴリズムを、ザチャリー（Zachary）の空手クラブのネットワーク（参考文献２２）に適用した。この無指向性グラフは、アルゴリズムの評価のために参考文献９，１２，１５において広く用いられてきた。ザチャリーは、ある期間にわたり、空手クラブのメンバー間の関係を記録した。この研究の間、オーナーとトレーナ間の内紛の後、クラブが徐々に二分された。元々のネットワークと、二分された後の分割の様子を図７Ａに示す。本発明による局所コミュニティ発見アルゴリズムを、ネットワーク内の３つの重要なノードに対して適用した。図７を参照し、ノード１および３３は、管理者とインストラクタをそれぞれ示し、ノード３４はノード３３と近い関係を持つ高次のノードを表す。ここで用いるコミュニティは、参考文献９のものと異なり、そのため、結果が異なることに留意されたい。本発明によるアルゴリズムは、クラスタ内の近くに連結したノードを探す。識別したコミュニティは明らかに重複部分を持つ。ノードのサイズは、コミュニティ内での強度と比例する。図７Ｂは、ノード１に対しての局所コミュニティ発見の結果を示す。想定通り、ノード１７は、コミュニティに対して強い結びつきがないため、孤立している。図７Ｃは、インストラクタに対する、局所コミュニティ発見の結果を示す。ノード２７は、コミュニティとの社会的結びつきが強くないために、コミュニティから孤立している。また、ノード１０，２５，２６，２８，２９が孤立している。図７Ｄは、ノード３４に対するコミュニティを示し、このコミュニティが管理者を含んでいることを示している。浸透確率が対称的、すなわち、ノードｉとｊが同一の連結部分であっても、コミュニティに内包する頂点は、対称的とはならず、ノード３４は、ノード１のコミュニティに含まれない。これは、コミュニティの閾値が、ネットワークの近傍によって、２つのコミュニティで異なるからである。またコミュニティ構造を発見するアルゴリズムも適用した。７個の重複するコミュニティを識別した。図８は、検出したコミュニティ間の関係を図で示す。図９に２つの主要なコミュニティを表す。再び、ノードのサイズは、コミュニティ内での強度と比例する。本アルゴリズムにより、正確にコミュニティを識別可能であり、さらに、コミュニティにおける各ノードの役割と強度を識別することが可能である。いくつかのノードは、コミュニティ間の重複部分に明らかに属し、双方のコミュニティと弱く結びついている。想定した通りに、ノード１および３４は、双方のコミュニティに属しており、これは、両ノードが双方のコミュニティに社会的に強く結びついているからである。また、ノード１２が、管理者（アドミニストレータ）のコミュニティから除外されている。これは、ノード１２がノード１に対して単一の連結をしているからである。
【００６２】
本明細書において、局所的な方法により、ある頂点のコミュニティを発見する新しい分散アルゴリズムを提案する。本アルゴリズムでは、強く相互連結した頂点の集合である、コミュニティの社会的な定義を利用する。本発明によるアルゴリズムを一般化（法則化）し、ネットワークに対するコミュニティのリストを作成する。コミュニティ間の重複を許容し、ネットワークの摂動に対するロバストネス（エラー耐性）を確保することにより、本アルゴリズムが、従来のアルゴリズムよりどのように優れているかを示す。コミュニティにおいて強度の強いノードは、似たような局所コミュニティを持つという事実を利用することにより、本アルゴリズムをさらに最適化することが可能であり、この計算の重複をなくすことで、本アルゴリズムの計算量を削減することが可能である。
【００６３】
基本的な本アルゴリズムにおける変更例では、以下を行う、すなわち、
１．単一のノードの代わりに、種ノードの集合から開始する。
２．大域的で、一様の浸透確率の代わりに、各ノードｉに対して、０から１の間の重みＷ１を割り当てる。ノードｉとｊとの間の各辺に０から１の間の重みＷ１、２を割り当てる。そして、各ノードは、浸透確率ＰＰｅｒｃでメッセージを渡す代わりに、関数ｆ（ＰＰｅｒｃ，Ｗｉ，Ｗｉ，ｊ）として定める確率でメッセージを渡す。この関数は例えば、ＰＰｅｒｃ・Ｗｉ・Ｗｉ，ｊである。
３．ノードおよびリンクは、異なる型を持つことができ、各型は予め定めた重みを有することができる。
４．異なるリンクの重みを、使用パターンまたはコンセプトに基づいて、ある特定のユーザー用に仕込みまた調整することができる。例えば、生物工学の検索を行うユーザーには、食品産業のような他の概念におけるノードの重みを減らすことができる。
５．このメトリックに対するクイック検索を行うことにより、浸透確率に対するスイーピング（掃域探索）を最適化することが可能である。
６．コミュニティの発見の結果を用いて、リンクとノードの重みを調整することができる。
【００６４】
本発明は、適用範囲が極めて広範囲であって、いかなるデータの集合に対してもほぼ適用することが可能である。図１０Ａは、本発明による一般化（法則化）したシステムの一般化（法則化）した処理の流れ図である。この流れ図は、ネットワークの形成、様々な重みの割り当て、および、ネットワークでの局所コミュニティの発見を具える。この処理をフィードバックにより再定義し、クエリー、コミュニティの結果および／またはユーザーのフィードバックにより、重みを調整し、ノードを改変する。図１０Ｂは、参照モデルのシステムアーキテクチャを図示する。本システムは、様々な階層を含む。様々な利用可能な情報データベースからメタデータを読み込み、これらを整理、処理しメタデータのレポジトリに入れる。様々な情報の読み込みコンポーネントを用い、特定のアプリケーション用にデータを解析する。客とウェブサービスは、一般的なインターフェイスを持ったポータルネットワークにアクセスし、クエリーを行い、情報読み込みフレームワークと再定義した情報表示フレームワークが処理した結果を受け取る。図１０Ｃは、本発明によるコアアーキテクチャモデルを図示し、ここで、メタデータのレポジトリは、システムアーキテクチャに関して上述したように、異なる型のデータを解析した連結ストレージからなる。様々なプラグインを用いて、構造的解析エンジンと連動させ、クエリーに答えることができる。標準的な、コマンド／レポートのＡＰＩを用いて、ウェブサービスを介して本システムにアクセスする。
【００６５】
学術論文、特許、米国食品医薬局の臨床治験の書類、製品の説明書、ニュース報道、市場分析、識者による意見書、営業報告書および、これらの和集合や積集合といった書類に対して適用可能である。また、ワールドワイドウェブ、電子メールおよびスパムのフィルタの解析の応用にも適用可能である。また、本発明は、転写調整ネットワークといった生物学的ネットワークのパターン検出や、例えば軍事的な保安や自国の保安への応用目的のための、社会的ネットワークおよびコミュニティに適用可能である。
【００６６】
特許情勢分析において、本発明を用いることが可能で、競争相手の解析をし、会社、概念および技術を継続的に解析した結果にフラグを立てることで、監視役のように競争相手を監視することができる。図１１Ａは、特許情報への応用のためのシステムの流れ図を図示する。結果に対するユーザーの調整をメタデータレポジトリにフィードバックすることにより、結果を再定義する。図１１Ｂは、本発明によるアルゴリズムを適用する前のトランザクションの流れ（トランザクションフロー）を示す。図１１Ｃは、本発明によるアルゴリズムを用いた特許情勢分析への適用に対するトランザクションの流れを示す。
【００６７】
また、本発明により、ユーザーがコミュニティの閲覧をし、単純なバイナリフィルタによって結果を微調整することが可能である。市場分析の適用において、本発明を用い、競争相手、技術、最新ニュース、技術論文や出版物に関する市場の様々な切り口に対するポートフォリオを得ることができる。コミュニティ間の関係を調べることで、コミュニティ間の隔たりがわかり、それにより、競争相手が行っていない機会を見つけることができる。
【００６８】
本発明を用いて、あるウェブサイトの近傍のウェブと、その影響と、ウェブにおけるリンクおよびコミュニティとを見つけることができる。また、ある期間にわたり、近傍の変化を監視することができる。また、本発明により、電子メールとスパムのフィルタを行うことができる。これは、あるアドレスに関連のある人からのメッセージのみを配達し、スパムを減らす方法により行う。
【００６９】
近年、頼んでいない広告メールまたはスパムの問題が、電子メールの遍在的問題と認識されてきている。本発明は、電子認証に関する、より一般的なフレームワークを提供する。このフレームワークは、スパムの問題に対する解決策を提供するだけではなく、電子メールへのアクセスを信頼できる個人に制限することができる。新たな分散的な方法は、浸透理論に基づき、仮想空間において局所ネットワークが信頼する個々のユーザーを、単純な局所的な相互作用を用いることで識別する。日常生活においては、推薦や社会的な結びつきを用いることで、信用と信頼を確認している。同じ社会的なアプローチを用い、電子メールのメッセージの浸透的な通信と、相互作用を社会的な接点に限ることとによって、通信を、局所的に信頼し重複したコミュニティに制限することができる。本発明による方法はさらに、社会的ネットワークの性質を利用し、ユーザーの個人的な電子メールのネットワークに基づく分散的な信頼の網を構築し、同時に、スパムメールおよび不必要な送信元からの電子メールを防ぐ。本アルゴリズムは、電子メールでのコミュニケーションに対する新たなパラダイムを示し、これは、優良リストと有害リストに分ける単純なアプローチに対して優れていることが証明される。
【００７０】
問題は、スパムメールだけでなく、ユーザーが、ユーザーの知らない人からの電子メールを受け取ることにある。連絡先リストに無い場合または、ＣＣ（カーボンコピー）のメールによる紹介でない場合、多くの人は単にそのような電子メールを削除する。このオンラインでの推薦の概念は、本発明により一般化でき、不可視化および直感的なものにできる。本発明による方法は、ベイジアンフィルタおよびテキストに基づくフィルタと組み合わせることができる。
【００７１】
これを実行するアルゴリズムの後方では、本発明が、あるユーザーに対して、重複するコミュニティを適用する。電子メールのヘッダーを改変し、現在の受信者（Ｔｏ）と最終送付先（Ｆｉｎａｌ−Ｔｏ）を含むようにする。そして、電子メールを受け取ると、最終送付先が、そのユーザーの場合、その電子メールはユーザーの受信箱に届けられる。この場合以外で、現在の送付先が自分であり、電子メールの生存期間がある閾値Ｉより小さい場合、その電子メールを、連絡先リストにいる人に、転送確率Ｐで転送する。この転送確率はユーザーが選択し、ユーザーが定める電子メールのコミュニティを制限することができる。ＥというＥメールのメール処理に関するアルゴリズム１を以下の表１に示す。
【表１】
2008545178.tif 000006
【００７２】
ここで、ＳＥＮＤＭＡＩＬ（ＦｉｎａｌＴｏ，Ｆｒｏｍ，Ｔｏ）は、Ｔｏ，ＦｒｏｍおよびＦｉｎａｌＴｏに関して適切なヘッダーを付けてメールを送信することを意味する。
【００７３】
本発明によるアルゴリズムは、分散的な方法または、大規模な電子メールプロバイダ用のメールサーバにおいて本アルゴリズムをエミュレートする集中的な方法で実装可能である。本発明による変形例において、転送確率を、送信者とユーザー間の電子メールのトラフィックに応じて重み付けることができる。
【００７４】
交際活動や娯楽活動を含む社会的ネットワークにおいて、本発明を利用し、社会的な相互作用のデータを用いてコミュニティとコミュニティ間の関係とを識別し、人の集団での最も強い社会的な結びつきを見つけることが可能である。
【００７５】
転写調節ネットワークのような生物学的ネットワークに関して、本発明を用いて、複雑な細胞内の処理を許容しつつ、大規模で処理量の多い配列や実験データから、細胞システムの機能的な設計図を発見ことができる。詳細については、非特許文献１を参照されたい。本発明を用いて、例えば、ゲノムデータや他のデータを取り出し、配列データとの機能的および構造的な相関をとることができる。また、本発明により、文献、特許、患者病歴、治験および、その他のデータを、取り出し、患者の病気の診断や予後診断を支援することが可能である。
【非特許文献１】インターネットサイト  http://arxiv.org/abs/q-bio.MN/0501039
【００７６】
本発明を自国の保安に関するデータに対して適用することで、傾向やコミュニティを明らかにすることが可能である。自国の保安に関するある集団や挙動の傾向を見つけることで、関係のある性質をもつコミュニティを識別することができる。
【００７７】
本発明は、リレーショナル・データベース、関係写像（マッピング）、グラフデータベースを含むデータベースによって実現することができる。例えば、様々な種類の製品版データベースを本発明に用いることができ、このようなデータベースは、例えば、スウェーデン王国ウプサラ  バンガーズガタン  ８Ｓ−７５３  ２０（Bangardsgatan 8S-753 20 Uppsala Sweden）に居所するＭｙＳＱＬ  ＡＢ社のＭｙＳＱＬ（登録商標）や、米国ワシントン州リッディモンド（Richmond, Washington）に居所するマイクロソフト社のＳＱＬ（登録商標）や、米国ファルフォニア州レッドウッドショア  オラクル  パークウェイ  ５００（500 Oracle Parkway, Redwood Shores, CA 94065）に居所するオラクル社のＯｒａｃｌｅ（登録商標）がある。
【００７８】
自然言語処理ツールを本発明とともに用い、例えば構文解析を行うことができる。このような自然言語処理ツールは、米国ニューヨーク州  アーモンク  ニューオーチャード（New Orchard Road, Armonk, New York 10504914-499-1900）に居所するＩＢＭ社のＷｅｂＦｏｕｎｔａｉｎ（登録商標）や、米国テキサス州ダラス（Dallas, Texas）に居所するＥｎｇｅｎｉｕｍ社のＥｎｇｅｎｉｕｍや、米国ニュージャージー州ピスカタウェイ（Piscataway, NJ）に居所するテルコーディア・テクノロジー社のＴｅｌｃｏｒｄｉａ  Ｌａｔｅｎｔ  Ｓｅｍａｎｔｉｃ  Ｉｎｄｅｘｉｎｇ  Ｓｏｆｔｗａｒｅ（登録商標）や、米国テネシー州ノックスビル（Knoxville Tennessee）に居所するテネシー大学のＧｅｎｅｒａｌ  Ｔｅｘｔ  Ｐａｒｓｅｒがある。
【００７９】
また、本発明によると、グラフの可視化や配置のツールを用いて、解析の質を向上することができる。このようなツールは、独国ザールブリュッケン６６１２３スツールザッツェンハウスヴェーク６９（Stuhlsatzenhausweg 69, 66123 Saarbruecken, Germany）に居所するアプスイントアンゲヴァンズト・インフォマティーク社のａｉＳｅｅ（登録商標）や、カルフォルニア大学バークレー校（University of California, Berkekey）とパロアルト研究所（Palo Alto Research Center）において、ジェフリー・ヒア（Jeffrey Heer）により、ＧＮＵに従い書かれたオープンソースのＰｒｅｆｕｓｅや（非特許文献２参照）、Ｊグラフ社のＪｇｒａｐｈ（非特許文献３参照）がある。
【非特許文献２】インターネット  http://prefuse.sourceforge.net/
【非特許文献３】インターネット  http://www.jgraph.com/
【００８０】
本発明を実施例に関して説明しているが、本発明は実施例に限定されるものではない。本発明に関し熟慮することで、当業者により、さらなる変形や改良がなされることが予想されるが、このような変形はすべて、本特許請求の範囲を逸脱しないものである。
【００８１】
参考文献のリストを以下に示す
［１］ Bagrow, J., and Bollt, E. A Local Method for Detecting Communities. ArXiv Condensed Matter e-prints (Dec. 2004). 
［２］ Bollobas, B. Random Graphs Second Edition. Cambridge University Press, United Kingdom, 2001.
［３］ Boscolo, R., Rezaei, B. A., Boykin, P. O., and Roychowdhury, V. P. Functionality Encoded In Topology? Discovering Macroscopic Regulatory Modules from Large-Scale Protein-DNA Interaction Networks. Reprint arXiv:q-bio/0501039 (Jan. 2005).［４］ Clauset, A., Newman, M. E., and Moore, C. Finding community structure in very large networks. Phys. Rev. E 70, 6 (Dec. 2004), 066111-+.
［５］ Erdos, P., and Renyi, A. On the evolution of random graphs. Publications of the Math. Inst, of the Hungarian Academy of Sc. (1960).
［６］ Erdos, P., and Renyi, A. On the strength of connectedness of a random graph. Acta Mathematica Scientia Hungary 12 (1961), 261-267. 
［７］ Flake, G. W., Lawrence, S., Giles, C. L., and Coetzee, F. M. Self-organization and identification of web communities. Computer 35, 3 (2002), 66-71. 
［８］ Garton, L., Haythornthwaite, C, and Wellman,B. Studying online social networks. In Doing Internet Research, S. Jones, Ed. Sage, Thousand Oaks, CA, 1999, pp. 75-105. 
［９］ Girvan, M., and Newman, M. E. J. Community structure in social and biological networks. PNAS 99, 12 (2002), 7821-7826. 
［１０］ Latapy, M., and Pons, P. Computing communities in large networks using random walks. ArXiv Condensed Matter e-prints (Dec. 2004).
［１１］ Luis, J. G.-B. Community structure of modules in the apache project. 
［１２］ Newman, M. E. Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 6 (June 2004), 066133-+ 
［１３］ Newman, M. E. J. Coauthorship networks and patterns of scientific collaboration. PNAS 101 (2004), 5200-5205. 
［１４］ Pothen, A., Simon, H. D., and Liou, K.-P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 1 1 , 3 (1990), 430-452.
［１５］ Radicchi, F., Castellano, C, Cecconi, F., Loreto, V., and Parisi, D. Defining and identifying communities in networks. PNAS 101, 9 (2004), 2658-2663.
［１６］ Rezaei, B. A., and Roychowdhury, V. P. Percolation Crawlers: Finding webneighborhoods. preprint (2004). 
［１７］ Rives, A. W., and Galitski, T. Modular organization of cellular networks. PNAS 100, 3 (2003), 1128-1133.
［１８］ Scott, J. Social Network Analysis: A Handbook, 2nd ed. Sage Publications, London, 2000. 
［１９］ Wasserman, S., and Faust., K. Cambridge University Press. Acta Mathematica Scientia Hungary (1994).
［２０］ Wellman, B., Salaff, J., Dimitrova, D., Garton, L., Gulia, M., and Haythornthwaite, C. Computer networks as a social networks: collaborative work, telework, and virtual community. Annual Reviews Sociology 22 (1996), 213-238.
［２１］ Wu, F., and Huberman, B. A. Finding communities in linear time: a physics approach. European Physical Journal B 38 (2004), 331-338. 
［２２］ Zachary, W. W. San information flow model for conflict and fission in small groups. Journal of Anthropological Research 33 (1977), 452473.
［２３］ ＨをグラフＧ（Ｖ，Ｅ）におけるノードの部分集合とし、ＫをＨの真部分集合とする。α（Ｋ）が、ＫのメンバーをＶ−Ｋのメンバー（Ｋにはないノードの部分集合）に連結する辺の数を表す。Ｈのすべての真部分集合Ｋに対してα（Ｋ）＞α（Ｈ）が成り立つとき、Ｈは、ＧのＬＳ集合となる。ＬＳ集合の重要な性質は、辺の連結性が高いことである。特に、ＬＳ集合の各ノードは、ＬＳ集合の他のメンバーに対して、メンバーでないものに比べ、辺の連結性が高い。特に、ＬＳ集合の各ノードは、ＬＳ集合の他のメンバーに対して、メンバーでないものに比べ、辺の連結性（λ）が高い。この特徴のみにより凝集性の部分集合を定義すると、最大のノードの部分集合Ｓとしてラムダ集合を定義し、任意のａ，ｂ，ｃ∈Ｓおよびｄ∈Ｖ−Ｓに対して、λ（ａ，ｂ）＞λ（ｃ，ｄ）となる。λが高いと、同じラムダ集合のメンバーを、互いに引き離すのは難しい。これは、グラフからラムダ集合のノードを引き離すために必要な辺の数をλが定めているからである。
［２４］ 参考文献９に示されているように、間隔度の定義は、最短路やランダムウォークに基づく、いくつかの方法がある。
［２５］ B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,. Bell System Technical Journal 49, 291-307 (1970).
【図面の簡単な説明】
【００８２】
【図１Ａ】図１Ａ〜図１Ｆは、特定ソースのための、またはすべての頂点対間における辺間隔度を比較する拡散対浸透、および所定の頂点を始点とする浸透を示し、ネットワークは、１〜９および７〜１５の２つの重複するコミュニティで構成されているものとし、図１Ａは、２つの重複するコミュニティを持つ元々の原ネットワークを示す。
【図１Ｂ】頂点１および１５を始点とする、またすべての頂点対の辺間隔度を示す図であり、重複するコミュニティの辺の太さは辺間隔度に比例し、重複する頂点の辺は、より高い隔度を持つように示す。
【図１Ｃ】頂点１および１５を始点とする、またすべての頂点対の辺間隔度を示す他の図である。
【図１Ｄ】頂点１および１５を始点とする、またすべての頂点対の辺間隔度を示すさらに他の図である。
【図１Ｅ】頂点１および１５からの浸透を示す図であり、ソース頂点コミュニティ内の頂点は、返答メッセージの割合が高いことを示す。
【図１Ｆ】頂点１および１５からの浸透を示す他の図である。
【図２Ａ】コミュニティ構造を識別したときに連結成分のサイズが比較的一定になることを示す図であり、様々な浸透確率において連結成分のサイズを測定したものであり、図２Ａでは、頂点１から浸透を始める。
【図２Ｂ】コミュニティ構造を識別するときに連結成分のサイズが比較的一定になることを示す他の図であり、図２Ｂでは、頂点１５から浸透を始める。
【図３】基本的なネットワークのモデルを示し、グラフＧがランダムＥＲグラフであり、任意の頂点対が確率ｐ０で連結する。サブグラフΓは、コミュニティ内の頂点で構成され、すなわちコミュニティ内の頂点は共通の関心や話題を共有し、そのため高い連結確率ｐΓを持つ。
【図４Ａ】コミュニティのネットワークモデルを示す図であり、グラフＧがランダムＥＲグラフであり、任意の頂点対が確率ｐ０で連結する。サブグラフΓ１とΓ２は、コミュニティ内の頂点で構成され、すなわちコミュニティ内の頂点は共通の関心や話題を共有し、そのため高い連結確率ｐΓ１およびｐΓ２をそれぞれ持つことを示す。
【図４Ｂ】コミュニティのネットワークモデルを示す他の図であり、コミュニティが重複部分を持つ。すなわちコミュニティが共通の頂点を持つことを示す。
【図５Ａ】ランダムに生成したグラフのモデルを示す図であり、本発明によるアルゴリズムおよびＧＮコミュニティ迅速発見アルゴリズム（参考文献９）を用いて適正に分類した頂点の割合を、コミュニティ間の辺の数に対して示す。
【図５Ｂ】ランダムに合成したグラフのモデルを示す他の図であり、本発明によるアルゴリズムおよびＧＮコミュニティ迅速発見アルゴリズム（参考文献９）により適正に分類した頂点の割合を、コミュニティ間の辺の数に対して示し、コミュニティ間の辺の数がコミュニティ内の辺の数に近づいたときにＧＮアルゴリズムがコミュニティの検出に失敗するとともに、本発明によるアルゴリズムによりコミュニティを検出することを示す。
【図６Ａ】図６Ａは、ランダムに生成した重複するコミュニティに対する、局所コミュニティ発見アルゴリズムの使用を示す図である。ＧＮアルゴリズムを含む従来の分割アルゴリズムが、重複の識別に失敗し、共通の頂点として１つのコミュニティに分割している。浸透型コミュニティ発見アルゴリズムでは、重複部分のコミュニティとノードの両方を識別している。図６Ａにおいては、ランダムに生成した元々のコミュニティを示し、１つのコミュニティにのみ属している頂点を青色と、明るい青色でそれぞれ示し、両方のコミュニティに属している頂点を黄色で、残りの頂点を灰色で示している。
【図６Ｂ】ランダムに生成した重複するコミュニティに対する、局所コミュニティ発見アルゴリズムの使用を示す他の図である。図６Ｂは、ＧＮアルゴリズムによるコミュニティの発見結果を示しており、重複するノードが１つのコミュニティに分割されており、分類の失敗した頂点を赤丸で囲んでいる。
【図６Ｃ】ランダムに生成した重複するコミュニティに対する、局所コミュニティ発見アルゴリズムの使用を示すさらに他の図である。図６Ｃは、浸透型コミュニティ発見アルゴリズムの結果を示しており、２つのコミュニティにおける重複部分のノードが両方のコミュニティに属している。頂点のサイズは、コミュニティ内での強度に比例する。構造的に、コミュニティは非常に均一である。分類の失敗した頂点を赤丸で囲んでいる。
【図７Ａ】アドミニストレータ１、インストラクタ３３および高次のノード３４に対する局所コミュニティ発見アルゴリズムの実行の様子を示す図である。検出したノードを青色で示し、ノードのサイズは、コミュニティ内での強度に比例する。ザチャリー（Zachary）の空手クラブのネットワークおいて、青色のノードが最終的にアドミニストレータのコミュニティに分けられ、黄色のノードがアドミニストレータに追従している。
【図７Ｂ】アドミニストレータ１、インストラクタ３３および高次のノード３４に対する局所コミュニティ発見アルゴリズムの実行の様子を示す他の図であり、ノード１に対するコミュニティの発見結果を示す。
【図７Ｃ】アドミニストレータ１、インストラクタ３３および高次のノード３４に対する局所コミュニティ発見アルゴリズムの実行の様子を示すさらに他の図であり、ノード３３に対するコミュニティの発見結果を示す。
【図７Ｄ】アドミニストレータ１、インストラクタ３３および高次のノード３４に対する局所コミュニティ発見アルゴリズムの実行の様子を示す別の図であり、ノード３４に対するコミュニティの発見結果を示す。
【図８】コミュニティ発見アルゴリズムにより、２つの主要なコミュニティと、他の５つの小さい重複するコミュニティを発見したことを示している。
【図９Ａ】本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示す図である。強度０．２０より強いノードを青色で示し、青色のノードのサイズは、コミュニティに属する強度に比例する。コミュニティは、本特許明細書で示すように複数の重複部分を持つ。図９Ａは、本発明によるアルゴリズムにより発見したインストラクタのコミュニティ１を示す。
【図９Ｂ】本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示す他の図であり、発見したアドミニストレータのコミュニティ４を示す。ノード３４を含むいくつかの重複したノードを組み込んでおり、これは、両方のコミュニティに結びつきがあることによる。また、ノード１２を除外しており、これはノード１２がノード１に対して単一の結びつきをし、コミュニティにあまり属していないからである。これは、ここでのコミュニティの定義とその他の定義との重要な違いである。
【図９Ｃ】本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示すさらに他の図であり、発見したコミュニティ２を示す。
【図９Ｄ】本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示すさらにまた他の図であり、発見したコミュニティ３を示す。
【図９Ｅ】図９Ｅは、本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示す別の図であり、発見したコミュニティ５を示す。
【図９Ｆ】図９Ｆは、本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示すさらに別の図であり、発見したコミュニティ６を示す。
【図９Ｇ】図９Ｇは、本発明によるアルゴリズムを用い発見した上位のコミュニティと５つの小さいコミュニティを示すさらにまた別の図であり、発見したコミュニティ７を示す。
【図１０Ａ】本発明による一般化したシステムの流れ図を示す。
【図１０Ｂ】本発明による一般化したシステムのアーキテクチャを示す。
【図１０Ｃ】本発明によるコアアーキテクチャモデルを示す。
【図１１Ａ】特許データベースに適用したシステムの流れ図であり、全体のシステムの流れ図を示す。
【図１１Ｂ】特許データベースに適用したシステムの他の流れ図であり、本発明によるアルゴリズムを適用する前のトランザクションの流れを示す。
【図１１Ｃ】特許データベースへの適用のためのシステムのさらに他の流れ図であり、本発明のアルゴリズムの適用におけるトランザクションの流れを示す。
【図１Ａ】
2008545178.tif 000007
【図１Ｂ】
2008545178.tif 000008
【図１Ｃ】
2008545178.tif 000009
【図１Ｄ】
2008545178.tif 000010
【図１Ｅ】
2008545178.tif 000011
【図１Ｆ】
2008545178.tif 000012
【図２Ａ】
2008545178.tif 000013
【図２Ｂ】
2008545178.tif 000014
【図３】
2008545178.tif 000015
【図４Ａ】
2008545178.tif 000016
【図４Ｂ】
2008545178.tif 000017
【図５Ａ】
2008545178.tif 000018
【図５Ｂ】
2008545178.tif 000019
【図６Ａ】
2008545178.tif 000020
【図６Ｂ】
2008545178.tif 000021
【図６Ｃ】
2008545178.tif 000022
【図７Ａ】
2008545178.tif 000023
【図７Ｂ】
2008545178.tif 000024
【図７Ｃ】
2008545178.tif 000025
【図７Ｄ】
2008545178.tif 000026
【図８】
2008545178.tif 000027
【図９Ａ】
2008545178.tif 000028
【図９Ｂ】
2008545178.tif 000029
【図９Ｃ】
2008545178.tif 000030
【図９Ｄ】
2008545178.tif 000031
【図９Ｅ】
2008545178.tif 000032
【図９Ｆ】
2008545178.tif 000033
【図９Ｇ】
2008545178.tif 000034
【図１０Ａ】
2008545178.tif 000035
【図１０Ｂ】
2008545178.tif 000036
【図１０Ｃ】
2008545178.tif 000037
【図１１Ａ】
2008545178.tif 000038
【図１１Ｂ】
2008545178.tif 000039
【図１１Ｃ】
2008545178.tif 000040
【国際調査報告】
2008545178.tif 000041