(57)【要約】【課題】個人ウェブサイト間のハイパーリンクに基づいて生成される管理者のコンタクトネットワークにおいて、欠損したリンクを精度良く補完できるリンク補完装置、リンク補完方法及びリンク補完プログラムを提供すること。【解決手段】リンク補完装置１は、複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶するサイト管理ＤＢ２２と、リンク情報に基づいて管理者をノードとする無向グラフを生成するグラフ生成部１１と、生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類するタイプ分類部１２と、タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完するリンク補完部１３と、を備える。【選択図】図４
2015191439.tif 000002
【特許請求の範囲】
【請求項１】
複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部と、
前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成部と、
前記生成部により生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類部と、
前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完部と、を備えるリンク補完装置。
【請求項２】
前記分類部は、前記直接リンクがないノードのペアを、当該ノード間のホップ数、及び共通の隣接ノードの数に基づいて、複数のタイプに分類する請求項１に記載のリンク補完装置。
【請求項３】
前記生成部は、リンク元の個人ウェブサイトが所定のタイプでないリンク情報を除外して、前記無向グラフを生成する請求項１又は請求項２に記載のリンク補完装置。
【請求項４】
前記生成部は、ノード間のハイパーリンクの方向又は数に基づいて、前記無向グラフにおける当該ノード間のリンクの有無を決定する請求項１から請求項３のいずれかに記載のリンク補完装置。
【請求項５】
前記記憶部は、個人属性情報を更に記憶し、
前記生成部は、指定された前記個人属性情報の条件に基づいて、前記管理者及び前記リンク情報を抽出する請求項１から請求項４のいずれかに記載のリンク補完装置。
【請求項６】
複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部を参照し、前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成ステップと、
前記生成ステップにおいて生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類ステップと、
前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完ステップと、をコンピュータが実行するリンク補完方法。
【請求項７】
複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部を参照し、前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成ステップと、
前記生成ステップにおいて生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類ステップと、
前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完ステップと、をコンピュータに実行させるためのリンク補完プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンタクトネットワークにおけるリンクを補完する装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、インターネット上で公開されているウェブサイトの中には、オフラインの個人に紐づいた１又は複数のオンラインの個人により管理される個人ウェブサイトが存在する。
ここで、オフラインの個人とは、ネットワーク（インターネット）を利用する現実のユーザそれぞれをいい、ネットワーク上で１又は複数の人格を持つ。ネットワーク上の人格をここではオンラインの個人と呼び、オフラインの個人とオンラインの個人とは、１対１又は１対多の関係にある。オフラインの個人はオンラインの個人を介し１又は複数のサービスプロバイダそれぞれに対してアカウントを作成して、１つ以上の個人ウェブサイトを管理している。
近年、特に中学生や高校生の間では、各人が複数のオンラインの個人を持ち、それぞれのオンラインの個人で複数の個人ウェブサイトを作成し、自身のサイト間のみならず、他者とのサイト間で互いにハイパーリンクを設け、情報やメッセージの公開及び交換を行うことが多い。
【０００３】
これらの個人ウェブサイト間のハイパーリンクに基づいて、管理者であるオンラインの個人をノードとする友達関係の無向グラフ（コンタクトネットワーク）を生成すると、現実世界の管理者の仲間集団は、コンタクトネットワーク上のクリークとして現れることが多い。
したがって、このクリークを検出することにより、現実世界で形成されている仲間集団を推測できる。
【０００４】
ところが、ハイパーリンクの観測漏れやパスワードによる秘匿等によって、収集された個人ウェブサイト間のハイパーリンクの一部が欠損している場合、実際にはあるはずのクリークが見逃されてしまう。
非特許文献１には、ノード間のリンク距離（ホップ数）毎にリンクの有無を機械学習して予測する方法が示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｒ．Ｎ．  Ｌｉｃｈｔｅｎｗａｌｔｅｒ，  Ｊ．Ｔ．  Ｌｕｓｓｉｅｒ  ａｎｄ  Ｎ．Ｖ．  Ｃｈａｗｌａ，  “Ｎｅｗ  Ｐｅｒｓｐｅｃｔｉｖｅｓ  ａｎｄ  Ｍｅｔｈｏｄｓ  ｉｎ  Ｌｉｎｋ  Ｐｒｅｄｉｃｔｉｏｎ，”  ＫＤＤ２０１０，  ｐｐ．  ２４３−２５２，  ２０１０．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１の方法は、スケールフリーのネットワークを想定しているため、現実世界の人間関係が強く反映された個人ウェブサイトの特殊なネットワークでは、リンク予測の精度が十分ではなかった。
【０００７】
本発明は、個人ウェブサイト間のハイパーリンクに基づいて生成される管理者のコンタクトネットワークにおいて、欠損したリンクを精度良く補完できるリンク補完装置、リンク補完方法及びリンク補完プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係るリンク補完装置は、複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部と、前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成部と、前記生成部により生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類部と、前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完部と、を備える。
【０００９】
前記分類部は、前記直接リンクがないノードのペアを、当該ノード間のホップ数、及び共通の隣接ノードの数に基づいて、複数のタイプに分類してもよい。
【００１０】
前記生成部は、リンク元の個人ウェブサイトが所定のタイプでないリンク情報を除外して、前記無向グラフを生成してもよい。
【００１１】
前記生成部は、ノード間のハイパーリンクの方向又は数に基づいて、前記無向グラフにおける当該ノード間のリンクの有無を決定してもよい。
【００１２】
前記記憶部は、個人属性情報を更に記憶し、前記生成部は、指定された前記個人属性情報の条件に基づいて、前記管理者及び前記リンク情報を抽出してもよい。
【００１３】
本発明に係るリンク補完方法は、複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部を参照し、前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成ステップと、前記生成ステップにおいて生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類ステップと、前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完ステップと、をコンピュータが実行する。
【００１４】
本発明に係るリンク補完プログラムは、複数の個人ウェブサイトの管理者のＩＤ、及び当該複数の個人ウェブサイト間におけるハイパーリンクによる隣接関係を示したリンク情報を記憶する記憶部を参照し、前記リンク情報に基づいて、前記管理者をノードとする無向グラフを生成する生成ステップと、前記生成ステップにおいて生成されたグラフの中で、直接リンクがないノードのペアを、共通の隣接ノードの数に基づいて、複数のタイプに分類する分類ステップと、前記タイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する補完ステップと、をコンピュータに実行させる。
【発明の効果】
【００１５】
本発明によれば、個人ウェブサイト間のハイパーリンクに基づいて生成される管理者のコンタクトネットワークにおいて、欠損したリンクを精度良く補完できる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る個人ウェブサイトと、その管理者との関係を示す図である。
【図２】実施形態に係るサービスプロバイダ、アカウント及び個人ウェブサイトの関係を示す図である。
【図３】実施形態に係るオンラインＩＤが割り当てられた結果を示す概要図である。
【図４】実施形態に係るリンク補完装置の機能構成を示すブロック図である。
【図５】実施形態に係る収集履歴管理テーブルを示す図である。
【図６】実施形態に係るサイト間リレーションテーブルを示す図である。
【図７】実施形態に係る個人属性テーブルを示す図である。
【図８】実施形態に係るノードペアの分類例を示す図である。
【図９】実施形態に係るグラフ生成処理を示すフローチャートである。
【図１０】実施形態に係るリンク補完処理を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について説明する。
本実施形態に係るリンク補完装置１は、オンラインの個人が管理する個人ウェブサイト間のハイパーリンクに基づいて、オンラインの個人をノードとするコンタクトネットワークを生成すると共に、欠損したリンクを補間する装置である。なお、リンク補完装置１は、サーバ装置やＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）等、様々な情報処理装置（コンピュータ）であってよい。
【００１８】
図１は、本実施形態に係る個人ウェブサイトと、その管理者との関係を示す図である。
現実の人物であるオフラインの個人は、ネットワーク（インターネット）上で、１又は複数のオンラインの個人を管理している。また、オンラインの個人は、１又は複数のサービスプロバイダそれぞれに対してアカウントを作成して、１つ以上の個人ウェブサイトを管理している。以下、単に管理者という場合は、オンラインの個人を指す。
【００１９】
各オンラインの個人は、例えば、同じ学校の生徒であったり、同じ趣味を持つグループの一員であったり、オンラインの他者と一定の人間関係を持っている。そのため、複数のオンラインの個人がそれぞれ管理している個人ウェブサイトの間は、ハイパーリンクで参照されていることも多い。
【００２０】
ここで、個人ウェブサイトとは、オンラインの個人又は複数の個人が、自身に関する情報を公開したり、オンラインの他者とメッセージを交換したりするためのウェブサイトをいう。個人ウェブサイトは、サービスプロバイダから機能又はサービス毎に、アカウントを作成したオンラインの個人毎に提供されるＨＴＭＬファイルの集合体である。
例えば、以下のタイプの個人ウェブサイトがそれぞれ複数のサービスプロバイダにより提供されている。
【００２１】
プロフ（プロフィール）・・・個人のプロフィールを公開できるウェブサイト
ゲスブ（ゲストブック）・・・訪問者が履歴としてコメントを投稿できるウェブサイト
リアル（リアルタイム）・・・個人の現況を短い文章で投稿できるウェブサイト
ブログ・・・日々の記録を公開できるウェブサイト
マイリンク・・・他者の個人ウェブサイトへのリンクを公開できるウェブサイト
ホムペ（ホームページ）・・・多目的に利用できる個人用のウェブサイト
【００２２】
オンラインの個人は、上記の複数のタイプの個人ウェブサイトを、サービスプロバイダ毎に異なるアカウントで作成しているため、同一のＩＤによる紐付け（名寄せ）ができていないことが多い。例えば、「オンラインＩＤ（ＯｎＩＤ）＝１」であるオンラインの個人は、プロフ、ゲスブ及びリアルを管理している。これらの個人ウェブサイトは、「ＯｎＩＤ＝１」の情報を有しておらず、異なるアカウントＩＤ（ＡｃＩＤ＝１及び２）で管理されている。
【００２３】
図２は、本実施形態に係るサービスプロバイダ、アカウント及び個人ウェブサイトの関係を示す図である。
【００２４】
オンラインの個人（ＯｎＩＤ＝１）は、例えば、プロフ及びゲスブを提供しているサービスプロバイダＳＰ−Ａに対してアカウント１を登録し、プロフ及びゲスブを管理している。また、同一のオンラインの個人（ＯｎＩＤ＝１）は、リアル及びゲスブを提供しているサービスプロバイダＳＰ−Ｂに対して、アカウント２を登録し、リアルを管理している。
このように、オンラインの個人は、複数のサービスプロバイダの中から好きな個人ウェブサイトを選択し、複数のアカウントによって複数の個人ウェブサイトを管理できる。
【００２５】
リンク補完装置１は、所定の範囲で個人ウェブサイトを収集した後、個人ウェブサイト間のリンク情報に基づいて、管理者であるオンラインの個人が同一である個人ウェブサイトに対して、同一のオンラインＩＤ（ＯｎＩＤ）を割り当て、複数の個人ウェブサイトをオンラインの個人毎に分類する。
【００２６】
図３は、本実施形態に係るリンク補完装置１によりオンラインＩＤが割り当てられた結果を示す概要図である。
【００２７】
同一のオンラインＩＤ（ＯｎＩＤ）が割り当てられた１又は複数の個人ウェブサイトは、アカウントＩＤ（ＡｃＩＤ）が同一とは限らず、異なるサービスプロバイダにより提供される個人ウェブサイトが選択されていると、異なるアカウントＩＤによって識別される。
ここで、オンラインＩＤによって名寄せされた個人ウェブサイト群の間に存在するハイパーリンクを可視化することによって、管理者であるオンラインの個人の間のリンク構造が把握される。これにより、例えば、ネットいじめ等の人間関係に起因するトラブルについて、生徒指導に必要な情報として、ネットワークでの人間関係を教師等に提供できる。
【００２８】
図４は、本実施形態に係るリンク補完装置１の機能構成を示すブロック図である。
リンク補完装置１は、制御部１０と、記憶部２０と、通信部３０と、入力部４０と、出力部５０とを備える。
【００２９】
制御部１０は、リンク補完装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、上記のハードウェアと協働し、本実施形態における各種機能を実現している。制御部１０は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であってよい。なお、制御部１０が備える各部の機能は後述する。
【００３０】
記憶部２０は、ハードウェア群をリンク補完装置１として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ハードディスク（ＨＤＤ）であってよい。具体的には、記憶部２０には、本実施形態の各種機能を実現させるため制御部１０に実行させるプログラム（リンク補完プログラム）が記憶される。
【００３１】
さらに、記憶部２０は、サイト保存ＤＢ２１と、サイト管理ＤＢ２２とを備える。サイト保存ＤＢ２１は、プログラムにて取得される個人ウェブサイトのページデータ（ＨＴＭＬファイル群）を記憶する。また、サイト管理ＤＢ２２は、プログラムにて作成又は編集される後述の収集履歴管理テーブル２２１、サイト間リレーションテーブル２２２及び個人属性テーブル２２３を記憶する。
【００３２】
収集履歴管理テーブル２２１には、インターネットから所定のルールに従って収集された個人ウェブサイトの履歴が記録される。サイト間リレーションテーブル２２２には、個人ウェブサイト間のハイパーリンクの情報が記録される。個人属性テーブル２２３には、オンラインの個人に関する現実世界における属性情報が提供された場合に記録される。
【００３３】
また、サイト間リレーションテーブル２２２の情報に基づいて、各個人ウェブサイトの管理者であるオンラインの個人を識別するオンラインＩＤが割り当てられると、収集履歴管理テーブル２２１及びサイト間リレーションテーブル２２２が更新される。
なお、個人ウェブサイトの収集、及びオンラインＩＤの割り当てには、既存の提案手法が利用できる（例えば、特願２０１１−０７１１０９号明細書、特願２０１０−１０８２４２号明細書）。
【００３４】
図５は、本実施形態に係るサイト管理ＤＢ２２に格納される収集履歴管理テーブル２２１を示す図である。
【００３５】
収集履歴管理テーブル２２１は、収集ＩＤ、ルートＵＲＬ、リンク元ＵＲＬ、個人ウェブサイトの代表ＵＲＬ（ＵＲＬ（Ｕ））、保存先、ホップ数、オンラインＩＤ（ＯｎＩＤ（Ｕ））及び収集日時等を記憶する。
【００３６】
ここで、収集ＩＤは、収集処理が実行される毎に付与される識別番号である。ルートＵＲＬは、収集処理を行う際に指定された収集のための起点となる個人ウェブサイトのＵＲＬである。保存先は、サイト保存ＤＢ２１内における対象の個人ウェブサイトの記憶場所を示すＵＲＬである。
【００３７】
また、ホップ数は、指定された個人ウェブサイトをルートノードとし、リンクされた隣接する個人ウェブサイト間のハイパーリンクを１ホップとしたときの、ルートノードからのホップ数である。
【００３８】
図６は、本実施形態に係るサイト管理ＤＢ２２に格納されるサイト間リレーションテーブル２２２を示す図である。
サイト間リレーションテーブル２２２は、収集ＩＤ、リンク元の個人ウェブサイトの情報（ＵＲＬ（Ｕ）、Ｔｙｐｅ（Ｕ）、Ｃ（Ｕ）、ＡｃＩＤ（Ｕ）、ＯｎＩＤ（Ｕ））、リンク先の個人ウェブサイトの情報（ＵＲＬ（Ｖ）、Ｔｙｐｅ（Ｖ）、Ｃ（Ｖ）、ＡｃＩＤ（Ｖ）、ＯｎＩＤ（Ｖ））、リンク本数（Ｎ（Ｕ→Ｖ））及びリンク発生日時（Ｌｄａｔｅ（Ｕ→Ｖ））等を記憶する。
なお、Ｃ（Ｕ）及びＣ（Ｖ）は、サイトの利用形態を表す分類（クラス）であり、個人ウェブサイトのＵＲＬから判別される。具体的には、ＣｌａｓｓＡは、プロフ及びホムペが分類され、オンラインの個人が他者と識別するために作成する個人ウェブサイトである。ＣｌａｓｓＢは、ゲスブ及びマイリンクが分類され、オンラインの個人がＣｌａｓｓＡに付随して作成する個人ウェブサイトである。ＣｌａｓｓＣは、リアル及びブログが分類され、オンラインの個人が他者と識別するため、又はＣｌａｓｓＡに付随して作成する個人ウェブサイトである。
【００３９】
ここで、ＡｃＩＤは、サービスプロバイダの識別子と、サービスプロバイダ毎に発行されるアカウントの識別子とを含む。これらの識別子は、個人ウェブサイトのＵＲＬによって識別される。ここで、同一のサービスプロバイダにおいてアカウントが同一であれば、管理者（オンラインの個人）は同一であると見なせるが、サービスプロバイダが異なれば、アカウントが同一であっても管理者が同一であるとは限らない。
【００４０】
図７は、本実施形態に係るサイト管理ＤＢ２２に格納される個人属性テーブル２２３を示す図である。
【００４１】
個人属性テーブル２２３は、オンラインＩＤ（ＯｎＩＤ）、個人ウェブサイトの代表ＵＲＬ、実名、ハンドルネーム、性別、地域、学校、学年、学級等を記憶する。
これらの属性情報は、例えば学校等の組織から提供され、又は個人ウェブサイト内のテキスト情報から抽出され、グラフ生成のためのノード及びリンクの選択に利用される。
【００４２】
通信部３０は、リンク補完装置１が他の装置と情報を送受信する場合のネットワーク・アダプタであり、ネットワーク（インターネット）を介して個人ウェブサイトを管理しているサーバ１００にアクセスし、個人ウェブサイトのページデータを取得して制御部１０へ提供する。
【００４３】
入力部４０は、リンク補完装置１に対する利用者からの指示入力を受け付けるインタフェース装置である。入力部４０は、例えば、キーボード、マウス及びタッチパネル等により構成される。
【００４４】
出力部５０は、利用者にデータの入力を受け付ける画面を表示したり、リンク補完装置１による処理結果の画面を表示したりするディスプレイ装置を含む。さらに、出力部５０は、ブラウン管表示装置（ＣＲＴ）や液晶表示装置（ＬＣＤ）等のディスプレイ装置の他、プリンタ等の各種出力装置を含んでよい。
【００４５】
次に、制御部１０の機能を詳述する。
制御部１０は、グラフ生成部１１（生成部）と、タイプ分類部１２（分類部）と、リンク補完部１３（補完部）と、アプリケーション部１４とを備える。これら各部は、リンク補完プログラムを実行することにより実現される機能ブロックである。
【００４６】
グラフ生成部１１は、サイト間リレーションテーブル２２２のリンク情報に基づいて、管理者（オンラインの個人）をノードとする無向グラフを生成する。
このとき、グラフ生成部１１は、リンク元の個人ウェブサイトが所定のタイプでないリンク情報を除外して、グラフを生成する。所定のタイプとは、例えば、人間関係を表す静的なリンクを含み静的なサイトに区分される「プロフ」、「ホムペ」、「マイリンク」である。
【００４７】
また、グラフ生成部１１は、ノード間のハイパーリンクの方向又は数に基づいて、無向グラフにおけるノード間のリンクの有無を決定する。例えば、双方向に１本以上のハイパーリンクがある場合、片方向でも５本以上のハイパーリンクがある場合等、所定のルールが設定されてよい。
【００４８】
また、グラフ生成部１１は、指定された個人属性情報の条件に基づいて、管理者及びリンク情報を抽出する。具体的には、グラフ生成部１１は、例えば特定の学校の生徒からなる管理者リストを個人属性テーブル２２３から抽出し、リンク元又はリンク先がこの管理者リストに含まれるリンク情報をサイト間リレーションテーブル２２２から抽出してグラフを生成する。
なお、リンク元及びリンク先の両方が管理者リストに含まれるリンク情報を抽出したり、特定の管理者から所定のホップ数までのリンク情報を抽出したり、この他、抽出条件は様々に設定可能である。
【００４９】
タイプ分類部１２は、グラフ生成部１１により生成されたグラフの中で、直接リンクがないノードのペアを、ノード間のホップ数、及び共通の隣接ノードの数（Ｃｏｍｍｏｎ  Ｎｅｉｇｈｂｏｒｓ）に基づいて、複数のタイプに分類する。
【００５０】
図８は、本実施形態に係るノードペアの分類例を示す図である。
この例では、管理者１〜７からなる管理者リストが与えられ、グラフ生成部１１によりこれらの管理者をノードとする無向グラフが生成されている。
【００５１】
このグラフからは、ノードのペアは２１通り得られるが、そのうち直接リンクがある、すなわちホップ数が１のペアが７つ発見されている。
タイプ分類部１２は、直接リンクがない、すなわちホップ数が２以上のノードのペアを、複数のタイプに分類する。この例では、「ホップ数が３以上」、「ホップ数が２、かつ、共通の隣接ノード数が１」、「ホップ数が２、かつ、共通の隣接ノード数が２以上」の３種類に分類した場合を示している。
【００５２】
リンク補完部１３は、タイプ分類部１２により分類されたタイプ毎に、機械学習のための教師データの生成とノードのペアの特徴量に基づく所定の機械学習によって、リンクの欠損を予測して補完する。
機械学習のアルゴリズムは、既存のものが利用可能であり、例えば、決定木、Ｒａｎｄｏｍ  Ｆｏｒｅｓｔ、サポートベクタマシン等の手法が用いられる。
また、ノードのペアの特徴量は、例えば、Ｃｏｍｍｏｎ  Ｎｅｉｇｈｂｏｒｓ、Ａｄａｍｉｃ／Ａｄａｒ、Ｊａｃｃａｒｄ’ｓ  Ｃｏｅｆｆｉｅｎｔ、Ｐｒｅｆｅｒｅｎｔｉａｌ  Ａｔｔａｃｈｍｅｎｔ、Ｋａｔｚβ、ＰｒｏｐＦｌｏｗ等、従来提案されているものが利用可能であり、これらの複数が用いられてもよい。
【００５３】
なお、機械学習に用いられる特徴量の種類は、分類されたタイプ毎に異なっていてもよい。例えば、共通の隣接ノードの数が６未満ではＡｄｍｉｃ／Ａｄａｒを、６以上ではＰｒｅｆｅｒｅｎｔｉａｌ  Ａｔｔａｃｈｍｅｎｔを優先的に使用する。
【００５４】
アプリケーション部１４は、サイト管理ＤＢ２２の情報を利用者へ提供する機能ブロックである。アプリケーション部１４は、例えば、リンク情報に基づいて、個人ウェブサイトの管理者間のハイパーリンクを可視化する等の処理を行い、処理結果を出力部５０へ出力して利用者に提供する。
【００５５】
図９は、本実施形態に係るグラフ生成処理を示すフローチャートである。
ステップＳ１において、グラフ生成部１１は、個人属性が条件（例えば、特定の学校の生徒）に合致する管理者のリストを、個人属性テーブル２２３から取得する。
なお、個人ウェブサイト収集時のルートからのホップ数等、個人属性情報とは異なる情報を条件としてもよい。また、条件を指定せず、グラフ生成部１１は、全ての管理者を抽出してもよい。
【００５６】
ステップＳ２において、グラフ生成部１１は、リンク元又はリンク先の管理者がステップＳ１の管理者リストに含まれるリンク情報を、サイト間リレーションテーブル２２２から取得する。
なお、グラフ生成部１１は、リンク元及びリンク先の両方の管理者が管理者リストに含まれるリンク情報を取得してもよく、取得条件は適宜設定されてよい。
【００５７】
ステップＳ３において、グラフ生成部１１は、ステップＳ２でサイト間リレーションテーブル２２２から取得したリンク情報のうち、リンク元の個人ウェブサイトが静的なタイプ（例えば、プロフ、ホムペ、マイリンク）であるリンク情報を選択する。グラフ生成部１１は、さらに限定的に、例えばリンク元の個人ウェブサイトのタイプがマイリンクであるリンク情報のみを選択してもよい。
【００５８】
ステップＳ４において、グラフ生成部１１は、ステップＳ３で選択されたリンク情報に基づいて、所定の条件（例えば、相互に１本以上のハイパーリンクが存在する）を満たすノード間に無向重みなしのリンクを設定した無向グラフを生成する。
【００５９】
図１０は、本実施形態に係るリンク補完処理を示すフローチャートである。
ステップＳ１１において、タイプ分類部１２は、グラフ中のノードの管理者がいずれも管理者リストに含まれるノードペアを取得する。
【００６０】
ステップＳ１２において、タイプ分類部１２は、ステップＳ１１で取得したノードペアについて、生成したグラフの情報からノード間のホップ数及び共通隣接ノード数を算出する。
なお、共通隣接ノード数の算出には、管理者リストに含まれていない管理者のノードを対象外としてもよい。
【００６１】
ステップＳ１３において、タイプ分類部１２は、ホップ数が２以上の、すなわち直接リンクがないノードペアを、ホップ数及び共通隣接ノード数によって複数のタイプに分類する。
【００６２】
ステップＳ１４において、リンク補完部１３は、ステップＳ１３で分類されたタイプ毎に、所定の機械学習によって、リンクの有無を推定する。
【００６３】
ステップＳ１５において、リンク補完部１３は、ステップＳ１４でリンクが有ると推定されたノードペアの情報を、サイト間リレーションテーブル２２２又は別のテーブルに登録する。サイト間リレーションテーブル２２２を利用する場合、推定されたリンクは無向であるため、リンク補完部１３は、例えばノード間双方へのリンク情報として２つのレコードを追加する。
【００６４】
本実施形態によれば、リンク補完装置１は、個人ウェブサイト間のハイパーリンクに基づいて生成される管理者のコンタクトネットワークにおいて、共通の隣接ノード数に基づく複数のタイプにノードペアを分類し、タイプ毎にノードの有無を予測する。したがって、リンク補完装置１は、現実世界の人間関係が強く反映された個人ウェブサイトの特殊なネットワークにおいて、欠損したリンクを精度良く補完できる。
さらに、リンク補完装置１は、ノード間のホップ数を更に基準にしてノードペアを分類する。これにより、リンク補完装置１は、欠損したリンクを精度良く補完できる。
【００６５】
リンク補完装置１は、収集されたリンク情報のうち、リンク元の個人ウェブサイトが静的なタイプでないリンク情報を除外する。したがって、リンク補完装置１は、現実世界をより反映したコンタクトネットワークを生成できる。
【００６６】
リンク補完装置１は、コンタクトネットワークにおける無向重みなしのリンクの有無を、ノード間のハイパーリンクの方向又は数、あるいは両方の条件により決定する。したがって、リンク補完装置１は、有向のハイパーリンクに基づいて、効率的にコンタクトネットワークを生成できる。
【００６７】
リンク補完装置１は、個人属性情報を記憶し、指定された個人属性情報の条件に基づいて管理者及びリンク情報を抽出する。したがって、リンク補完装置１は、指定された特定の範囲におけるコンタクトネットワークを効率的に生成し、クリークの検出を効率化できる。
【００６８】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００６９】
リンク補完装置１によるリンク補完方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（リンク補完装置１）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００７０】
１  リンク補完装置
１０  制御部
１１  グラフ生成部（生成部）
１２  タイプ分類部（分類部）
１３  リンク補完部（補完部）
１４  アプリケーション部
２０  記憶部
２１  サイト保存ＤＢ
２２  サイト管理ＤＢ
３０  通信部
４０  入力部
５０  出力部
２２１  収集履歴管理テーブル
２２２  サイト間リレーションテーブル
２２３  個人属性テーブル
【図１】
2015191439.tif 000003
【図２】
2015191439.tif 000004
【図３】
2015191439.tif 000005
【図４】
2015191439.tif 000006
【図５】
2015191439.tif 000007
【図６】
2015191439.tif 000008
【図７】
2015191439.tif 000009
【図８】
2015191439.tif 000010
【図９】
2015191439.tif 000011
【図１０】
2015191439.tif 000012