(57)【要約】【課題】集中的アルゴリズムを用いることなく、ネットワークの運用中に各ノードが分散的に処理を実行することによって、そのネットワークにおけるコミュニティ構造を検出することができる方法、ノード、管理装置及びプログラムを提供する。【解決手段】ノードは、接続されたリンク毎に、合計媒介値を記憶する。ルートノードが、要求メッセージを全てのリンクへ送信する。これに対し、エッジノードから順に応答メッセージが、ルートノードへ転送される。このとき、応答メッセージには、リンク数としての媒介値が含まれる。全てのノードが、ルートノードに順次割り当てられると共に、合計媒介値が加算されていく。最終的に、全てのリンクの中で、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティを構成する。【選択図】図１
2010141442.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出方法であって、
前記ノードは、接続されたリンク毎に、合計媒介値を記憶しており、
割り当てられたルートノードが、要求メッセージを全てのリンクへ送信するステップと、
前記要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するステップと、
要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、前記要求メッセージを全ての他リンクへ転送するステップと、
要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出し、当該リンクの前記合計媒介値に前記媒介値を加算するステップと、
前記エッジノードとして、算出された前記媒介値を含む応答メッセージを、前記要求受信リンクへ返信するステップと、
１つ以上の応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、前記自媒介値を［０］として前記媒介値を算出し、当該リンクの前記合計媒介値に前記媒介値を加算するステップと、
前記リレーノードとして、算出された前記媒介値を含む前記応答メッセージを、前記応答受信リンク以外の全ての他リンクへ送信するステップと、
前記ルートノードが、１つ以上の応答メッセージを受信するステップと
を有する第１のステップと、
全てのノードが、前記ルートノードに順次割り当てられると共に、第１のステップを繰り返す第２のステップと、
全てのリンクの中で、前記合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティを検出する第３のステップと
を有することを特徴とするコミュニティ構造検出方法。
【請求項２】
第３のステップについて、
いずれかのノードが、前記合計媒介値を含む通知メッセージを、全てのリンクへ送信するステップと、
前記通知メッセージを受信したノードは、自ノードの合計媒介値が、前記通知メッセージの合計媒介値よりも大きい場合、自ノードの合計媒介値を含む通知メッセージを更に全てのリンクへ送信するステップと
を有し、全てのノードが、最大合計媒介値及びそのノード情報を媒介中心として認識することを特徴とする請求項１に記載のコミュニティ構造検出方法。
【請求項３】
第３のステップについて、
前記最大合計媒介値のリンクを論理的に分断した２つのノードは、当該リンク以外に他の経路のリンクが存在するか否かを判定するステップと、
他の経路のリンクが存在しない場合、２つのコミュニティを検出するステップと、
他の経路のリンクが存在する場合、第１のステップ及び第２のステップを更に実行するステップと
を更に有することを特徴とする請求項２に記載のコミュニティ構造検出方法。
【請求項４】
リンクを介して相互に接続されたネットワークを構成するノードであって、
接続されたリンク毎に、合計媒介値を記憶する合計媒介値記憶手段と、
ルートノードに割り当てられた際に、要求メッセージを全てのリンクへ送信するルート要求送信手段と、
１つ以上の応答メッセージを受信するルート応答受信手段と、
前記要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するリンク数判定手段と、
前記リンク数判定手段によって、要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、前記要求メッセージを全ての他リンクへ転送するリレー要求転送手段と、
前記リンク数判定手段によって、要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出するエッジ媒介値算出手段と、
前記エッジ媒介値算出手段によって算出された媒介値を含む応答メッセージを、前記要求受信リンクへ返信するエッジ応答送信手段と
１つ以上の前記応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、前記自媒介値を［０］として前記媒介値を算出するリレー媒介値算出手段と、
前記リレー媒介値算出手段によって算出された前記媒介値を含む前記応答メッセージを、前記応答受信リンク以外の全ての他リンクへ送信するリレー応答転送手段と、
前記合計媒介値記憶手段における当該リンクの前記合計媒介値に、前記エッジ媒介値算出手段及び前記リレー媒介値算出手段によって算出された前記媒介値を加算する合計媒介値加算手段と
を有し、
全てのリンクの中で、前記合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識することを特徴とするノード。
【請求項５】
前記合計媒介値を含む通知メッセージを全てのリンクへ送信すると共に、該通知メッセージを受信した際に、自ノードの合計媒介値が、前記通知メッセージの前記合計媒介値よりも大きい場合、自ノードの合計媒介値を含む通知メッセージを更に全てのリンクへ送信する最大合計媒介値送信手段を更に有し、
全てのノードが、最大合計媒介値及びそのノード情報を媒介中心として認識することを特徴とする請求項４に記載のノード。
【請求項６】
請求項５に記載の複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出する管理装置であって、
ノード及びリンクから構成されるネットワーク構造情報を蓄積するトポロジデータベースと、
複数のノードの前記ルート要求送信手段を順次、ルートノードとして機能させるルート制御手段と、
前記最大合計媒介値及びそのノード情報を受信し、媒介中心として認識する合計媒介値取得手段と、
前記トポロジデータベースを用いて、前記合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識するコミュニティ構造検出手段と
を有することを特徴とする管理装置。
【請求項７】
前記トポロジデータベースを用いて、論理的に分断した２つのノードは、最大合計媒介値となる当該リンク以外に他の経路のリンクが存在するか否かを判定するために、前記ノードの前記最大合計媒介値送信手段を制御する他経路判定手段を更に有し、
他の経路のリンクが存在する場合、前記合計媒介値が最大となるリンクを論理的に分断した後、更に、コミュニティ構造を検出するべく前記ルート制御手段及び前記最大合計媒介値取得手段を機能させることを特徴とする請求項６に記載の管理装置。
【請求項８】
複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するために、ノードに搭載されたコンピュータを機能させるコミュニティ構造検出プログラムであって、
接続されたリンク毎に、合計媒介値を記憶する合計媒介値記憶手段と、
ルートノードに割り当てられた際に、要求メッセージを全てのリンクへ送信するルート要求送信手段と、
１つ以上の応答メッセージを受信するルート応答受信手段と、
前記要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するリンク数判定手段と、
前記リンク数判定手段によって、要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、前記要求メッセージを全ての他リンクへ転送するリレー要求転送手段と、
前記リンク数判定手段によって、要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出するエッジ媒介値算出手段と、
前記エッジ媒介値算出手段によって算出された媒介値を含む応答メッセージを、前記要求受信リンクへ返信するエッジ応答送信手段と
１つ以上の前記応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、前記自媒介値を［０］として前記媒介値を算出するリレー媒介値算出手段と、
前記リレー媒介値算出手段によって算出された前記媒介値を含む前記応答メッセージを、前記応答受信リンク以外の全ての他リンクへ送信するリレー応答転送手段と、
前記合計媒介値記憶手段における当該リンクの前記合計媒介値に、前記エッジ媒介値算出手段及び前記リレー媒介値算出手段によって算出された前記媒介値を加算する合計媒介値加算手段と
してコンピュータを機能させ、全てのリンクの中で、前記合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識することを特徴とするコミュニティ構造検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおけるコミュニティ構造検出方法、ノード、管理装置及びプログラムに関する。
【背景技術】
【０００２】
図１は、ノード及びリンクから構成されるネットワーク構成図である。
【０００３】
「ネットワーク」とは、複数のノード（頂点）と、ノード間を接続するリンク（辺）によって構成される抽象的構造をいう。この構造は、現実的なシステムに適用されている。インターネットに適用された場合、ノードを「ページ」とし、リンクを「ページ間の接続」と見なすことができる。例えばＳＮＳ(Social Networking System)によれば、ノードを「個人ページ」とし、リンクを「友人・知人関係」と見なすこともできる。また、通信事業者ネットワークに適用された場合、ノードを「通信設備装置」とし、リンクを「通信回線」と見なすことができる。
【０００４】
このようなネットワークの構造的特徴から、「コミュニティ」と称される集合が注目されている。「コミュニティ」とは、そのコミュニティ内のノードとは「密」に接続し合っているものの、コミュニティ外のノードとは「疎」に接続しているような集合をいう。このようなコミュニティ構造は、インターネットによればページの分類に適用され、通信事業者ネットワークによれば通信設備の増強箇所の特定に適用される。
【０００５】
特に、インターネットのＳＮＳによれば、個人における所属グループの特定に適用される。人間関係を表す社会ネットワークにおけるコミュニティを同定することによって、誰がどのコミュニティに属しているかを知ることができる。その個人が属するコミュニティに応じて、適切な情報やサービスを提供することもできる。また、複数のコミュニティに所属している関係を同定することによって、人間的勢力関係を理解し、又は、コミュニティの発生理由を解明することもできる。
【０００６】
コミュニティ構造を検出するための指標として、例えば「次数中心性」「近接中心性」「媒介通信性」がある。「次数中心性」とは、接続されたリンク数が最も多いノード、即ち、ネットワーク内でハブとなるノードを特定する。「近接中心性」とは、接続されたリンク数が少なくても、ネットワーク内の全てのノードまで短いホップ数で到達できるノードを特定する。「媒介中心性(Betweenness Centrality)」とは、リンク数やホップ数に関係なく、一方のコミュニティと他方のコミュニティとを結ぶ媒介となる唯一のノードを特定する。
【０００７】
ネットワーク内で媒介中心性を有するノードは、コミュニティ間の情報の流れを制御することができるという特性を有する。ランダムに接続されたネットワーク内で、「媒介中心性」を有するノードを特定することによって、コミュニティ構造を検出することができる。
【０００８】
近年、インターネットにおけるコミュニティ構造の検出は、セキュリティの観点からも重要視されている。具体的には、悪意のあるユーザが、複数の偽のユーザＩＤを使ってコミュニティを形成し、セキュリティ・アタック(例えばSybil attack)をする行為がある。このような悪意のあるコミュニティを、インターネットの中から同定することができれば、それらの行為を排除することができる。
【０００９】
【特許文献１】M. Newman and M. Girvan、「Finding andevaluating community structure in networks」、Physical Review E,69, 026113 (2004)、[online］、［平成２０年１１月２５日検出］、インターネット＜ＵＲＬ：http://arxiv.org/abs/cond-mat/0308217＞
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、コミュニティ構造を検出するための媒介中心性は、ノード毎に、他の全てのノードに対する最短経路から算出される。この計算は、ネットワーク全体の構造情報を全て蓄積したデータベースを用いて、集中的アルゴリズムによって実行される。そのために、大規模ネットワークへの適用が困難となるだけでなく、ノードの動的移動によっては計算できないという問題があった。また、最短経路が複数存在した場合、その計算量は更に複雑となっていた。
【００１１】
そこで、本発明は、集中的アルゴリズムを用いることなく、ネットワークの運用中に各ノードが分散的に処理を実行することによって、そのネットワークにおけるコミュニティ構造を検出することができる方法、ノード、管理装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明によれば、複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出方法であって、
ノードは、接続されたリンク毎に、合計媒介値を記憶しており、
割り当てられたルートノードが、要求メッセージを全てのリンクへ送信するステップと、
要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するステップと、
要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、要求メッセージを全ての他リンクへ転送するステップと、
要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出し、当該リンクの合計媒介値に媒介値を加算するステップと、
エッジノードとして、算出された媒介値を含む応答メッセージを、要求受信リンクへ返信するステップと、
１つ以上の応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、自媒介値を［０］として媒介値を算出し、当該リンクの合計媒介値に媒介値を加算するステップと、
リレーノードとして、算出された媒介値を含む応答メッセージを、応答受信リンク以外の全ての他リンクへ送信するステップと、
ルートノードが、１つ以上の応答メッセージを受信するステップと
を有する第１のステップと、
全てのノードが、ルートノードに順次割り当てられると共に、第１のステップを繰り返す第２のステップと、
全てのリンクの中で、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティを検出する第３のステップと
を有することを特徴とする。
【００１３】
本発明のコミュニティ構造検出方法における他の実施形態によれば、
第３のステップについて、
いずれかのノードが、合計媒介値を含む通知メッセージを、全てのリンクへ送信するステップと、
通知メッセージを受信したノードは、自ノードの合計媒介値が、通知メッセージの合計媒介値よりも大きい場合、自ノードの合計媒介値を含む通知メッセージを更に全てのリンクへ送信するステップと
を有し、全てのノードが、最大合計媒介値及びそのノード情報を媒介中心として認識することも好ましい。
【００１４】
本発明のコミュニティ構造検出方法における他の実施形態によれば、
第３のステップについて、
最大合計媒介値のリンクを論理的に分断した２つのノードは、当該リンク以外に他の経路のリンクが存在するか否かを判定するステップと、
他の経路のリンクが存在しない場合、２つのコミュニティを検出するステップと、
他の経路のリンクが存在する場合、第１のステップ及び第２のステップを更に実行するステップと
を更に有することも好ましい。
【００１５】
本発明によれば、リンクを介して相互に接続されたネットワークを構成するノードであって、
接続されたリンク毎に、合計媒介値を記憶する合計媒介値記憶手段と、
ルートノードに割り当てられた際に、要求メッセージを全てのリンクへ送信するルート要求送信手段と、
１つ以上の応答メッセージを受信するルート応答受信手段と、
要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するリンク数判定手段と、
リンク数判定手段によって、要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、要求メッセージを全ての他リンクへ転送するリレー要求転送手段と、
リンク数判定手段によって、要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出するエッジ媒介値算出手段と、
エッジ媒介値算出手段によって算出された媒介値を含む応答メッセージを、要求受信リンクへ返信するエッジ応答送信手段と
１つ以上の応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、自媒介値を［０］として媒介値を算出するリレー媒介値算出手段と、
リレー媒介値算出手段によって算出された媒介値を含む応答メッセージを、応答受信リンク以外の全ての他リンクへ送信するリレー応答転送手段と、
合計媒介値記憶手段における当該リンクの合計媒介値に、エッジ媒介値算出手段及びリレー媒介値算出手段によって算出された媒介値を加算する合計媒介値加算手段と
を有し、
全てのリンクの中で、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識することを特徴とする。
【００１６】
本発明のノードにおける他の実施形態によれば、合計媒介値を含む通知メッセージを全てのリンクへ送信すると共に、該通知メッセージを受信した際に、自ノードの合計媒介値が、通知メッセージの合計媒介値よりも大きい場合、自ノードの合計媒介値を含む通知メッセージを更に全てのリンクへ送信する最大合計媒介値送信手段を更に有し、
全てのノードが、最大合計媒介値及びそのノード情報を媒介中心として認識することも好ましい。
【００１７】
本発明によれば、前述の複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出する管理装置であって、
ノード及びリンクから構成されるネットワーク構造情報を蓄積するトポロジデータベースと、
複数のノードのルート要求送信手段を順次、ルートノードとして機能させるルート制御手段と、
最大合計媒介値及びそのノード情報を受信し、媒介中心として認識する合計媒介値取得手段と、
トポロジデータベースを用いて、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識するコミュニティ構造検出手段と
を有することを特徴とする。
【００１８】
本発明の管理装置における他の実施形態によれば、
トポロジデータベースを用いて、論理的に分断した２つのノードは、最大合計媒介値となる当該リンク以外に他の経路のリンクが存在するか否かを判定するために、ノードの最大合計媒介値送信手段を制御する他経路判定手段を更に有し、
他の経路のリンクが存在する場合、合計媒介値が最大となるリンクを論理的に分断した後、更に、コミュニティ構造を検出するべくルート制御手段及び最大合計媒介値取得手段を機能させることも好ましい。
【００１９】
本発明によれば、複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するために、ノードに搭載されたコンピュータを機能させるコミュニティ構造検出プログラムであって、
接続されたリンク毎に、合計媒介値を記憶する合計媒介値記憶手段と、
ルートノードに割り当てられた際に、要求メッセージを全てのリンクへ送信するルート要求送信手段と、
１つ以上の応答メッセージを受信するルート応答受信手段と、
要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定するリンク数判定手段と、
リンク数判定手段によって、要求受信リンク以外に１つ以上の他リンクが有ると判定された場合、要求メッセージを全ての他リンクへ転送するリレー要求転送手段と、
リンク数判定手段によって、要求受信リンク以外に他リンクが無いと判定された場合、エッジノードとして、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出するエッジ媒介値算出手段と、
エッジ媒介値算出手段によって算出された媒介値を含む応答メッセージを、要求受信リンクへ返信するエッジ応答送信手段と
１つ以上の応答メッセージを受信した際に、リレーノードとして、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、自媒介値を［０］として媒介値を算出するリレー媒介値算出手段と、
リレー媒介値算出手段によって算出された媒介値を含む応答メッセージを、応答受信リンク以外の全ての他リンクへ送信するリレー応答転送手段と、
合計媒介値記憶手段における当該リンクの合計媒介値に、エッジ媒介値算出手段及びリレー媒介値算出手段によって算出された媒介値を加算する合計媒介値加算手段と
してコンピュータを機能させ、全てのリンクの中で、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識することを特徴とする。
【発明の効果】
【００２０】
本発明のコミュニティ構造検出方法、ノード、管理装置及びプログラムによれば、集中的アルゴリズムを用いることなく、ネットワークの運用中に各ノードが分散的に処理を実行することによって、そのネットワークにおけるコミュニティ構造を検出することができる。
【発明を実施するための最良の形態】
【００２１】
以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。
【００２２】
図２は、本発明における第１のシーケンス図である。
【００２３】
（Ｓ２０１）最初に、ルートノードとして、ノードＡが選択されたとする。ルートノードＡは、要求メッセージを全てのリンク［Ａ⇔Ｂ］［Ａ⇔Ｃ］へ送信する。
【００２４】
（Ｓ２０２）ノードＢは、ノードＡから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ｂ⇔Ｄ］が有るので、リレーノードとして機能する。ノードＢは、その要求メッセージを他リンク［Ｂ⇔Ｄ］へ転送する。
【００２５】
（Ｓ２０３）ノードＣは、ノードＡから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ｃ⇔Ｄ］が有るので、リレーノードとして機能する。ノードＣは、その要求メッセージを他リンク［Ｃ⇔Ｄ］へ転送する。
【００２６】
（Ｓ２０４）ノードＤは、ノードＢ及びノードＣから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ｄ⇔Ｅ］が有るので、リレーノードとして機能する。ノードＤは、その要求メッセージを他リンク［Ｄ⇔Ｅ］へ転送する。
【００２７】
（Ｓ２０５）ノードＥは、ノードＤから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ｅ⇔Ｆ］［Ｅ⇔Ｇ］［Ｅ⇔Ｈ］が有るので、リレーノードとして機能する。ノードＥは、その要求メッセージを、全ての他リンク［Ｅ⇔Ｆ］［Ｅ⇔Ｇ］［Ｅ⇔Ｈ］へ転送する。
【００２８】
（Ｓ２０６）ノードＦ、Ｇ及びＨ各々は、ノードＥから要求メッセージを受信した際に、要求受信リンク以外の他リンクが無いので、エッジノードとして機能する。ノードＦ、Ｇ及びＨ各々は、以下の媒介値を算出する。
媒介値＝（自媒介値１）／（要求受信リンク数）
＝１／１
＝１
そして、ノードＦ、Ｇ及びＨ各々は、その媒介値［１］を含む応答メッセージを、要求受信リンク（ノードＥ）へ返信する。
【００２９】
（Ｓ２０７）ノードＥは、ノードＦ、Ｇ及びＨ各々から応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（１＋１＋１）＋１）｝／１
＝４
尚、ノードＥは、３つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は１となる。
【００３０】
ノードＥは、媒介値［４］を合計媒介値（初期値０）に加算して、リンク［Ｅ⇔Ｄ］の合計媒介値［４］とする。そして、ノードＥは、媒介値［４］を含む応答メッセージを、ノードＤへ転送する。
【００３１】
（Ｓ２０８）ノードＤは、ノードＥから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（４）＋１｝／２
＝５／２
尚、ノードＤは、１つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は２となる。
【００３２】
ノードＤは、リンク［Ｄ⇔Ｂ］について媒介値［５／２］を合計媒介値（初期値０）に加算して、リンク［Ｄ⇔Ｂ］の合計媒介値［５／２］とする。そして、ノードＤは、媒介値［５／２］を含む応答メッセージを、ノードＢへ転送する。また、ノードＤは、リンク［Ｄ⇔Ｃ］について媒介値［５／２］を合計媒介値（初期値０）に加算して、リンク［Ｄ⇔Ｃ］の合計媒介値［５／２］とする。そして、ノードＤは、媒介値［５／２］を含む応答メッセージを、ノードＣへ転送する。
【００３３】
（Ｓ２０９）ノードＢは、ノードＤから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（５／２）＋１）｝／１
＝５／２＋１
尚、リレーノードＢは、１つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は１となる。
【００３４】
ノードＢは、リンク［Ｂ⇔Ａ］について媒介値［５／２＋１］を合計媒介値（初期値０）に加算して、リンク［Ｂ⇔Ａ］の合計媒介値［５／２＋１］とする。そして、ノードＢは、媒介値［５／２＋１］を含む応答メッセージを、ノードＡへ転送する。
【００３５】
（Ｓ２１０）ノードＣは、ノードＤから応答メッセージを受信した際に、以下の式によって、媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（５／２）＋１）｝／１
＝５／２＋１
尚、リレーノードＣは、１つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は１となる。
【００３６】
ノードＣは、リンク［Ｃ⇔Ａ］について媒介値［５／２＋１］を合計媒介値（初期値０）に加算して、リンク［Ｃ⇔Ａ］の合計媒介値［５／２＋１］とする。そして、ノードＣは、媒介値［５／２＋１］を含む応答メッセージを、ノードＡへ転送する。
【００３７】
ルートノードＡは、ノードＢ及びＣから応答メッセージを受信する。そして、ルートノードＡは、リンク［Ａ⇔Ｂ］の合計媒介値［５／２＋１］を認識し、リンク［Ａ⇔Ｃ］の合計媒介値［５／２＋１］を認識する。
【００３８】
図３は、本発明における第２のシーケンス図である。
【００３９】
（Ｓ３０１）次に、ルートノードとして、ノードＢが選択されたとする。ルートノードＢは、全てのリンクへ要求メッセージを送信する。
【００４０】
（Ｓ３０２）ノードＡは、ノードＢから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ａ⇔Ｃ］が有るので、リレーノードとして機能する。ノードＡは、その要求メッセージを他リンク［Ａ⇔Ｃ］へ転送する。
【００４１】
（Ｓ３０３）ノードＤは、ノードＢから要求メッセージを受信した際に、要求受信リンク以外の他リンク［Ｄ⇔Ｅ］［Ｄ⇔Ｃ］が有るので、リレーノードとして機能する。ノードＤは、その要求メッセージを他リンク［Ｄ⇔Ｅ］［Ｄ⇔Ｃ］へ転送する。
【００４２】
（Ｓ３０４）ノードＣは、ノードＡ及びＤから要求メッセージを受信した際に、要求受信リンク以外の他リンクが無いので、エッジノードとして機能する。ノードＣは、以下の媒介値を算出する。
媒介値＝（自媒介値１）／（要求受信リンクの数）
＝（１）／２
＝１／２
そして、ノードＣは、その媒介値［１／２］を含む応答メッセージを、各要求受信リンク（ノードＡ、ノードＤ）へ返信する。
【００４３】
ノードＣについて、リンク［Ｃ⇔Ａ］の合計媒介値［５／２＋１］に、媒介値［１／２］を加算し、リンク［Ｃ⇔Ａ］の合計媒介値［５／２＋１＋１／２＝４］とする。そして、ノードＣは、媒介値［１／２］を含む応答メッセージを、ノードＡへ転送する。また、リンク［Ｃ⇔Ｄ］の合計媒介値［５／２＋１］に、媒介値［１／２］を加算し、リンク［Ｃ⇔Ｄ］の合計媒介値［５／２＋１＋１／２＝４］とする。そして、ノードＣは、媒介値［１／２］を含む応答メッセージを、ノードＤへ転送する。
【００４４】
（Ｓ３０５）図２のＳ２０５と同じ処理となる。
【００４５】
（Ｓ３０６）図２のＳ２０６と同じ処理となる。但し、リンク［Ｆ⇔Ｅ］［Ｇ⇔Ｅ］［Ｈ⇔Ｅ］について、記憶された合計媒介値［１］に媒介値［１］が加算され、合計媒介値［２］となる。
【００４６】
（Ｓ３０７）図２のＳ２０７と同じ処理となる。但し、リンク［Ｅ⇔Ｄ］について、記憶された合計媒介値［４］に媒介値［４］が加算され、合計媒介値［８］となる。
【００４７】
（Ｓ３０８）ノードＤは、ノードＥから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（１／２＋４）＋１）｝／１
＝５＋１／２
尚、ノードＤは、２つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は１となる。
【００４８】
ノードＤは、リンク（Ｄ⇔Ｂ）について、記憶された合計媒介値［５／２］に媒介値［５＋１／２］を加算して、合計媒介値［８］とする。そして、ノードＤは、媒介値［５＋１／２］を含む応答メッセージを、ノードＢへ転送する。
【００４９】
（Ｓ３０９）ノードＡは、ノードＣから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値０）｝
／（応答受信リンク以外の他リンクの数）
＝｛（１／２）＋０）｝／１
＝１／２
尚、ノードＡは、１つのリンクから応答メッセージを受信するために、応答受信リンク以外の他リンクの数は１となる。ここで、ノードＡは、既にルートノードとして動作したものであるので、自媒介値［０］として媒介値を算出する。
【００５０】
ノードＡは、リンク（Ａ⇔Ｂ）について、記憶された合計媒介値［７／２］に媒介値［１／２］を加算して、合計媒介値［８］とする。そして、ノードＡは、媒介値［１／２］を含む応答メッセージを、ノードＢへ転送する。
【００５１】
ルートノードＢは、ノードＡ及びＤから応答メッセージを受信する。そして、ルートノードＢは、リンク（Ｂ⇔Ａ）の合計媒介値［８］と記憶し、リンク（Ｂ⇔Ｄ）の合計媒介値［８］と記憶する。
【００５２】
図４は、本発明における第３のシーケンス図である。
【００５３】
次に、ルートノードとして、ノードＣが選択されたとする。ルートノードＣは、要求メッセージを全てのリンクへ送信する。ノードＢは、既にルートノードとして動作したために、媒介値［０］の応答メッセージをノードＡ及びノードＤへ返信する。ノードＡも、媒介値［０］の応答メッセージを、ノードＣへ返信する。ノードＦ、Ｇ及びＨは、エッジノードとして、媒介値［１］の応答メッセージを返信する。ノードＥは、リレーノードとして、３個の媒介値［１］の応答メッセージを受信するために、媒介値［４］の応答メッセージをノードＤへ返信する。ノードＤは、ノードＥから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
＝｛（４＋０）＋１｝／１
＝５
ノードＤは、媒介値［５］の応答ノードを、ルートノードＤへ返信する。
【００５４】
図５は、本発明における第４のシーケンス図である。
【００５５】
次に、ルートノードとして、ノードＤが選択されたとする。ルートノードＤは、要求メッセージを全てのリンクへ送信する。ノードＡは、既にルートノードとして動作したために、媒介値［０］の応答メッセージをノードＢ及びノードＣへ返信する。ノードＢ及びノードＣも、媒介値［０］の応答メッセージを、ノードＤへ返信する。ノードＦ、Ｇ及びＨは、エッジノードとして、媒介値［１］の応答メッセージを返信する。ノードＥは、リレーノードとして、３個の媒介値［１］の応答メッセージを受信するために、媒介値［４］の応答メッセージをノードＤへ返信する。
【００５６】
図６は、本発明における第５のシーケンス図である。
【００５７】
次に、ルートノードとして、ノードＥが選択されたとする。ルートノードＥは、要求メッセージを全てのリンクへ送信する。ノードＡ、Ｂ、Ｃ及びＤは、既にルートノードとして動作したために、媒介値［０］の応答メッセージをノードＥへ返信する。ノードＦ、Ｇ及びＨは、エッジノードとして、媒介値［１］の応答メッセージを返信する。
【００５８】
図７は、本発明における第６のシーケンス図である。
【００５９】
次に、ルートノードとして、ノードＦが選択されたとする。ルートノードＦは、要求メッセージを全てのリンクへ送信する。ノードＡ、Ｂ、Ｃ及びＤは、既にルートノードとして動作したために、媒介値［０］の応答メッセージをノードＥへ返信する。ノードＧ及びＨは、エッジノードとして、媒介値［１］の応答メッセージを返信する。ノードＥは、ノードＧ及びＨから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値０）｝
／（応答受信リンク以外の他リンクの数）
＝｛（２）＋０｝／１
＝２
ノードＥは、媒介値［２］の応答ノードを、ルートノードＦへ返信する。
【００６０】
図８は、本発明における第７のシーケンス図である。
【００６１】
次に、ルートノードとして、ノードＧが選択されたとする。ルートノードＧは、要求メッセージを全てのリンクへ送信する。ノードＡ、Ｂ、Ｃ、Ｄ及びＦは、既にルートノードとして動作したために、媒介値［０］の応答メッセージをノードＥへ返信する。ノードＨは、エッジノードとして、媒介値［１］の応答メッセージを返信する。ノードＥは、ノードＨから応答メッセージを受信した際に、以下の式によって媒介値を算出する。
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値０）｝
／（応答受信リンク以外の他リンクの数）
＝｛（１）＋０｝／１
＝１
ノードＥは、媒介値［１］の応答ノードを、ルートノードＧへ返信する。
【００６２】
図９は、本発明における合計媒介値を表すネットワーク構成図である。
【００６３】
図９によれば、最大合計媒介値は［１６］であって、ノードＤとノードＥが媒介中心として特定される。このとき、媒介中心となる２つのノードのリンクを論理的に分断し、２つのコミュニティと認識することができる。
【００６４】
図１０は、全てのノードに最大合計媒介値を認識させるシーケンス図である。
【００６５】
（Ｓ１００１）最初に、いずれかのノード（図１０によればノードＡ）が、自らの最大合計媒介値（及びそのリンクを介する２つのノードの情報）を含む通知メッセージを、全てのリンクへ送信する。ノードＡは、記憶している合計媒介値［４］の通知メッセージを、ノードＢ及びＣへ送信する。
【００６６】
（Ｓ１００２）また、ノードＢは、記憶している合計媒介値［８］が、通知メッセージの合計媒介値［４］よりも大きいので、自ノードの合計媒介値［８］（及びそのリンクを介する２つのノードの情報）を含む通知メッセージを更に全てのリンクへ送信する。このとき、ノードＣも、ノードＢと同様に動作する。
【００６７】
（Ｓ１００３）更に、ノードＤは、記憶している合計媒介値［１６］が、通知メッセージの合計媒介値［８］よりも大きいので、自ノードの合計媒介値［１６］（及びそのリンクを介する２つのノードの情報）を含む通知メッセージを更に全てのリンクへ送信する。この通知メッセージを受信したノードＡ〜Ｃ及びＥ〜Ｈは、記憶している合計媒介値が、通知メッセージの合計媒介値［１６］以下であるので、更なる通知メッセージを送信しない。
【００６８】
これによって、全てのノードが、最大合計媒介値［１６］と、そのリンクを介する２つのノードとを認識する。ここで、最大合計媒介値のリンクを論理的に分断する。
【００６９】
（Ｓ１００４）次に、最大合計媒介値のリンクを論理的に分断した２つのノードは、当該リンク以外に他の経路のリンクが存在するか否かを判定する。具体的には、一方のノードが、他方のノードを宛先とするパケットを送信するものであってもよい。
【００７０】
（Ｓ１００５）分断した２つのノードの間で、他の経路のリンクが存在しない場合、２つのコミュニティを構成していることを検出する。
【００７１】
尚、分断した２つのノードの間で、他の経路のリンクが存在する場合、論理的に分断した状態で、図２からの図９までのステップを更に実行する。これを繰り返すことによって、分断した２つのノードの間で、他の経路のリンクが存在しない場合、２つのコミュニティを構成していることを検出する。
【００７２】
図１１は、本発明におけるノードの機能構成図である。
【００７３】
図１１よれば、ノード１は、合計媒介値記憶部１００と、ルートノード制御部１１１と、ルート要求送信部１１２と、ルート応答受信部１１３と、要求受信部１２１と、リンク数判定部１２２と、リレー要求転送部１２３と、エッジ応答送信部１２４と、応答受信部１３１と、リレー応答転送部１３２と、エッジ媒介値算出部１４１と、リレー媒介値算出部１４２と、合計媒介値加算部１４３と、最大合計媒介値送信部１５１とを有する。これら機能構成部は、ノードに搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００７４】
合計媒介値記憶部１００は、接続されたリンク毎に、合計媒介値を記憶する。
【００７５】
ルートノード制御部１１１は、自ノードが、ルートノードに割り当てられた際に、ルート要求送信部１０２を機能させる。自ノードがルートノードであるか否かは、管理装置２からの制御に基づくものであってもよいし、ノード同士で分散的に決定されるものであってもよい。
【００７６】
ルート要求送信部１１２は、ルートノード制御部１１１によってルートノードに割り当てられた際に、要求メッセージを全てのリンクへ送信する。
【００７７】
ルート応答受信部１１３は、１つ以上の応答メッセージを受信する。このとき、ルート応答受信部１１３は、ルートノードとしての機能を終了するべく、ルートノード制御部１１１へ通知する。
【００７８】
要求受信部１２１は、他のノードから要求メッセージを受信する。受信された要求メッセージは、リンク数判定部１２１へ出力される。
【００７９】
リンク数判定部１２２は、要求メッセージを受信した際に、要求受信リンク以外に１つ以上の他リンクが有るか否かを判定する。要求受信リンク以外に１つ以上の他リンクが有る場合、リレー要求転送部１２３へ指示し、又は、要求受信リンク以外に他リンクが無い場合、エッジ媒介値算出部１４１へ指示する。
【００８０】
リレー要求転送部１２３は、要求受信リンク以外に１つ以上の他リンクが有る場合、要求メッセージを全ての他リンクへ転送する。
【００８１】
エッジ媒介値算出部１４１は、要求受信リンク以外に他リンクが無い場合、
媒介値＝（自媒介値１）／（要求受信リンク数）
によって媒介値を算出する。算出された媒介値は、エッジ応答送信部１２４及び合計媒介値加算部１４３へ出力される。
【００８２】
エッジ応答送信部１２４は、エッジ媒介値算出部１４１によって算出された媒介値を含む応答メッセージを、要求受信リンクへ返信する。
【００８３】
応答受信部１３１は、他のノードから応答メッセージを受信する。受信された応答メッセージは、リレー媒介値算出部１４２へ出力される。
【００８４】
リレー媒介値算出部１４２は、１つ以上の応答メッセージを受信した際に、
媒介値＝｛（全ての応答メッセージの媒介値の合計値）＋（自媒介値１）｝
／（応答受信リンク以外の他リンクの数）
によって媒介値を算出すると共に、自ノードが既にルートノードとして動作した場合、自媒介値を［０］として媒介値を算出する。算出された媒介値は、リレー応答転送部１３２及び合計媒介値加算部１４３へ出力される。
【００８５】
リレー応答転送部１３２は、リレー媒介値算出部１４２によって算出された媒介値を含む応答メッセージを、応答受信リンク以外の全ての他リンクへ送信する。
【００８６】
合計媒介値加算部１４３は、合計媒介値記憶部１００における当該リンクの合計媒介値に、エッジ媒介値算出部１４１及びリレー媒介値算出部１４２によって算出された媒介値を加算する。
【００８７】
最大合計媒介値送信部１５１は、合計媒介値を含む通知メッセージを全てのリンクへ送信すると共に、該通知メッセージを受信した際に、自ノードの合計媒介値が、通知メッセージの合計媒介値よりも大きい場合、自ノードの合計媒介値を含む通知メッセージを更に全てのリンクへ送信する。
【００８８】
最終的に、最大合計媒介値送信部１５１によって、全てのリンクの中で、合計媒介値が最大となる媒介中心としての２つのノードが検出される。そのノード間のリンクを論理的に分断し、２つのコミュニティと認識することができる。
【００８９】
図１２は、本発明におけるネットワークのシステム構成図である。
【００９０】
図１２によれば、ネットワークに、管理装置２が接続されている。管理装置２は、複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出する。管理装置２は、トポロジデータベース２００と、ルート制御部２０１と、合計媒介値取得部２０２と、他経路判定部２０３と、コミュニティ構造検出部２０４とを有する。これら機能構成部は、管理装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００９１】
トポロジデータベース２００は、ノード及びリンクから構成されるネットワーク構造情報を蓄積する。
【００９２】
ルート制御部２０１は、複数のノードにおけるルートノード制御部１１１を制御する。
【００９３】
合計媒介値取得部２０２は、最大合計媒介値及びそのノード情報を受信し、トポロジデータベース２００によって媒介中心を特定する。
【００９４】
コミュニティ構造検出部２０３は、トポロジデータベースを用いて、合計媒介値が最大となるリンクを論理的に分断し、２つのコミュニティと認識する。
【００９５】
他経路判定部２０４は、トポロジデータベース２００を用いて、論理的に分断した２つのノードは、最大合計媒介値となる当該リンク以外に他の経路のリンクが存在するか否かを判定する。他の経路のリンクが存在する場合、合計媒介値が最大となるリンクを論理的に分断した後、ルート制御部１１１から、最初のノードから順に、ルートノードを指定する。
【００９６】
以上、詳細に説明したように、本発明のコミュニティ構造検出方法、ノード、管理装置及びプログラムによれば、集中的アルゴリズムを用いることなく、ネットワークの運用中に各ノードが分散的に処理を実行することによって、そのネットワークにおけるコミュニティ構造を検出することができる。
【００９７】
本発明が通信事業者ネットワークに適用された場合、媒介中心を特定することにより、運用者が、重要な通信回線を知ることができる。ネットワークの障害（リンク不通や切断）発生時に、媒介値の高い通信回線から復旧することで、ネットワーク全体の障害の影響を小さくすることができる。また、通信ネットワークの設計・構築の段階であっても、媒介中心を有するノードをどの箇所に配置されているかを判断することができる。これにより、例えば、媒介中心性が均一なネットワークを構築し、又は、特定のリンク（回線速度が大きいリンク）の媒介中心性を増強することもできる。
【００９８】
また、本発明がインターネットに適用された場合、媒介中心を特定することにより、そのノードにコンテンツレプリカサーバを配置することもできる。媒介中心となる２つのノードは、コミュニティ間の共通の通信リンクとなるからである。これにより、媒介中心となる通信リンクにコンテンツの伝送が集中することを避けることができる。
【００９９】
また、本発明がＳＮＳに適用された場合、媒介中心性が大きいリンクを有するユーザ（ノード）を検出することができ、その社会ネットワークにおける重要人物を特定することができる。また、コミュニティを検出し、そのコミュニティの規模（例えばゴルフに興味があるユーザが集まったコミュニティのユーザ数）の変化を観察することによって、流行の変化を知ることもできる。
【０１００】
更に、インターネットにおけるコミュニティ構造を検出することによって、悪意のあるユーザが、複数の偽のユーザＩＤを使って形成したコミュニティを同定することもできる。これによって、そのような悪意のコミュニティを、そのネットワークから論理的に分断することもできる。
【０１０１】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【０１０２】
【図１】ノード及びリンクから構成されるネットワーク構成図である。
【図２】本発明における第１のシーケンス図である。
【図３】本発明における第２のシーケンス図である。
【図４】本発明における第３のシーケンス図である。
【図５】本発明における第４のシーケンス図である。
【図６】本発明における第５のシーケンス図である。
【図７】本発明における第６のシーケンス図である。
【図８】本発明における第７のシーケンス図である。
【図９】本発明における合計媒介値を表すネットワーク構成図である。
【図１０】全てのノードに最大合計媒介値を認識させるシーケンス図である。
【図１１】本発明におけるノードの機能構成図である。
【図１２】本発明におけるネットワークのシステム構成図である。
【符号の説明】
【０１０３】
１  ノード
１００  合計媒介値記憶部
１１１  ルートノード制御部
１１２  ルート要求送信部
１１３  ルート応答受信部
１２１  要求受信部
１２２  リンク数判定部
１２３  リレー要求転送部
１２４  エッジ応答送信部
１３１  応答受信部
１３２  リレー応答転送部
１４１  エッジ媒介値算出部
１４２  リレー媒介値算出部
１４３  合計媒介値加算部
１５１  最大合計媒介値送信部
２  管理装置
２００  トポロジデータベース２００
２０１  ルート制御部
２０２  合計媒介値取得部
２０３  他経路判定部
２０４  コミュニティ構造検出部
【図１】
2010141442.tif 000003
【図２】
2010141442.tif 000004
【図３】
2010141442.tif 000005
【図４】
2010141442.tif 000006
【図５】
2010141442.tif 000007
【図６】
2010141442.tif 000008
【図７】
2010141442.tif 000009
【図８】
2010141442.tif 000010
【図９】
2010141442.tif 000011
【図１０】
2010141442.tif 000012
【図１１】
2010141442.tif 000013
【図１２】
2010141442.tif 000014