(57)【要約】【課題】ネットワーク構造からコミュニティ生成を行う際に、そのネットワーク構造において実際に形成されているコミュニティを生成し易くする。【解決手段】第１生成手段１１は、複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、ノードに付されたメタデータ及びリンクに付されたメタデータの少なくともいずれか一方を用いて、ノード間を結ぶサブリンクを生成する。算出手段１２は、複数のノードに含まれる一のノードが、ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間を前記サブリンクに沿って遷移する場合における第２の遷移確率を用いて算出する。第２生成手段１３は、算出手段１２により算出された分類割合から、前記ノードが属するコミュニティを生成する。【選択図】図１
2019159776.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、該ノードに付されたメタデータ及び該リンクに付されたメタデータの少なくともいずれか一方を用いて、前記ノード間を結ぶサブリンクを生成する第１生成手段と、
前記複数のノードに含まれる一のノードが、前記ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、前記ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間を前記サブリンクに沿って遷移する場合における第２の遷移確率を用いて算出する算出手段と、
前記算出された分類割合から、前記ノードが属するコミュニティを生成する第２生成手段と
を有する情報処理装置。
【請求項２】
前記一のノードから他のノードへの前記第１の遷移確率の総和が固定値である
請求項１に記載の情報処理装置。
【請求項３】
複数の前記ノードにおいて前記総和が共通の値である
請求項２に記載の情報処理装置。
【請求項４】
前記メタデータは種別毎に重みが設定され、
前記算出手段は、一のノードから前記サブリンクにより結ばれた他のノードに遷移する場合における該他のノードのそれぞれに遷移する確率として、該一のノードに付されたメタデータの各々に定められた重みの合計値に対する該メタデータの各々の重みの割合を算出し、該算出された割合を用いて前記分類割合を算出する
請求項２又は３に記載の情報処理装置。
【請求項５】
前記第１の遷移確率は、各ノードに付されたリンクの総数を用いた演算により前記ノード毎に算出され、
一のメタデータについての前記第２の遷移確率は、該メタデータが付されたノード間の遷移については共通の値が用いられ、該メタデータが付されていない場合はゼロとされる
請求項２乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
前記算出手段は、前記一のメタデータについての前記第２の遷移確率として、該メタデータが付されたノード間の遷移については、該メタデータが付されたノードの総数の逆数を算出する
請求項５に記載の情報処理装置。
【請求項７】
コンピュータに、
複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、該ノードに付されたメタデータ及び該リンクに付されたメタデータの少なくともいずれか一方を用いて、前記ノード間を結ぶサブリンクを生成するステップと、
前記複数のノードに含まれる一のノードが、前記ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、前記ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間を前記サブリンクに沿って遷移する場合における第２の遷移確率を用いて算出するステップと、
前記算出された分類割合から、前記ノードが属するコミュニティを検出するステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワークとして表現された複雑システムの分析に関する技術が提案されている。特許文献１及び２には、ネットワークからコミュニティを抽出する技術が記載されている。また、特許文献３には、ユーザがネットワーク内の単一のノードを種ノードとして特定できない場合でも、ユーザのクエリに対応するネットワーク内のコミュニティを抽出する技術として、ネットワーク情報に基づき各ノードの初期評価値を計算し、各ノードの評価値を第１成分と第２成分に分けて各ノードの評価値の時間発展を計算することが記載されている。また、特許文献４には、現実的な人脈情報を認識する技術として、予定表などのメタデータが有するデータの特性に応じて、人物同士の関連の強度に重み付けを行うことが記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特表２００８−５４５１７８号公報
【特許文献２】特開２００９−１７６０７２号公報
【特許文献３】特開２０１７−１０２７１２号公報
【特許文献４】特開２００７−１９３６８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、従来の技術では、ネットワーク構造から抽出（生成）されるコミュニティが、そのネットワークにおいて実際に形成されているコミュニティと必ずしも一致しない場合がある。
本発明は、ネットワーク構造からコミュニティ生成を行う際に、そのネットワーク構造において実際に形成されているコミュニティを、メタデータを用いない場合に比べて生成し易くすることを目的とする。
【課題を解決するための手段】
【０００５】
本発明の請求項１に係る情報処理装置は、複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、該ノードに付されたメタデータ及び該リンクに付されたメタデータの少なくともいずれか一方を用いて、前記ノード間を結ぶサブリンクを生成する第１生成手段と、前記複数のノードに含まれる一のノードが、前記ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、前記ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間を前記サブリンクに沿って遷移する場合における第２の遷移確率を用いて算出する算出手段と、前記算出された分類割合から、前記ノードが属するコミュニティを生成する第２生成手段とを有する。
【０００６】
本発明の請求項２に係る情報処理装置は、請求項１に記載の構成において、前記一のノードから他のノードへの前記第１の遷移確率の総和が固定値であることを特徴とする。
【０００７】
本発明の請求項３に係る情報処理装置は、請求項２に記載の構成において、複数の前記ノードにおいて前記総和が共通の値であることを特徴とする。
【０００８】
本発明の請求項４に係る情報処理装置は、請求項２又は３に記載の構成において、前記メタデータは種別毎に重みが設定され、前記算出手段は、一のノードから前記サブリンクにより結ばれた他のノードに遷移する場合における該他のノードのそれぞれに遷移する確率として、該一のノードに付されたメタデータの各々に定められた重みの合計値に対する該メタデータの各々の重みの割合を算出し、該算出された割合を用いて前記分類割合を算出する。
【０００９】
本発明の請求項５に係る情報処理装置は、請求項２乃至４のいずれか１項に記載の構成において、前記第１の遷移確率は、各ノードに付されたリンクの総数を用いた演算により前記ノード毎に算出され、一のメタデータについての前記第２の遷移確率は、該メタデータが付されたノード間の遷移については共通の値が用いられ、該メタデータが付されていない場合はゼロとされることを特徴とする。
【００１０】
本発明の請求項６に係る情報処理装置は、請求項５に記載の構成において、前記算出手段は、前記一のメタデータについての前記第２の遷移確率として、該メタデータが付されたノード間の遷移については、該メタデータが付されたノードの総数の逆数を算出することを特徴とする。
【００１１】
本発明の請求項７に係るプログラムは、コンピュータに、複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、該ノードに付されたメタデータ及び該リンクに付されたメタデータの少なくともいずれか一方を用いて、前記ノード間を結ぶサブリンクを生成するステップと、前記複数のノードに含まれる一のノードが、前記ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、前記ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間を前記サブリンクに沿って遷移する場合における第２の遷移確率を用いて算出するステップと、前記算出された分類割合から、前記ノードが属するコミュニティを検出するステップとを実行させるためのプログラムであることを特徴とする。
【発明の効果】
【００１２】
請求項１及び７に係る発明によれば、ネットワーク構造からコミュニティ検出を行う際に、そのネットワーク構造において実際に形成されているコミュニティを、メタデータを用いない場合に比べて検出し易い。
請求項２に係る発明によれば、第１の遷移確率の総和を固定値としない場合に比べて計算量を少なくすることができる。
請求項３に係る発明によれば、第１の遷移確率の総和が複数のノードにおいて共通の値でない場合に比べて、計算量を少なくすることができる。
請求項４に係る発明によれば、一のノードからサブリンクにより結ばれた他のノードに遷移する確率を、各メタデータに設定された重みを用いて算出しない場合に比べて、計算量を少なくすることができる。
請求項５に係る発明によれば、第２の遷移確率を用いた分類割合の計算に要する計算量を少なくすることができる。
請求項６に係る発明によれば、第２の遷移確率を用いた分類割合の計算に要する計算量を少なくすることができる。
【図面の簡単な説明】
【００１３】
【図１】情報処理装置の機能構成を例示する図
【図２】ネットワーク情報の内容を例示する図
【図３】情報処理装置のハードウェア構成を例示する図
【図４】情報処理装置１０が行う処理の流れを例示するフローチャート
【図５】サブリンクの内容を例示する図
【図６】確率ρを説明するための図
【図７】サブリンクについての計算量を説明するための図
【図８】従来の技術において検出されるコミュニティを例示する図
【発明を実施するための形態】
【００１４】
［１］構成
図１は、本実施形態に係る情報処理装置１０の構成を例示するブロック図である。情報処理装置１０は、ネットワークにおいてコミュニティ分解を行う。ここでネットワークとは、複数のノード及びリンクの集合をいい、特に通信ネットワークに限定されない。リンクは、これら複数のノードのうち少なくとも一部のノードについて、ノード間を結ぶものである。ノードは、コンピュータ装置上のソフトウェア、コンピュータ装置、通信装置、又は仮想的なエンティティである。リンクは、通信ネットワークの伝送路、又は２つ以上のノードの関連性を示すデータである。この実施形態において、ネットワークは例えば、複数のＷｅｂページ（ノード）とＷｅｂページ間のリンクとを含むインターネット、ソーシャルネットワーク、複数の文書（ノード）間の引用関係を示すネットワーク、複数の企業間の取引関係を示すネットワーク、ユーザによる購買履歴のネットワーク、交通網、遺伝子制御・タンパク相互作用ネットワークである。
【００１５】
コミュニティは１又は複数のノードの集合である。コミュニティは、ネットワーク中のノード同士のつながりがより密であり、その中のノードとその外のノードとのつながりがより疎である部分である。すなわち、コミュニティは、ネットワークにおいてノードが密につながったかたまりを表す。ひとつのノードは１又は複数のコミュニティに属する。
【００１６】
個々のコミュニティには、何らかの意味が付随する。例えば、ＷＷＷにおいて、関連するトピックを扱うＷｅｂページは、相互にリンクが貼られている場合が多いので、コミュニティを形成する。すなわち、複数のＷｅｂページ（ノード）とＷｅｂページ間に貼られたリンクとを含むネットワークにおいて、共通のトピックが扱われたＷｅｂページの集合がコミュニティの一例である。また、ソーシャルネットワークにおいては、共通する活動に携わる人々、あるいは、学校の同期などがコミュニティを形成する。すなわち、複数のユーザ情報（ノード）とユーザ同士の繋がり関係を示すリンクとを含むネットワークにおいて、学校の同級生が集められたグループがコミュニティの一例である。また、例えば、複数のユーザ情報（ノード）とユーザ同士の繋がり関係を示すリンクとを含むネットワークにおいて、共通の購買傾向を有するユーザの集合がコミュニティの一例である。
【００１７】
図２はネットワークを表すネットワーク情報の内容を例示する図である。ネットワーク情報は、複数のノード及び複数のノードを結ぶ複数のリンクを含む。ネットワーク情報は、例えば相互参照を含むＨＴＭＬデータ、組織の所属関係のデータ、友人関係のデータである。図２に例示されるネットワーク情報Ｎ１は、１５個のノードと２２個のリンクとの情報を含む。各ノードには、１から１５までのノード番号が付与されている。例えば、ノード番号が「１」であるノード（以下、ノード［１］と表す）は、ノード［２］及びノード［４］のノードとのリンクを有する。なお、ネットワーク情報に含まれるノード数及びリンク数はこれより多くてもよく、例えばノードの数は１０万程度であってもよい。
【００１８】
ネットワークに含まれるノード及び／又はリンクには、１又は複数のメタデータが付されている。メタデータは、ネットワークの構造とは別にノード又はリンクに付されたデータであり、ノード又はリンクについての付加的なデータである。メタデータは例えば、ユーザを示すノードに付された、性別、年齢、出身校、社名、又は勤務地を示すデータである。ひとつのノード又はリンクに付されているメタデータは、１つであってもよく、複数であってもよい。例えば、ひとりのユーザ（ノード）に、「ｂ大学出身」を示すメタデータと、「Ｃ社勤務」というメタデータとが付されていてもよい。また、ネットワークに含まれる一部のノード（リンク）にメタデータが付されていてもよく、全部のノード（リンク）にメタデータが付されていてもよい。
【００１９】
図１の説明に戻る。情報処理装置１０は、第１生成手段１１、算出手段１２及び第２生成手段１３を有する。第１生成手段１１は、複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、ノードに付されたメタデータ及びリンクに付されたメタデータの少なくともいずれか一方を用いて、ノード間を結ぶサブリンクを示すデータを生成する。サブリンクとは、共通するメタデータが付されているノード間を結ぶものである。リンクがネットワークにもともと含まれているのに対し、サブリンクはネットワークに含まれているものではなく、情報処理装置１０により生成される。第１生成手段１１により行われるサブリンクを生成する処理には、元々あるリンクの一部を何らかの条件（メタデータ等）で選択する処理が含まれる。この場合、選択されたリンクがサブリンクとなる。
【００２０】
算出手段１２は、複数のノードに含まれる一のノードが、ネットワークに含まれる複数のコミュニティのそれぞれに分類される分類割合を、ノード間を前記リンクに沿って遷移する場合における第１の遷移確率、及び前記のノード間をサブリンクに沿って遷移する場合における第２の遷移確率を用いて算出する。この実施形態では、リンクとサブリンクは区別され、リンクに沿って遷移する場合における第１の遷移確率と、サブリンクに沿って遷移する場合における第２の遷移確率とがそれぞれ算出される。第２生成手段１３は、算出手段１２により算出された分類割合から、前記ノードが属するコミュニティを生成する。
【００２１】
図３は情報処理装置１０のハードウェア構成を例示する図である。図において、メモリ１５１は各種データを記憶する。プロセッサ１５２はメモリ１５１に記憶されているプログラムに従いデータ処理を行う。通信ＩＦ１５３は外部の装置と有線または無線によりデータ通信を行うインターフェイスである。ＵＩ部１５４は例えばタッチスクリーンとキーとを備える。
【００２２】
この例で、メモリ１５１に記憶されているプログラムをプロセッサ１５２が実行することにより、図１に示される情報処理装置１０の機能が実行される。プログラムを実行しているプロセッサ１５２は、第１生成手段１１、算出手段１２及び第２生成手段１３の一例である。
【００２３】
［２］動作
図４は情報処理装置１０が行う、ネットワーク情報からコミュニティを生成する処理の流れを例示するフローチャートである。この実施形態では、ネットワークに含まれるＮ個のノードを、Ｋ個以下の複数のコミュニティに分類する。ここで、Ｎ及びＫは正の整数である。この分類処理においては、１つのノードが複数のコミュニティに分類される場合もある。
【００２４】
ステップＳ１０１において、情報処理装置１０は、ネットワークに含まれるノードに付されたメタデータを用いて、ノード間を結ぶサブリンクを生成する。この実施形態では、共通のメタデータが付されているノード同士がサブリンクで結ばれる。例えば、情報処理装置１０は、対象となるノードを特定し、対象ノードに付されたメタデータに含まれる項目のうち対象となる項目を特定し、対象ノード以外のノードのメタデータを対象として、対象項目に対象値が含まれるノードを特定する。情報処理装置１０は、こうして特定されたノードと対象ノードとの間にサブリンクを設定する。このサブリンクには、メタデータとして対象値が記録される。
【００２５】
図５は生成されるサブリンクの内容を例示する図である。図５の例では、メタデータａ、メタデータｂ、メタデータｃの３種類のメタデータがノードに付されており、共通のメタデータが付されているノード同士がサブリンクで結ばれる。メタデータａに対応するサブリンクはサブリンクＬａであり、メタデータｂに対応するサブリンクはサブリンクＬｂであり、メタデータｃに対応するサブリンクはサブリンクＬｃである。サブリンクＬａは対象値「ａ大出身」に相当するサブリンクであり、サブリンクＬｂは対象値「ｂ大出身」に相当するサブリンクであり、サブリンクＬｃは対象値「ｃ社社員」に相当するサブリンクである。
【００２６】
図４の説明に戻る。ステップＳ１０２において、情報処理装置１０は、メタデータｂに対して、重みμ（ｂ）を定める。重みμ（ｂ）は、メタデータｂをどれくらい重視するかを示す値である。この実施形態では、重みμ（ｂ）はユーザにより設定される。すなわち、ユーザがＵＩ部１５４を用いて重みμ（ｂ）の値をメタデータｂの種別毎に設定する。
【００２７】
ステップＳ１０３及びステップＳ１０４において、ノード間をリンクに沿ってランダムに遷移する場合における遷移確率を表す行列Ｔと、ノード間をサブリンクに沿ってランダムに遷移する場合における遷移確率を表す行列ＴＭ（ｂ）とを、別々に生成する。
【００２８】
まず、ステップＳ１０３において、情報処理装置１０は、ノード間をリンクに沿ってランダムに遷移する場合における遷移確率を表す行列Ｔを生成する。例えば、図２の例において、ノード［１］を起点としてリンクに沿ってランダムに他のノードに遷移する場合、１／２の確率でノード［２］に遷移し、１／２の確率でノード［４］に遷移する。これらの遷移確率をまとめて表したものが、行列Ｔの第１列である。他の行列要素についても同様に構成されている。一般に、ノード［ｎ］とノード［ｍ］とがリンクで接続されている場合にＡｎｍ＝１、ノード［ｎ］とノード［ｍ］とがリンクで接続されていない場合にＡｎｍ＝０となる隣接行列Ａを用いて、ノードの総数をＮとする場合に、行列Ｔは以下の数式（１）で定義される。数式（１）に含まれる数式（２）はリンクの総数である。
【数１】
2019159776.tif 000003
【数２】
2019159776.tif 000004
【００２９】
次いで、ステップＳ１０４において、情報処理装置１０は、ノード間をサブリンクに沿ってランダムに遷移する場合における遷移確率を表す行列ＴＭ（ｂ）を生成する。行列ＴＭ（ｂ）は隣接行列Ａ（ｂ）を用いて生成される。隣接行列Ａ（ｂ）と行列ＴＭ（ｂ）とは、以下の数式（３）で定義される。
【数３】
2019159776.tif 000005
【００３０】
2019159776.tif 000006
【００３１】
数式（１）に示されるように、リンクに沿って遷移する遷移確率は、各ノードに付されたリンクの総数（数式（２））を用いた演算により、ノード毎に異なる値が算出される。一方、数式（３）に示されるように、メタデータに対応するサブリンクに沿って遷移する遷移確率は、そのメタデータが付されたノード間の遷移については共通の値が用いられ、そのメタデータが付されていない場合はゼロとされる。また、この実施形態では、そのメタデータについての遷移確率として、メタデータが付されたノード間の遷移については、メタデータが付されたノードの総数の逆数が算出される。
【００３２】
次いで、ステップＳ１０５において、情報処理装置１０は、ネットワーク情報が表すネットワークのノード間をリンクに沿ってランダムに遷移する場合における定常確率分布ｐst（ｎ）を算出する。定常確率分布ｐst（ｎ）は、ノード間をリンクに沿ってランダムに遷移する場合における遷移確率を表す行列Ｔを用いて算出される。
【００３３】
定常確率分布ｐst（ｎ）は、以下の数式（４）で求められる連立Ｎ方程式を解くことにより求められる。定常確率分布ｐst（ｎ）は、行列Ｔの固有ベクトルであって、固定値が１のものである。
【数４】
2019159776.tif 000007
【００３４】
2019159776.tif 000008
【００３５】
2019159776.tif 000009
【数５】
2019159776.tif 000010
【００３６】
2019159776.tif 000011
【００３７】
2019159776.tif 000012
【数６】
2019159776.tif 000013
【００３８】
ステップＳ１０９において、情報処理装置１０は、ｐｔ−１（ｎ｜ｋ）＝ｐｔ（ｎ｜ｋ）とし、πｋold=πｋnew とする置き換えを行う。
【００３９】
ステップＳ１１０において、情報処理装置１０は、第ｔ回目の逐次計算による分類割合ｐｔ（ｎ｜ｋ）を算出する。ここで、ｔは逐次計算の回数を表す正の整数である。ｐｔ（ｎ｜ｋ）は、１つ前の逐次計算により得られるｐｔ−１（ｎ｜ｋ）、πｋ、及び割合（数式（５））を用いて算出される。例えば、第１回目の逐次計算では、ｐ０（ｎ｜ｋ）、πｋ、及び割合（数式（５））を用いてｐ１（ｎ｜ｋ）が算出される。
【００４０】
情報処理装置１０は、以下の数式（７）で定められる関係により第ｔ回目の逐次計算による分類割合ｐｔ（ｎ｜ｋ）を算出する。また、数式（７）の一部は、数式（８）で定められる関係により算出される。
【数７】
2019159776.tif 000014
【数８】
2019159776.tif 000015
【００４１】
数式（７）において、αは正の実数である。確率ρは一のノードからネットワークのリンクに沿って他のノードに進む遷移確率の総和であり、サブリンクに沿って進む確率の総和が（１−ρ）である。この確率ρは固定値である。すなわち、この実施形態では、ひとつのノードからリンクに沿って他のノードに進む遷移確率の総和（確率ρ）が固定値であるとともに、ひとつのノードからサブリンクに沿って他のノードに進む遷移確率の総和（確率（１−ρ））も固定値である。また、この実施形態では、ネットワークに含まれる全てのノードにおいて、確率ρは同じ値が用いられる。すなわち、ネットワークに含まれる複数のノードにおいて、総和（確率ρ）は共通の値が用いられる。
【００４２】
また、サブリンクに沿って進む確率（１−ρ）のうち、メタデータｂに付随するサブリンクに沿って進む確率は、以下の数式（９）で定められる。
【数９】
2019159776.tif 000016
【００４３】
数式（９）において、数式（１０）はノード［ｎ］に付されたメタデータの集合を表し、数式（１１）は、ノード［ｎ］に付されたメタデータについて行われる足し算を示す。
【数１０】
2019159776.tif 000017
【数１１】
2019159776.tif 000018
【００４４】
すなわち、この実施形態では、メタデータは種別毎に重みが設定され、情報処理装置１０は、一のノードからサブリンクにより結ばれた他のノードに遷移する場合における他のノードのそれぞれに遷移する確率として、一のノードに付されたメタデータの各々に定められた重みの合計値に対するメタデータの各々の重みの割合を算出し、算出された割合を用いて分類割合を算出する。
【００４５】
図６は確率ρについての具体例を示す図である。図６は、ひとつのノードに３本のリンク、メタデータａに対応する１本のサブリンク、及び、メタデータｂに対応する１本のサブリンクが貼られている場合が例示されている。この実施形態では、確率ρで３本のリンクに沿って進み、確率（１−ρ）で２本のサブリンクに沿って進むと決められる。更に、２本のサブリンクに進む確率のうち、サブリンクＬａに進む確率はμ（ａ）／μ（ａ）＋μ（ｂ）であり、サブリンクＬｂに進む確率はμ（ｂ）／μ（ａ）＋μ（ｂ）である。
【００４６】
すなわち、ランダムウォーカーがネットワークのリンクに沿って進むかサブリンクに沿って進むかを選ぶ確率ρ及び確率（１−ρ）は、ノードの個性（そのノードにリンクが何本付随するか、サブリンクが何本付随するか）に依存しない。
【００４７】
図４の説明に戻る。ステップＳ１１１において、情報処理装置１０は、ネットワークのコミュニティ［ｋ］の重要度πｋを算出する。重要度πｋは、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合（数式（５））が大きいほど大きな値となるように算出される。この実施形態では、以下の数式（１２）によりコミュニティ［ｋ］の重要度πｋが算出される。
【数１２】
2019159776.tif 000019
【００４８】
ステップＳ１１２において、情報処理装置１０はカウンタｇをインクリメントする。ステップＳ１１３において、情報処理装置１０は、カウンタｇの値が予め定められた定数Ｇと等しい場合（ステップＳ１１３；ＹＥＳ）、ステップＳ１１４の処理に進む。一方、カウンタｇの値が定数Ｇと等しくない場合（ステップＳ１１３；ＮＯ）、情報処理装置１０はステップＳ１０８の処理に戻る。
【００４９】
ステップＳ１１４において、情報処理装置１０は、算出された分類割合ｐ（ｎ｜ｋ）から、ノード［ｎ］が属する１以上のコミュニティを生成する。ノード［ｎ］がコミュニティ［ｋ］に属する割合は、分類割合ｐ（ｎ｜ｋ）の値により定められる。また、情報処理装置１０は、分類割合ｐ（ｎ｜ｋ）及び重要度πｋから算出される帰属度ｑ（ｋ｜ｎ）に基づき、ノード［ｎ］が属するコミュニティを生成してもよい。帰属度ｑ（ｋ｜ｎ）は数式（１３）により求められる。
【数１３】
2019159776.tif 000020
【００５０】
ところで、ネットワークのコミュニティ構造がわかることは、そのネットワークで表現された複雑システムの理解と活用を大いに助けることになる。例えば、あるコミュニティのメンバーに絞った効率的な商品宣伝などが可能になる。しかしながら、複雑システムをネットワークで表現する場合に、調査や観測の不正確さやノイズにより、しばしばノードやリンクに欠損や間違いが起こる場合がある。例えば、ソーシャルネットワークの表現において、本来はいるべき人（ノード）がいない、二人は知り合いなのにリンクがない、あるいは逆に、知り合いではないのにリンクがある、などということが起こる。
【００５１】
ノードやリンクに欠損や間違いがある場合、従来の方法のようにネットワーク構造だけに基づくならば、コミュニティ抽出が数学的な意味で正しく行われたとしても、抽出されたコミュニティは、本来抽出されるべき意味（本来のグルーピング）を正しく反映していないおそれがある。
【００５２】
図８は従来の技術において検出されるコミュニティを例示する図である。図の例では、コミュニティ検出処理により検出されたコミュニティＣ１、Ｃ２及びＣ３と、本来のグルーピングであるコミュニティＣ１１、Ｃ１２及びＣ１３とにずれが生じている。
【００５３】
それに対しこの実施形態では、メタデータをコミュニティ検出に利用することにより、本来のグルーピングを反映したコミュニティ検出が行われ易く、コミュニティ生成の精度が向上する。また、ネットワーク分析において、計算量は一般にリンクの数にスケールするため、リンクの数が多くなるほど計算量は膨大になってしまう。そのため、メタデータで（サブリンクではなく）リンクを生成すると計算量が膨大になってしまう場合がある。それに対しこの実施形態では、サブリンクについては逐次計算を行わない。すなわち、情報処理装置１０は、リンクとは別のサブリンクを生成し、リンクについての演算とは別の演算で、サブリンクについての演算（サブリンクの数が多くても計算量が増えない演算）を行い、コミュニティを生成する。そのため、メタデータの数が多い場合でも計算量が膨大になってしまうことが抑制される。
【００５４】
また、この実施形態では、ランダムウォーカーがネットワークのリンクに沿って進むかサブリンクに沿って進むかを選ぶ確率（１−ρ）は、ノードの個性（そのノードにリンクが何本付随するか、サブリンクが何本付随するか）に依存しない。そのため、ひとつのノードで計算した結果が全てのノードで再利用される。すなわち、ノードの数が多い場合であっても計算量が大きくなることが抑制される。具体的には、上述の数式（７）において、以下の数式（１４）による計算を１回だけ計算すればよく、ノード［ｎ］毎に計算する必要がない。
【数１４】
2019159776.tif 000021
【００５５】
図７はサブリンクについての計算量を説明するための図である。ネットワークに含まれる全てのノードにおいて、サブリンクからの合計入力はノードに付されたサブリンクの数に依存しない。すなわち、ネットワークに含まれる全てのノードにおいて、サブリンクからの合計入力は、数式（１４）により算出される値となる。
【００５６】
［３］変形例
上述した実施形態は、本発明の実施の一例に過ぎず、以下のように変形させてもよい。また、上述した実施形態及び以下に示す各変形例は、必要に応じて組み合わせて実施されてもよい。
【００５７】
（１）上述の実施形態では、メタデータがノードに付されている場合の処理の流れを例示したが、メタデータがリンクに付されているネットワーク構造であってもよく、また、ノードとリンクの両方にメタデータが付されていてもよい。この場合、情報処理装置１０は、複数のノードとノード間を結ぶリンクとを含むネットワークにおいて、ノードに付されたメタデータ及びリンクに付されたメタデータの少なくともいずれか一方を用いて、ノード間を結ぶサブリンクを生成する。メタデータがリンクに付されている場合、情報処理装置１０は、隣接行列Ａ（ｂ）を次の数式（１５）で定め、この隣接行列Ａ（ｂ）を用いて遷移確率行列を定める。
【数１５】
2019159776.tif 000022
【００５８】
（２）上述の実施形態では、メタデータの種別毎にユーザが重みを設定したが、重みの設定方法は上述した実施形態で示したものに限られない。例えば、情報処理装置１０が予め定められたアルゴリズムに従ってメタデータの種別毎の重み値を設定してもよい。また、全てのメタデータについて共通する値が重み値として設定されてもよい。
【００５９】
（３）上述の実施形態では、情報処理装置１０は、共通のメタデータが付されているノード同士を結ぶサブリンクを示すデータを生成した（図４のステップＳ１０１）。この処理に代えて、情報処理装置１０は、ネットワークに含まれるリンクの一部を、予め定められた条件に従って選択してもよい。この場合、選択されたリンクがサブリンクとして扱われ、選択されていないリンクがリンクとして扱われる。
【００６０】
（４）上述の実施形態では、解析対象であるネットワークにおいてノード間を結ぶリンクは方向を有しないが、ネットワークに含まれるリンクが一方通行であってもよい。
【００６１】
（５）上述した実施形態において、情報処理装置１０のプロセッサ１５２により実行されるプログラムは、インターネットなどの通信回線を介してダウンロードされてもよい。また、これらのプログラムは、磁気記録媒体（磁気テープ、磁気ディスクなど）、光記録媒体（光ディスクなど）、光磁気記録媒体、半導体メモリなどの、コンピュータが読取可能な記録媒体に記録した状態で提供されてもよい。
【符号の説明】
【００６２】
１０…情報処理装置、１１…第１生成手段、１２…算出手段、１３…第２生成手段、１５１…メモリ、１５２…プロセッサ、１５３…通信ＩＦ、１５４…ＵＩ部。
【図１】
2019159776.tif 000023
【図２】
2019159776.tif 000024
【図３】
2019159776.tif 000025
【図４】
2019159776.tif 000026
【図５】
2019159776.tif 000027
【図６】
2019159776.tif 000028
【図７】
2019159776.tif 000029
【図８】
2019159776.tif 000030