JP2008107867A

JP2008107867A - コミュニティ抽出方法、コミュニティ抽出処理装置

Info

Publication number: JP2008107867A
Application number: JP2006287116A
Authority: JP
Inventors: Yaemi Teramoto; やえみ寺本; Yasutsugu Morimoto; 康嗣森本; Tatsuhiko Miyata; 辰彦宮田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2006-10-23
Filing date: 2006-10-23
Publication date: 2008-05-08
Also published as: US20080097994A1

Abstract

【課題】人物間の関係とその内容を表すデータの集合から、共通の話題や関心に基づいた関係を高密度に持った人物の集合であるコミュニティを抽出すること。
【解決手段】関係内容データをクラスタリングするステップと、関係ネットワークのコア部を抽出するステップと、コア部を関係内容データのデンドログラムにマッピングするステップと、デンドログラムを用いて、関係の内容の類似度に基づいたクラスタを拡大しながらコミュニティを形成するステップと、コミュニティを集約するステップとの各処理を実行することにより、コミュニティを抽出する。
【選択図】図１

Description

本発明は、電子計算機などの情報処理装置を用い、人物間の関係とその内容を表すデータの集合から、共通の話題や関心に基づいた関係を高密度に持った人物の集合であるコミュニティを抽出する技術に関する。

近年、メール・ブログ・掲示板・チャット・ソーシャルネットワークサービス（ＳＮＳ）といったコミュニケーションツールや、Webにおけるリンクや閲覧履歴などの情報から、人と人との関係を電子データとして蓄積することが可能となっている。こういった状況において、電子データから抽出した人物間の関係を社会ネットワークとして分析することにより、ネットワークの特徴に基づいた新たな価値提供を目指す技術が着目されている。そのひとつとして、人物の集合であるコミュニティを見つけ出し、ある人物に合うコミュニティを選択したり、コミュニティにその特徴に合った情報を提供したりする技術が開発されている。

特開２００４−１２７１９６号公報（特許文献１）に記載された発明においては、端末が送受信した情報を元に各端末の特徴単語リストをつくり、単語リスト間の類似度によって端末をグルーピングしている。ただし、端末間の関係は考慮していない。

特開２００５−２４４６４７号公報（特許文献２）に記載された発明においては、電子メールにおけるメール転送が高い頻度で行われているユーザ同士を結んだネットワークを求め、そのネットワークを潜在的なコミュニティとして出力している。ただし、メールの記述内容は考慮していない。

非特許文献１に記載されたコア部抽出法においては、Ｗｅｂの人名共起を用いて形成した人間関係のネットワークから、リンクの密集する部分をコア部として抽出している。ただし、人間関係の内容や特徴は考慮していない。

特開２００４−１２７１９６号公報特開２００５−２４４６４７号公報斉藤和己他, ＳＲ：ネットワークの密結合するコア部抽出法, WEIN2005 John Scott, Social Network Analysis A Handbook Second Edition, Chapter 6&7, pp. 100-145, SAGE Publications Ltd, 2000 Buckley, et al, New retrieval approaches using SMART: TREC4, pp. 25-48, 1996 Richard O. Duda et al, Pattern Classification Second Edition, Chapter 10, pp.550-557, A Wiley-Interscience Publication, 2001 馬場肇, 改訂 Namazuシステムの構築と活用, ソフトバンククリエイティブ, 2003年7月1日出版金光淳, 社会ネットワーク分析の基礎（第６章中心性）, 勁草書房, 2003年12月20日出版 Dieter Jungnickel, Graphs, Networks And Algorithms（3. Shortest Paths）, Springer, ２００４年１０月３１日出版

従来のコミュニティ抽出方法には、人物間の関係の密度に着目した手法と、プロファイルの似た人物をまとまりにする手法がある。しかし、現実の人間社会では、人は複数の役割を持ち、役割ごとに複数のコミュニティに参加している。また、同じ２者間の関係にも、役割によって複数の種類があると考えられる。従来方法では、こういった現実社会の人間関係のあり方の特徴を表現することが困難である。

本発明の目的は、人物間の関係とその内容を表すデータの集合から、共通の話題や関心に基づいた関係を高密度に持った人物の集合であるコミュニティを抽出する技術によって、現実の人間社会に即したコミュニティ抽出手段を提供することである。

本発明の他の目的は、上記コミュニティ抽出を利用した応用機能から得られた情報を人物間の関係に自動的に反映させるコミュニケーション履歴のフィードバック手段を提供することである。

上記目的を達成するために、本発明のコミュニティ抽出方法では、関係の内容に基づいたクラスタリングと、人物間の関係の密度の高いコア部の抽出とを相互作用させてコミュニティを抽出する。具体的には、コア部をデンドログラム（樹状図）の部分木にマッピングしてそこからスタートし、デンドログラムを用いて、関係の内容の類似度に基づいたクラスタを拡大しながらコミュニティを形成する。コミュニティの密度や処理クラスタの大きさや処理繰り返し回数を閾値としてコミュニティの形成処理を終了し、コミュニティを出力する。

本発明を適用した典型的なシステムは、データを保持するデータ保持手段、保持されたデータを処理するデータ処理手段を少なくとも備えた情報処理装置によって構成される。ネットワークに適用した場合には、ネットワークにより接続された複数の情報端末、これら情報端末相互の通信を制御するコミュニケーションシステム、当該通信により情報端末間で送受信される情報を処理する検索システムを備え、情報端末をアクセスするユーザは例えばＩＤで識別されるものとする。

また、本発明の範囲は新規なコミュニティ抽出処理を行う検索システムであり、具体例ではネットワークに接続されるサーバおよびサーバ上で動作するプログラムで構成される。この検索システムではネットワーク上を流れるデータを監視または収集し、当該データを類似度に基づいてクラスタリングし、デンドログラムを作成する（後に図６で詳述する）。別の態様では、あらかじめ蓄積したデータをもとにして、データ処理を行いコミュニティを抽出する。この場合には、システムはスタンドアロンでよい。また、特定のデータに関与した複数ユーザの関連付けを行い、人間関係データを構築する。関与とは、例えば、送受信、作成、参照、修正などをいう（後に図８、図２４等で説明する）。

本発明ではデータの関連（類似性など）を示すデンドログラムと人間関係ネットワークを相互参照することにより、特定のテーマに関連するコミュニティを抽出することができる。処理動作は後に実施例で詳述するが、以下に、本発明の検索システムの基本的な動作例を説明する。

本発明ではユーザ相互の関連性を示す人間関係ネットワークを生成し、データとして保持する。後に詳述するが、人間関係ネットワークは例えば図7の72のようなものであり、ユーザＡ，Ｂ，Ｃなどの相互の関連を示す。関連とは一例として、同じデータへの関与の度合い、頻度や、メール等連絡の頻度、回数などで表すことができる。

また、ユーザが関与する関係内容データの類似度に基づいてクラスタリングしたデンドログラムを作成し、データとして保持する。後に詳述するが、デンドログラムは例えば図7の71のようなものである。この例では、データ１，２，３等は類似度によりツリー状にマッピングされ、さらにデータに関与するユーザＡ，Ｂ，Ｃもデータに関連付けて示されうる。

次に人間関係ネットワークから複数のユーザを構成メンバとして包含する１または複数のコア部を抽出する。例えば人間関係ネットワーク72からユーザＡ，Ｂ，Ｃを関連性の強いコアとして抽出する。抽出の手法は公知の手法を用いることができる。例えばグラフ理論に基づき高密度部分を抽出することが可能である。

次に、このコア部をデンドログラムにマッピングして、少なくともコア部の構成メンバを含むコミュニティを形成する。マッピングは、コア部の構成メンバとデンドログラムの部分木の構成メンバとの重複度を用いることができる。具体例としては、デンドログラムのクラスタリングされた部分木に着目し、コア部の構成メンバの少なくとも一部をデータに関与するユーザとして含む部分木を抽出する。

例えば、デンドログラムの末端部（図において下方）から部分木を順次検索していき、構成メンバを含む部分木をコミュニティとして抽出する。図7の例では、Ｔ０の部分木が構成メンバであるユーザＡ，Ｂ，Ｃを含むコミュニティとして抽出できる。注意すべきは、データ２を介してコア部の構成メンバＣと関係を持つユーザＤもコミュニティに含まれることである。

以上のようにして、人間関係および類似データへの関与の度合い（あるいは有無）の両方の情報を用いて、コミュニティ抽出を行うことができる。

さらに、本発明の好ましい態様では、データの関連を示すデンドログラムと人間関係ネットワークを相互参照して、コミュニティを拡張していくことができる。

再度図7を参照して具体例を示す。デンドログラムの部分木Ｔ０は人間関係ネットワークのコア部の構成メンバであるユーザＡ、Ｂ，Ｃを全て含むので最も類似度が高い部分木と解釈されるため、これを基本コミュニティとする。次に類似度が高い部分木はメンバＡとＣを含むＴ２１である。ここで、部分木Ｔ２１において、これに属する関係内容データ4，5，6をやり取りした（またはこれにアクセスした）ユーザＡ，Ｃ，Ｅ，Ｆを基本コミュニティへの追加候補とし、追加候補のユーザと基本コミュニティの何れかのメンバとの間に人間関係（例えば同じデータへのアクセス、通信）が有る場合に追加候補のユーザを基本コミュニティのメンバとして追加する。図7の例では、人間関係ネットワーク７２を参照することで、基本コミュニティのメンバＡと候補Ｆには人間関係があることが分かるので、Ｆはコミュニティに追加される。

同様の処理を順次繰り返すことにより、コミュニティを拡張することができる。拡張の手順としては、例えばデンドログラムを集約方向（ルート方向、図では上方向）へ辿り、次に類似性が高いデンドログラムの部分木を探索して同様の処理を繰り返せばよい。
なお、、処理を繰り返すとコミュニティは拡大するが、無限に繰り返すのはデータの量が大きい場合は現実的でないので、繰り返し回数に閾値を設けるのが実用的である。

例えば、以下の例がある
（１）コミュニティ内の関係密度を閾値とし、一定以上希薄になったとき処理を終了する手法
（２）次にコミュニティへの追加の対象となるデンドログラムの部分木の大きさを閾値とし、一定上大きくなったときて処理を終了する手法
（３）デンドログラムを集約方向へ辿りコミュニティにメンバを追加する処理の繰り返し回数を閾値として処理を終了する手法
また、これらを組み合わせて判断することもできる。

本発明によれば、所定のテーマに関連するユーザを効果的にコミュニティとして抽出が可能となる。

本発明のコミュニティ抽出方法の効果的な用途の一つにKnow-Who検索システムがある。以下、Know-Who検索システムに適用された場合のコミュニティ抽出方法について説明する。

図９に、実施例のネットワーク概要図を示す。情報端末905,906,907,908が、IPネットワーク904を介して、SIP(Session Initiation Protocol)サーバ901、プレゼンスサーバ902、KnowWho検索サーバ903と接続されている。SIPは文字、音声、映像等のあらゆるユーザ間コミュニケーションについて，相手ユーザの呼び出しから相手ユーザとのコミュニケーション終了までの状態を制御するプロトコルであり、IETF(Internet Engineering Task Force)で標準化されたプロトコルである。但し、本例では制御をSIPで行っているが、制御プロトコルはSIP以外でも特に構わない。ユーザＡ914が、情報端末905の備えるKnowWho検索用アプリケーション909を用いて、欲する情報に関する有識者を探すKnowWho検索の要求を送信すると、IPネットワークを介してKnowWho検索サーバ903がその要求を受け、検索を実行し、検索結果を送信し、その検索結果を情報端末905が受信して表示する。ユーザＡは検索結果からコミュニケーション相手（ここではユーザＢ、ユーザＣ、ユーザＤのいずれかとする）を選択し、情報端末905,906,907,908の備えるコミュニケーション用アプリケーション910,911,912,913を用い、IPネットワーク904とSIPサーバ901、プレゼンスサーバ902を介して、選択したユーザと端末間通信を行う。

図１１、図１２、図１３、図１４はそれぞれ本実施例の図９に示す情報端末905、KnowWho検索サーバ903，プレゼンスサーバ902，SIPサーバ901の機能ブロック図である。図１１、図１２、図１３、図１４の機能ブロック図は、ソフトウェア上実現される論理的な機能構成を示した図であるが、各機能ブロックをハードウェアで構成しても構わない。

図１０には図１１、図１２、図１３、図１４で示した機能ブロックが、ハードウェア上、どのように実現されているかを示した。図１０は例えばＩＰネットワーク904に接続されるサーバないしコンピュータの構成を示すものである。これは、本体1001と入出力装置1011,1012を備える。ＣＰＵ1003を動作させるプログラムに応じて、図９に示す情報端末905、KnowWho検索サーバ903，プレゼンスサーバ902，SIPサーバ901のいずれかまたは複数の役割を分担させることができる。すなわち、図１１、図１２、図１３、図１４に示した種々の機能ブロックの動作は、図１０に示すメモリ1002の処理モジュール群1005に収納されており、動作時にはＣＰＵ1003がその動作手順を読み出して実行する。個々の処理モジュールが動作する際に必要な情報は、ハードディスク等のディスクストレージ上に保存された恒久的な情報管理テーブル1006、及びメモリ1002上の一時的な情報管理テーブル1004に格納されており必要に応じて読み出し，書き込みが行われる。また，905〜908に示す情報端末が実際に文字通信を行う際には1011に示すキーボード・マウスをマウス・キーボード入力インターフェース1009に接続して利用し，音声，映像通信を行う際には1012に示すスピーカ，マイク，PCカメラなどのデバイスを音声・映像入出力インターフェース1010に接続して利用する。実際のデータはデータバス1007を経由してCPU1003に転送され処理が行われる。また，IPネットワーク904にはネットワークインターフェース1008を経由して接続する。

これより、図１１、図１２、図１３、図１４の各機能ブロック図の説明をするが、まずは最も重要な、図１２のKnow-Who検索サーバ903の機能について説明する。

図１２のKnow-Who検索サーバ903は主に２つの役割を持つ。１つ目の役割は、人間関係データの構築である。人間関係情報送受信部1208より人間関係情報を受信し、人間関係構築部1201にて人間関係データを構築・更新する。受信する人間関係情報は、メールなどのコミュニケーションに用いられたデータ、複数の人物が共同で作成した文書データ、人物間で送受信された画像データなど様々な形態が考えられるが、複数の人物が関与するデータと定義する。人間関係構築部では、まず、受信した人間関係情報を関係データテーブルの形式にする。関係データテーブルの例を図２４に示す。2401はデータID、2402はデータ内容、2403は各データによって関係を持っている関係保持者を表す。データ内容は、前述したように、テキスト、音声、画像など様々な形式が可能であり、図２４の例ではデータ内容は特定しない。次に、関係データテーブルから、人物をノード、関係をエッジとした関係ネットワークを、人物間の関係データ数を要素値とした行列として作成する。関係ネットワークの例を図２２に示す。なお、人間関係情報送受信部が受信する情報を用いて、関係ネットワークの要素値を直接書き換えることも考えられる。これに関しては、実施例２において述べる。２つ目の役割はKnow-Who検索の実行である。情報送受信部1207のKnow-Who検索関連情報送受信部1209にて検索クエリと検索要求を受信し、Know-Who検索部1206にて、人間関係解析部1202の各モジュール1203,1204,1205を用いて検索を実行し、Know-Who検索関連情報送受信部1209より検索結果を送信する。Know-Who検索部1206にて実行される検索には、コミュニティ検索部1210にて実行されるコミュニティ検索と、仲介経路検索部1211にて実行される仲介経路検索の２つがある。これらの処理の詳細を以下に述べる。

図１、図２、図３、図４、図２５のフローチャートを用いて、Know-Who検索部1206の処理を説明する。

図２５は、コミュニティ検索部1210の処理の全体の流れのフローチャートである。Know-Who検索部では、受信した検索要求が特定の知識分野に関する有識者を検索するコミュニティ検索であった場合に、コミュニティ検索部による処理を実行する。検索クエリとなる特定の知識分野は、キーワードなどによって与えられる。

コミュニティ抽出ステップS2501では、関係データテーブル（図24）と関係ネットワーク行列（図22）を入力とし、コミュニティテーブルを出力する。コミュニティテーブルの例を、図２１に示す。2101はコミュニティIDを表す。2102は、コミュニティに属するメンバを表す。2103は、コミュニティ内の関係データを表す。S2105は、S2502にて付与されるコミュニティのスコアを表す。S2501の処理はコミュニティ抽出部1203によって実行される。処理の詳細は後述する。

コミュニティ検索スコア算出ステップS2502では、S2501によって出力されたコミュニティを入力とし、受信した検索クエリに対する適合度スコアを算出する。関係内容データがテキストデータであった場合の適合度スコア算出方法の例としては、コミュニティデータ（コミュニティ内の人間関係内容を表すデータ。詳細は後述。）をマージしたテキストデータを各コミュニティに対して作成し、全文検索エンジン（非特許文献５）などを用いて検索クエリに対する作成したテキストデータのスコア付けを行い、これをコミュニティの検索クエリに対する適合度スコアとする方法などがある。コミュニティ検索スコアの算出により、コミュニティを検索クエリに適合した順番に並び替えて表示することが可能となる。

中心性算出ステップS2503では、S2501によって出力されたコミュニティを入力とし、各コミュニティに対し、コミュニティメンバの中心性を算出する。S2503の処理は、中心性算出部1204にて実行される。中心性は、ネットワークにおいて各ノードが中心的である度合いを表す指標である（非特許文献６）。中心性の算出により、コミュニティメンバを中心的である度合いの高い順番に並び替えて表示することが可能となる。

コミュニティ出力ステップS2504では、S2501にて抽出したコミュニティの集合と、S2502,S2503にて算出したスコアと中心性の値を出力する。コミュニティ検索クエリを送信したユーザは、出力されたコミュニティとコミュニティメンバの情報を用いて、特定の知識分野の有識者を効率的に選択することができる。

図１、図２、図３、図４は、コミュニティ抽出部1203の処理のフローチャートである。これより、図２１、図２４のデータ例を入力として、コミュニティ抽出処理の動作を説明する。例では、データ１からデータ６の６つのデータによって、Ａ,B,C,D,E,Fの６名が関係を持っている。

図１は、コミュニティ抽出処理の全体の流れを表すフローチャートである。
関係内容データクラスタリングステップS11では、関係の内容を表すテキスト・画像・音声などのデータ集合を入力とし、データを近いもの（類似度の高いもの）から纏め上げたデンドログラムを出力する。このデンドログラムを、関係内容データのクラスタリングデンドログラムと呼ぶ。クラスタリングデンドログラムを用いると、内容の類似に基づいた関係内容データの集合であるクラスタを様々な大きさで作ることができる。関係内容データのクラスタは、関係内容データクラスタリングデンドログラムの任意の部分木とする。関係と関係内容データの例を以下に挙げる。メールによるコミュニケーションでは、メールの送信者と受信者という関係に対しメール題目・本文のテキストや画像などの添付ファイルが関係内容データとなる。Webページの閲覧では、Webページの作成者と参照者という関係に対しWebページの記載内容が関係内容データとなる。論文の共著では、主著者と共著者または共著者と共著者という関係に対し論文記述内容が関係内容データとなる。処理の詳細は図２のフローチャートを用いて後述する。

関係ネットワークからコア部を抽出するステップS12では、関係ネットワークを入力とし、前記関係ネットワークから関係の密度の高いコア部を抽出して出力する。コア部抽出手法には、グラフ理論におけるN-Clique、K-Plex（非特許文献２）、SR法（非特許文献１）などを適用できる。このコア部の集合は、コミュニティ形成の種として用いられる。例では、図２２の関係ネットワークを入力とし、全てのノード間にエッジの存在するサブグラフである1-Cliqueをコア部として抽出すると、(A,B,C)の３名からなるコア部が抽出される。コア部は、図２３のコア部テーブルによって管理される。2301はコア部ID、2302はコア部を形成するメンバを表す。

コア部を関係内容データのデンドログラムにマッピングするステップS13では、S11で出力したデンドログラムとS12で出力したコア部を入力とし、コア部とデンドログラム部分木のペアを出力する。このコア部と部分木のペアは、コミュニティ形成の開始点となる。処理の詳細は図３のフローチャートを用いて後述する。

コミュニティ形成ステップS14では、S13で出力したコア部とデンドログラム部分木のペアを入力とし、各々のペアを開始点に、デンドログラムを用いて関係内容データのクラスタを拡大して形成したコミュニティを出力する。このステップによって、関係の内容に共通性があり関係の密度も高いコミュニティが形成される。処理の詳細は図４のフローチャートを用いて後述する。

コミュニティ集約ステップS15では、S14で形成したコミュニティすべてを入力とし、重複の大きい複数のコミュニティを一つのコミュニティに集約して最終的なコミュニティの集合を出力する。コミュニティを集約する条件は、コミュニティメンバ重複度（数３）、コミュニティデータ重複度（数４）が閾値以上であることと定義することができる。このステップによって、開始点は異なったがコミュニティ形成の過程を経て同一のコミュニティに拡張されたものを一つのコミュニティに集約する。

図２は、関係内容データクラスタリングステップS11のフローチャートである。
関係内容データ間距離算出ステップS21では、関係内容データ集合を入力とし、各データ間の距離を値とする距離行列を出力する。この距離行列は、クラスタリングデンドログラムの算出に用いられる。関係内容データがメールなどのテキストデータであった場合を用いて、距離行列算出方法を具体的に説明する。各関係内容テキストデータから形態素解析技術などを用いて単語を切り出し、各データに対する、単語とその出現頻度のリストを作成する。作成した単語リストを用いて、各データに対し全てのデータを、類似度をもとにスコア付けする。スコアの計算方法としてSMART（非特許文献３）などの方法が知られており、この方法を用いると、比較のもととなるデータとの類似度が高いデータほど高いスコアが付与される。ここまでのテキストデータ間のスコア付けの方法は、類似文書検索において公知な技術である。計算したスコアを、比較のもととなるデータ自身に付与されたスコアが１となるように正規化する。各データの正規化されたスコアを最大値である１から引いたものを、比較のもととなるデータとの間の距離とする。さらに、データ１を基準にしたデータ２の距離と、データ２を基準にしたデータ１の距離との平均値をデータ１，２間の距離とする。例における、データ１から６の距離行列を、図５に示す。図５の距離行列では、要素(i,j)が、データiとデータjの間の距離を表すが、要素(i,j)と要素(j,i)は同じ値となるため三角行列で示してある。要素(i,i)は、同一のテキスト間の距離を表すため値は0となる。関係内容データ間の距離は、テキストの類似の他にも、データ内容の類似、データのジャンルの類似や一致、データ形式の一致、データそのものの一致などを用いて定義できる。

関係内容データクラスタリングステップS22では、S21で算出した距離行列を入力とし、関係内容データのクラスタリングデンドログラムを出力する。クラスタリングデンドログラムの算出方法には、階層的クラスタリング手法（非特許文献４）などを用いる。このクラスタリングデンドログラムを用いると、内容に基づいた関係内容データのクラスタを様々な大きさで作ることができる。また、あるクラスタに最も距離の近いクラスタを足すことで、クラスタをデータの類似に基づいて拡大することが可能である。図５の距離行列を入力として算出したクラスタリングデンドログラムを図６に示す。図６における１から６のラベルのついたデータが、図５の距離行列の行と列の要素であるデータ１から６である。図６のクラスタリングデンドログラムは、図２０に示すクラスタリングデンドログラムテーブルによって管理される。2001はクラスタIDを表し、2002は親クラスタIDを表し、2003は子クラスタIDを表し、2004は兄弟クラスタIDを表す。図６のデンドログラムにおける例では、データ１で構成されるクラスタID＝１のクラスタ（クラスタ１）は、親クラスタが、データ１，２で構成されるクラスタ７、兄弟クラスタが、データ２で構成されるクラスタ２であり、子クラスタは持たない。また、クラスタ７は、親クラスタが、データ１，２，３で構成されるクラスタ８、子クラスタが、と、データ２で構成されるクラスタ２、兄弟クラスタが、データ３で構成されるクラスタ３である。
図３は、コア部をデンドログラム部分木にマッピングするステップS13のフローチャートである。

コア部マッピングステップS31では、S11で出力したクラスタリングデンドログラムとS12で出力したコア部の集合を入力とする。デンドログラム部分木の構成メンバを、該部分木に含まれる関係内容データによって関係を持っている人物の集合とし、各コア部に対して、メンバの重複度の最も高いデンドログラム部分木を対応させた結果を出力する。メンバの重複度は、数１のように定義することができる。このステップにより、各コア部にデンドログラム部分木が対応付けられ、それらがコミュニティ形成の開始点となる。

コア部集約ステップS32では、S31で出力したコア部とデンドログラムの対応を入力とする。同一または包含関係にある部分木に複数のコア部がマッピングされた場合、条件にしたがってコア部を集約して、コア部と部分木のペアの集合を出力する。集約の際の条件には、メンバの重複度（数１）を用いることができる。すなわち、コア部間のメンバの重複度が閾値以上の場合は集約して両コア部のメンバの和を一つのコア部とみなす。コア部が３つ以上ある場合は、最も重複度の高いペアから集約する。このステップによって、S12で抽出されたコア部のうち冗長なものを集約して絞り込む。

図４は、コミュニティ形成ステップS14の詳細処理のフローチャートである。S14では、S13で出力されたコア部と部分木のペアの集合を入力とし、各ペアに対して図４のフローチャートの処理を用いてコミュニティを形成し、形成したコミュニティの集合を出力する。図４のフローチャートに示した処理の入力は、コア部と部分木のペアの一つであり、出力は入力されたペアから形成したコミュニティである。

ここから、図４のフローチャートの各ステップを、図７、図８を用いて説明する。
図７の71は図６のものに等しいクラスタリングされたデンドログラムである。データ１から６の下には、各データによって関係を持っている人物２名（ＡからＦのうちいずれか）が示されている。図７の72は71のクラスタリングデンドログラムの人物関係のネットワークである。72のＡからＦは、71におけるＡからＦの人物に対応する。

72の人物関係ネットワークをS12に入力し、1-Cliqueを用いると、A,B,Cの３人からなるコア部が出力される。コア部は直感的には関連性の強い人物の集合を示しているといえる。これを図８の81に示す。このコア部をS13に入力すると、71のデンドログラム部分木（クラスタ）Ｔ_０にマッピングされる。次に（A,B,C）の３人からなるコア部と、デンドログラム部分木Ｔ_０をS41に入力する。

カレントクラスタ初期値設定ステップS41では、カレントクラスタの初期値に、入力されたデンドログラム部分木を設定する。カレントクラスタとは、処理中のデンドログラム部分木を指す。71におけるＴ_０がカレントクラスタの初期値となる。

コミュニティ初期値設定ステップS42では、コミュニティに初期値を設定する。コミュニティは、コミュニティメンバとコミュニティデータからなる。コミュニティメンバはコミュニティを構成する人物の集合、コミュニティデータはコミュニティ内でやりとりされたデータの集合である。コミュニティメンバの初期値は、入力されたコア部とカレントクラスタで重複しているメンバの集合とする。コミュニティデータの初期値は、カレントクラスタに属する関係内容データのうち、初期コミュニティメンバ内の任意の２者間でやりとりされたものの集合とする。図７の例では、コミュニティメンバが(A,B,C)、コミュニティデータがデータ１となる。これを、図８の82のＣ_０に示す。

コミュニティメンバ・データ追加ステップS43では、コミュニティに新たにメンバ・データを追加する。追加するメンバは、カレントクラスタに含まれる人物であって、コミュニティに含まれない人物のうち、条件を満たす人物とする。追加の条件は、カレントクラスタに含まれる関係内容データによってコミュニティメンバと直接関係を持つ人物、と定義することができる。追加するデータは、カレントクラスタに含まれるデータであって、コミュニティデータに含まれないデータのうち、コミュニティメンバ（新規追加した人物を含む）同士でやりとりされたデータとする。このステップによって、関係の内容と、コミュニティとのつながりの２つの基準を考慮して、コミュニティの一員にふさわしい人物を追加する。図７の例では、コミュニティメンバにデータ２の内容でＣと関係を持っているDが、コミュニティデータにデータ２が追加される。これを、82のＣ_１に示す。

終了判定ステップS44では、コミュニティ形成処理の終了を判定する。終了条件は、以下の３つの閾値とその組合せを用いて定義できる。一つ目の閾値は、数２に示す関係密度である。関係密度が閾値以下になったらコミュニティ形成処理を終了する。二つ目の閾値は、処理繰り返し回数である。処理繰り返し回数は、S41に入力された部分木から開始していくつ上の階層の部分木まで処理対象とするかを表す。処理繰り返し回数が大きくなるに従って、カレントクラスタ内の関係内容データの類似度は低くなる。三つ目の閾値は、次の処理に追加するクラスタのサイズである。次の処理に追加するクラスタのサイズが閾値以上であれば、コミュニティ形成処理を終了する。処理するクラスタのサイズが大きいと、既に処理したクラスタ内のデータとの類似度の低いデータが多く含まれると考えられる。このステップによって、コミュニティと認識する集合の境界が決まる。各々の閾値を、コミュニティ密度60%、処理繰り返し回数５回またはクラスタリングデンドログラムのルートに達するまで、追加クラスタサイズ10データ、と仮定する。82のC_１では、コミュニティ密度は、4/6=0.67、処理繰り返し回数１回、追加クラスタサイズ１（71のクラスタＴ_１１）であり、いずれの閾値も超えることはない。

カレントクラスタ更新ステップS45では、カレントクラスタを、カレントクラスタの親クラスタに更新する。このステップは、S44の終了判定が「いいえ」だった場合に実行され、実行後はS43に戻る。このステップによって、クラスタの階層を１段上に上げて、より大きなクラスタをコミュニティ形成の範囲とする。図７の例では、S44の終了判定が「いいえ」だったためS45に進み、Ｔ_１がカレントクラスタとなる。

S45の処理が終了したら、S43に戻りコミュニティにメンバとデータを追加する。図７の例では、コミュニティメンバに追加はなく、コミュニティデータにデータ３が追加される。これを、82のＣ_２に示す。

S43の処理が終了したら、S44に進み、処理終了判定を行う。82のＣ_２では、コミュニティ密度は4/6=0.67、処理繰り返し回数２回、追加クラスタサイズ３（71のクラスタＴ_２１）であり、いずれの閾値も超えることはない。

S44の終了判定が「いいえ」だったためS45に進み、Ｔ_２がカレントクラスタとなる。
S43に戻り、コミュニティメンバにデータ６の内容でＡと関係を持っているＦが、コミュニティデータにデータ４とデータ６が追加される。これを、82のＣ_３に示す。データ５の内容で関係を持っているＥとＦはどちらもコミュニティメンバに入っていなかったため、追加されない。

S43の処理が終了したら、S44に進み、処理終了判定を行う。82のＣ_３では、コミュニティ密度は5/10=0.5、処理繰り返し回数３回、追加クラスタサイズ０であり、コミュニティ密度が閾値を超えているため終了条件を満たす。

コミュニティ出力ステップS46は、S44の終了判定が「はい」だった場合に実行され、形成したコミュニティを出力する。ただし、コミュニティ密度に関しては、閾値を越える直前のものを出力する。図７の例では、82のＣ_２が出力される。

次に、図２６を用いて、仲介経路検索部1211の処理を説明する。
仲介経路算出ステップS2601では、仲介経路検索クエリと関係ネットワークを用いて、仲介経路検索クエリを送信したユーザと、仲介希望先の有識者ユーザとの間をつなぐ仲介経路を算出する。S2603の処理は、仲介経路算出部1205にて実行される。仲介経路算出方法としては、ネットワーク上の２ノード間の最短経路を算出する、Warshall-Floyd法（非特許文献７）などの方法がある。算出した仲介経路は、図２９に示すような仲介経路テーブルによって管理される。

仲介経路出力ステップS2602では、S2601にて算出した仲介経路を出力する。仲介経路検索クエリを送信したユーザは、出力された仲介経路の人物に、仲介希望先の有識者との間の仲介を依頼することができる。
以上が、Know-Who検索サーバの機能説明である。

次に、図１１を用いて、情報端末905の機能を説明する。情報端末905は、コミュニケーション用アプリケーション910と、Know-Who検索用アプリケーション909とを備える。Know-Who検索用アプリケーションは、Know-Whoの機能に関連する動作の制御を行い、情報送受信部1111のKnow-Who関連情報送受信部1113によってKnow-Who検索サーバと通信する。Know-Who検索要求送信や、Know-Who検索結果の画面表示などの処理は、Know-Who検索管理部1105のKnow-Who検索制御部1107が実行する。コミュニケーション用アプリケーションは、端末間通信の機能に関連する動作の制御を行い、情報送受信部1108のコミュニケーション情報送受信部1109によってSIPサーバ及びプレゼンスサーバと通信する。コミュニケーション制御部1101の文字・音声映像情報入出力部1102は、外部入出力デバイスからの情報を管理し、SIPサーバとの通信を制御する。プレゼンス・バディリスト管理・制御部は、プレゼンスサーバとの通信を制御し、プレゼンス・バディリストの表示を管理する。また、Know-Who検索用アプリケーションのコミュニケーション制御部1106、コミュニケーション制御情報送受信部1112と、コミュニケーション用アプリケーションのアプリケーション動作制御情報処理部1104、アプリケーション動作制御情報送受信部1110によって、Know-Who検索用アプリケーションとコミュニケーション用アプリケーションが連携する。

次に、図１３を用いて、プレゼンスサーバの機能を説明する。プレゼンスサーバ902は、情報送受信機能1304のプレゼンス情報送受信部1305によって、情報端末のプレゼンス情報を受信し、その情報を、プレゼンス情報・バディリスト情報管理機能1301のプレゼンス情報管理部1302によって管理する。また、バディリスト関連情報送受信部1306によって、情報端末のバディリスト追加削除操作の情報を受信し、その情報を、バディリスト管理部1303によって管理する。プレゼンス情報・バディリスト情報は、図１８のプレゼンスサーバログテーブルのような形式で管理される。1801はユーザIDである。1802はユーザの行動内容である。1803は行動内容の詳細である。

次に、図１４を用いて、SIPサーバの機能を説明する。SIPサーバ901は、プレゼンス情報、サブスクライブ管理機能1401のユーザ状態管理部1402と、情報送受信機能1405のSIPメッセージ送受信部1406によって、情報端末間のメッセージを送受信する情報端末同士の通信を仲介する。また、ユーザ通信履歴管理部1403によって情報端末間の通信履歴を管理し、履歴情報送受信部1407によって、情報端末間の通信履歴をKnow-Whoサーバに通知する。情報端末間の通信履歴は、図１７のSIPサーバログテーブルのような形式で管理される。1701は送信元ユーザIDである。1702は送信先ユーザIDである。1703は通信手段である。1704は通信が行われた時刻である。1705は通信の内容（テキストなど）である。

図１５は、図９に示したシステムの動作シーケンス図である。図１５のシーケンスを追って図９の動作内容の詳細を説明する。
図１５は、ユーザＡがKnow-Who検索を行い有識者ユーザＣとコミュニケーションを取る動作のシーケンス図である。

ステップ1501において、ユーザAはKnow-Who検索サーバにログインする。ステップ1502において、ユーザＡはKnow-Who検索要求をKnow-Who検索サーバ903に送信する。検索クエリとなる特定の知識分野は、キーワードなどによって与えられる。検索要求を受信したKnow-Who検索サーバは、Know-Who検索処理を実行し、ステップ1503において検索結果を送信する。ステップ1504において、ユーザＡは、情報端末のKnow-Who検索用アプリケーションが表示した検索結果を用いて、コミュニケーションを希望する有識者を選択する。ステップ1505において、ユーザＡは、自身と選択した有識者との間の仲介経路の検索要求をKnow-Who検索サーバ903に送信する。仲介経路検索要求を受信したKnow-Who検索サーバは仲介経路検索処理を実行し、ステップ1506において検索結果を送信する。ユーザＡは、情報端末の検索用アプリケーション909が表示した検索結果から、仲介者としてユーザＢを選択し、ステップ1507において、コミュニケーション用アプリケーションを起動する。ステップ1508においてユーザＡの情報端末のKnow-Who検索用アプリケーションはKnow-Who検索サーバにコミュニケーション用アプリケーション起動通知を送信する。ステップ1509において、ユーザＡはSIPサーバに、ユーザＢへの仲介依頼を送信し、SIPサーバはユーザＢのコミュニケーション用アプリケーションに仲介依頼を送信する。ステップ1510において、仲介依頼を受けたユーザＢはSIPサーバに、ユーザＣへの情報提供依頼を送信し、SIPサーバはユーザＣのコミュニケーション用アプリケーションに情報提供依頼を送信する。ステップ1511において、情報提供依頼を受けたユーザＣはユーザＡとの議論を行う。

図１６は、情報端末のKnow-Who検索アプリケーションのKnow-Who検索結果画面イメージ図である。1601はクエリ入力部である。1602はKnow-Who検索ボタンである。このボタンをクリックすると、情報端末からKnow-Who検索サーバへKnow-Who検索要求が送信される。1603はコミュニティ一覧である。Know-Who検索サーバから受信した、S2504の出力であるコミュニティを表示する。コミュニティ一覧は、S2502で算出したスコアの順にソートして表示する。1604はコミュニティメンバ一覧であり、1603の選択欄にて選択したコミュニティのメンバとS2604で算出した中心性を表示する。コミュニティメンバ一覧は、中心性の順にソートして表示する。1605は仲介経路検索ボタンである。このボタンをクリックすると、情報端末からKnow-Who検索サーバへ、検索実行ユーザから1604の選択欄にて選択した人物への仲介経路検索要求が送信される。1606は仲介経路一覧である。S2602にて出力した仲介経路検索結果をKnow-Who検索サーバから受信したものを表示する。

ユーザは図16に示されるインターフェースを用いて、興味のあるテーマ（この例では「フラッシュマイコン」「自動車」）に関連したコミュニティを検索し、コミュニティ一覧1603として閲覧することができ、選択したコミュニティのメンバはメンバ一覧1604で閲覧することができる。そして、コミュニティに参加したい場合は、仲介経路1606のパスを用いてコミュニティメンバにコンタクトし、あるいは、コミュニティへの参加が可能となる。

参加の処理の一例としては、このようなユーザの検索履歴または仲介経路へのコミュニケーション履歴をもとに、当該検索あるいはコミュニケーションを行ったユーザをコミュニティに自動的に追加することもできる。すなわち、人間関係のネットワークの構築にユーザのアクションをフィードバックすることも可能である。

実施の形態2では、Know-Who検索サーバがユーザのKnow-Who検索操作履歴と、当該操作に引き続くユーザの通信履歴をSIPサーバから受け取り、ユーザが仲介経路に提示された仲介者や有識者とのコミュニケーションを、新たな人間関係の構築や、既存の人間関係の変化として、Know-Who検索サーバの人間関係構築部にフィードバックする構成とすることで、Know-Who検索を用いたコミュニケーションの自発性を反映させる、コミュニケーション抽出方法を用いたKnow-Who検索システムについて説明する。

本実施の形態では、図２２に示す関係ネットワーク行列の要素は、関係の有無(0,1)ではなく、関係の重みを反映した0から1の間の値として表す。図２７に例を示す。例えば、標準的な関係の有無を重み0.5として定義し、上述のような自発的な関係構築により関係ネットワーク行列が更新される場合には、ユーザと有識者の間の要素の値を、1を超えない範囲で増大させる。これは関係を強化することに相当する。また、場合によっては関係の弱化を反映させるために0を下回らない範囲で減少させることも可能である。これは、ユーザと有識者の関係が悪化したことを反映する場合である。

以下、図２８を用いて実施の形態２における人間関係の変化をフィードバックする処理手順について説明する。

図２８において、ステップ1501からステップ1511までのシーケンスは図１５における説明と同様である。ステップ1512において、SIPサーバは、ユーザＡとユーザＣとの通信履歴をKnow-Who検索サーバに送信する。具体的にはSIPサーバが保持する図１７に示すテーブルの各レコードの内容を送信する。ステップ1513において、Know-Who検索サーバは、通信履歴を用いて人間関係更新処理を実行する。

以上のようにすることで、Know-Who検索システムを利用し、有効なコミュニケーションが行われた場合には、ユーザAが自発的に有識者ユーザCとの関係ネットワークを新たに構築しようとしたと判断し、当該ユーザAと当該有識者ユーザCの関係ネットワーク行列の該当する要素を設定する。具体的には、ステップ1512でKnow-Who検索サーバが受信した図１７に示す通信履歴と、図１９に示すKnow-Whoサーバが内部で保持する各ユーザの操作履歴の中のコミュニケーションを開始した事を示すレコード1904の様な情報を照らし合せる事でKnow-Who検索サーバを利用してコミュニケーションが発生したことを判断する。この場合標準的な関係の有無の重み0.5より大きな値を設定する。自発的な関係はより強固な関係と考えられるためである。具体的には現状の要素値(ここでは初期値が0.5であるとする)を、予め定めた増分式に従い増加させる。例えば、現在の要素値をxとし、Bを1以下の正数とすると(x+(1-x)*B) を新たな要素の値とすることができる。これは関係の強化を意味する。この際、関係ネットワーク行列を対称に、すなわちユーザから有識者への関係、有識者からユーザへの関係の両方を増大させても良い。あるいは、ユーザから有識者への関係のみ増大させても良い。

更に、ユーザAと有識者ユーザCの関係を仲介した仲介者ユーザBも既存の関係ネットワークの要素の値を増大させる。これは、自発的な他者間の新たな関係の形成に寄与できた実際に機能する関係として評価できるためである。この際、関係ネットワーク行列を対称に、すなわち仲介元ユーザから仲介先ユーザへの関係、仲介先から仲介元への関係の両方を増大させても良い。あるいは、仲介元から仲介先への関係のみ増大させても良い。
以上のような場合、関係は一方向である。

ステップ1514において、ユーザＡが、有用な仲介者である仲介者ユーザＢと、今後も議論を継続したい相手である有識者ユーザＣのバディリストへの登録要求をプレゼンスサーバ902に送信する。ステップ1516において、プレゼンスサーバ902はバディリスト登録履歴をKnow-Who検索サーバ903に送信する。具体的にはプレゼンスサーバが保持する図１８に示すテーブルの各レコードの内容を送信する。Know-Whoサーバは上記のコミュニケーションの場合と同様に、図１８に示す履歴と図１９のレコード1904を照らし合わせてKnow-Who検索サーバを利用してバディリスト登録が発生したことを判断する。ステップ1517において、Know-Who検索サーバは人間関係更新処理を実行する。

バディリストへの登録は、単にメールを数度やり取りした間柄に比べより強い人間関係の構築に寄与する。ここでKnow-Who検索サーバ903は、ステップ1517で、上述のように、関係ネットワーク行列の該当要素の値を増大させる。
尚、バディリストは関係者一方の意思で任意に設定、解除されるため、関係マトリクスに設定する場合には、一方向の関係として設定する。
尚、バディリストからの削除は、該当する要素の値を減少させることに相当することは言うまでもない。

更に、ステップ1518において、有識者ユーザＣは、今後も議論を継続してもよい相手であるユーザＡのバディリストへの登録要求をプレゼンスサーバに送信する。ステップ1519において、プレゼンスサーバはバディリスト登録履歴をKnow-Who検索サーバに送信する。ステップ1520において、Know-Who検索サーバは人間関係更新処理を実行する。ステップ1518,1519,1520の処理は、ステップ1514,1516,1517の処理と同様である。

一般的に、コミュニティの中心的な人物である有識者ユーザCがユーザAをバディリストに登録するかどうかが、ユーザAがコミュニティのメンバに加えられるかどうかに影響を及ぼす。本システムはこの状況をエミュレートする。

以上のようにKnow-Who検索システムを利用したコミュニケーションの履歴がフィードバックされることにより、インフォーマルで、より関係の強固なコア部の抽出が行えるとともに、関係性の強いコミュニティの抽出が可能となる。

具体的には、コミュニティコア部の抽出時に、関係を連続値で表した図２７の関係マトリクスを用いたり、コミュニティメンバ・データ追加ステップS43において、コミュニティメンバと直接関係を持つ人物、という条件定義を、予め定められた値以上の強さの関係、すなわち関係マトリクスの要素値(例えば0.6) 以上を持つ人物、に変更することによって、よりインフォーマル度が高く関係性の強いコミュニティを抽出できる。

以上のように、実施例においては、人物間の関係のネットワークと、関係内容データのクラスタリングを用いて、関係内容データに共通性があり、相互関係が高密度な人物の集合をコミュニティとして取り出すことができる。

また、関係を内容ごとに考慮してコミュニティを形成することにより、複数の役割を持った人物をそれぞれの役割のコミュニティに同時に属させるようなコミュニティの抽出が可能となる。

また、各コミュニティに対しコミュニティを形成する関係の内容をコミュニティデータとして取り出すことにより、コミュニティの話題や関心の特徴を的確に表現したり、キーワードに合致するコミュニティを検索したりすることが可能となる。

また、コミュニケーション履歴のフィードバックを行うことにより、より実際の人物間の関係に忠実なコミュニティ抽出が可能となる。

インターネットにおける広告配信・情報提供システム、組織コンサルティングを支援する組織分析システム、Know-Who検索システム、コミュニティ検索システムなどへの応用が可能である。

コミュニティ抽出方法のフローチャートを示した図である。関係内容データクラスタリングステップの詳細処理のフローチャートを示した図である。コア部を関係内容データのデンドログラムにマッピングするステップの詳細処理のフローチャートを示した図である。コミュニティ形成ステップの詳細処理のフローチャートを示した図である。距離行列の一例を示した図である。関係内容データのクラスタリングデンドログラムの一例を示した図である。関係内容データのクラスタリングデンドログラムと、それに対応する人物関係ネットワークを示した図である。コミュニティ形成過程を示した図である。 Know-Who検索システム、コミュニケーションシステム、情報端末のネットワーク概要図を示した図である。物理装置構成図を示した図である。情報端末のモジュール構成図を示した図である。 Know-Who検索サーバのモジュール構成図を示した図である。プレゼンスサーバのモジュール構成図を示した図である。 SIPサーバのモジュール構成図を示した図である。実施例１のKnow-Who検索システムのシーケンス図である。 Know-Who検索アプリケーションの画面イメージ図である。 SIPサーバログテーブルを示した図である。プレゼンスサーバログテーブルを示した図である。 Know-Whoサーバ操作履歴テーブルを示した図である。クラスタリングデンドログラムテーブルを示した図である。コミュニティテーブルを示した図である。実施例１の関係ネットワーク行列を示した図である。コア部テーブルを示した図である。関係データテーブルを示した図である。コミュニティ検索のフローチャートを示した図である。仲介経路検索のフローチャートを示した図である。実施例２の関係ネットワーク行列を示した図である。実施例２のKnow-Who検索システムのシーケンス図である。仲介経路テーブルを示した図である。

符号の説明

５１距離行列
６１関係内容データのクラスタリングデンドログラム
７１関係内容データのクラスタリングデンドログラムと関係を持っている人物
７２人物関係ネットワーク
８１人物関係ネットワークにおけるコア部
８２コミュニティ形成過程。

Claims

データを保持するデータ保持手段、保持されたデータを処理するデータ処理手段を少なくとも備えた情報処理装置によって実行されるコミュニティ抽出方法であって、
ユーザ相互の関連性を示す人間関係ネットワークを生成し、上記データ保持手段に保持するステップと、
上記ユーザが関与する関係内容データを類似度に基づいてクラスタリングしたデンドログラムを作成し、上記データ保持手段に保持するステップと、
前記人間関係ネットワークから複数の上記ユーザの少なくとも一部を構成メンバとして包含する１または複数のコア部を抽出するステップと、
該コア部を前記デンドログラムにマッピングして、上記構成メンバの少なくとも一部を含むコミュニティを抽出するステップと、
により構成することを特徴とするコミュニティ抽出方法。
前記コア部をデンドログラムにマッピングするステップは、
コア部の構成メンバとデンドログラムの部分木の構成メンバとの重複度を用いること、
を特徴とする請求項１に記載のコミュニティ抽出方法。
前記コミュニティを形成するステップは、
前記デンドログラムを用いて類似度の高い他の部分木を探索し、
該探索した部分木に属する関係内容データに関与するユーザをコミュニティへの追加候補とし、
該追加候補のユーザと該コミュニティの何れかのメンバとの間に該探索した部分木に属する関係内容データに基づく人間関係が有る場合に、前記追加候補のユーザを該コミュニティのメンバとして追加する処理を順次繰り返すこと、
を特徴とする請求項２に記載のコミュニティ抽出方法。
前記コミュニティを形成するステップは、
コミュニティ内の関係密度を閾値として処理を終了すること、
を特徴とする請求項３に記載のコミュニティ抽出方法。
前記コミュニティを形成するステップは、
次にコミュニティへの追加の対象となるデンドログラムの部分木の大きさを閾値として処理を終了すること、
を特徴とする請求項3に記載のコミュニティ抽出方法
前記コミュニティを形成するステップは、
前記デンドログラムの部分木を探索してコミュニティにメンバを追加する処理の繰り返し回数を閾値として処理を終了すること、
を特徴とする請求項３に記載のコミュニティ抽出方法
前記１または複数のコア部を元にしてコミュニティを形成した結果、複数のコミュニティが得られた場合に、更にコミュニティを集約するステップを行うこと、
を特徴とする請求項４乃至６に記載のコミュニティ抽出方法。
前記コミュニティを集約するステップは、
二つのコミュニティのメンバの重複度及び各コミュニティの形成過程で追加されたメンバが関与する関係内容データの二つのコミュニティ間での類似度を閾値として、一つのコミュニティに集約するか否かを決定すること、
を特徴とする請求項７に記載のコミュニティ抽出方法。
データを保持するデータ保持手段、保持されたデータを処理するデータ処理手段を少なくとも備えたコミュニティ抽出処理装置であって、
上記データ処理手段は、
ユーザ相互の関係をネットワーク構成で表現する人間関係ネットワークを生成する人間関係ネットワーク構築手段と、
上記人間関係ネットワークを構成するユーザの関係を表す関係内容データを類似度に基づいてクラスタリングしたデンドログラムを作成するデンドログラム生成手段と、
上記人間関係ネットワークからグラフ理論に基づき高密度部分である１または複数のコア部を抽出するコア部抽出手段と、
該コア部を前記デンドログラムにマッピングするコミュニティ形成手段と、
によって構成されることを特徴とするコミュニティ抽出処理装置。
前記コミュニティ形成手段に、
コミュニティ形成処理終了判定手段を備えることを特徴とする、
請求項９に記載のコミュニティ抽出処理装置。
コミュニティ集約手段を備えることを特徴とする、
請求項９または１０に記載のコミュニティ抽出処理装置。
前記人間関係ネットワーク構築手段はユーザの検索履歴またはコミュニケーション履歴を人間関係ネットワークの構築にフィードバックすることを特徴とする、請求項9に記載のコミュニティ抽出処理装置。