JP5350319B2 - 友人推薦装置及び方法及びプログラム - Google Patents

Description

本発明は、友人推薦装置及び方法及びプログラムに係り、特に、BBS(Bulletin Boad System)、SNS(Social Network Service)、QAサイト等の、ネットワーク上で提供されるユーザ間のコミュニケーションにおいて、ユーザの集合であるコミュニティ内のコミュニケーションを活性化させるために、コミュニティの友人を紹介する友人推薦装置及び方法及びプログラムに関する。

近年、インターネットの発展に伴い、ネットワークを介したコミュニケーションが普及している。中でも、メーリングリストや掲示板、チャット、ブログ、ＱＡサイト、ソーシャルネットワーキングサービスなどにおいて、ユーザ間の面識の有無に関わらず、コミュニティを形成し、活発なコミュニケーションおよび情報交換が行われている。

このようなネットワーク上のコミュニティにおいて、さまざまな企業が商品やサービスを宣伝し、さらに消費者の生の声を収集するのに利活用している。ユーザは、自身の趣味や興味に関して、情報交換や情報収集をし、また新たな人との出会いの場として活用している。

そういったコミュニティを活性化する手法は、これまでいくつも提案されてきた。例えば、新旧問わず様々なユーザとコミュニケーションをとっている重要ユーザを発見し、その所属するコミュニティを活性コミュニティとしてユーザに提示する装置が開示されている（例えば、特許文献１参照）。これは、重要ユーザの存在が、ユーザにおける見ず知らずの相手とのコミュニケーションに感じる不安を軽減し、コミュニケーションしやすい環境を作るという仮説に基づいた手法である。

また、友人である可能性の高い２ユーザを発見し、それらにコミュニケーションをとらせる手法も提案されている。友人関係は、離散数学でいうところのグラフにモデル化できる。例えば、ユーザＡがユーザＢを友人と認識している場合に、Ａ、Ｂそれぞれをノードとみなし、Ａを始点、Ｂを終点とする有向枝が存在するとみなせば、有向グラフにモデル化できる。このとき、一般のグラフには成長に制約があり、それを利用することでエッジの発生する可能性の高い２ノード、つまり友人になる可能性の高い２ユーザを発見するものがある（例えば、非特許文献１参照）。この手法を用いて友人になる可能性の高い２ユーザにコミュニケーションをとらせることでコミュニティを活性化することができる。

特開２００５−２３５１１８号公報

Liben-Nowell, D. et al, ``The link prediction problem for social networks'', CIKM '03* Proceedings of the twelfth international conference on Information and knowledge management, ACM Press New York, 2003.

従来のオンラインコミュニティ活性化手法は、コミュニティそのものの性質か、あるいはコミュニティに属する１人のユーザの性質しか着目していない。しかしながら、コミュニケーションは本来２人のユーザで行われるものである。

例えば、特許文献１に記載の手法では、コミュニティの性質からユーザにとってどのコミュニティが参加しやすいかはわかるが、ユーザの性質に着目していないためそのコミュニティのどのメンバとコミュニケーションがとりやすいかはわからない。従って、十分にコミュニティを活性化することはできないと考えられる。

また、非特許文献１記載の、グラフに基づく友人である２ユーザを発見する手法は、一般的なグラフに適用される手法に基づいており、個々のグラフの特性は考慮しない。そのため、十分な精度で友人である２ユーザを発見できないという問題点があった。

本発明は、このような問題に鑑みてなされたもので、その目的とするところは、コミュニティ内のユーザ間の友人関係をグラフにモデル化した際に、そのグラフの特性に基づいて将来友人となる可能性の高い２ユーザを発見し、友人として推薦することによりコミュニケーションを促進することが可能な友人推薦装置及び方法及びプログラムを提供することである。

上記の課題を解決するために、本発明（請求項１）は、各ユーザがIDを持ち、ユーザ間でコミュニケーションをとることを目的とするオンラインコミュニティシステムにおいて、友人を推薦するための友人推薦装置であって、
オンラインコミュニティにおけるユーザを取得し、コミュニケーション記憶手段に格納するコミュニケーション情報取得手段と、
コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける３ユーザをコミュニケーションの有無のパターンから分類し、３−ノードのグラフ情報として３−部分グラフ記憶手段に格納する３−部分グラフ情報取得手段と、
コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける２ユーザについて、コミュニケーションの有無に関する情報と、３−部分グラフ記憶手段の３−部分グラフ情報から、オンラインコミュニティにおける２ユーザについて、２ユーザ以外の別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの頻度を取得し、エッジタイプ記憶手段に格納するエッジタイプ情報取得手段と、
オンラインコミュニティにおける２ユーザについて、エッジタイプ記憶手段に格納されているコミュニケーションの有無に関する情報と、別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とを用いて、重みパラメータを算出し、重みパラメータ記憶手段に格納する重みパラメータ取得手段と、
ユーザの識別子が与えられると、前記コミュニケーションの有無に関する情報と、別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数と、重みパラメータ記憶手段の重みパラメータとを用いて、該ユーザに対して別ユーザを友人として推薦する友人推薦手段と、を有する。

また、本発明（請求項２）は、重みパラメータ算出手段において、
コミュニケーションの有無に関する情報と、別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とに基づいて、ロジスティック回帰分析によって重みパラメータを算出する手段を含む。

また、本発明（請求項３）は、各ユーザがIDを持ち、ユーザ間でコミュニケーションをとることを目的とするオンラインコミュニティシステムにおいて、友人を推薦するための友人推薦方法であって、
コミュニケーション記憶手段、３−部分グラフ記憶手段、エッジタイプ記憶手段、重みパラメータ記憶手段を格納し、コミュニケーション情報取得手段、３−部分グラフ情報取得手段、エッジタイプ情報取得手段、重みパラメータ取得手段、友人推薦手段とを有する装置において、
コミュニケーション情報取得手段が、オンラインコミュニティにおけるユーザを取得し、コミュニケーション記憶手段に格納するコミュニケーション情報取得ステップと、
３−部分グラフ情報取得手段が、コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける３ユーザをコミュニケーションの有無のパターンから分類し、３−ノードのグラフ情報として３−部分グラフ記憶手段に格納する３−部分グラフ情報取得ステップと、
エッジタイプ情報取得手段が、コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける２ユーザについて、コミュニケーションの有無に関する情報と、３−部分グラフ記憶手段の３−部分グラフ情報から、オンラインコミュニティにおける２ユーザについて、２ユーザ以外の別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの頻度を取得し、エッジタイプ記憶手段に格納するエッジタイプ情報取得ステップと、
重みパラメータ取得手段が、オンラインコミュニティにおける２ユーザについて、エッジタイプ記憶手段に格納されているコミュニケーションの有無に関する情報と、別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とを用いて、重みパラメータを算出し、重みパラメータ記憶手段に格納する重みパラメータ取得ステップと、
友人推薦手段が、ユーザの識別子が与えられると、３−部分グラフ記憶手段のコミュニケーションの有無に関する情報と、エッジタイプ記憶手段の別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数と、重みパラメータ記憶手段の重みパラメータとを用いて、該ユーザに対して別ユーザを友人として推薦する友人推薦ステップと、を行う。

また、本発明（請求項４）は、重みパラメータ算出ステップにおいて、
コミュニケーションの有無に関する情報と、別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とに基づいて、ロジスティック回帰分析によって重みパラメータを算出する。

また、本発明（請求項５）は、請求項１乃至請求項２のいずれか１項に記載の友人推薦装置を構成する各手段としてコンピュータを機能させるための友人推薦プログラムである。

本発明はコミュニティの成長過程において、特に３ユーザに注目しその中での友人関係の構造の典型的な変化を発見し、その情報を用いることでそのコミュニティ中で友人となる可能性の高い２ユーザを発見する。友人関係の構造の典型的な変化はコミュニティ毎に抽出されるため、これまでの一般的なネットワークの成長パターンに基づく手法よりも高精度にユーザに友人を推薦できるようになる。

本発明の一実施の形態における友人推薦装置の構成図である。 本発明の一実施の形態におけるコミュニケーション情報テーブルの例である。 本発明の一実施の形態における図２の友人関係を表すグラフである。 本発明の一実施の形態における３−部分グラフ情報テーブルの例である。 本発明の一実施の形態における３−部分グラフにおける各ノードのポジションである。 本発明の一実施の形態における３ノード連結有向グラフの全パターンである。 本発明の一実施の形態におけるエッジタイプ出現頻度テーブルの例である。 本発明の一実施の形態における３−ノード連結有向グラフにより決定されるエッジタイプである。 本発明の一実施の形態における友人推薦時の処理のフローチャートである。 本発明の一実施の形態における図０のステップ２００の詳細な処理のフローチャートである。 本発明の一実施の形態における図１０のステップ２２０の詳細な処理のフローチャートである。 本発明の一実施の形態における各３−部分グラフに対応するコミュニケーション行列である。 本発明の一実施の形態における図９のステップ３００の詳細な処理のフローチャートである。 本発明の一実施の形態における図１３のステップ３４０の詳細な処理のフローチャートである。 本発明の一実施の形態におけるエッジタイプ決定ルール表（ｆ_u,v＝０の場合）である。 本発明の一実施の形態におけるエッジタイプ決定ルール表（ｆ_u,v＝１の場合）である。 本発明の一実施の形態における図９のステップ４００の詳細な処理のフローチャートである。 本発明の一実施の形態における重みパラメータ更新時の処理のフローチャートである。

以下図面と共に、本発明の実施の形態を説明する。

本発明も、非特許文献１と同様、ユーザ間の友人関係をグラフにモデル化し、そのグラフの成長の制約に基づいて友人になる可能性の高い２ユーザを発見する。グラフの成長の制約といっても、ネットワークモチーフ（Milo, R. et al., "Network motifs: simple building blocks of complex networks," 2002）と呼ばれるグラフの局所構造に頻繁に出現する部分グラフの形状に着目した手法である。ネットワークモチーフはグラフの種類によって異なることが知られている。そのため、スケールフリー性のような一般的なグラフの成長の制約よりは、より高精度に将来友人となる可能性の高い２ユーザを発見可能であると考えた。

具体的には、一般にグラフにはそれぞれ出現しやすい部分グラフの形状は決まっている。したがって出現しやすい部分グラフを発見できれば、その出現しやすい部分グラフをさらに出現させる２ノード間、すなわちエッジが発生しそうな２ノードを発見することができる。

本発明では、部分グラフでも、特に３ノードのものに着目した。これは、ノード数が増えれば増えるほど計算のコストがかかるためである。２ノード間にエッジが発生するかどうかについて、別のもう１つのノードからなる部分グラフの形状に着目すると、その部分グラフの形状はエッジの有無、方向性、対称性から２４種類しか存在しない。つまり着目している２ノードに対して、それ以外の１ノードからなる部分グラフの形状が２４種類のどれに分類されるかをカウントする。すると、２ノードは２４次元の、各成分が自然数のベクトルとみなせる。

現在のグラフの各２ノード間のエッジの有無を訓練データとし、エッジの無い２ノード間をテストデータとみなせば、従来のベクトル識別モデルの利用が可能となる。すなわち、訓練データからグラフに出現しやすい部分グラフの形状を学習し、その部分グラフの形状に基づきエッジの発生しやすい２ノードを高精度に発見する。その２ノードにあたる２ユーザ間でコミュニケーションを推薦することにより、コミュニティの活性化を図る。

以下に具体的に説明する。

図１は、本発明の一実施の形態における友人推薦装置の構成を示す。

同図に示す友人推薦装置１は、コミュニケーション情報抽出部１０、３−部分グラフ情報テーブル構築部２０、エッジタイプ出現頻度テーブル構築部３０、友人推薦部４０、重みパラメータ更新部５０、記憶部６０、通信部７０、入出力部８０から構成され、通信部７０はネットワーク３に接続されており、入出力部８０は、入力装置や表示装置等の外部装置４に接続されている。

３―部分グラフ情報テーブル構築部２０は、３−部分グラフマッチング部２１から構成される。

記憶部６０は、コミュニケーション情報テーブル６１、３−部分グラフ情報テーブル６２、エッジタイプ出現頻度テーブル６３、重みパラメータ記憶部６４を格納する記憶媒体である。以下に記憶部６０内の各テーブルについて説明する。

＜コミュニケーション情報テーブル＞
コミュニケーション情報テーブル６１には、図２に示すように、ユーザＩＤフィールド、友人ＩＤフィールドが含まれる。

ユーザＩＤフィールドは、ユーザを特定する識別子が、コミュニケーション情報抽出部１０により設定される。

友人ＩＤフィールドは、当該行のユーザの友人にあたる別のユーザのユーザＩＤが、コミュニケーション情報抽出部１０により設定される。

コミュニケーション情報テーブル６１に記載されているユーザ間の友人関係は、各ユーザをノードとし、ユーザＩＤフィールド記載のユーザに対応するノードから友人ＩＤフィールド記載のユーザに対応するノードへ有向枝を張ると、離散数学で扱う有向グラフにモデル化することができる。図３に、図２のコミュニケーション情報テーブル６１の例を有向グラフにモデル化したものを示す。

＜３−部分グラフ情報テーブル＞
３−部分グラフ情報テーブル６２には、図３に示すように、ポジション１ユーザＩＤフィールド、ポジション２ユーザＩＤフィールド、ポジション３ユーザＩＤフィールド、３−部分グラフパターンフィールドが含まれる。

ポジション１〜３フィールドには、当該行の３ユーザの友人関係をグラフで表したときのそれぞれのノードに対応するユーザを特定する識別子が、３?部分グラフ情報テーブル構築部２０により設定される。また、図４に３?部分グラフにおける各ノードのポジションを示す。

３−部分グラフパターンフィールドには、当該行の３−部分グラフのパターンを表す数値が、３−部分グラフ情報テーブル構築部２０により設定される。

ここで、３−部分グラフのパターンについて説明する。まず、３−部分グラフ情報テーブル６２には、連結でない３−部分グラフは設定されない。すなわち、他の２ノードとまったく枝を共有しないノードが存在するような３−部分グラフは設定されない。このような３ノードからなる連結な有向グラフを同型なものは同じパターンとして全て分類すると、図５に示すように１３通りしか存在しない。ここで「グラフGがG'と同型である」とは、Gの任意の枝 e=(v,w) について、(f(v),f(w)) がG'に属するような全単射な写像ｆが存在する、すなわちノードを入れ換えることで全く同じものになることを意味する。

＜エッジタイプ出現頻度テーブル＞
エッジタイプ出現頻度テーブル６３には、図６に示すように、ユーザ１ＩＤフィールド、ユーザ２ＩＤフィールド、友人フィールド、エッジタイプ１〜２４出現頻度フィールド が含まれる。

ユーザ１ＩＤフィールド、ユーザ２ＩＤフィールドには、それぞれコミュニケーション情報テーブル６１のユーザＩＤフィールド、もしくは友人ＩＤフィールドに出現するユーザを特定する識別子の、すべての順列がエッジタイプ出現頻度テーブル構築部３０により設定される。ただし、ユーザ１ＩＤフィールドとユーザ２ＩＤフィールドが同じ値をとることはない。

友人フィールドは、コミュニケーション情報テーブル６１に、ユーザＩＤフィールドが当該行のユーザ１ＩＤフィールドの値で、かつ友人ＩＤフィールドが当該行のユーザ２ＩＤフィールドの値を持つ行が存在する場合には"１"が、そうでない場合には"０"が、エッジタイプ出現頻度テーブル構築部３０により設定される。

次に、エッジタイプについて説明する。グラフに含まれる全ての２ノードの順列（u、v とする）を考える。また、u，vを含む３−部分グラフ全てを抽出する。このとき、uを始点とし、vを終点とする枝がないと仮定した場合でも連結であるような３−部分グラフのみを考える。そのような３−部分グラフの u， v以外のもう１つのノードを今 wとする。このとき、uを始点とし vを終点とするエッジが存在しないと仮定したときの３−部分グラフでの u， v， wの入次数（何本の枝の終点か）と出次数（何本の枝の始点か）と、u を始点とし vを終点とするエッジが存在すると仮定したときの u, v, wの入次数と出次数の取り得る値は全部で２４通りしかない。簡単のために図示すると、図８のようになる。

このとき、エッジタイプ１〜２４出現頻度フィールドは、当該行のユーザ１ u、ユーザ２ vに対して、エッジタイプ１?２４に分類されるような wが何個存在するかが、エッジタイプ出現頻度テーブル構築部３０により設定される。

次に、本発明の一実施の形態における友人登録時の処理の流れについて説明する。ユーザ uがユーザ vを友人として登録すると、コミュニケーション情報抽出部１０がコミュニケーション情報テーブル６１にユーザＩＤフィールドの値が u、友人ＩＤフィールドの値が vである行を追加する。

次に、図９を用いて本発明の一実施の形態における友人推薦時の流れについて説明する。友人を推薦するタイミングは、ユーザがシステムにログインしたときや、システム管理者側が明示的に友人を推薦する命令をシステムに送ったときが考えられる。

ステップ１００）コミュニケーション情報抽出部１０が、コミュニケーション情報テーブル６１に記載された情報を記憶部６０より抽出し、それを３−部分グラフ情報テーブル構築部２０とエッジタイプ出現頻度テーブル構築部３０、友人推薦部４０に受け渡す。

ステップ２００）３−部分グラフ情報テーブル構築部２０が、コミュニケーション情報抽出部１０より受け渡されたコミュニケーション情報テーブル６１に記載の情報より３−部分グラフ情報テーブル６２を記憶部６０に構築し、エッジタイプ出現頻度テーブル構築部３０に受け渡す。

ステップ３００）エッジタイプ出現頻度テーブル構築部３０が、コミュニケーション情報テーブル構築部１０により受け渡されたコミュニケーション情報テーブル６１記載の情報と、３−部分グラフ情報テーブル構築部２０により受け渡された３−部分グラフ情報テーブル６２に記載の情報を用いてエッジタイプ情報テーブル６３を記憶部６０に構築し、友人推薦部４０に受け渡す。

ステップ４００）友人推薦部４０が、コミュニケーション情報テーブル構築部１０により受け渡されたコミュニケーション情報テーブル６１記載の情報と、エッジタイプ出現頻度テーブル構築部３０により受け渡されたエッジタイプ出現頻度テーブル６３記載の情報を用いてユーザに友人を推薦する。

次に、上記の図９のステップ２００の処理を詳細に説明する。

図１０は、本発明の一実施の形態における図９のステップ２００の詳細な処理のフローチャートである。

ステップ２１０）３−部分グラフ情報テーブル構築部２０が、コミュニケーション情報テーブル抽出部１０より受け渡されたコミュニケーション情報テーブル６１の情報中に出現する、ユーザＩＤフィールド、友人ＩＤフィールドのとりうる値の３つの全組合せを取得する。

ステップ２２０）３−部分グラフマッチング部２１が、３−部分グラフ情報テーブル構築部２０より受け渡された前記ユーザＩＤフィールドの組合せ (u₁,u₂,u₃) をもとに、ユーザＩＤの組合せ (u₁,u₂,u₃) に対応する３−部分グラフが１３種類のパターンのうちどれと一致するかを判別したもの pattern_u1,u2,u3 と、(u₁,u₂,u₃)のうち３−部分グラフのポジション１、ポジション２、ポジション３にあてはまるユーザＩＤp₁, p₂, p₃を取得する。

ステップ２３０）３−部分グラフ情報テーブル構築部２２が、ポジション１ユーザＩＤフィールドの値がp₁、ポジション２ユーザＩＤフィールドの値がp₂、ポジション３ユーザＩＤフィールドの値がp₃、３−部分グラフパターンフィールドの値がpattern_u1,u2,u3であるような行を３−部分グラフ情報テーブル６２に挿入する。

次に、上記の図１０のステップ２２０の処理を詳細に説明する。
図１１は、本発明の一実施の形態における図１０のステップ２２０の詳細な処理のフローチャートである。

ステップ２２１）３−部分グラフマッチング部２１が、ユーザＩＤフィールドの組合せ(u₁,u₂,u₃)に対応する全６通りの順序(u₁,u₂,u₃)、(u₁,u₃,u₂)、(u₂,u₁,u₃)、(u₂,u₃,u₁)、(u₃,u₁,u₂)、(u₃,u₂,u₁)を取得する。

ステップ２２２）３−部分グラフマッチング部２１が、３−部分グラフ情報テーブル構築部２０より受け渡されたコミュニケーション情報テーブル６１の情報をもとに、ユーザＩＤフィールドの順序(p₁,p₂,p₃)に対応する３行３列のコミュニケーション行列M_p1,p2,p3を作成する。具体的には、コミュニケーション行列M_p1,p2,p3の各成分は、対角成分の値を＊、x行y列の値がユーザＩＤフィールドの値がp_xであり、かつ友人ＩＤフィールドの値がp_yであるような行がコミュニケーション情報テーブル６１に存在する場合は"１"、ない場合は"０"で与える。なお、コミュニケーション行列M_p1,p2,p3の対角成分の値を＊で与えたが、これは他のどのような値でも良い。

図１２に、３−部分グラフマッチング処理のための、１３種類の各パターンにおけるコミュニケーション行列M_k(k=1,…,13)を示す。各コミュニケーション行列の各成分は、対角成分の値を＊、x 行 y 列の値をｘ番目のノードからｙ番目のノードにエッジがある場合は"１"、ない場合は"０"で与える。なお、M_kの対角成分の値は、M_p1,p2,p3と一致するように設定する。

ステップ２２３）３−部分グラフマッチング部２１が、一時変数kを用意し、その値を１に初期化する。

ステップ２２４）３−部分グラフマッチング部２１が、ユーザＩＤフィールドの順列 (p₁,p₂,p₃) に対応する３行３列のコミュニケーション行列 M_p1,p2,p3 とｋ番目のパターンを表すコミュニケーション行列M_kが一致するかどうかを判別する。

ステップ２２５）３−部分グラフマッチング部２１が、ユーザＩＤフィールドの順列 (u₁,u₂,u₃) に対応する３−部分グラフパターンフィールドの値 pattern_u1,u2,u3 をｋとし、３−部分グラフ情報データベース構築部２２に受け渡す。

ステップ２２６）３−部分グラフマッチング部２１が、一時変数kをインクリメントする。

次に、上記の図９のステップ３００の処理を詳細に説明する。

図１３は、本発明の一実施の形態における図９のステップ３００の詳細な処理のフローチャートである。

ステップ３１０）エッジタイプ出現頻度テーブル構築部３０が、コミュニケーション情報テーブル抽出部１０より受け渡されたコミュニケーション情報テーブル６１記載の情報中に出現する、ユーザＩＤフィールド、友人ＩＤフィールドのとりうる値の２つの全順列を取得する。

ステップ３２０）エッジタイプ出現頻度テーブル構築部３０が、コミュニケーション情報テーブル抽出部１０より受け渡された前記２ユーザＩＤの順列(u, v)について、コミュニケーション情報テーブル６１にユーザＩＤフィールドの値が u、友人ＩＤフィールドの値が v であるような行が存在する場合はf_u,v=1、存在しない場合は f_u,v=0とする。

ステップ３３０）エッジタイプ出現頻度テーブル構築部３０が、３−部分グラフ情報テーブル構築部２０より受け渡された３−部分グラフ情報テーブル６２中で、ポジション１〜３ユーザＩＤフィールドに u、v を共に含む行集合T_u,vを取得する。

ステップ３４０）エッジタイプ出現頻度テーブル構築部３０が、u、v、f_u,v、T_u,v をもとにエッジタイプ出現頻度テーブル６３を更新する。

次に、上記の図１３のステップ３４０の処理を詳細に説明する。

図１４は、本発明の一実施の形態における図１３のステップ３４０の詳細な処理のフローチャートである。

ステップ３４１）エッジタイプ出現頻度テーブル構築部３０が、未処理の３−部分グラフ情報 t_u,v∈T_u,v のそれぞれについて、当該行t_u,vでは３−部分グラフパターンフィールドの値が pattern_u,v で、ポジション p_u(∈{1,2,3}) ユーザＩＤフィールドの値がuであり、ポジション p_v(∈{1,2,3})、ユーザＩＤフィールドの値がvであるとする。

ステップ３４２）エッジタイプ出現頻度テーブル構築部３０が、f_u,v、p_u、p_v、pattern_u,v を元に図１５、１６に示すエッジタイプ決定ルールにてu，vのエッジタイプe_u,vを決定する。なお、本実施の形態では、当該エッジタイプ決定ルールは予めメモリ（図示せず）に格納されているものとする。

図１５、１６に、図１３のステップ３４０におけるエッジタイプ決定ルールを示す。図１５は、f_u,v =0の場合のエッジタイプ決定ルールである。例えば、２行目７列目は、f_u,v =0 かつp_u=3かつ p_v=2かつ pattern_u,v=1 のときエッジタイプe_u,vが"２"に決まることを表す。同様に、図１６は f_u,v =1の場合のエッジタイプ決定ルールである。

ステップ３４３）エッジタイプ出現頻度テーブル構築部３０が、エッジタイプ出現頻度テーブル６３に、ユーザ１ＩＤフィールドがu 、ユーザ２ＩＤフィールドがvの行が存在しない場合、ユーザ１ＩＤフィールドの値がu、ユーザ２ＩＤフィールドの値がv、友人フィールドの値がf_u,v、エッジタイプ１〜２４フィールドの値が0の行をエッジタイプ出現頻度テーブル６３に挿入する。

ステップ３４４）エッジタイプ出現頻度テーブル構築部３０が、エッジタイプ出現頻度テーブル６３記載の情報でユーザ１ＩＤフィールドの値がuで、ユーザ２ＩＤフィールドの値がvの行を取得し、エッジタイプe_u,vフィールドの値をインクリメントする。

次に、上記の図９のステップ４００の処理を詳細に説明する。

図１７は、本発明の一実施の形態における図９のステップ４００の詳細な処理のフローチャートである。

ステップ４１０）友人推薦部４０が、コミュニケーション情報抽出部１０より受け渡されたコミュニケーション情報テーブル６１記載の情報中に出現する、ユーザＩＤフィールド、友人ＩＤフィールドのとりうる値の２つの全順列を取得する。

ステップ４２０）友人推薦部４０が、コミュニケーション情報抽出部１０より受け渡されたコミュニケーション情報テーブル６１中にユーザＩＤフィールドの値がu、かつ友人ＩＤフィールドの値がvの行が存在するか否か判定する。

ステップ４３０）友人推薦部４０が、エッジタイプ出現頻度テーブル６２中でユーザ１ＩＤフィールドの値がuで、かつユーザ２ＩＤフィールドの値が v の行のエッジタイプｉ (i=1,…,24) 出現頻度フィールドの値x_u,v,i を取得する。

ステップ４４０）友人推薦部４０が、重みパラメータ記憶部６４から重みパラメータλ_i (i=1,…,24) を取得する。

ステップ４５０）友人推薦部４０が、ユーザ u に対する v の推薦スコア score_u,v を以下に示す式（１）を用いて算出する。

ステップ４６０）友人推薦部４０が、前記ユーザuに対するvの推薦スコア score_u,v を用いてユーザuにvを友人として推薦すべきかどうか決定する。その際、推薦スコアの値が大きいものから順に予め設定した任意の人数N(N=1,2,3,…) 人を推薦すべき友人としてもよいし、推薦スコアに対し、ある閾値を設けて、推薦スコアがその値を超えるものを推薦するべき友人としてもよい。

次に、重みパラメータ更新時の処理の詳細について説明する。

図１８は、本発明の一実施の形態における重みパラメータ更新時の処理のフローチャートである。重みパラメータは、本実施の形態のように、文献２（Hosmer, D.W. et al., "Applied logistic regression", 2000）記載のロジスティック回帰モデルを用いて自動で算出してもよいし、文献３（Cristianini, N. et al., "An introduction to Support Vector Machines: and other kernel-based learning methods", 2000）記載のサポートベクトルマシン等を用いて自動で算出してもよいし、人手にて適当な重みパラメータを設定してもよい。重みパラメータの更新は、システムの管理者の明示的な入力で開始するようにしてもよいし、定期的にバッチ処理するようにしてもよい。

ステップ５１０）重みパラメータ更新部５０が、コミュニケーション情報抽出部１０より受け渡されたコミュニケーション情報テーブル６１中のユーザＩＤフィールド、友人ＩＤフィールドに出現する全２ユーザの順列を取得する。

ステップ５２０）重みパラメータ更新部５０が、前記各２ユーザの順列(u, v)について、エッジタイプ出現頻度テーブル６３中でユーザ１ＩＤフィールドの値がuで、かつユーザ２ＩＤフィールドの値がvの行の友人フィールドの値f_u,vと、エッジタイプｉ、出現頻度フィールドの値x_u,v,iを取得する。

ステップ５３０）重みパラメータ更新部５０が、前記２ユーザの順列 (u, v)について、以下に示す式（２）を用いてuがvを友人にする確率P(f_u,v=1|u,v)を算出する。

上記の式（２）は式（１）の値を確率化したもので、式（１）の値が高ければ高いほど値が１に近づき、式（１）の値が低ければ低いほど値が０に近づく。

ステップ５４０）重みパラメータ更新部５０が、前記全２ユーザの順列 (u, v) について、u が v を友人にする確率から、データに対する重みパラメータ λ_i (i=0,…,24) の尤度 L(λ)を以下に示す式（３）を用いて算出する。

上記の式（３）は、重みパラメータが与えられたデータ（本実施の形態の場合、u、v、f_u,v）にどれだけ適合しているかを表す尺度であり、式（３）で算出される値を最大にするλ_i が最も適切な重みパラメータとなる。

ステップ５５０）重みパラメータ更新部５０が、文献４（Liu, D.C. et al., "On the limited memory BFGS method for large scale optimization", 1989）記載の準ニュートン法等による最適化手法により、式（３）で表されるL（λ）を最大にするλ_iを算出する。

ステップ５６０）重みパラメータ更新部５０が、算出した重みパラメータλ_iを重みパラメータ記憶部６４に記録する。

上記のように、本実施の形態によれば、３ユーザ（ノード）に限定して計算コストを抑え、その３ノードのエッジ、方向性、対象性に着目すると２４種類に分類することができる。この２４種類の各パターンで発生する実際の友人関係の頻度を求めることで、どのパターンで友人関係が発生しやすいかが判別できる。友人関係の発生しやすいパターンを検出し、推薦スコアを算出し、推薦スコアが大きいユーザを推薦すべき友人として出力することができる。

なお、上記の実施の形態の図１に示す友人推薦装置の各構成要素の動作をプログラムとして構築し、友人推薦装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

１ 友人推薦装置
２ 外部端末
３ ネットワーク
４ 外部装置
１０ コミュニケーション情報抽出部
２０ ３−部分グラフ情報テーブル構築部
２１ ３−部分グラフマッチング部
３０ エッジタイプ出現頻度テーブル構築部
４０ 友人推薦部
５０ 重みパラメータ更新部
６０ 記憶部
６１ コミュニケーション情報テーブル
６２ ３−部分グラフ情報テーブル
６３ エッジタイプ出現頻度テーブル
６４ 重みパラメータ記憶部
７０ 通信部
８０ 入出力部

Claims (5)

1. 各ユーザがIDを持ち、ユーザ間でコミュニケーションをとることを目的とするオンラインコミュニティシステムにおいて、友人を推薦するための友人推薦装置であって、
   前記オンラインコミュニティにおけるユーザを取得し、コミュニケーション記憶手段に格納するコミュニケーション情報取得手段と、
   前記コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける３ユーザをコミュニケーションの有無のパターンから分類し、３−ノードのグラフ情報として３−部分グラフ記憶手段に格納する３−部分グラフ情報取得手段と、
   前記コミュニケーション記憶手段の前記コミュニケーション情報から、オンラインコミュニティにおける２ユーザについて、コミュニケーションの有無に関する情報と、前記３−部分グラフ記憶手段の前記３−部分グラフ情報から、オンラインコミュニティにおける２ユーザについて、２ユーザ以外の別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの頻度を取得し、エッジタイプ記憶手段に格納するエッジタイプ情報取得手段と、
   オンラインコミュニティにおける２ユーザについて、前記エッジタイプ記憶手段に格納されている前記コミュニケーションの有無に関する情報と、前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とを用いて、重みパラメータを算出し、重みパラメータ記憶手段に格納する重みパラメータ取得手段と、
   ユーザの識別子が与えられると、前記コミュニケーションの有無に関する情報と、前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数と、前記重みパラメータ記憶手段の前記重みパラメータとを用いて、該ユーザに対して別ユーザを友人として推薦する友人推薦手段と、
   を有することを特徴とする友人推薦装置。
2. 前記重みパラメータ算出手段は、
   前記コミュニケーションの有無に関する情報と、前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とに基づいて、ロジスティック回帰分析によって重みパラメータを算出する手段を含む
   請求項１記載の友人推薦装置。
3. 各ユーザがIDを持ち、ユーザ間でコミュニケーションをとることを目的とするオンラインコミュニティシステムにおいて、友人を推薦するための友人推薦方法であって、
   コミュニケーション記憶手段、３−部分グラフ記憶手段、エッジタイプ記憶手段、重みパラメータ記憶手段を格納し、コミュニケーション情報取得手段、３−部分グラフ情報取得手段、エッジタイプ情報取得手段、重みパラメータ取得手段、友人推薦手段とを有する装置において、
   前記コミュニケーション情報取得手段が、前記オンラインコミュニティにおけるユーザを取得し、前記コミュニケーション記憶手段に格納するコミュニケーション情報取得ステップと、
   前記３−部分グラフ情報取得手段が、前記コミュニケーション記憶手段のコミュニケーション情報から、オンラインコミュニティにおける３ユーザをコミュニケーションの有無のパターンから分類し、３−ノードのグラフ情報として前記３−部分グラフ記憶手段に格納する３−部分グラフ情報取得ステップと、
   前記エッジタイプ情報取得手段が、前記コミュニケーション記憶手段の前記コミュニケーション情報から、オンラインコミュニティにおける２ユーザについて、コミュニケーションの有無に関する情報と、前記３−部分グラフ記憶手段の前記３−部分グラフ情報から、オンラインコミュニティにおける２ユーザについて、２ユーザ以外の別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの頻度を取得し、前記エッジタイプ記憶手段に格納するエッジタイプ情報取得ステップと、
   前記重みパラメータ取得手段が、オンラインコミュニティにおける２ユーザについて、前記エッジタイプ記憶手段に格納されている前記コミュニケーションの有無に関する情報と、前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とを用いて、重みパラメータを算出し、前記重みパラメータ記憶手段に格納する重みパラメータ取得ステップと、
   前記友人推薦手段が、ユーザの識別子が与えられると、前記３−部分グラフ記憶手段の前記コミュニケーションの有無に関する情報と、前記エッジタイプ記憶手段の前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数と、重みパラメータ記憶手段の前記重みパラメータとを用いて、該ユーザに対して別ユーザを友人として推薦する友人推薦ステップと、
   を行うことを特徴とする友人推薦方法。
4. 前記重みパラメータ算出ステップにおいて、
   前記コミュニケーションの有無に関する情報と、前記別の１ユーザがそれぞれ３ユーザのコミュニケーションの有無のパターンでいずれに分類されるかの数とに基づいて、ロジスティック回帰分析によって重みパラメータを算出する
   請求項３記載の友人推薦方法。
5. 請求項１乃至請求項２のいずれか１項に記載の友人推薦装置を構成する各手段としてコンピュータを機能させるための友人推薦プログラム。

Images