(57)【特許請求の範囲】
【請求項１】
コンピュータを、
ネットワーク内の各ノードの、クエリに対する適合度合いを示す評価値を計算する評価値計算手段、
前記各ノードの評価値のうちの第１成分は当該ノードから出るリンクに従ってリンク先のいずれかのノードへと遷移し、前記各ノードの評価値のうちの第２成分は当該ノードから出るリンクとは無関係に他のノードへと遷移する、という計算ルールに従って、遷移後の前記各ノードの評価値を計算する、前記第２成分の遷移計算手段であって、前記計算ルールでは、前記第２成分は、０に近い第１範囲内の評価値を持つノードよりも前記第１範囲よりも高い評価値を持つノードに対してより多く遷移すると共に、前記ノードの評価値に占める前記第１成分の割合は前記評価値の増加に従って単調増加する、遷移計算手段、
前記遷移計算手段の計算した前記各ノードの遷移後の評価値に基づき、前記クエリに対応する１以上のノードを特定する特定手段、
として機能させるためのプログラム。
【請求項２】
前記特定手段は、前記遷移計算手段の計算した前記各ノードの遷移後の評価値があらかじめ定めた閾値より大きい値を持つノード群を、前記クエリに対応するコミュニティとして特定する、ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記特定手段は、特定したノード群を、前記遷移計算手段の計算した前記各ノードの遷移後の評価値が高い順に示したリストを生成する、ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
前記計算ルールでは、前記ノードの評価値に占める前記第１成分の割合は、前記評価値が閾値以下であるノードについては０である、ことを特徴とする請求項１〜３のいずれか１項に記載のプログラム。
【請求項５】
ネットワーク内の各ノードの、クエリに対する適合度合いを示す評価値を計算する評価値計算手段と、
前記各ノードの評価値のうちの第１成分は当該ノードから出るリンクに従ってリンク先のいずれかのノードへと遷移し、前記各ノードの評価値のうちの第２成分は当該ノードから出るリンクとは無関係に他のノードへと遷移する、という計算ルールに従って、遷移後の前記各ノードの評価値を計算する、前記第２成分の遷移計算手段であって、前記計算ルールでは、前記第２成分は、０に近い第１範囲内の評価値を持つノードよりも前記第１範囲よりも高い評価値を持つノードに対してより多く遷移すると共に、前記ノードの評価値に占める前記第１成分の割合は前記評価値の増加に従って単調増加する、遷移計算手段と、
前記遷移計算手段の計算した前記各ノードの遷移後の評価値に基づき、前記クエリに対応する１以上のノードを特定する特定手段と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び情報処理装置に関する。
【背景技術】
【０００２】
現実世界に存在する巨大で複雑なネットワークである「複雑ネットワーク」の研究が進んでおり、複雑ネットワークの分析やその分析結果を利用したサービスが種々提案されている。複雑ネットワークには、例えば、膨大な数のウェブページ群から構成されるＷＷＷ（World Wide Web）、インターネット、ソーシャルネットワーク、文書引用ネットワーク、ユーザ商品ネットワーク、遺伝子制御ネットワーク、タンパク相互作用ネットワーク等がある。
【０００３】
複雑ネットワーク科学において、ネットワーク中のリンク（エッジとも呼ばれる）が密な部分のことを「コミュニティ」と呼ぶ（後述の非特許文献１，２参照）。コミュニティは、ネットワークで表現される複雑系を構成する個々の機能モジュールに対応するとも考えられる。複雑ネットワーク等のネットワークからコミュニティを抽出する手法が様々に提案されている。
【０００４】
非特許文献１，２は、ネットワークからコミュニティを検出するアルゴリズムに関する総説である。これまでに提案されてきたコミュニティ検出アルゴリズムのうち注目すべきもの（例えばモジュラリティ最大化、情報圧縮、ラベル伝搬、クリークパーコレーション、ブロックモデル）はすべてこれら文献に記載されている。
【０００５】
非特許文献３〜６には、ユーザ等から指定された１個の種ノードをメンバとして含むコミュニティを検出する方法が開示されている。これら文献に開示された方法では、指定された種ノードを起点として、ネットワーク内のノードをたどりながらコミュニティにノードを付け足していき、コミュニティの評価値を評価関数により計算する。その評価値を最適化することで、目的のコミュニティを求める。
【０００６】
特許文献１には、ノード間の遷移がマルコフ連鎖に従うネットワークにおいて、指定されたノードを始点とする経路のうち、たどる可能性の最も高い経路を、マルコフ連鎖の遷移確率に基づく時間遷移の繰り返し演算によって求める方法が記載されている。
【０００７】
特許文献２には、ノード間の遷移がマルコフ連鎖に従うネットワークにおいて、ユーザからの検索条件に適合するノード群を求めるための計算負荷が高いパーソナライズド・ページランクアルゴリズムの演算処理を、ネットワーク全体ではなく、検索条件に関連する部分に限定するための方法が記載されている。この方法では、学習用データを用いてネットワーク上のマルコフ連鎖のクラスタリングを学習すると共に、ユーザからの検索条件に該当するノード群とクラスタリングの学習結果とから、検索条件に適合するクラスタを抽出し、そのクラスタに属するノード群からなる部分ネットワークに対してパーソナライズド・ページランクアルゴリズムを実行する。
【０００８】
特許文献３に記載された情報処理装置は、ログ情報を文書ＤＢ（データベース）から取得するログ取得手段と、文書情報を操作する利用者をノードとし、同一の文書情報を操作した利用者間にリンクを張って、ネットワーク構造を生成するネットワーク生成手段と、ネットワーク構造からリンクの生成確率に基づく確率モデルを用いて共通の関連性を有する複数の利用者の集合をコミュニティとして抽出するコミュニティ抽出手段と、コミュニティにおける利用者の確率分布である所属率又はコミュニティにおける利用者のネットワーク指標の期待値である影響度を指標として算出する利用者指標算出手段とを有する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Newman, M.E.J. Communities, modules and large-scale structure in networks. Nature Physics 8, 25-31 (2011)
【非特許文献２】Fortunato, S. Community detection in graphs. Physic Report 486, 75-174 (2010)
【非特許文献３】Bagrow, J.P., Bollt, E.M.: Local method for detecting communities. Phys. Rev. E 72, 046108 (2005)
【非特許文献４】Clauset, A.: Finding local community structure in networks. Phys. Rev. E 72, 026132 (2005)
【非特許文献５】Lancichinetti, A., Fortunato, S., Kertesz, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11, 033015 (2009)
【非特許文献６】Okamoto, H.: Local Detection of Communities vt Neural-Network Dynamics. LNCS 8131, 50--57 (2013)
【特許文献】
【００１０】
【特許文献１】特開２０１３−４１５３０号公報
【特許文献２】特開２０１３−１６８１２７号公報
【特許文献３】特開２０１５−４６１０２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
指定された種ノードを起点として、ネットワーク内のノードをたどりながらコミュニティにノードを付け足していき、評価値の高いコミュニティを求める方法では、ユーザが種ノードを指定する必要がある。ユーザが種ノードを特定できない場合や、１つの種ノードに絞り込めない場合等には、そのような方法は利用できない。
【００１２】
本発明は、ユーザがネットワーク内の単一のノードを種ノードとして特定できない場合でも、ユーザのクエリに対応するネットワーク内のコミュニティを抽出できるようにすることを目的とする。
【課題を解決するための手段】
【００１３】
請求項１に係る発明は、コンピュータを、ネットワーク内の各ノードの、クエリに対する適合度合いを示す評価値を計算する評価値計算手段、前記各ノードの評価値のうちの第１成分は当該ノードから出るリンクに従ってリンク先のいずれかのノードへと遷移し、前記各ノードの評価値のうちの第２成分は当該ノードから出るリンクとは無関係に他のノードへと遷移する、という計算ルールに従って、遷移後の前記各ノードの評価値を計算する、前記第２成分の遷移計算手段であって、前記計算ルールでは、前記第２成分は、０に近い第１範囲内の評価値を持つノードよりも前記第１範囲よりも高い評価値を持つノードに対してより多く遷移すると共に、前記ノードの評価値に占める前記第１成分の割合は前記評価値の増加に従って単調増加する、遷移計算手段、前記遷移計算手段の計算した前記各ノードの遷移後の評価値に基づき、前記クエリに対応する１以上のノードを特定する特定手段、として機能させるためのプログラムである。
【００１４】
請求項２に係る発明は、前記特定手段は、前記遷移計算手段の計算した前記各ノードの遷移後の評価値があらかじめ定めた閾値より大きい値を持つノード群を、前記クエリに対応するコミュニティとして特定する、ことを特徴とする請求項１に記載のプログラムである。
【００１５】
請求項３に係る発明は、前記特定手段は、特定したノード群を、前記遷移計算手段の計算した前記各ノードの遷移後の評価値が高い順に示したリストを生成する、ことを特徴とする請求項１又は２に記載のプログラムである。
【００１６】
請求項４に係る発明は、前記計算ルールでは、前記ノードの評価値に占める前記第１成分の割合は、前記評価値が閾値以下であるノードについては０である、ことを特徴とする請求項１〜３のいずれか１項に記載のプログラムである。
【００１７】
請求項５に係る発明は、ネットワーク内の各ノードの、クエリに対する適合度合いを示す評価値を計算する評価値計算手段と、前記各ノードの評価値のうちの第１成分は当該ノードから出るリンクに従ってリンク先のいずれかのノードへと遷移し、前記各ノードの評価値のうちの第２成分は当該ノードから出るリンクとは無関係に他のノードへと遷移する、という計算ルールに従って、遷移後の前記各ノードの評価値を計算する、前記第２成分の遷移計算手段であって、前記計算ルールでは、前記第２成分は、０に近い第１範囲内の評価値を持つノードよりも前記第１範囲よりも高い評価値を持つノードに対してより多く遷移すると共に、前記ノードの評価値に占める前記第１成分の割合は前記評価値の増加に従って単調増加する、遷移計算手段と、前記遷移計算手段の計算した前記各ノードの遷移後の評価値に基づき、前記クエリに対応する１以上のノードを特定する特定手段と、を有する情報処理装置である。
【発明の効果】
【００１８】
請求項１，２又は５に係る発明によれば、ユーザがネットワーク内の単一のノードを種ノードとして特定できない場合でも、ユーザのクエリに対応するネットワーク内のコミュニティを抽出できる。
【００１９】
請求項３に係る発明によれば、クエリに対するノードの適合度合いだけでなく、ネットワーク内でのノード同士のリンク状況も加味して、クエリに対する評価値の高いノードのリストを提供することができる。
【００２０】
請求項４に係る発明によれば、閾値以下の評価値に対応する第１成分の割合を０より大きい値とする場合と比べて、遷移計算手段における計算で、クエリに対応するコミュニティに含まれるノードと、そのコミュニティに含まれないノードとの差をより明確にすることができる。
【図面の簡単な説明】
【００２１】
【図１】実施形態の情報処理装置の機能構成の一例を示す図である。
【図２】評価値ｐn（ｔ）とその中のリンク遷移成分ｆn（ｔ）との関係を示すグラフの例を示す図である。
【図３】クエリに対する適合度合いだけではコミュニティに属さない偽メンバーが抽出される可能性があるのに対し、ネットワークのリンク状況を加味して評価値の時間発展を繰り返し計算することで、偽メンバーを排除したコミュニティが抽出されることを説明するための図である。
【図４】評価値ｐn（ｔ）とその中のリンク遷移成分ｆn（ｔ）との関係を示すグラフの別の例を示す図である。
【発明を実施するための形態】
【００２２】
図１を参照して、本発明の一実施形態の装置構成を説明する。
【００２３】
ネットワーク情報記憶部１０は、処理の対象となるネットワーク（例えばＷＷＷ）を表す情報（以下「ネットワーク情報」と呼ぶ）を記憶する記憶装置である。ネットワーク情報には、当該ネットワークの構造を示す情報、すなわち当該ネットワーク内のノード同士のリンク接続の関係を示す接続関係情報が含まれる。この接続関係情報は、例えば隣接行列の形で表現される。なお、周知のように隣接行列Ａｎｍは、ノードｍからノードｎへリンクが張られていればＡｎｍ＝１、そうでなければＡｎｍ＝０となる行列である。また、ネットワークの接続関係情報は、遷移行列Ｔｎｍの形で表現される情報であってもよい。遷移行列Ｔｎｍは、ノードｍ上に居るエージェントがノードｍからノードｎへのリンクをたどって、ノードｎに遷移する確率を示す行列である。ノードｍからノードｎへのリンクがない場合は、Ｔｎｍの値は０である。また、あるノードｍに着目した場合、Ｔｎｍをネットワーク内の全ノードｎにわたって総和すると「１」となる。
【００２４】
また、ネットワーク情報には、各ノードの属性情報が含まれていてもよい。ノードの属性情報には、そのノードが表すエンティティが持つ１以上の属性の値が含まれる。例えばノードがウェブページを表している場合、そのウェブページのコンテンツデータ（そのページを表すＨＴＭＬの記述）はそのノードの属性情報の１つである。またノードが論文を表すものである場合、ノードの属性情報にはその論文の内容（テキスト）、著者名、掲載雑誌名等が含まれ得る。また、対象のネットワークがソーシャルネットワークである場合個々のノードはそれぞれ人に対応するが、この場合のノードの属性情報には、そのノードに対応する人の氏名、年齢、性別、職業、所属組織等の情報が含まれ得る。
【００２５】
処理対象のネットワークの情報が本装置の外部に存在する場合、ネットワーク情報取得部１２が、そのネットワークの情報を取得する。例えば、対象のネットワークがＷＷＷである場合、ネットワーク情報取得部１２は、いわゆるクローラーによりリンクをたどってウェブページ群を収集し、収集した情報からノード（ウェブページ）間の接続（リンク）関係や各ノードの属性情報を抽出する。また、ＳＮＳ（ソーシャルネットワークサービス）が管理しているソーシャルネットワークを対象とする場合、ネットワーク情報取得部１２は、ＳＮＳが公開しているインタフェースを利用するなどして、そのソーシャルネットワークの情報を取得する。ネットワーク情報取得部１２が取得したネットワーク情報は、ネットワーク情報記憶部１０に記憶される。
【００２６】
クエリ受付部１４は、対象のネットワークに対するクエリ（問合せ）をユーザから受け付ける。クエリは、対象のネットワーク内のノード群の中から、ユーザの意図に適したものを絞り込むための条件である。クエリの形式は特に限定されない。
【００２７】
例えば、クエリは、ノードが持つ１以上の属性に関する検索条件であってもよい。ノードがウェブページ等の文書に対応している場合、キーワード（検索語）等や複数のキーワードからなる論理式をクエリとしてもよい。また、著者と掲載雑誌名のように複数の属性に関する条件の組み合わせをクエリとしてもよい。
【００２８】
またクエリは、対象のネットワーク内のノード群のうちの特定の１以上のノードを直接指定するものであってもよい。例えば、ソーシャルネットワークを構成する多数の人（ノード）の中から、ユーザの中学時代の同窓生のコミュニティを見つけたい場合に、同窓生として心当たりのある何人かを指定し、これら指定した人の組み合わせをクエリとする場合がこれに該当する。
【００２９】
初期評価値計算部１６は、クエリ受付部１４が受け付けたクエリに対する各ノードの適合度合いを示す評価値の初期値（初期評価値）を計算する。クエリが検索条件である場合、この初期評価値の計算は、検索条件に対する適合度（スコア）を計算する検索アルゴリズムの計算方式により行えばよい。例えば、ネットワーク情報記憶部１０に記憶された各ノードの属性情報に基づき、各ノードがその検索条件に適合している程度を計算すればよい。また、検索アルゴリズムが求めた適合度を正規化（例えば全ノードの評価値の合計が１になるようにする処理）したものを評価値として用いてもよい。また、１以上のノードを直接指定するクエリの場合、指定されたノード以外のノードの初期評価値は０とし、指定された各ノードの初期評価値は正の値（例えば１を指定されたノードの数で割った値）としてもよい。また、ユーザに指定した各ノードの初期評価値を入力させてもよい。なお、ノードの「評価値」は０以上の実数とする。
【００３０】
時間発展計算部１８は、各ノードの評価値の時間発展を計算する。
【００３１】
ネットワーク内の各ノードの評価値（ページランク値）の時間発展を計算するアルゴリズムとして、ページランクアルゴリズムがよく知られている。ページランクアルゴリズムは、一人のエージェントがネットワーク内のノード間をリンクを辿りながらランダムに歩き回るマルコフ連鎖ランダムウォークのアナロジーに基づいており、エージェントが存在する確率が高いノードほどページランク値が高くなる。ページランクアルゴリズムは、ノードｍ上のエージェントはノードｍから出る１以上のリンクを等確率で選択してリンク先のノードへと遷移すると仮定し、ノード群の評価値の時間発展を計算する。また、実際に得られる情報から各リンクの強さを求め、リンクの強さに応じてエージェントがそのリンクを選択する確率を決める方法も知られている。ページランクアルゴリズム等の従来手法でのノード評価値の時間発展の計算は、エージェントのノード間での遷移はリンクを通って行われることを前提としている。
【００３２】
これに対し、本実施形態の時間発展計算部１８で用いる計算ルールでは、ノード間のエージェントの遷移には、ネットワーク上のリンクを通る遷移の成分だけでなく、評価値が高いノードに対してリンクを通らずに直接ジャンプする遷移の成分も含まれ得るものと想定する。すなわち、ノードの評価値を第１成分と第２成分とに分け、第１成分はそのノードから出るリンクを通って他のノードに遷移し、第２成分はリンクと無関係に他のノードに遷移するものとする。第１成分のことを「リンク遷移成分」、第２成分のことを「非リンク遷移成分」と呼ぶ。ノードの評価値のうちリンク遷移成分はそのノードのリンク先のいずれかのノードにしか遷移できないが、非リンク遷移成分はそのノードのリンク先以外のノードにも遷移し得る。
【００３３】
また時間発展計算部１８の計算ルールでは、非リンク遷移成分は、評価値が高いノードに対して遷移しやすい（すなわち、より多くの量が遷移する）ようにする。例えば、あるノードの非リンク遷移成分が遷移する度合い（確率）が、遷移先のノードの評価値の増加に伴って単調増加するようにしてもよい。これを逆から見ると、ノードの評価値のうち他のノード群の非リンク遷移成分の（当該ノードへの）遷移に由来する部分は、当該ノードの評価値の増加に伴って単調に増加することになる。非リンク遷移成分をこのように定めることで、非リンク遷移成分は評価値の高いノードに集まりやすくなる。１つの例として、非リンク遷移成分の遷移先を、評価値があらかじめ定めた閾値以上であるノード群に限定してもよい。この例では、非リンク遷移成分は、評価値が閾値以下のノードには遷移しない。
【００３４】
また時間発展計算部１８の計算ルールでは、ノードの評価値に占めるリンク遷移成分の割合は、ノードの評価値の増加に伴って単調増加するものとする。この場合、非リンク遷移成分がノードの評価値に占める割合は、その評価値の増加に伴って単調減少することとなる。このようにすることで、評価値の低いノードの評価値は、リンクに沿って遷移する代わりに、評価値の高いノードに集まっていきやすい。その一方、評価値の高いノードの評価値は、リンクに沿って他のノードに遷移していく傾向が高い。したがって、ネットワーク内に評価値の高いノードがある程度集まってリンクで相互に接続されている部分があれば、時間発展を繰り返した場合でも、その部分のノードの間でリンクを介して評価値が巡っていくので、その部分のノードの評価値が全般的に高くなる。この「部分」が１つの「コミュニティ」を形成する。一方、ネットワーク内で評価値の高い他のノード群から離れた位置に評価値の高いノードが孤立していた場合、その評価値はリンクを介して他のノードに流出する一方、他のノードからそのノードへ流入する評価値は少ないので、時間発展の結果そのノードの評価値は低くなっていく。したがって、仮にクエリから求められた初期評価値が高いノードがあったとしても、他から孤立している場合には、そのノードはコミュニティのメンバとして抽出されにくい。
【００３５】
１つの例では、評価値がある閾値θ未満（あるいは以下）であるノードについては、リンク遷移成分を０とする。この例では、評価値がその閾値θ未満であるノードの評価値はすべて非リンク遷移成分として取り扱われ、上述したように、ネットワークのリンクとは無関係に、評価値の高いノードに対して優先的に遷移する。
【００３６】
遷移していく評価値成分の源泉は、初期評価値計算部１６がクエリに基づき求めた各ノードの初期評価値であり、初期評価値が高いノードの評価値は、主としてリンクを介してリンク先のノードに流出していく。しかし、初期評価値が高いノード群が密にリンクで接続されている部分（すなわち、コミュニティ）では、他の評価値の高いノードからのリンクを介して評価値成分が流入するので、その部分のノードの評価値は高く維持される。一方、その部分から外に向かうにつれてノードの評価値は下がっていき、非リンク遷移成分が優位になっていくので、評価値はリンク先に遷移するよりも、評価値が高いノードにいわば戻っていく部分が多くなる。特に、評価値が閾値θ未満のノードについてはリンク遷移成分を０とする方式では、その閾値未満のノードの評価値は、リンク経由でコミュニティの外側に流出することはなく、その全量が評価値が高いノード（ほとんどがコミュニティ内のノード）に移る。したがって、時間発展が進むと、コミュニティの内側のノード群の評価値は高く維持される一方、コミュニティの外側の実質上すべてのノードは評価値が０になっていく。したがって、時間発展が収束した後の最終的な評価値が０より大きいノードを抽出すれば、それら抽出したノードの集合が、当初のクエリに対応するコミュニティとなる。なお、ここで抽出の閾値に用いた０は、あくまで理想的な場合のものである。実際には、何らかの事情で収束後もコミュニティ外部のノードが正の小さい値の評価値を持つ場合もあり得るので、そのような外部ノードをコミュニティのメンバとして抽出しないよう、抽出の閾値を正の値（例えば上述の閾値θ）とする。
【００３７】
具体的な一例として、時間発展計算部１８は、次の式１〜３により各ノードｎの評価値ｐn（ｔ）の時間発展を計算する。
【数１】
0006572758.tif 000002
【００３８】
ここでｐn（ｔ）は、時刻ｔにノードｎが持つ評価値であり、ネットワーク全体でのノードｎの評価値の合計が１になるよう正規化済みの値である。すなわち、
【数２】
0006572758.tif 000003
である。またＮはネットワークの全ノードの数である。すなわち、ノードの識別番号であるｎは１〜Ｎの値をとる。またθは評価値ｐn（ｔ）に対して設定された閾値である。
【００３９】
式２で定義される関数ｆn（ｔ）は、ノードｎの評価値ｐn（ｔ）のうちのリンク遷移成分である。この例では、リンク遷移成分ｆn（ｔ）は、評価値ｐn（ｔ）が閾値θ未満であれば０であり、評価値ｐn（ｔ）が閾値θ以上であれば（ｐn（ｔ）−θ）である。この例における評価値ｐn（ｔ）に対するリンク遷移成分ｆn（ｔ）を示すグラフの例を図２に示す。図２では閾値θ＝０．１としているが、これは一例に過ぎない。
【００４０】
図２に示す太い実線のグラフが式２に従うリンク遷移成分ｆn（ｔ）を示している。破線のグラフは、参考のために、評価値ｐn（ｔ）の全部がリンク遷移成分ｆn（ｔ）である場合（すなわちｆn（ｔ）＝ｐn（ｔ））の場合のリンク遷移成分ｆn（ｔ）を示している。
【００４１】
また式３に示すように、関数Ｆ（ｔ）は、ネットワークの全ノードのリンク遷移成分ｆn（ｔ）の総和である。
【００４２】
式１の右辺第１項は、リンク遷移成分の遷移によりもたらされる評価値成分を示している。この成分は、時刻（ｔ−１）における各ノードｍのリンク遷移成分ｆm（ｔ−１）が、ネットワーク内のノード間の接続関係を示す遷移行列Ｔｎｍに従ってノードｎに遷移した場合の評価値の総和である。
【００４３】
また式１の右辺第２項は、非リンク遷移成分の遷移によりもたらされる評価値成分を示している。この成分について、以下に詳しく説明する。
【００４４】
ノードの評価値のうちの非リンク遷移成分は次式で表される。
【数３】
0006572758.tif 000004
【００４５】
非リンク遷移成分をネットワークの全ノードにわたって総和すると、次式に示すようになる。
【数４】
0006572758.tif 000005
【００４６】
これから分かるように、式１の右辺第２項に含まれる［１―Ｆ（ｔ−１）］は、時刻（ｔ−１）におけるネットワークの全ノードの非リンク遷移成分の総和である。そして、右辺第２項は、この総和に対し、注目するノードｎのリンク遷移成分ｆn（ｔ−１）のその総和に占める割合を乗じた値となっている。すなわち、右辺第２項は、全ノードの非リンク遷移成分の総和を、各ノードｎのリンク遷移成分の大きさに比例して分配したものである。したがってこの例では、評価値ｐn（ｔ）が高いノードほど、非リンク遷移成分に由来する評価値の分配を多く受けることになる。
【００４７】
式１では、説明を簡潔にするため、時間発展の１サイクルである単位時間の長さを１としている。１サイクルを他の長さとした場合にも、式１と同様の考え方で計算が可能である。
【００４８】
この例では、時間発展計算部１８は、初期評価値計算部１６が計算した各ノードｎの初期評価値の集合｛ｐn（０）｝（時刻ｔ＝０）を開始点として、上記式１の時間発展を繰り返し計算していく。開始点である初期評価値の集合｛ｐn（０）｝のことを、初期パタンと呼ぶ。時間発展計算部１８は、時刻ｔを単位時間１ずつ進めながら、この式１の計算を、評価値ｐn（ｔ）が収束するまで繰り返す。収束の判定は従来の方式で行えばよい。例えば、全ノードｎについて、ある時刻の評価値ｐn（ｔ）と前の時刻の評価値ｐn（ｔ−１）との差があらかじめ定めた閾値以下になった場合に、評価値ｐn（ｔ）が収束したと判定すればよい。
【００４９】
このようにして求められた収束後のノードｎの評価値ｐnsteadは、ネットワーク内のノード間の接続（リンク）関係の影響を織り込んだ上での、ユーザからのクエリに対するノードｎの適合度合いを表す。
【００５０】
コミュニティ抽出部２０は、時間発展計算部１８が求めた、収束後（すなわち定常状態）の評価値ｐnsteadから、クエリに適合したコミュニティ（ノードの集合）を抽出する。例えば、定常状態の評価値ｐnsteadがあらかじめ定めた閾値（０以上の値）より大きいノードｎを、コミュニティのメンバとして抽出する。またコミュニティ抽出部２０は、抽出したコミュニティのメンバーのリストを生成し、画面表示してもよい。また、このリストは、メンバーを最終的な評価値の順にソートしたものとしてもよい。
【００５１】
時間発展計算部１８の計算の結果求められる収束後のノードｎの評価値の集合｛ｐnstead｝は、ネットワークのノードｎの評価値の集合が取り得る状態の中でのアトラクタの１つである。初期パタン｛ｐn（０）｝を多少変化させても、時間発展計算により同じアトラクタに到達する。したがって、ユーザが初期パタンを厳密に特定しなくても、ある程度以上の精度で特定できていれば、時間発展計算で同じアトラクタに到達できる。
【００５２】
また、初期パタン｛ｐn（０）｝の中に、求めたいコミュニティの外に位置するが初期評価値は高いノードが含まれていたとしても、初期評価値の高いノードの大部分がそのコミュニティ内に含まれていれば、時間発展計算により、そのコミュニティ外のすべてのノードの評価値が０乃至小さい値となった同じアトラクタに到達することができる。例えば、図３の（ａ）に示すネットワーク１００において破線の円１１０の内部にあるノード１０２群が、求めたいコミュニティであるとする。ここで、（ａ）内の濃色の６個のノードが、ユーザが入力したクエリから求められた初期評価値が高いノードであったとする。この例では、初期評価値が高いノードのうちの多数はコミュニティ１１０内に含まれているが、いくつかはコミュニティ１１０の外部にある。これらコミュニティ１１０外の評価値の高いノードは、コミュニティ１１０にとって偽メンバーである。このような偽メンバーを含む初期パタンに対して時間発展計算部１８の繰り返し計算を適用すると、図３の（ｂ）に示すように、コミュニティ１１０の内部のノード１０２群が高い評価値（濃色で示す）となり、コミュニティ１１０の外部のノードは偽メンバーであったものも含めすべて、０乃至きわめて小さい評価値となる。すなわち、クエリから求めた初期パタンに多少の偽メンバーが含まれていても、時間発展計算部１８及びコミュニティ抽出部２０は、偽メンバーを含まない正しいコミュニティーを抽出する。
【００５３】
以上に説明したように、ユーザが最初に入力するクエリが、求めたいコミュニティをある程度正確に特定できていれば、求めたいコミュニティを抽出することができる。求めたいコミュニティの外に位置するが初期評価値は高いノードは、そのコミュニティから見れば偽メンバーであるといえるが、本実施形態の方法では、初期パタンに偽メンバーが含まれていたとしても、求めたいコミュニティを抽出できるのである。
【００５４】
以上に説明した実施形態をあくまで例示に過ぎず、本発明の範囲内で様々な変形が可能である。
【００５５】
例えば、上述の式２（図２も参照）に示したリンク遷移成分ｆn（ｔ）の定義式はあくまで一例に過ぎない。例えば、別の例として、評価値ｐn（ｔ）が閾値θ未満ではｆn（ｔ）＝０だが、θ以上ではｆn（ｔ）＝ｐn（ｔ）とする定義式を用いてもよい。この例は、評価値ｐn（ｔ）が閾値θ以上のノードについては、評価値ｐn（ｔ）のうちの全量がリンク遷移成分となり、非リンク遷移成分は０となる。この例のリンク遷移成分ｆn（ｔ）のグラフは図４に示す実線のグラフのようなものとなる。
【００５６】
また、図２（式２）と図４の例では、評価値ｐn（ｔ）が閾値θ未満の範囲については、リンク遷移成分ｆn（ｔ）は０であったが、これも一例に過ぎない。評価値ｐn（ｔ）内でリンク遷移成分ｆn（ｔ）の占める割合が評価値ｐn（ｔ）の増加に伴って単調増加するという条件を満たしていれば、評価値ｐn（ｔ）が０〜閾値θまでの範囲内のリンク遷移成分ｆn（ｔ）の値を０より大きい値（例えばｐn（ｔ）が０から増えるにつれてｆn（ｔ）が０から徐々に増えるなど）としてもよい。この条件が満たされれば、コミュニティ内のノードからコミュニティ外のノードへと流出しにくくなるので、時間発展によりコミュニティとその外部との評価値の差が明確になっていく。なお、リンク遷移成分ｆn（ｔ）は、評価値ｐn（ｔ）のうち、当該ノードｎから出るリンクに沿って遷移する成分の量を示すものであるから、評価値ｐn（ｔ）を上回る値となることはない。
【００５７】
また、以上の説明に現れる（ａ）リンク遷移成分が０である上限の評価値を示す閾値θ（図２参照）と、（ｂ）コミュニティとして抽出するノードが持つべき評価値の下限である閾値とは、同じ値でなくてもよい。
【００５８】
以上に例示した情報処理装置は、コンピュータにそれら各装置の機能を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）やＳＳＤ（ソリッドステートドライブ）等の固定記憶装置を制御するコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカルエリアネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ＨＤＤ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。
【符号の説明】
【００５９】
１０  ネットワーク情報記憶部、１２  ネットワーク情報取得部、１４  クエリ受付部、１６  初期評価値計算部、１８  時間発展計算部、２０  コミュニティ抽出部。
【図１】
0006572758.tif 000006
【図２】
0006572758.tif 000007
【図３】
0006572758.tif 000008
【図４】
0006572758.tif 000009