(57)【要約】  ソーシャルネットワーキングシステムにおけるユーザのコネクションを、互いのコネクションの関係または親和性の尺度に基づき複数のクラスタにグループ化する。コネクション間の親和性はコネクション自体の関係に基づき、コネクションが同一ソーシャルサークルの中に存在する可能性を示す。同一クラスタ内に存在しないコネクションと比較して他のコネクションとの比較的高い親和性を有するコネクションを有する傾向があるクラスタが、ユーザのコネクション間の親和性に基づき形成される。コネクションをコネクションペア同士の親和性に基づきクラスタに縮約するために反復型階層的クラスタ化アルゴリズムが使用され得る。
2014526092.tif 000002
【特許請求の範囲】
【請求項１】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおいて関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記ユーザのコネクションに対する親和性の複数の尺度を決定するステップであって、親和性の各尺度は、前記コネクションのうちの２つ以上のコネクション間の関連性に少なくとも部分的に基づき決定される、親和性の尺度決定ステップと、
前記コネクションの少なくとも１つのサブセットを１つ以上のクラスタにグループ化するステップであって、前記コネクションは前記決定された親和性の尺度に基づきクラスタに割り当てられる、グループ化ステップと、
前記クラスタの識別子と、前記ユーザのコネクションのうちのどのコネクションが前記クラスタに割り当てられたかとを含む前記グループ化ステップの結果を出力する結果出力ステップと、を含む方法。
【請求項２】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、該２つ以上のコネクションが前記ソーシャルネットワーキングシステムにおいて互いに関係を確立したか否かを含む、請求項１に記載の方法。
【請求項３】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、共通してコネクション同士が前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザの重なりの尺度を含む、請求項１に記載の方法。
【請求項４】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、共通してコネクション同士が前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザであって、前記コネクションに密接に関連付けられたと決定された他のユーザの重なりの尺度を含む、請求項１に記載の方法。
【請求項５】
共通してコネクション同士が関係を確立した前記他のユーザは、前記ソーシャルネットワーキングシステムにおける該他のユーザの過去の相互作用に基づき前記コネクションに密接に関連付けられていると決定される、請求項４に記載の方法。
【請求項６】
前記グループ化ステップは、前記決定された親和性の尺度に基づき前記コネクションについて階層的クラスタ化アルゴリズムを実行するステップを含む、請求項１に記載の方法。
【請求項７】
前記グループ化ステップは、親和性の前記尺度の残りが閾値未満になるまで、
親和性の最も高い尺度に関連付けられた２つ以上のコネクションを識別するステップと、
前記識別されたコネクションを新たなクラスタに縮約するステップと、
前記新たなクラスタと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の親和性の新たな尺度を再計算するステップと、を繰り返すステップを含む、請求項１に記載の方法。
【請求項８】
前記再計算された親和性の新たな尺度は、前記識別されたコネクションと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の前記親和性の尺度の平均値に基づく、請求項７に記載の方法。
【請求項９】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおいて関係を確立した前記ソーシャルネッ
トワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記コネクションのうちの少なくとも複数のペアの各々に対して、前記コネクションのペア間の関連性に少なくとも部分的に基づき前記コネクションのペア間の親和性の尺度を決定するステップと、
計算システムによって、
親和性の最も高い尺度に関連付けられた２つ以上のコネクションを識別することと、
前記識別されたコネクションを新たなクラスタに縮約することと、
前記新たなクラスタと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の親和性の新たな尺度を再計算することと、
前記残りの親和性の最も高い尺度が閾値未満になったときに前記クラスタ化を停止することと、を行うことによって前記コネクションを１つ以上のクラスタに繰り返しクラスタ化するステップと、
前記クラスタ化の結果を出力するステップであって、前記結果は前記クラスタの識別子と前記クラスタに割り当てられた前記ユーザのコネクションとを含む、結果出力ステップと、を含む方法。
【請求項１０】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、前記２つ以上のコネクションが前記ソーシャルネットワーキングシステムにおいて互いに関係を確立したか否かを含む、請求項９に記載の方法。
【請求項１１】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、共通してコネクション同士が前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザの重なりの尺度を含む、請求項９に記載の方法。
【請求項１２】
親和性の前記尺度が基づく前記コネクションのうちの前記２つ以上のコネクション間の前記関連性は、共通してコネクション同士が前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザであって、前記コネクションに密接に関連付けられていると決定された他のユーザの重なりの尺度を含む、請求項９に記載の方法。
【請求項１３】
共通してコネクション同士が関係を確立した前記他のユーザは、前記ソーシャルネットワーキングシステムにおける該他のユーザの過去の相互作用に基づき前記コネクションに密接に関連付けられていると決定される、請求項１２に記載の方法。
【請求項１４】
前記再計算された親和性の新たな尺度は前記識別されたコネクションと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の前記親和性の尺度の平均値に基づく、請求項９に記載の方法。
【請求項１５】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおける関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記ユーザのコネクション間の親和性を決定するステップと、
１つ以上のクラスタを生成するために前記決定された親和性に基づき前記コネクションをクラスタ化するステップであって、同一クラスタ内に存在するコネクション間の親和性の多数は、同一クラスタ内に存在しないコネクション間の親和性より高い、クラスタ化ステップと、
前記クラスタ化の結果を出力するステップであって、前記結果は前記クラスタの識別子と前記クラスタに割り当てられた前記ユーザのコネクションとを含む、結果出力ステップと、を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してソーシャルネットワーキングに関し、詳細にはソーシャルネットワーキングシステムにおけるユーザのコネクションのクラスタを生成することに関する。
【背景技術】
【０００２】
ソーシャルネットワーキングシステムは、他のユーザとの関係を形成するか、またはそうでなければ１人もしくは複数の他のユーザとの関連性を示すことにより、ユーザが他のユーザをコネクションとして指定できるようにする。次に、ユーザは、メディア項目を投稿するか、またはそのメディア項目と相互作用し、アプリケーションを使用し、グループに参加し、イベントを列挙してそのイベントへの出席を確認し、ページを作成し、ユーザのコネクションとの社会的交流を容易にする他のタスクを行うことができる。ソーシャルネットワーキングシステムでは、ユーザは膨大な数のコネクションを有してもよく、これらのコネクションはユーザの実生活における様々な経験から引き出され得る。例えば、ユーザは、学校からの多くのコネクションと、仕事からの他のコネクションと、多様なソーシャル（社会的な）サークルを形成するさらに他のコネクションの組とを有し得る。
【０００３】
ソーシャルネットワーキングシステムにおけるいくつかのアプリケーションでは、ユーザのコネクションを、共通のソーシャルサークルの中に存在する他の人々のグループにクラスタ化することが望ましいことがある。ユーザに対するコネクションのクラスタは、互いの親和性に基づきそのコネクションの共通の特徴を反映し得る。これにより、例えば、招待者同士は通常互いを知っているので、ユーザのコネクションをイベントに招待することを容易にする。クラスタのユーザ設定、コンテキスト、共通特徴、およびユーザのクラスタのメンバとの親和性、その他の要因などに応じて、コネクションのクラスタを、ユーザに対し選択的に阻止するか、または促進することができる。特に、ユーザのコネクションを自動的にクラスタ化することで、ユーザの異なる相互作用におけるプライバシ設定を変更するユーザのニーズを満たした。ソーシャルネットワーキングシステムはまた、膨大な数の潜在的なコネクションをユーザが調べて、それらの中の１つまたは複数を発見するための負担を軽減し得る。
【０００４】
いくつかのソーシャルネットワーキングシステムは、ユーザがユーザのコネクションを所定のグループまたは友達の一覧に直接入れる手動クラスタを形成できるようにする。しかし、手動クラスタ化は非常に時間がかかる可能性があり、多くのユーザは友達のクラスタを手動で作る努力をしない可能性が高い。さらに、ユーザは、自身のコネクション間の相互関係を知る最良の立場に無いかもしれなく、したがって、共通ソーシャルサークルの中に存在するユーザのコネクションの正確なクラスタを形成することができないであろう。これらの制限は、膨大な数のコネクションをナビゲートし、それらのコネクションを首尾一貫した友達のグループにグループ化しようとする際に標準以下のユーザ使用体験をもたらし得る。正確な友達のクラスタの作成に関する制限が与えられている中で、プライバシについての懸念はまた、指定したアクションの組が特定のクラスタのユーザのコネクションにだけ可視となる、ということをユーザが知るのと同程度に、ユーザがソーシャルネットワーキングと相互作用することを妨げ得る。
【０００５】
既存のクラスタ化のアルゴリズムは、必要に応じた計算に適用できない。ソーシャルネットワーキングシステムにおけるコネクション間の関係は急速に変化し、ソーシャルグラフ全体について計算集約的アルゴリズム（ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｉｎｔｅｎｓｉｖｅ  ａｌｇｏｒｉｔｈｍ）を実行することは挑戦的課題である。さらに、コネクシ
ョンのクラスタを作成する手動の方法は上に説明したようにいくつかの欠点を有する。
【図面の簡単な説明】
【０００６】
【図１】本発明の一実施形態に応じてクラスタ化されたソーシャルネットワーキングシステムにおけるユーザとユーザのコネクションの図。
【図２】本発明の一実施形態によるソーシャルネットワーキングシステムの高レベル実施形態を示す図。
【図３】本発明の一実施形態によるユーザの最上位友達を決定するための処理のフローチャート。
【図４】本発明の一実施形態によるコネクション間の親和性に基づきユーザのコネクションをクラスタ化する処理のフローチャート。
【図５】本発明の一実施形態によるユーザのコネクションと結果として生じたクラスタとの間の親和性を表す樹状図の一例を示す図。
【図６】本発明の一実施形態によるソーシャルネットワーキングシステムにおけるユーザのコネクションをクラスタ化する処理のフローチャート。
【発明を実施するための形態】
【０００７】
添付図面は、説明の目的だけのために本発明の様々な実施形態を描写する。当業者は、本明細書に示される構造と方法の代替実施形態が本明細書に記載の発明の原理から逸脱することなく採用され得るということを以下の論述から容易に認識することになる。
【０００８】
本発明の実施形態は、ユーザのコネクションのクラスタを形成する機構を提供する。このクラスタ化はコネクションをクラスタにグループ化するためのユーザからの入力を必要とすること無く自動的に行われ得る。ユーザのコネクションは、互いのコネクションの関係の尺度に基づきクラスタにグループ化され、これによりコネクションが共通ソーシャルサークルに存在するか否かを示す。ユーザのコネクションのうちの２つのコネクション間の関係の尺度を、これら２つのコネクション間の親和性と呼ぶことがある。コネクション間の親和性を測定する様々な手法が使用されてもよく、例えば、コネクション同士自体が接続されているか否か、コネクション同士が共通に有する他のコネクションの数、当該コネクションと共通の最上位コネクションの相対数、コネクション間の他の共通性、および／または他のコネクションに対する関係の他の共通性が使用され得る。次に、ユーザのコネクションの１つまたは複数のクラスタ（同一クラスタ内に存在しないコネクションと比較して他のコネクションとの比較的高い親和性を有するコネクションを有する傾向がある）がユーザのコネクション間の親和性に基づき形成される。
【０００９】
一実施形態では、親和性行列で表され得る親和性の尺度がユーザのコネクションの各ペア間で決定される。互いの間で最も高い親和性を有するコネクションおよび／またはクラスタのペア同士を組み合わせることによりコネクションのペアをクラスタに縮約する（ｃｏｌｌａｐｓｅ）ように、階層的クラスタ化アルゴリズムが上記行列に適用される。コネクションがクラスタに追加されると、新たな一組の親和性が、このクラスタについて、追加されたコネクションの親和性に基づき既存の他のコネクションまたはクラスタの各々に対して計算される。このアルゴリズムは、さらに、コネクションをより大きなクラスタに縮約することを正当化するのに十分に高い親和性を有するコネクション、またはコネクションのクラスタが無くなるまで、繰り返し実行される。その結果は、ユーザのコネクションの１つまたは複数のクラスタの組であり、各クラスタ内のコネクションは、そのクラスタ内に存在しないコネクションとの親和性より高い互いの親和性を有する傾向がある。
【００１０】
オンラインソーシャルネットワーキングシステムは、ユーザがユーザ自身をソーシャルネットワーキングシステムの他のユーザと関連付けてそれらとのコネクションを確立できるようにする。２人のユーザが接続されると、ユーザは、ソーシャルネットワーキングシ
ステムというコンテキスト内では「コネクション」、「友達」、「コンタクト」、または「知り合い」であると言われる。一般的に、ソーシャルネットワーキングシステムにおいて接続されることで、接続されたユーザ同士が、未接続のユーザに通常利用可能なものより互いについての多くの情報にアクセスできるようにする。同様に、ソーシャルネットワーキングシステムにおいて接続されることで、ユーザに、電子メール（ソーシャルネットワーキングシステム内外の）、インスタントメッセージ、テキストメッセージ、電話、または任意の他の通信インターフェイスなどにより他のユーザと通信するためのより容易なアクセスを許容する。最後に、接続されることで、ユーザが、他のユーザのアップロードコンテンツ項目を見るか、それらについてコメントするか、それらをダウンロードするか、またはそれらを支持するようにアクセスすることを許容し得る。コンテンツ項目の例には、限定されるものではないがメッセージ、待ち行列型メッセージ（例えば電子メール）、テキストおよびＳＭＳ（ショートメッセージサービス）メッセージ、コメントメッセージ、任意の他の好適なメッセージング技術を使用して送信されたメッセージ、ＨＴＴＰリンク、ＨＴＭＬファイル、画像、ビデオ、オーディオクリップ、文書、文書編集、カレンダーエントリまたはイベント、他のコンピュータ関連ファイルが挙げられる。
【００１１】
ソーシャルネットワーキングシステムのユーザは、コンテンツ項目、ユーザ情報、ユーザアクション（例えば、ソーシャルネットワーキングシステムにおいてなされた通信、または二人のユーザがコネクションとなること）、またはソーシャルネットワーキングシステムにおける任意の他の活動またはデータなどの対象と相互作用し得る。この相互作用は、対象と通信するか、またはその対象についてコメントすることなどにより、親和性に関連付けられたボタンまたはリンク（「いいね！」ボタンなど）をクリックすることにより、コンテンツ項目、ユーザ情報またはユーザアクションを他のユーザと共有することにより、コンテンツ項目をダウンロードするか、または単にそのコンテンツ項目を見ることにより、または任意の他の相互作用のための好適な手段によるなどの様々な形式を取り得る。ソーシャルネットワーキングシステムのユーザはまた、他のユーザを接続するか、または他のユーザと友達になることにより、または他のユーザと通信することにより、またはソーシャルネットワーキングシステムにおいて共通コネクションを有することにより他のユーザと相互作用し得る。さらに、ソーシャルネットワーキングシステムのユーザは、グループを形成するか、もしくはそのグループに参加してもよく、またはファンページを好み得るか、もしくはそうでなければファンページと関連付けられてもよい。最後に、ソーシャルネットワーキングシステムユーザは、コンテンツ項目、ウェブサイト、他のユーザ、またはソーシャルネットワーキングシステムに接続されるか、もしくはソーシャルネットワーキングシステムに関連付けられたソーシャルネットワーキングシステムのウェブページのコンテキスト外の他の情報と相互作用し得る。例えば、ニュースウェブサイトに関する記事は、ソーシャルネットワーキングシステムのユーザが同記事の賛意を表すためにクリックすることができる「いいね！」ボタンを有し得る。これらの相互作用およびソーシャルネットワーキングシステムのコンテキスト内の任意の他の好適なアクションは、ソーシャルネットワーキングシステムデータ内に記録されてもよく、これは、所与の状況においてとられ得るアクションを予測するために使用され得る。次に、これらの予測は、ソーシャルネットワーキングシステムとのより多くのユーザ相互作用を促進しユーザ体験を強化するために使用され得る。
【００１２】
ソーシャルネットワーキングシステムは各ユーザに対してユーザプロファイルを維持する。特定の会員が他の会員に対してとるアクションは、データベースまたは他のデータリポジトリ内に維持された情報を通じて各ユーザのプロファイルに関連付けられる。このようなアクションとしては、例えば、他の会員へのコネクションを追加する、他の会員にメッセージを送る、他の会員からのメッセージを読む、他の会員に関連付けられたコンテンツを見る、および他の会員により投稿されたイベントに参加することなどが含まれ得る。ユーザプロファイルはまた、様々なユーザの職務経歴、学歴、趣味または嗜好、位置また
は同様なデータなどの特徴を記載し、同様なまたは共通の職務経歴、趣味、または学歴を有するユーザを示すデータなどユーザ間の１つまたは複数の関係を記載するデータを含む。ユーザはまた、メッセージを、ステータス更新の形式で、特に自身のプロファイルに投稿することができる。ソーシャルネットワーキングシステムのユーザは、その許可を得れば他のユーザのプロファイルを見ることができる。いくつかの実施形態では、ユーザのコネクションとなることで、ユーザのプロファイルを見るための許可を自動的に提供される。
【００１３】
ソーシャルネットワーキングシステムはまた、ネットワーク上で生のコンテンツをフィルタ処理するためのアルゴリズムを採用することにより、最も関連のある情報を閲覧するユーザへ配信しようとする。コンテンツは、地理的位置、雇用者、職種、年令、音楽嗜好、関心、または他の属性などユーザのプロファイル内の属性に基づきフィルタ処理される。ニュースフィード記事は、ユーザの親和性によりフィルタ処理された生成コンテンツの順位または属性に基づき最も関連のある情報をユーザへ配信するように生成され得る。同様に、特定の閲覧するユーザに示される広告の社会的状況を提供するためにソーシャル・エンドースメント情報が使用され得る。
【００１４】
ソーシャルネットワーキングシステムはまた、アプリケーション開発者に、ユーザが相互作用するための新たな手法を提供するソーシャルネットワーキングシステムの機能を拡張するアプリケーションを作成する能力を提供する。例えば、アプリケーションは、ユーザが他のユーザと通信するための関心ある手法を提供するか、またはユーザがマルチプレーヤゲームに参加するか、もしくは特定のトピックに関するニュースなどのいくつかの関心ある情報を収集し、それを会員に定期的に表示できるようにし得る。アプリケーションにとって、ソーシャルネットワーキングシステムはプラットフォームに類似する。アプリケーションはまた、ソーシャルネットワーキングシステムにおける対象と考えられ得る。
【００１５】
ユーザのコネクションに基づきクラスタを決定する処理を自動化することにより、本発明の実施形態はソーシャルネットワーキングシステム上のユーザの体験を改善する。次に、ソーシャルネットワーキングは、クラスタ内のコネクションに対する共通な特徴を決定してもよく、コンテキストとクラスタの特徴とに応じていくつかのクラスタを選択的に表示または非表示にし得る。例えば、ユーザが以前の同級生と接続するためにアプリケーションを使用しているとき、ユーザが通った学校と大学を表すクラスタからのコネクションだけが表示され得る。同様に、ユーザが、ユーザの設定に応じて、ユーザの生活の中の個人的イベントについてのメッセージを一斉通信するとき、メッセージは、職場内のユーザのコネクションを表すクラスタに表示されないことがある。別の例は、選択した一組のクラスタからのコネクションだけがユーザの完全なプロファイルまたはユーザにより投稿された写真を見ることを許可することをユーザに選択させることに関わる。これらの例では、ユーザは、膨大であり得るコネクションの一覧をナビゲートし、ユーザのコネクションの各々に対しどのような情報を表示するか、または表示しないかに関する明確なコネクション毎の決定を行う必要性を免れる。
【００１６】
図１は、ソーシャルネットワーキングシステムにおけるユーザのコネクションをクラスタ化する概念を示す高レベル図である。ソーシャルネットワーキングシステムにおけるユーザ１００は複数のコネクション１２０に接続される。これらのコネクション１２０の各々はまた、ユーザのコネクション１２０だけでなく、ユーザ１００に直接接続されない他の二次コネクション１４０にも接続され得る。少なくとも２つのコネクション１２０に共通な二次コネクション１４０だけが図１では示される。加えて、限定された数のコネクション１２０と二次コネクション１４０だけが図１では示されるが、ソーシャルネットワーキングシステムは任意の数のコネクション１２０と二次コネクション１４０に対応し得る。
【００１７】
本明細書に記載されるように、本発明の実施形態はユーザのコネクション１２０の少なくともいくつかを１つまたは複数のクラスタ１６０にグループ化する。クラスタ１６０は、同一クラスタ１６０内の他のコネクション１２０との共通関係を有すると決定されたユーザの１つまたは複数のコネクション１２０を含む。以下にさらに詳細に説明されるように、コネクション１２０は、コネクション１２０の各ペア間で決定された親和性に基づきクラスタ１６０に分割され得る。コネクションのペアの親和性は、コネクション１２０が互いに接続されるか否か（例えば、コネクション１２０ａと１２０ｂが接続されコネクション１２０ｃと１２０ｅは接続されない）と、コネクション１２０が共通に有する二次コネクション１４０の数（例えば、コネクション１２０ａと１２０ｂは１つの二次コネクション１４０ｂを共通に有する）などの要因に少なくとも部分的に基づき決定され得る。
【００１８】
図２は、一実施形態によるソーシャルネットワーキングシステムの高レベルブロック図である。図２は、ソーシャルネットワーキングシステム２００、ユーザ装置２０２、およびネットワーク２０８により接続された外部アプリケーション２０４を示す。ユーザ１００は、パーソナルコンピュータまたはモバイルフォンなどのユーザ装置２０２を使用してソーシャルネットワーキングシステム２００と相互作用する。ユーザ装置２０２は、ウェブブラウザまたは固有アプリケーションなどのアプリケーションを通じてソーシャルネットワーキングシステム２００と通信し得る。ユーザ装置２０２とソーシャルネットワーキングシステム２００間の典型的な相互作用は、ソーシャルネットワーキングシステム２００の他のユーザのプロファイルを見る、メディア項目を投稿しそれと相互作用する、グループに加入する、イベントを列挙しイベントへの出席を確認する、現地でチェックインする、いくつかのページを「いいね！」する、ページを作成する、および社会的交流を容易にする他のタスクを行うなどの動作を含む。
【００１９】
ソーシャルネットワーキングシステム２００は、そのユーザとソーシャルネットワーキング環境内に表された対象とについての情報、およびユーザと対象間の関係を記憶するために使用される複数のコンポーネントを含む。ソーシャルネットワーキングシステム２００は、上に説明したようなシステムのユーザ装置２０２に対するいくつかのアクションを可能にするためのコンポーネントを追加的に含む。ソーシャルグラフ２１０は、各ユーザ１００が有するソーシャルネットワーキングシステム２００の他のユーザとのコネクションを記憶する。ソーシャルグラフ２１０はまた、いくつかの実施形態では、二次コネクションを記憶し得る。したがってコネクションは直接または間接的であり得る。例えば、ユーザＡがユーザＢの一次コネクションであり、ＢはＣの一次コネクションであれば、Ｃはソーシャルグラフ２１０上のＡの二次コネクションである。
【００２０】
アクション記憶装置２１５は、ソーシャルネットワーキングシステム２００のユーザにより行われたアクションを記憶する。アクションは、それらのアクションに関連付けられた時間の指示と、アクションに関する任意の対象への参照とを含み得る。加えて、アクション記憶装置２１５は、ユーザと対象間の過去の相互作用に関する統計値を記憶し得る。例えば、アクション記憶装置２１５は、３０日以内のユーザによるウォール投稿の数、３０日以内にユーザにより投稿された写真の数、および３０日以内にユーザのコメントを受信した個別のユーザの数を含み得る。２人のユーザすなわちユーザＡとユーザＢとの間の所定のリンクに対して、アクション記憶装置は、ＡからＢへのプロファイルページの閲覧数、ＡからＢへの写真ページの閲覧数、ＡとＢとが同一写真内にタグ付けされた回数などのアクションを含んでもよく、これらのアクションは、タイムスタンプに関連付けられてもよく、または期限（例えば、２４時間、９０日など）によりフィルタ処理されてもよい。アクション記憶装置２１５内に記録されるアクションは、示唆されたアクションの選択肢をソーシャルネットワーキングシステム２００がユーザに提供することに応答してユーザにより行われる作られた（ｆａｒｍｅｄ）アクションであり得る。
【００２１】
最上位友達予想器２１６は、ユーザ１００がコネクション１２０と相互作用する可能性がどの程度あるかを予測する得点を計算するように得点化関数を使用する。得点は、コネクション１２０と相互作用することに対するユーザの関心を表し得る。一実施形態では、コネクション１２０を有するユーザ１００の過去の相互作用は、コネクション１２０との同様な相互作用に対するユーザの将来の関心のシグナルとして使用される。このシグナルは、コネクション１２０がユーザの最上位友達のうちの１人か否かに対する代用となる。得点に基づき、ソーシャルネットワーキングシステムはユーザ１００に対する最上位友達を決定する。機械学習機２３５は、最上位友達を決定するために使用される得点化関数を決定する機械学習アルゴリズムを実装する。最上位友達予想器２１６の実施形態は２０１１年４月２５日出願の米国仮特許出願第１３／０９３，７４４号明細書に開示されており、その全体を参照として本明細書に援用する。
【００２２】
図３は、本発明の一実施形態による、ユーザの要求に基づき最上位友達を決定するための処理を示す。ソーシャルネットワーキングシステム２００はユーザ１００に対する最上位友達の要求を受信する（３１０）。本発明のいくつかの実施形態では、要求は、戻される最上位友達の数を指定し得る。次に、ソーシャルネットワーキングシステム２００は、プロファイルからの静的データと共に、ユーザ１００とユーザのコネクション１２０との過去の相互作用に関する統計値を取得する（３２０）。ソーシャルネットワーキングシステム２００は、最上位友達の一覧を決定する（３４０）前にコネクション１２０の各々に対して得点を計算し（３３０）、その最上位友達の一覧を出力として提供する（３５０）。いくつかの実施形態では、出力として提供される最上位友達の一覧は各最上位友達に割り当てられた得点によりソートされる。
【００２３】
認証管理部２１４は、ユーザ装置２０２上のユーザ１００をソーシャルネットワーキングシステム２００上のソーシャルグラフに属するものとして認証する。認証管理部２１４は、ソーシャルネットワーキングシステム２００に対応するアプリケーションを有する任意のユーザ装置２０２にユーザ１００がログインできるようにする。いくつかの実施形態では、ＡＰＩ  ２１２は、外部アプリケーション２０４を通じてユーザを検証するために、認証管理部２１４と連動して働く。
【００２４】
ソーシャルネットワーキングシステム２００はまた、１つまたは複数のプラットフォームアプリケーション２４５と１つまたは複数の外部アプリケーション２０４とに対応し得る。プラットフォームアプリケーション２４５は、ソーシャルネットワーキングシステム２００内で動作するアプリケーションであるが、ソーシャルネットワーキングシステム２００のオペレータ以外の第三者により提供され得る。プラットフォームアプリケーション２４５は、ソーシャルゲーム、メッセージサービス、およびソーシャルネットワーキングシステム２００により提供されるソーシャルプラットフォームを使用する任意の他のアプリケーションを含み得る。外部アプリケーション２０４は、ＡＰＩ  Ｂ２０を通じてソーシャルネットワーキングシステム２００と相互作用し得る。外部アプリケーション２０４は、ＡＰＩ  Ｂ２０により対応する様々な動作を行うことができる。例えば、ユーザが、ソーシャルネットワーキングシステム２００を通じて互いにメッセージを送信したり、またはソーシャルネットワーキングシステム２００を通じて送られる広告を示すことができるようにする。
【００２５】
親和性計算器２２０はコネクションのペアに対する親和性を計算する。コネクションのペアの親和性はコネクションのペア間の関係の尺度であり、とりわけ（ａ）コネクション１２０が互いにソーシャルグラフ２１０において接続されるか否かと（ｂ）コネクション１２０が共通に有する最上位友達の相対数とに応じる。親和性計算器２２０は、コネクションのペアの各々に対する最上位友達を取得するか、または入力と共に最上位友達を取得
する要求を、最上位友達予想器２１６へ送信し得る。いくつかの実施形態では、親和性は次のように定義される。
【００２６】
【数１】
2014526092.tif 000003
ここで、Ａ（ｆｉ，ｆｊ）はコネクションｆｉおよびｆｊの親和性であり、ｉ＝１，２，．．．、かつｉ≠ｊであり、
αは予め規定された定数であり、
コネクションｆｉおよびｆｊに対して、ｉ＝１，２，．．．、かつｉ≠ｊであるとき、１（ｆｉ，ｆｊ）は、コネクションｆｉとｆｊとが互いに接続されるか否かに応じて１または０であることを示し、
Ｔ（ｆｉ）は、最上位友達の一覧を一組として戻す最上位友達予想器２１６により計算される最上位友達関数であり、
Ｎ（Ｓ）は組Ｓ内の要素の数を戻す関数である。
これは、ユーザの２つのコネクション間の親和性を計算するための機構の単なる一例であり、様々な他の計算が使用され得る。例えば、関数１（ｆｉ，ｆｊ）は、ｆｉとｆｊとが互いに接続されれば、１以外の定数を戻し得る。
【００２７】
式（１）の右辺の第２項の分母は、共通の最上位友達の数を示す分子の正規化を表す。正規化は、ソーシャルグラフ２１０から識別される最上位友達の数の中のユーザ間の差異を相殺するために行われる。予め規定された定数αを変化させることにより、親和性計算器２２０は、２つのコネクションの連結性（ｃｏｎｎｅｃｔｅｄｎｅｓｓ）に割り当てられた相対的重みと、２つのコネクションが共通に有する最上位友達の相対数とを変化させることができる。
【００２８】
図４は、一実施形態においてクラスタモジュール２１８により行われる処理を示す。クラスタモジュール２１８は、ユーザのコネクション１２０を、コネクション１２０間の親和性に基づき１つまたは複数のクラスタ１６０にグループ化する責任を負う。一実施形態では、クラスタモジュール２１８は、コネクションのペア１２０毎に親和性計算器２２０に直接要求して、コネクション１２０により表される行と列を有する親和性の行列を受信する（４１０）。行列以外の表現とデータ構造もまた、コネクションのペア１２０間の親和性を記憶するために使用され得る。別の実施形態では、クラスタモジュール２１８は、最上位友達予想器２１８からコネクション１２０の各々に対する最上位友達を最初に取得し、入力としてこの最上位友達を親和性計算器へ提供する。図１に示された例示的コネクション１２０に基づく親和性行列の例を表１に示す。行列以外のデータ構造を含む表現の形式は当業者にとって自明であろう。
【００２９】
【表１】
2014526092.tif 000004
次に、クラスタモジュール２１８は行列内で最も高い親和性を有するコネクションのペアを決定する（４２０）。この例では、コネクション１２０ｃと１２０ｄとが最も高い親和性を有すると決定されるので、コネクション１２０ｃと１２０ｄとはクラスタに入れられる最初のものとなる。クラスタモジュール２１８はまた、表２に示すように、残りのコネクション１２０ａ、１２０ｂ、１２０ｅ、および１２０ｆの各々のコネクション１２０ｃと１２０ｄとに対する親和性の平均値を得る（４３０）。次に、クラスタモジュール２１８は、コネクション１２０ｃと１２０ｄとをクラスタ１６０ａとして示される新たなクラスタに縮約する（４４０）。表２に示すように、この新たなクラスタ１６０ａはコネクション１２０ｃと１２０ｄとを置換し、それらのコネクションの親和性の平均値は、クラスタ１６０ａの他のコネクション１２０ａ、１２０ｂ、１２０ｅ、および１２０ｆとの親和性に使用される。
【００３０】
【表２】
2014526092.tif 000005
最初のクラスタ１６０ａが作成されると、クラスタモジュール２１８はこの処理を繰り返す。この処理は、閾値を越える残りの親和性が存在しなくなる（コネクション１２０のより大きなクラスタ１６０へのさらなる縮約を正当化するには既存のコネクション１２０およびクラスタ１６０が十分に相互関係付けされていないということを示す）まで繰り返され得る。この実施形態では、閾値親和性値は２．０であり、この閾値を越える親和性が存在するので、クラスタモジュール２１８は、コネクションとクラスタ間の親和性の新たな行列とともにステップ４２０へ戻る。この例では、ステップ４２０へ進む前に受信された行列を表２に示す。
【００３１】
この例を続けると、表２に示すように、コネクション１２０ａと１２０ｂとは最も高い親和性を有すると決定される。上述の処理を繰り返すことにより、コネクション１２０ａと１２０ｂとは新たなクラスタ１６０ｂに縮約され、新たな親和性がコネクション１２０
ａと１２０ｂとの親和性を平均化することによりクラスタ１６０ｂに対して計算される。その結果を表３に示す。
【００３２】
【表３】
2014526092.tif 000006
表３から、最も高い残りの親和性がコネクション１２０ｅとクラスタ１６０ａとの間に存在する。したがって、この最も高い親和性に関連付けられたコネクションが（すなわち、既にクラスタ１６０ａ内に存在するコネクション１２０ｃと１２０ｄだけでなくコネクション１２０ｅも）クラスタ１６０ａに組み込まれる。この新たなクラスタ１６０ａの親和性は、上に説明したようにクラスタ１６０ａ内のコネクション１２０の親和性を平均化することから取得されてもよく、結果として表４を生じる。コネクション１２０ｅとクラスタ１６０ａとの間の単純平均が示されるが、クラスタ内のコネクションの数に基づく加重平均など他の可能性が利用され得る。
【００３３】
【表４】
2014526092.tif 000007
この例では示さないが、２つのクラスタ１６０自体は、コネクション１２０が他のコネクション１２０またはクラスタ１６０と組み合わされることができるのと同じ手法で合成クラスタに縮約され得る。上述のように、この例における親和性閾値は２．０である。この閾値を越える残りの親和性は存在しないので、クラスタモジュール２１８は、コネクション１２０とクラスタ１６０とをより大きな新たなクラスタ１６０に組み込むことを停止する。このようにして、クラスタモジュール２１８は、クラスタ１６０の識別子と各クラスタ１６０内に存在するコネクション１２０とを含み得るクラスタ化処理の結果を出力する。
【００３４】
クラスタモジュール２１８は、コネクションおよびクラスタの中間組（ｉｎｔｅｒｍｅｄｉａｔｅ  ｓｅｔ）だけでなくクラスタ１６０の最終出力も当業者らにとって知られたデータ構造である樹状図上に記憶する。図５は、先の例におけるクラスタ１６０を表すために使用される樹状図の一例を示す。一実施形態では、距離５２０により示される（コネクション１２０により表される葉から測定される）個々の樹状図枝の高さは次式で与えられる。
【００３５】
ｄ（ａｉ，ａｊ）＝１／Ａ（ａｉ，ａｊ）    （１）
ここで、Ａ（ａｉ，ａｊ）はコネクションまたはクラスタａｉおよびａｊの親和性であり、ｉ＝１，２，．．．、かつｉ≠ｊであり、
ｄ（ａｉ，ａｊ）は、ｉ＝１，２，．．．、かつｉ≠ｊであるコネクションまたはクラスタａｉおよびａｊに対応する樹状図の枝の高さである。より一般的には、距離５２０は、式（１）に示される距離５２０の任意の一定倍数であってもよく、またはペア的親和性（ｐａｉｒ−ｗｉｓｅ  ａｆｆｉｎｉｔｙ）に反比例する他の所定の関係であってもよい。
【００３６】
いくつかの実施形態では、クラスタモジュール２１８は、出力のためのクラスタ１６０を決定した後、クラスタ１６０を図５に示すような単一の汎用クラスタにさらに縮約し得る。その結果のデータ構造（コネクション間に枝の構造を含む）は、システムが可変閾値に基づきクラスタを迅速に生成できるようにする。例えば、閾値を厳しくする（例えば、図５で、バーを低くすることによって表される、閾値親和性を増すことにより）ことによってクラスタ化を少なくし、一方、閾値を緩和することでクラスタ化を多くする。これにより、ユーザ１００が、所望量のユーザのコネクション１２０のクラスタ化を得るために閾値を変化できるようにする。
【００３７】
図６は、ソーシャルネットワーキングシステムにおけるユーザ１００のコネクションをクラスタ化するためにクラスタモジュール２１８により使用される処理の一例を示す。ソーシャルネットワーキングシステム２００は最初に、クラスタ化すべきユーザ１００のコネクション１２０を受信する（６１０）。次に、ソーシャルネットワーキングシステム２００はコネクション１２０に対する最上位友達を取得し（６２０）、先に述べたようにクラスタモジュール２１８内のコネクションの各ペア１２０に対して親和性を決定する（６３０）。再びクラスタモジュール２１８を使用して、ソーシャルネットワーキングシステムは、いくつかの実施形態では、指定された最小数のクラスタ１６０を決定するまで、または図４の反復処理においてクラスタ間の最大親和性が指定された最小値未満になるまでコネクションを繰り返し縮約する（６４０）。
【００３８】
本発明の実施形態はまた、ソーシャルネットワーキングシステム全体において表され得る組織に属するコネクションをクラスタ化するために使用され得る。
本発明の実施形態の前述の記載は、例示目的のために提示されており網羅的であることを目的としない、または開示された正確な形式に本発明を限定することを目的としない。上記開示に照らし多くの修正形態と変形形態が可能であるということを当業者であれば理解するであろう。
【００３９】
本明細書のいくつかの部分は、情報に対する動作のアルゴリズムとシンボル表現という意味で本発明の実施形態について説明する。これらのアルゴリズム的説明および表現は、その作業の本質を他の当業者に効果的に伝達するためにデータ処理技術の当業者により一般的に用いられる。これらの操作は、機能的に、コンピュータ的に、または論理的に説明されたが、コンピュータプログラムまたはそれと等価な電気回路、マイクロコードなどにより実装されるものと理解される。さらに、一般性を失うことなくこれらの動作の構成をモジュールと呼ぶこともまたしばしば便利であることが理解される。説明された動作およびそれらの関連するモジュールはソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組合せによって具現され得る。
【００４０】
本明細書に記載のステップ、動作、または処理の任意のものは、１つまたは複数のハードウェアまたはソフトウェアモジュールにより単独でまたは他の装置と組み合わせて実行または実装され得る。一実施形態では、ソフトウェアモジュールは、説明したステップ、動作、または処理の任意なもの、またはそれらのすべてを行うためのコンピュータプロセ
ッサにより実行することができるコンピュータプログラムコードを含むコンピュータ可読媒体を含むコンピュータプログラム製品と共に実装される。
【００４１】
本発明の実施形態はまた、本明細書内の動作を行うための装置に関係し得る。この装置は特に、必要な目的のために構築されてもよく、および／またはコンピュータ内に記憶されたコンピュータプログラムにより選択的に活性化または再構成される汎用コンピュータ装置を含み得る。このようなコンピュータプログラムは、コンピュータシステムバスに結合され得る非一時的な有形のコンピュータ可読記憶媒体または電子命令を記憶するのに好適な任意のタイプの媒体に記憶され得る。さらに、本明細書において参照する任意のコンピュータシステムは、シングルプロセッサを含み得るか、または計算能力向上のためのマルチプロセッサプ設計を採用するアーキテクチャであり得る。
【００４２】
本発明の実施形態はまた、本明細書に記載の計算処理により生成される製品に関係し得る。このような製品は計算処理から生じる情報を含んでもよく、情報は非一時的で有形のコンピュータ可読記憶媒体上に記憶され、コンピュータプログラム製品または本明細書に記載の他のデータ組み合わせの任意の実施形態を含み得る。
【００４３】
最後に、本明細書で使用される言語は読み易さと教示的目的のために主として選択されており、本発明の主題を定義または限定するために選択されたものでないことがある。したがって、本発明の範囲は、この詳細明細書により限定されるのではなく、むしろ本明細書に基づく応用に関する任意の特許請求の範囲により限定されるように意図されている。したがって、本発明の実施形態の開示は、以下の特許請求の範囲に記載される本発明の範囲の限定ではなく例示となるように意図されている。
【図１】
2014526092.tif 000008
【図２】
2014526092.tif 000009
【図３】
2014526092.tif 000010
【図４】
2014526092.tif 000011
【図５】
2014526092.tif 000012
【図６】
2014526092.tif 000013
【国際調査報告】
2014526092.tif 000014