(57)【特許請求の範囲】
【請求項１】
１つ以上のコンピューティング・デバイスが、複数のノードとノード間の複数のエッジとを含むソーシャル・グラフにアクセスする工程であって、前記ノードは、ソーシャル・ネットワーキング・システムのユーザに対応するユーザ・ノードを含む、工程と、
１つ以上のコンピューティング・デバイスが、第１のユーザ・ノードに対応するユーザの特定のユーザ特性を表す特性スコアが割り当てられていない第１のユーザ・ノードを識別する工程と、
１つ以上のコンピューティング・デバイスが、１つ以上の第２の近隣ノードを識別する工程であって、各第２の近隣ノードは該ノードに対応する前記特定のユーザ特性を表す特性スコアを有し、各第２の近隣ノードは、前記ソーシャル・グラフにおいて少なくとも１つのエッジによって前記第１のユーザ・ノードに接続されている、工程と、
１つ以上のコンピューティング・デバイスが、識別された前記１つ以上の第２の近隣ノードのうちの１または複数の第２の近隣ノードを選択する工程と、
１つ以上のコンピューティング・デバイスが、各第２の近隣ノードと前記ソーシャル・グラフにおいて１つのエッジによって該第２の近隣ノードに接続されている１つ以上の他のユーザ・ノードの各々とについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードのユーザに対する親和性を決定する工程と、
１つ以上のコンピューティング・デバイスが、各第２の近隣ノードについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードに対応するユーザに対する前記親和性が閾値よりも大きいとき、該第２の近隣ノードを該他のユーザ・ノードに接続するエッジを、該第２の近隣ノードの数に対応する第１の数のエッジに含める工程と、
１つ以上のコンピューティング・デバイスが、前記第１のユーザ・ノードに特性スコアを割り当てる工程であって、前記特性スコアは、選択された各第２の近隣ノードの特性スコアを、該第２の近隣ノードに対応するエッジの前記第１の数により除算した値の合計である、工程と、
を備える方法。
【請求項２】
前記ソーシャル・グラフにおいて前記第２の近隣ノードを他のユーザ・ノードに接続する前記エッジは、前記第２の近隣ノードから離れる向きの指向性のエッジを含む、請求項１に記載の方法。
【請求項３】
ユーザ・ノードのユーザのユーザ特性は、前記ソーシャル・ネットワーキング・システムのコンセプトに対する該ユーザの態度に相当する、請求項１に記載の方法。
【請求項４】
ソフトウェアを具現する１以上の非一時的なコンピュータ可読記憶媒体であって、前記ソフトウェアは実行時、
複数のノードとノード間の複数のエッジとを含むソーシャル・グラフにアクセスする工程であって、前記ノードは、ソーシャル・ネットワーキング・システムのユーザに対応するユーザ・ノードを含む、工程と、
第１のユーザ・ノードに対応するユーザの特定のユーザ特性を表す特性スコアが割り当てられていない第１のユーザ・ノードを識別する工程と、
１つ以上の第２の近隣ノードを識別する工程であって、各第２の近隣ノードは該ノードに対応する前記特定のユーザ特性を表す特性スコアを有し、各第２の近隣ノードは、前記ソーシャル・グラフにおいて少なくとも１つのエッジによって前記第１のユーザ・ノードに接続されている、工程と、
識別された前記１つ以上の第２の近隣ノードのうちの１または複数の第２の近隣ノードを選択する工程と、
各第２の近隣ノードと前記ソーシャル・グラフにおいて１つのエッジによって該第２の近隣ノードに接続されている１つ以上の他のユーザ・ノードの各々とについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードのユーザに対する親和性を決定する工程と、
各第２の近隣ノードについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードに対応するユーザに対する前記親和性が閾値よりも大きいとき、該第２の近隣ノードを該他のユーザ・ノードに接続するエッジを、該第２の近隣ノードの数に対応する第１の数のエッジに含める工程と、
前記第１のユーザ・ノードに特性スコアを割り当てる工程であって、前記特性スコアは、選択された各第２の近隣ノードの特性スコアを、該第２の近隣ノードに対応するエッジの前記第１の数により除算した値の合計である、工程と、
を行うように構成されている、媒体。
【請求項５】
前記ソーシャル・グラフにおいて前記第２の近隣ノードを他のユーザ・ノードに接続する前記エッジは、前記第２の近隣ノードから離れる向きの指向性のエッジを含む、請求項４に記載の媒体。
【請求項６】
ユーザ・ノードのユーザのユーザ特性は、前記ソーシャル・ネットワーキング・システムのコンセプトに対する該ユーザの態度に相当する、請求項４に記載の媒体。
【請求項７】
１つ以上のプロセッサと、前記プロセッサに結合されており、前記プロセッサによって実行可能な命令を含むメモリと、を備えるシステムであって、前記プロセッサは、前記命令を実行する時、
複数のノードとノード間の複数のエッジとを含むソーシャル・グラフにアクセスする工程であって、前記ノードは、ソーシャル・ネットワーキング・システムのユーザに対応するユーザ・ノードを含む、工程と、
第１のユーザ・ノードに対応するユーザの特定のユーザ特性を表す特性スコアが割り当てられていない第１のユーザ・ノードを識別する工程と、
１つ以上の第２の近隣ノードを識別する工程であって、各第２の近隣ノードは該ノードに対応する前記特定のユーザ特性を表す特性スコアを有し、各第２の近隣ノードは、前記ソーシャル・グラフにおいて少なくとも１つのエッジによって前記第１のユーザ・ノードに接続されている、工程と、
識別された前記１つ以上の第２の近隣ノードのうちの１または複数の第２の近隣ノードを選択する工程と、
各第２の近隣ノードと前記ソーシャル・グラフにおいて１つのエッジによって該第２の近隣ノードに接続されている１つ以上の他のユーザ・ノードの各々とについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードのユーザに対する親和性を決定する工程と、
各第２の近隣ノードについて、該第２の近隣ノードに対応するユーザの、前記他のユーザ・ノードに対応するユーザに対する前記親和性が閾値よりも大きいとき、該第２の近隣ノードを該他のユーザ・ノードに接続するエッジを、該第２の近隣ノードの数に対応する第１の数のエッジに含める工程と、
前記第１のユーザ・ノードに特性スコアを割り当てる工程であって、前記特性スコアは、選択された各第２の近隣ノードの特性スコアを、該第２の近隣ノードに対応するエッジの前記第１の数により除算した値の合計である、工程と、
を行うように構成されている、システム。
【請求項８】
前記ソーシャル・グラフにおいて前記第２の近隣ノードを他のユーザ・ノードに接続する前記エッジは、前記第２の近隣ノードから離れる向きの指向性のエッジを含む、請求項７に記載のシステム。
【請求項９】
ユーザ・ノードのユーザのユーザ特性は、前記ソーシャル・ネットワーキング・システムのコンセプトに対する該ユーザの態度に相当する、請求項７に記載のシステム。
【請求項１０】
第１のユーザが前記ソーシャル・ネットワーキング・システムのサービス利用規約に違反したことがあるか否かに基づいて、前記特性スコアが前記第１のユーザに割り当てられる、請求項１に記載の方法。
【請求項１１】
前記特性スコアに基づき、第１のユーザを悪い挙動のユーザに分類する工程と、
前記分類する工程の分類に基づき、前記第１のユーザに関連するソーシャル・ネットワーク・アカウントを無効化する工程と、
をさらに備える、請求項１に記載の方法。
【請求項１２】
前記特性スコアに基づき、第１のユーザを悪い挙動のユーザに分類する工程と、
前記分類する工程の分類に基づき、前記第１のユーザに関するソーシャル・ネットワークの機能を限定する工程と、
をさらに備える、請求項１に記載の方法。
【請求項１３】
前記特性スコアに基づき、第１のユーザを悪い挙動のユーザに分類する工程と、
前記分類する工程の分類に基づき、前記第１のユーザによって前記ソーシャル・ネットワーキング・システムにポストされたコンテンツをブロックする工程と、
をさらに備える、請求項１に記載の方法。
【請求項１４】
前記ソーシャル・グラフにおいて、１つのエッジにより前記第２の近隣ノードに接続された前記他のユーザ・ノードの各々に関して、該他のユーザ・ノードに対応する前記ユーザの、前記第２の近隣ノードに対応する前記ユーザに対する親和性を決定する工程をさらに備え、
前記第２の近隣ノードに対応する前記ユーザの、前記他のユーザ・ノードに対応する前記ユーザに対する前記親和性が、該他のユーザ・ノードに対応するユーザの、前記第２の近隣ノードに対応する前記ユーザに対する前記親和性よりも大きいとき、前記第２の近隣ノードを該他のユーザ・ノードに接続するエッジを前記第１の数のエッジに含める、請求項１に記載の方法。
【請求項１５】
前記ソーシャル・グラフにおいて、１つのエッジにより前記第２の近隣ノードに接続された前記他のユーザ・ノードの各々に関して、該他のユーザ・ノードに対応する前記ユーザの、前記第２の近隣ノードに対応する前記ユーザに対する親和性を決定する工程をさらに備え、
該他のユーザ・ノードに対応する前記ユーザの、前記第２の近隣ノードに対応する前記ユーザに対する前記親和性が、閾値よりも大きいとき、前記第２の近隣ノードを該他のユーザ・ノードに接続するエッジを前記第１の数のエッジに含める、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、一般にソーシャル・グラフに関する。
【背景技術】
【０００２】
ソーシャル・ネットワーキング・ウェブサイトを含むソーシャル・ネットワーキング・システムは、そのユーザ（人または組織）がソーシャル・ネットワーキング・システムと、またソーシャル・ネットワーキング・システムを通じて互いに対話することを可能にする。
【０００３】
ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システム内でそのユーザに関連付けられているユーザ・プロフィールを作成し記憶する。ユーザ・プロフィールは、人口統計情報、通信チャネル情報、およびユーザの個人的関心に関する情報を含んでもよい。また、ソーシャル・ネットワーキング・システムは、ユーザからの入力と共に、ソーシャル・ネットワーキング・システムの他のユーザとのユーザの関係の記録を作成および記憶し、サービス（たとえば、ウォール投稿、写真の共有、イベントの主催、メッセージング、ゲーム、または広告）を提供し、ユーザ間またはユーザの間でのソーシャル対話を容易にする。
【０００４】
ソーシャル・ネットワーキング・システムは、１または複数のネットワークを通じて、そのサービスに関係するコンテンツまたはメッセージをユーザの移動体コンピューティング・デバイスまたは他のコンピューティング・デバイスに送信する。ユーザは、ソーシャル・ネットワーキング・システム内のそのユーザのユーザ・プロフィールおよび他のデータにアクセスするために、ユーザの移動体コンピューティング・デバイスまたは他のコンピューティング・デバイス上にソフトウェア・アプリケーションをインストールしてもよい。ソーシャル・ネットワーキング・システムは、ユーザに接続された他のユーザの集約されたストーリのニュースフィードなど、コンテンツ・オブジェクトのパーソナライズされたセットを生成し、ユーザに対して表示してもよい。
【図面の簡単な説明】
【０００５】
【図１】ソーシャル・ネットワーキング・システムに関連付けられている一例のネットワーク環境の図。
【図２】一例のソーシャル・グラフの図。
【図３】ユーザ特性のスコアを決定するための一例の方法を示す図。
【図４】特性スコアの一例の計算を示す図。
【図５】一例のコンピュータ・システムの図。
【発明を実施するための形態】
【０００６】
特定の実施形態では、特定のユーザ特性を有する可能性の高いソーシャル・ネットワーキング・システムのユーザを推測するための方法について記載する。特定の実施形態では、最初に機械学習アルゴリズムまたは他の適切な方法を用いて、ソーシャル・ネットワーキング・システムのソーシャル・グラフにおいて、特定のユーザ特性を有するユーザに対応する１組のユーザ・ノードを識別し、各識別されたユーザ・ノードにスコアを割り当てる。特定の実施形態では、次いで、ソーシャル・グラフにおける他のユーザ・ノードについてのスコアを推定するために、識別されたユーザ・ノードをシードとして用いてよい。ユーザ・ノードのスコアは、割り当てられたスコアを有するユーザ・ノードに対するソーシャル・グラフにおけるそのユーザ・ノードのつながりに基づいて推定されてもよい。ユーザ・ノードについての推定されたスコアの値は、そのユーザ・ノードが特定のユーザ特
性を有するユーザに対応する見込みを示してもよい。
【０００７】
図１は、ソーシャル・ネットワーキング・システムに関連付けられている例示的なネットワーク環境１００を示す。ネットワーク環境１００は、互いにネットワーク１１０によって接続されたユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０を含む。図１は、ユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０の特定の構成を示すが、この開示は、ユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０の任意の好適な構成を企図する。限定するものとしてではなく一例として、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０の２以上は、ネットワーク１１０をバイパスして互いに直接的に接続されてもよい。別の例として、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０の２以上が、全体として、または部分的に互いに物理的に、または論理的に同じ場所にあってもよい。さらに、図１は、特定の数のユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を示すが、この開示は、任意の好適な数のユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を企図する。限定するものとしてではなく一例として、ネットワーク環境１００は、複数のユーザ１０１、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、サードパーティ・システム１７０、およびネットワーク１１０を含んでもよい。
【０００８】
特定の実施形態では、ユーザ１０１は、ソーシャル・ネットワーキング・システム１６０と、またはソーシャル・ネットワーキング・システム１６０を通じて対話、すなわち通信する個人（人間のユーザ）、エンティティ（たとえば、企業、事業者、またはサードパーティ・アプリケーション）、または（たとえば、個人またはエンティティの）グループであってよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、オンライン・ソーシャル・ネットワークをホストするネットワークアドレス指定可能なコンピューティング・システムであってよい。ソーシャル・ネットワーキング・システム１６０は、たとえばユーザプロフィール・データ、コンセプトプロフィール・データ、ソーシャル・グラフ情報、またはオンライン・ソーシャル・ネットワークに関係する他の好適なデータなど、ソーシャル・ネットワーキング・データを生成、記憶、受信、および送信する。ソーシャル・ネットワーキング・システム１６０は、ネットワーク環境１００の他の構成要素によって、直接的に、またはネットワーク１１０を通じてアクセスされてもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、ユーザ１０１がたとえば適切なプライバシ設定を設定することによってなど、自分達のアクションをソーシャル・ネットワーキング・システム１６０によって記録させる、または他のシステム（たとえば、サードパーティ・システム１７０）と共有させることについてオプトインまたはオプトアウトすることを可能にする認可サーバ（または他の適切な構成要素）を含んでもよい。ユーザのプライバシ設定は、そのユーザに関連付けられているどの情報が記録されるか、そのユーザに関連付けられている情報がどのように記録されるか、そのユーザに関連付けられている情報がいつ記録されるか、そのユーザに関連付けられている情報を誰が記録するか、そのユーザに関連付けられている情報が誰と共有されるか、およびそのユーザに関連付けられている情報が何の目的で記録され共有されるかを決定することができる。認可サーバは、ブロッキング、データのハッシュ化、匿名化、または他の適切な技術を通じて、ソーシャル・ネットワーキング・システム３０のユーザの１以上のプライバシ設定を適切に実施するために用いられる。特定の実施形態では、サードパーティ
・システム１７０は、ウェブサイトまたはアプリケーションをホストするネットワークアドレス指定可能なコンピューティング・システムであってよい。サードパーティ・システム１７０は、たとえば、ウェブ・ページ、テキスト、画像、映像、オーディオ、またはアプリケーションなど、サードパーティ・システム・データを生成、記憶、受信、および送信する。サードパーティ・システム１７０は、ネットワーク環境１００の他の構成要素によって、直接的に、またはネットワーク１１０を通じてアクセスされてもよい。特定の実施形態では、１または複数のユーザ１０１が１または複数のクライアント・システム１３０を使用し、ソーシャル・ネットワーキング・システム１６０またはサードパーティ・システム１７０にアクセスし、データを送り、それらからデータを受信してもよい。クライアント・システム１３０は、ソーシャル・ネットワーキング・システム１６０またはサードパーティ・システム１７０に直接的に、ネットワーク１１０を通じて、またはサードパーティ・システムを通じてアクセスしてもよい。限定するものとしてではなく一例として、クライアント・システム１３０は、サードパーティ・システム１７０にソーシャル・ネットワーキング・システム１６０を通じてアクセスしてもよい。クライアント・システム１３０は、たとえばパーソナル・コンピュータ、ラップトップ・コンピュータ、携帯電話、スマートフォン、またはタブレット・コンピュータなど、任意の好適なコンピューティング・デバイスであってよい。
【０００９】
この開示は、任意の好適なネットワーク１１０を企図する。限定するものとしてではなく一例として、ネットワーク１１０の１または複数の部分は、アドホック・ネットワーク、イントラネット、エクストラネット、仮想プライベート・ネットワーク（ＶＰＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、無線ＬＡＮ（ＷＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、無線ＷＡＮ（ＷＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、インターネットの一部分、公衆交換電話網（ＰＳＴＮ）の一部分、携帯電話ネットワーク、またはこれらの２以上の組合せを含んでもよい。ネットワーク１１０は、１または複数のネットワーク１１０を含んでもよい。
【００１０】
リンク１５０は、クライアント・システム１３０、ソーシャル・ネットワーキング・システム１６０、およびサードパーティ・システム１７０を通信ネットワーク１１０に、または互いに接続する。この開示は、任意の好適なリンク１５０を企図する。特定の実施形態では、１または複数のリンク１５０は、１または複数の有線（たとえば、デジタル加入者線（ＤＳＬ）またはＤＯＣＳＩＳ（Ｄａｔａ  Ｏｖｅｒ  Ｃａｂｌｅ  Ｓｅｒｖｉｃｅ
Ｉｎｔｅｒｆａｃｅ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ）など）、無線（たとえば、Ｗｉ−ＦｉまたはＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）など）、または光（たとえば、同期光ネットワーク（ＳＯＮＥＴ）または同期デジタル・ハイアラーキ（ＳＤＨ）など）リンクを含む。特定の実施形態では、１または複数のリンク１５０は、それぞれ、アドホック・ネットワーク、イントラネット、エクストラネット、ＶＰＮ、ＬＡＮ、ＷＬＡＮ、ＷＡＮ、ＷＷＡＮ、ＭＡＮ、インターネットの一部分、ＰＳＴＮの一部分、セルラ技術ベースのネットワーク、衛星通信技術ベースのネットワーク、別のリンク１５０、または２以上のそのようなリンク１５０の組合せを含む。リンク１５０は、必ずしもネットワーク環境１００全体を通じて同じであることを必要としない。１または複数の第１のリンク１５０は、１または複数の点で１または複数の第２のリンク１５０と異なってもよい。
【００１１】
図２は、例示的なソーシャル・グラフ２００を示す。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、１または複数のソーシャル・グラフ２００を１または複数のデータ・ストア内に記憶する。特定の実施形態では、ソーシャル・グラフ２００は、複数のノード（複数のユーザ・ノード２０２または複数のコンセプト・ノード２０４を含んでもよい）と、それらのノードを接続する複数のエッジ２０６とを含んでもよい。図２に示されている例示的なソーシャル・グラフ２００は、説明のために、２次元の
視覚マップ表現で示されている。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０、クライアント・システム１３０、またはサードパーティ・システム１７０は、適切な用途のためにソーシャル・グラフ２００および関連するソーシャル・グラフ情報にアクセスする。ソーシャル・グラフ２００のノードおよびエッジは、データ・オブジェクトとして、たとえばデータ・ストア（ソーシャル・グラフ・データベースなど）内に記憶されてもよい。そのようなデータ・ストアは、ソーシャル・グラフ２００のノードまたはエッジの、１または複数の検索可能または照会可能なインデックスを含んでもよい。
【００１２】
特定の実施形態では、ユーザ・ノード２０２は、ソーシャル・ネットワーキング・システム１６０のユーザに対応する。限定するものとしてではなく一例として、ユーザは、ソーシャル・ネットワーキング・システム１６０と、またはソーシャル・ネットワーキング・システム１６０を通じて対話または通信する個人（人間のユーザ）、エンティティ（たとえば、企業、事業者、またはサードパーティ・アプリケーション）、または（たとえば、個人またはエンティティの）グループであってよい。特定の実施形態では、ユーザがアカウントをソーシャル・ネットワーキング・システム１６０に登録するとき、ソーシャル・ネットワーキング・システム１６０は、そのユーザに対応するユーザ・ノード２０２を作成し、そのユーザ・ノード２０２を１または複数のデータ・ストア内に記憶する。本明細書に記載のユーザおよびユーザ・ノード２０２は、適切な場合、登録されたユーザ、および登録されたユーザに関連付けられているユーザ・ノード２０２に及ぶ。それに加えて、または代替として、本明細書に記載のユーザおよびユーザ・ノード２０２は、適切な場合、ソーシャル・ネットワーキング・システム１６０に登録しなかったユーザに及ぶ。特定の実施形態では、ユーザ・ノード２０２は、ユーザによって提供された情報、またはソーシャル・ネットワーキング・システム１６０を含む様々なシステムによって収集された情報に関連付けられてもよい。限定するものとしてではなく一例として、ユーザは、自分の名前、プロフィール写真、連絡先情報、誕生日、性別、婚姻状態、家族状態、雇用、学歴、好み、関心、または他の人口統計情報を提供してもよい。特定の実施形態では、ユーザ・ノード２０２は、ユーザに関連付けられている情報に対応する１または複数のデータ・オブジェクトに関連付けられてもよい。特定の実施形態では、ユーザ・ノード２０２は、１または複数のウェブ・ページに対応してもよい。
【００１３】
特定の実施形態では、コンセプト・ノード２０４は、コンセプトに対応する。限定するものとしてではなく一例として、コンセプトは、場所（たとえば、映画館、レストラン、目印、または都市など）、ウェブサイト（たとえば、ソーシャル・ネットワーキング・システム１６０に関連付けられているウェブサイト、またはウェブアプリケーションサーバに関連付けられているサードパーティウェブサイトなど）、エンティティ（たとえば、人、事業者、グループ、スポーツチーム、または有名人など）、ソーシャル・ネットワーキング・システム１６０内、またはウェブアプリケーションサーバなど外部サーバ上に位置するリソース（たとえば、オーディオファイル、映像ファイル、デジタル写真、テキストファイル、構造化文書、またはアプリケーションなど）、実際の財産または知的財産（たとえば、彫刻、絵画、映画、ゲーム、楽曲、着想、写真、または書物など）、ゲーム、アクティビティ、着想もしくは理論、別の好適なコンセプト、または２以上のそのようなコンセプトに対応してもよい。コンセプト・ノード２０４は、ユーザによって提供されたコンセプトの情報、またはソーシャル・ネットワーキング・システム１６０を含む様々なシステムによって収集された情報に関連付けられてもよい。限定するものとしてではなく一例として、コンセプトの情報は、名前もしくはタイトル、１または複数の画像（たとえば、本の表紙の画像）、ロケーション（たとえば、住所または地理的ロケーション）、（ＵＲＬに関連付けられる）ウェブサイト、連絡先情報（たとえば、電話番号または電子メール・アドレス）、他の好適なコンセプト情報、またはそのような情報の任意の好適な組合せを含んでもよい。特定の実施形態では、コンセプト・ノード２０４は、コンセプト・ノ
ード２０４に関連付けられている情報に対応する１または複数のデータ・オブジェクトに関連付けられてもよい。特定の実施形態では、コンセプト・ノード２０４は、１または複数のウェブ・ページに対応してもよい。
【００１４】
特定の実施形態では、ソーシャル・グラフ２００内のノードは、ウェブ・ページを表しても、ウェブ・ページによって表されてもよい（「プロフィール・ページ」と呼ばれる）。プロフィール・ページは、ソーシャル・ネットワーキング・システム１６０によってホストされ、またはそこからアクセス可能であってもよい。また、プロフィール・ページは、サードパーティ・システム１７０に関連付けられているサードパーティウェブサイト上でホストされてもよい。限定するものとしてではなく一例として、特定の外部ウェブ・ページに対応するプロフィール・ページは、その特定の外部ウェブ・ページであってもよく、プロフィール・ページが、特定のコンセプト・ノード２０４に対応してもよい。プロフィール・ページは、他のユーザのすべてまたは選択されたサブセットによって閲覧可能であってもよい。限定するものとしてではなく一例として、ユーザ・ノード２０２は、対応するユーザがコンテンツを追加し、宣言をし、または他の方法で自分を表現する、対応するユーザプロフィールページを有してもよい。限定するものとしてではなく別の例として、コンセプト・ノード２０４は、１または複数のユーザがコンセプト・ノード２０４に対応するコンセプトに特に関連してコンテンツを追加し、宣言をし、またはユーザ自身を表現する、対応するコンセプトプロフィールページを有してもよい。
【００１５】
特定の実施形態では、コンセプト・ノード２０４は、サードパーティ・システム１７０によってホストされるサードパーティウェブページまたはリソースを表す。サードパーティウェブページまたはリソースは、要素の中でもとりわけ、コンテンツ、選択可能なアイコンもしくは他のアイコン、またはアクションもしくはアクティビティを表す（たとえば、ＪａｖａＳｃｒｉｐｔ（登録商標）、ＡＪＡＸ、またはＰＨＰコードにより実装される）他の対話可能なオブジェクトを含んでもよい。限定するものとしてではなく一例として、サードパーティウェブページは、「いいね」、「チェックイン」、「食べる」、「推奨する」、または別の好適なアクションまたはアクティビティなど、選択可能なアイコンを含んでもよい。サードパーティウェブページを閲覧するユーザは、アイコンの１つ（たとえば、「食べる」）を選択することによって、アクションを行う。これによって、クライアント・システム１３０は、ユーザのアクションを示すメッセージをソーシャル・ネットワーキング・システム１６０へ送信する。ソーシャル・ネットワーキング・システム１６０は、メッセージに応答して、ユーザに対応するユーザ・ノード２０２とサードパーティウェブページまたはリソースに対応するコンセプト・ノード２０４との間にエッジ（たとえば、「食べる」エッジ）を作成し、エッジ２０６を１または複数のデータ・ストア内に記憶する。
【００１６】
特定の実施形態では、ソーシャル・グラフ２００内の１対のノードが、１または複数のエッジ２０６によって互いに接続されてもよい。１対のノードを接続するエッジ２０６は、その対のノード間の関係を表す。特定の実施形態では、エッジ２０６は、１対のノード間の関係に対応する１または複数のデータ・オブジェクトまたは属性を含み、または表してもよい。限定するものとしてではなく一例として、第１のユーザは、第２のユーザが第１のユーザの「友達」であることを示してもよい。この示したことに応答して、ソーシャル・ネットワーキング・システム１６０は、「友達要求」を第２のユーザに送信してもよい。第２のユーザが「友達要求」を確認した場合、ソーシャル・ネットワーキング・システム１６０は、ソーシャル・グラフ２００内で第１のユーザのユーザ・ノード２０２を第２のユーザのユーザ・ノード２０２に接続するエッジ２０６を作成し、エッジ２０６をソーシャル・グラフ情報としてデータ・ストア１６４の１または複数に記憶してもよい。図２の例では、ソーシャル・グラフ２００は、ユーザ「Ａ」とユーザ「Ｂ」とのユーザ・ノード２０２間の友達関係を示すエッジ２０６と、ユーザ「Ｃ」とユーザ「Ｂ」とのユーザ
・ノード２０２間の友達関係を示すエッジとを含む。本開示は特定のユーザ・ノード２０２を接続する特定の属性を有する特定のエッジ２０６について記載し示しているが、本開示は、ユーザ・ノード２０２を接続する任意の好適な属性を有する任意の好適なエッジ２０６を企図する。限定するものとしてではなく一例として、エッジ２０６は、友達関係、家族関係、仕事関係もしくは雇用関係、ファン関係、フォロワー関係、ビジタ関係、加入者関係、主従関係、相互的関係、非相互的関係、別の好適なタイプの関係、または２以上のそのような関係を表してもよい。さらに、本開示は一般にノードを接続されているものとして記載しているが、本開示は、ユーザまたはコンセプトも接続されているものとして記載している。本明細書では、接続されているユーザまたはコンセプトへの言及は、適切な場合、ソーシャル・グラフ２００内で１または複数のエッジ２０６によって接続されているユーザまたはコンセプトに対応するノードに及ぶ。
【００１７】
特定の実施形態では、ユーザ・ノード２０２とコンセプト・ノード２０４との間のエッジ２０６は、コンセプト・ノード２０４に関連付けられているコンセプトに向かってユーザ・ノード２０２に関連付けられているユーザによって行われる特定のアクションまたはアクティビティを表してもよい。限定するものとしてではなく一例として、図２に示されているように、ユーザは、コンセプトに対して「いいね」と表明することができ、コンセプトに「通った」、コンセプトを「プレイした」、「聴いた」、「調理した」、コンセプトに「勤務した」、またはコンセプトを「見た」のであり、コンセプトのそれぞれは、エッジタイプまたはサブタイプに対応する。コンセプト・ノード２０４に対応するコンセプトプロフィールページは、たとえば、選択可能な「チェックイン」アイコン（たとえば、クリッカ可能な「チェックイン」アイコン）または選択可能な「お気に入りに追加」アイコンを含んでもよい。同様に、ユーザがこれらのアイコンをクリックした後、ソーシャル・ネットワーキング・システム１６０は、それぞれのアクションに対応するユーザのアクションに応答して「お気に入り」エッジ、または「チェックイン」エッジを作成する。限定するものとしてではなく別の例として、ユーザ（ユーザ「Ｃ」）は、特定のアプリケーション（オンラインミュージックアプリケーションであるＳＰＯＴＩＦＹ）を使用して特定の楽曲（「イマジン」）を聴く。この場合には、ソーシャル・ネットワーキング・システム１６０は、ユーザに対応するユーザ・ノード２０２と楽曲およびアプリケーションに対応するコンセプト・ノード２０４との間に「聴いた」エッジ２０６および「使用した」エッジ（図２に図示）を作成し、ユーザがその楽曲を聞き、そのアプリケーションを使用したことを示す。さらに、ソーシャル・ネットワーキング・システム１６０は、楽曲およびアプリケーションに対応するコンセプト・ノード２０４間に「プレイした」エッジ２０６（図２に図示）を作成し、特定の楽曲が特定のアプリケーションによってプレイされたことを示す。この場合には、「プレイした」エッジ２０６は、外部アプリケーション（ＳＰＯＴＩＦＹ）によって外部オーディオファイル（楽曲「イマジン」）に対して行われたアクションに対応する。本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４とを接続する特定の属性を有する特定のエッジ２０６について記載しているが、本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４とを接続する任意の好適な属性を有する任意の好適なエッジ２０６を企図する。さらに、本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４の間の単一の関係を表すエッジについて記載しているが、本開示は、ユーザ・ノード２０２とコンセプト・ノード２０４との間の１または複数の関係を表すエッジを企図する。限定するものとしてではなく一例として、エッジ２０６は、ユーザが「いいね」と表明したこと、および特定のコンセプトを使用したことの両方を表してもよい。あるいは、別のエッジ２０６が、ユーザ・ノード２０２とコンセプト・ノード２０４（図２に示されているように、ユーザ「Ｅ」に関するユーザ・ノード２０２と「ＳＰＯＴＩＦＹ」に関するコンセプト・ノード２０４）との間の関係の各タイプ（または単一の関係の複数）を表してもよい。
【００１８】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、ソーシャル
・グラフ２００内でユーザ・ノード２０２とコンセプト・ノード２０４との間にエッジ２０６を作成する。限定するものとしてではなく一例として、（たとえば、ウェブブラウザまたはユーザのクライアント・システム１３０によってホストされる専用アプリケーションを使用することによってなど）コンセプトプロフィールページを閲覧するユーザは、「いいね」アイコンをクリックまたは選択することによって、ユーザがコンセプト・ノード２０４によって表されたコンセプトに対して「いいね」と表明することを示す。これによって、ユーザのクライアント・システム１３０は、コンセプトプロフィールページに関連付けられているコンセプトに対してユーザが「いいね」と表明することを示すメッセージをソーシャル・ネットワーキング・システム１６０へ送信する。ソーシャル・ネットワーキング・システム１６０は、そのメッセージに応答して、ユーザとコンセプト・ノード２０４との間の「いいね」エッジ２０６によって示されているように、ユーザに関連付けられているユーザ・ノード２０２とコンセプト・ノード２０４との間にエッジ２０６を作成してもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、エッジ２０６を１または複数のデータ・ストア内に記憶してもよい。特定の実施形態では、エッジ２０６は、特定のユーザ・アクションに応答してソーシャル・ネットワーキング・システム１６０によって自動的に形成されてもよい。限定するものとしてではなく一例として、第１のユーザが写真をアップロードし、映画を見たか、または楽曲を聴いた場合、エッジ２０６は、第１のユーザに対応するユーザ・ノード２０２とそれらのコンセプトに対応するコンセプト・ノード２０４との間に形成されてもよい。本開示は、特定のエッジ２０６を特定の方法で形成することについて記載しているが、本開示は、任意の好適なエッジ２０６を任意の好適な方法で形成することを企図する。
【００１９】
さらに、任意の２つのノード間の分離度は、一方のノードから他方のノードにソーシャル・グラフを横断するために必要とされるホップ（またはエッジ）の最小数として定義される。２つのノード間の分離度は、ソーシャル・グラフ内の２つのノードによって表されるユーザ間またはコンセプト間の関連性の尺度と考えることができる。
【００２０】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、互いについて様々なソーシャルグラフ・エンティティのソーシャル・グラフ親和性（本明細書では「親和性」と呼ばれる）を決定してよい。親和性は、ユーザ、コンセプト、コンテンツ、アクション、広告、オンライン・ソーシャル・ネットワークに関連付けられている他のオブジェクト、またはそれらの任意の適切な組み合わせなど、オンライン・ソーシャル・ネットワークに関連付けられている特定のオブジェクト間における関係の強さまたは関心のレベルを表すことができる。また、親和性は、サードパーティ・システム１７０または他の適切なシステムに関連付けられているオブジェクトに関して決定されてもよい。各ユーザ、主題、またはコンテンツのタイプについて、ソーシャルグラフ・エンティティに対する総合親和性が確立されてもよい。総合親和性は、ソーシャルグラフ・エンティティに関連付けられているアクションまたは関係の継続的なモニタリングに基づき、変化し得る。本開示では特定の方式による特定の親和性の決定について記載するが、本開示では任意の適切な方式による任意の適切な親和性の決定が想定される。
【００２１】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、親和性係数（本明細書では「係数」と呼ばれる）を用いてソーシャル・グラフ親和性を測定または定量してよい。この係数は、オンライン・ソーシャル・ネットワークに関連付けられている特定のオブジェクト間の関係の強さを表してよい、または定量してよい。また、この係数は、ユーザが特定のアクションを行う予測される確率を測定する確率または関数を表してもよく、この確率または関数は、そのアクションについてのそのユーザの関心に基づく。このようにして、ユーザの将来のアクションは、ユーザの以前のアクションに基づいて予測されることができ、その係数は少なくとも部分的にはユーザのアクションの履歴により計算され得る。係数は、オンライン・ソーシャル・ネットワークの内外の任意の数のアク
ションを予測するために用いられてよい。限定ではなく一例として、これらのアクションは、メッセージの送信、コンテンツのポスト、またはコンテンツに対するコメントなど、様々なタイプの通信、プロフィール・ページ、メディア、または他の適切なコンテンツのアクセスまたは閲覧など、様々なタイプの観察アクション、同じグループにある、同じ写真にタグ付けされる、同じロケーションにおいてチェックインされる、もしくは同じイベントに出席する、または他の適切なアクションなど、２つ以上のソーシャルグラフ・エンティティに関する様々なタイプの同時発生情報、または他の適切なアクションを含んでよい。本開示では特定の方式による特定の親和性の測定について記載するが、本開示では任意の適切な方式による親和性の測定が想定される。
【００２２】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数を計算するために様々な因子を用いてよい。これらの因子は、例えば、ユーザ・アクション、オブジェクト間の関係のタイプ、ロケーション情報、他の適切な因子、またはそれらの任意の組み合わせを含んでよい。特定の実施形態では、係数を計算するとき、様々な因子に異なる重み付けを行ってもよい。各因子の重みは静的であってもよく、例えば、ユーザ、関係のタイプ、アクションのタイプ、ユーザのロケーションなどによって変化してもよい。因子のための格付け、そのユーザに対する総合的な係数を決定するべく、それらの重みにしたがって組み合わせられてもよい。限定ではなく一例として、特定のユーザ・アクションには格付けおよび重みの両方が割り当てられる一方、その特定のユーザ・アクションに関連付けられている関係には、格付けと相互に関連する重みとが割り当てられる（例えば、したがって重みが計１００％になる）。特定のオブジェクトに対するユーザの係数を計算するために、そのユーザのアクションに割り当てられた格付けが、例えば、総合的な係数の６０％を含む一方、そのユーザとそのオブジェクトとの間の関係は、総合的な係数の４０％を含んでもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数を計算するために用いられる様々な因子の重みを決定するときに、例えば、情報がアクセスされてからの時間、減衰因子、アクセスの頻度、情報に対する関係またはそれに関する情報がアクセスされたオブジェクトに対する関係、オブジェクトに接続されたソーシャルグラフ・エンティティに対する関係、ユーザ・アクションの短期的または長期的な平均、ユーザ・フィードバック、他の適切な変数、またはそれらの任意の組み合わせなど、様々な変数を考慮してもよい。限定ではなく一例として、係数は、係数を計算するとき、より最近のアクションがより関連性を有するように、特定のアクションによって提供される信号の強さを時間とともに減衰させる減衰因子を含んでもよい。格付けおよび重みは、その係数が基づくアクションの継続的なトラッキングに基づいて、継続的に更新されてもよい。任意のタイプのプロセスまたはアルゴリズムが、各因子およびそれらの因子に割り当てられる重みの格付けの割当、結合、平均化などに用いられてよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、履歴のアクションおよび過去のユーザ応答、またはデータを様々なオプションに晒し応答を測定することによってユーザから集められたデータに基づきトレーニングされた機械学習アルゴリズムを用いて、係数を決定してもよい。本開示では特定の方式による特定の係数の計算について記載するが、本開示では任意の適切な方式による係数の計算が想定される。
【００２３】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、ユーザのアクションに基づき係数を計算してもよい。ソーシャル・ネットワーキング・システム１６０は、オンライン・ソーシャル・ネットワーク上、サードパーティ・システム１７０上、他の適切なシステム上、またはそれらの任意の組み合わせ上において、そのようなアクションを監視してよい。任意の適切なタイプのユーザ・アクションのトラッキングまたは監視が行われてよい。典型的なユーザ・アクションには、プロフィール・ページを閲覧すること、コンテンツを作成またはポストすること、コンテンツと対話すること、グループに参加すること、イベントへの参加をリストまたは確認すること、ロケーションにチェックインすること、特定のページに「いいね」と表明すること、ページを作成すること、およ
びソーシャル・アクションを行う他のタスクを実行することが含まれる。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のタイプのコンテンツを有するユーザのアクションに基づき、係数を計算してよい。コンテンツは、オンライン・ソーシャル・ネットワーク、サードパーティ・システム１７０、または別の適切なシステムに関連付けられてよい。コンテンツは、ユーザ、プロフィール・ページ、ポスト、ニュース・ストーリ、ヘッドライン、インスタント・メッセージ、チャット・ルーム会話、電子メール、広告、写真、動画、音楽、他の適切なオブジェクト、またはそれらの任意の組み合わせを含んでよい。ソーシャル・ネットワーキング・システム１６０は、ユーザのアクションを、そのアクションのうちの１つ以上が主題、コンテンツ、他のユーザなどに対する親和性を示すか否かを判定するために分析してよい。限定ではなく一例として、ユーザが、「コーヒー」またはその変形に関係するコンテンツを頻繁にポストする場合、ソーシャル・ネットワーキング・システム１６０は、ユーザがコンセプト「コーヒー」に関して高い係数を有すると決定してもよい。特定のアクションまたはアクションのタイプは、他のアクションよりも大きな重み、より高い格付け、またはその両方を割り当てられ、これが総合的な計算された係数に影響を与えてもよい。限定ではなく一例として、第１のユーザが第２のユーザに電子メールを送る場合、そのアクションに対する重みまたは格付けは、第１のユーザが単に第２のユーザのユーザ・プロファイル・ページを閲覧する場合よりも高くてもよい。
【００２４】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のオブジェクトの間の関係のタイプに基づき係数を計算してもよい。ソーシャル・グラフ２００を参照すると、ソーシャル・ネットワーキング・システム１６０は、係数を計算するとき、特定のユーザ・ノード２０２およびコンセプト・ノード２０４を接続するエッジ２０６の数および／またはタイプを分析してもよい。限定ではなく一例として、配偶者タイプのエッジ（２人のユーザが結婚していることを表す）によって接続されているユーザ・ノード２０２は、友達タイプのエッジによって接続されているユーザ・ノード２０２より高い係数を割り当てられてもよい。換言すれば、特定のユーザのアクション及び関係に割り当てられた重みに応じて、総合親和性は、ユーザの友達に関するコンテンツに対するよりもユーザの配偶者に関するコンテンツに対してより高くなるように決定されてもよい。特定の実施形態では、ユーザが別のオブジェクトと有する関係は、そのオブジェクトについての係数の計算に関して重みおよび／またはユーザのアクションの格付けに影響を与えてもよい。限定ではなく一例として、ユーザが第１の写真にタグ付けされているが、第２の写真にいいねと表明しかしない場合、コンテンツに対してタグ付けタイプの関係を有することにはコンテンツに対していいねタイプの関係を有するよりも高い重みおよび／または格付けが割り当てられることから、ソーシャル・ネットワーキング・システム１６０は、ユーザが第２の写真より第１の写真に関して高い係数を有すると決定してもよい。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、１以上の第２のユーザが特定のオブジェクトに対して有する関係に基づき、第１のユーザのための係数を計算してもよい。換言すれば、他のユーザがオブジェクトに対して有する接続および係数は、そのオブジェクトに対する第１のユーザの係数に影響を与えてもよい。限定ではなく一例として、第１のユーザが１以上の第２のユーザに接続されるか、１以上の第２のユーザに対する高い係数を有し、それらの第２のユーザが特定のオブジェクトに接続されるか、特定のオブジェクトに対する高い係数を有する場合、ソーシャル・ネットワーキング・システム１６０は、その特定のオブジェクトに対して第１のユーザが比較的高い係数を有するべきであると決定してもよい。特定の実施形態では、係数は特定のオブジェクト間の隔たりの程度に基づいてもよい。係数が低いほど、ソーシャル・グラフ２００において第１のユーザに間接的に接続されているユーザのコンテンツ・オブジェクトへの関心を第１のユーザが共有する見込みが減少することを表してもよい。限定ではなく一例として、ソーシャル・グラフ２００においてより近くにある（すなわち、より隔たりの程度が小さい）ソーシャルグラフ・エンティティ同士は、ソーシャル・グラフ２００においてより遠くにある
エンティティ同士よりも高い係数を有してもよい。
【００２５】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、ロケーション情報に基づき係数を計算してもよい。互いに地理的に近くにあるオブジェクト同士は、より離れたオブジェクト同士よりも、より関連している、または互いにより高い関心を有すると考えられてよい。特定の実施形態では、特定のオブジェクトに対するユーザの係数は、そのユーザに関連付けられている現在のロケーション（またはそのユーザのクライアント・システム１３０のロケーション）に対するそのオブジェクトのロケーションの近接度に基づいてもよい。第１のユーザは、第１のユーザのより近くにある他のユーザまたはコンセプトに、より高い関心を有し得る。限定ではなく一例として、ユーザが空港から１マイル（約１．６ｋｍ）に位置し、ガソリン・スタンドから２マイル（約３．２ｋｍ）に位置する場合、ソーシャル・ネットワーキング・システム１６０は、そのユーザに対する空港の近接度に基づき、ユーザがガソリン・スタンドよりも空港に対しより高い係数を有すると決定してもよい。
【００２６】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づきユーザに関する特定のアクションを行ってもよい。係数を用いて、ユーザが特定のアクションを行うか否かを、そのアクションについてのそのユーザの関心に基づき予測することができる。係数は、広告、検索結果、ニュース・ストーリ、メディア、メッセージ、通知、または他の適切なオブジェクトなど、ユーザに対する任意のタイプのオブジェクトを生成または提示するときに用いられてよい。また、適切な場合、係数は、そのようなオブジェクトのランクおよび順序を決定するためにも利用されて得る。このように、ソーシャル・ネットワーキング・システム１６０は、ユーザの関心および現在の状況に関連する情報を提供してもよく、それによって、それらがそのような関心を有する情報を見出す見込みを高める。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づきコンテンツを生成してもよい。コンテンツ・オブジェクトは、ユーザに特有の係数に基づき提供または選択されてもよい。限定ではなく一例として、係数はユーザに対するメディアを生成するために用いられてもよく、ユーザには、そのメディア・オブジェクトに関してそのユーザが高い総合係数を有するメディアが、提示される。限定ではなく別の一例として、限定ではなく一例として、係数はユーザに対する広告を生成するために用いられてもよく、ユーザには、その広告オブジェクトに関してそのユーザが高い総合係数を有する広告が、提示される。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、係数情報に基づき検索結果を生成してもよい。特定のユーザのための検索結果は、問い合わせを行うユーザに関して検索結果に関連付けられている係数に基づき、得点またはランクを決定されてよい。限定ではなく一例として、より高い係数を有するオブジェクトに対応する検索結果は、より低い係数を有するオブジェクトに対応する結果よりも、検索結果のページにおいて、より高いランクを決定されてもよい。
【００２７】
特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のシステムまたはプロセスからの係数の要求に応じて、係数を計算してもよい。ユーザが所与の状況において取り得る（あるいは対象となる）可能性の高いアクションを予測するために、任意のプロセスによって、ユーザの計算された係数が要求されてよい。また、この要求は、係数を計算するために用いられる様々な因子に用いる１組の重みを含んでもよい。この要求は、オンライン・ソーシャル・ネットワーク上で動作するプロセスから、サードパーティ・システム１７０から（例えば、ＡＰＩまたは他の通信チャンネルを介して）、または別の適切なシステムから届いてよい。要求に応じて、ソーシャル・ネットワーキング・システム１６０は、係数を計算してよい（または、係数が以前に計算され記憶されている場合、その係数情報にアクセスしてよい）。特定の実施形態では、ソーシャル・ネットワーキング・システム１６０は、特定のプロセスに関する親和性を測定してもよい。様々なプロセス（オンライン・ソーシャル・ネットワークに対して内外の両方）は、特定の１
つのオブジェクトまたは複数のオブジェクトからなる組に対する係数を要求してもよい。ソーシャル・ネットワーキング・システム１６０は、親和性の尺度を要求した特定のプロセスに関連する親和性の尺度を提供してもよい。このように、各プロセスは、プロセスが親和性の尺度を用いる様々なコンテキストに適合する親和性の尺度を受信する。
【００２８】
ソーシャル・グラフ親和性および親和性係数に関して、特定の実施形態では、米国特許出願第１１／５０３０９３号（２００６年８月１１日提出）、米国特許出願第１２／９７７０２７号（２０１０年１２月２２日提出）、米国特許出願第１２／９７８２６５号（２０１０年１２月２３日受信）、および米国特許出願第１３／６３２８６９号、において開示されている１以上のシステム、構成要素、要素、機能、方法、動作、または工程を利用してよい。それらの文献の各々を引用によって本明細書に援用する。
【００２９】
特定の実施形態では、ソーシャル・ネットワーキング・システムは、特定のユーザ特性を有する１以上のユーザを識別してもよい。ユーザ特性は、ソーシャル・ネットワーキング・システムにおけるユーザのアクティビティの質に相当してもよい。例えば、ユーザがソーシャル・ネットワーキング・システムにおいて望ましくないまたは悪いアクティビティを頻繁に行う場合、ソーシャル・ネットワーキング・システムは、そのユーザを悪い挙動のユーザ、すなわち、悪いユーザであると識別できる。悪いユーザは、スパム・メッセージの送信、偽のアイデンティファイの使用、悪いまたは禁止されたコンテンツ（例えば、不敬、卑猥な言葉、著作物）の頻繁な投稿、または悪いユーザが実社会において知っている可能性の低いユーザ（例えば、悪いユーザとは異なる大陸で生活しているユーザ）に対する頻繁な友達リクエストの送信など、しばしばソーシャル・ネットワーキング・システムの利用規約またはコミュニティ規約に違反する場合がある。ソーシャル・ネットワーキング・システムは、ユーザがソーシャル・ネットワーキング・システムにおいて所定の期間（例えば、３年間）を越えて望ましくないアクティビティを有していない場合、そのユーザを良い挙動のユーザ、すなわち、良いユーザであると識別できる。ソーシャル・ネットワーキング・システムは、高い質のコンテンツ（例えば、構成の良いコンテンツ、他の多くのユーザによって共有されるコンテンツ、または肯定的なコメントを受け取っているコンテンツ）を投稿すること、またはソーシャル・ネットワーキング・システムにおける他のユーザまたはコンセプトとの高い質の対話を有することなど、ユーザがソーシャル・ネットワーキング・システムにおいて望ましいアクティビティを頻繁に行う場合、そのユーザを良いユーザであると識別してもよい。
【００３０】
また、ユーザ特性は、ソーシャル・ネットワーキング・システムのコンセプトに対するユーザの態度に相当してもよい。例えば、ソーシャル・ネットワーキング・システムは、ユーザがコンセプトのコンセプト・ページに「いいね」と表明する場合、コンセプトのニュースフィードをサブスクライブしている場合、コンセプトに関係するコンテンツに対し肯定的なコメントを頻繁に有する場合、またはソーシャル・ネットワーキング・システムにおける他のユーザにコンセプト（例えば、「タイド（Ｔｉｄｅ）」製品）を推薦する場合、ユーザがコンセプト（例えば、洗濯用洗剤製品における「タイド」ブランド）に対し肯定的な態度を有すると識別してもよい。別の例では、ソーシャル・ネットワーキング・システムは、ユーザがコンセプトのニュースフィードのサブスクライブを止める場合、またはコンセプトについて否定的なコメントまたはポストを頻繁に有する場合、ユーザがコンセプトに対し否定的な態度を有すると識別してもよい。
【００３１】
ソーシャル・ネットワーキング・システムは、特定のユーザ特性を有するユーザを識別するために、所定の規則、統計的アルゴリズム、またはトレーニング・データ・セットを有する機械学習アルゴリズムを用いてもよい。しかしながら、特定のユーザ特性を識別するために利用可能な情報が限定されているために、ソーシャル・ネットワーキング・システムが特定のユーザ特性を有するユーザの小さなセットしか識別しない場合もある。一方
、特定のユーザ特性を有する可能性の高い追加のユーザを決定することが望ましい。ソーシャル・ネットワーキング・システムは、特定のユーザ特性を有する可能性の高いユーザを決定することによって、ソーシャル・ネットワーキング・システムに対する総合的なユーザ経験を向上させてもよい。例えば、ソーシャル・ネットワーキング・システムは、特定のコンセプトに対する肯定的な態度を有する可能性が高いユーザを決定して、ソーシャル・ネットワーキング・システムが特定のコンセプトに関係するページまたは広告をそれらのユーザに対し推薦する、または追加のユーザのうちの１人によって送出されるクエリに対する検索結果の順番を、その検索結果の特定のコンセプトに対する関連性に基づき再決定することを望む。別の例では、ソーシャル・ネットワーキング・システムは、悪いユーザである可能性が高いユーザを決定して、ソーシャル・ネットワーキング・システムが、それらの悪い可能性が高いユーザによってソーシャル・ネットワーキング・システムにポストされたコンテンツをフィルタリングして除くまたはブロックする、またはそれらの悪い可能性が高いユーザに利用可能なソーシャル・ネットワーキング機能を無効化するか減少させることを望む。
【００３２】
特定の実施形態では、特定のユーザ特性を有する可能性が高いユーザを推測するための方法について記載する。特定の実施形態では、ソーシャル・グラフにおいて、特定のユーザ特性を有するユーザに対応する１組のユーザ・ノードを識別し、各識別されたユーザ・ノードに特性スコアを割り当ててもよい。特定の実施形態では、ソーシャル・グラフにおける他のユーザ・ノードに対する特性スコアを推定するべく、識別されたユーザ・ノードをシードとして用いることによって、特定のユーザ特性を有する可能性が高いユーザに対応する他のユーザ・ノードを推測してもよい。例えば、ユーザ・ノードの特性スコアは、ソーシャル・グラフにおける割り当てられた特性スコアを有するユーザ・ノードに対する、そのユーザ・ノードの接続に基づいて推定されてもよい。ユーザ・ノードに対する推定された特性スコアの値は、そのユーザ・ノードの対応するユーザが特定のユーザ特性を有する見込みを示してもよい。
【００３３】
図３は、ユーザ特性のスコアを決定するための一例の方法３００を示す図である。方法３００は、ソーシャル・ネットワーキング・システムの１つ以上のコンピューティングデバイス（例えば、サーバ）によって実装されてもよい。また、方法３００は、ソーシャル・ネットワーキング・システムによって提供されるアプリケーション・プログラム・インタフェース（ＡＰＩ）を用いて、ソーシャル・ネットワーキング・システムのソーシャル・グラフにアクセスする１つ以上のコンピューティング・デバイス（例えば、サードパーティ・システムの）によって実装されてもよい。方法３００は、工程３１０によって開始できる。特定の実施形態では、工程３１０にて、１つ以上のコンピューティング・デバイスが、ソーシャル・ネットワーキング・システムのソーシャル・グラフにアクセスする。ソーシャル・グラフは、複数のノードとノード間の複数のエッジとを含んでよい。ノードは、図２に示される一例のソーシャル・グラフ２００によって示されるものなど、ソーシャル・ネットワーキング・システムのユーザに対応するユーザ・ノードと、ソーシャル・ネットワーキング・システムのコンセプトに対応するコンセプト・ノードとを含んでよい。なお、ノードおよびエッジの数や、ソーシャル・グラフによって保持されるデータの量は、非常に大きくてもよい。例えば、フェイスブック社（カリフォルニア州メンローパーク）によって維持されるソーシャル・グラフは、１０８を超えるユーザ・ノードと、それらのユーザ・ノード間の１０１０を超えるともだちエッジとを有することができる。
【００３４】
特定の実施形態では、工程３２０にて、コンピューティング・デバイスは、特定のユーザ特性を有するユーザに対応する１以上の第１のユーザ・ノードを識別する。例えば、コンピューティング・デバイスは、ソーシャル・ネットワーキング・システムにおける１以上の良いユーザに対応する第１のユーザ・ノードを識別してもよい。コンピューティング・デバイスは、上述の通り、トレーニング・データ・セットを有する機械学習アルゴリズ
ムに基づき特定のユーザ特性を有するユーザを識別してもよい。特定の実施形態では、特定のユーザ特性を有するユーザを識別するための任意の適切な方法が想定される。
【００３５】
特定の実施形態では、工程３４０にて、コンピューティング・デバイスは、各第１のユーザ・ノードに特性スコアを割り当てる。特性スコアは、整数、実数、または特定のユーザ特性を表す任意の適切な値であってよい。例えば、コンピューティング・デバイスは、識別された良いユーザに対応する各第１のユーザ・ノードに１の特性スコアを割り当ててもよい。
【００３６】
特性スコアの割り当てられていない第２のユーザ・ノードについて、特定の実施形態では、ソーシャル・グラフにおける特性スコアの割り当てられた１以上の第１のユーザ・ノードに対する第２のユーザ・ノードの接続に基づき、第２のユーザ・ノードのための特性スコアを推定する。すなわち、特定の実施形態では、第１のユーザ・ノード（特性スコアが割り当てらている）と第２のユーザ・ノードとの間においてソーシャル・グラフを横断することによって、第２のユーザ・ノードのための特性スコアを推定してもよい。特定の実施形態では、高い親和性の近隣ノードは第２のユーザ・ノードとより高い関連する対話を有し得るので、第２のユーザ・ノードとの高い親和性を有する、第２のユーザ・ノードの近隣ノードのみを通じて横断してもよい。すなわち、任意の可能な経路によりソーシャル・グラフ全体を横断すること（例えば、ランダムウォーク）に代えて、特定の実施形態では、第２のユーザ・ノードの特性スコアを推定するために高い親和性の近隣ノードを通じる接続のみが考慮されるように、第２のユーザ・ノードについてソーシャル・グラフの「刈り込み（ｐｒｕｎｅ）」を行ってもよい（したがって、横断される経路の数は減少する）。
【００３７】
特定の実施形態では、工程３４０にて、割り当てられる特性スコアを有しない少なくとも１つの第２のユーザ・ノードについて、コンピューティング・デバイスは、第２のユーザ・ノードに接続する１つ以上の近隣のユーザ・ノードを選択し、この選択は少なくとも部分的には各選択される近隣のユーザ・ノードと第２のユーザ・ノードとの間の親和性に基づく。コンピューティング・デバイスは、第２のユーザ・ノードとの親和性が最も高い近隣のユーザ・ノードを選択してもよい。上述のように、２つのユーザまたはユーザ・ノード間の親和性は、親和性係数または係数によって測定されてもよい。例えば、コンピューティング・デバイスは、第２のユーザの近隣ユーザ・ノードのランクを、そのそれぞれの第２のユーザとの係数に基づき決定し、上位のある数（例えば、１０個）または百分率（例えば、２０％）の近隣ユーザ・ノードを選択してもよい。特定の実施形態は、親和性に基づき第２のユーザ・ノードに接続される近隣ユーザ・ノードを選択するための任意の適切な方法が想定される。
【００３８】
特定の実施形態では、工程３５０にて、コンピューティング・デバイスは、第１のユーザノード（特性スコアが割り当てられている）のうちの少なくとも１つから第２のユーザ・ノードまでソーシャル・グラフを横断する間、特性スコアを反復的に集約することによって、第２のユーザ・ノードの特性スコアを推定する。この少なくとも１つの第１のユーザ・ノードは、ソーシャル・グラフにおいて第２のユーザ・ノードから１ホップ以上離れていてよい。一方、横断は、選択された近隣ユーザ・ノードのうちの少なくとも１つを各々含む１つ以上の経路を含んでよい。すなわち、各経路は、選択された近隣ユーザ・ノード（その少なくとも第２のユーザ・ノードに高い親和性を有する）のうちの少なくとも１つを通ってよい。コンピューティング・デバイスは、各経路に沿って１以上のユーザ・ノードの特性スコアを反復的に集約（例えば、合計まで加算）してもよい。ここで、各経路に沿ったユーザ・ノードの特性スコアは、割り当てられたまたは推定された特性スコアを含んでもよい。
【００３９】
コンピューティング・デバイスは、ソーシャル・グラフにおいて各特性スコアの対応するユーザ・ノードに接続するエッジの数に少なくとも部分的に基づき、各特性スコア（横断の経路に沿った各ユーザ・ノードの）の重み付けを行うことによって、第１のノード（特性スコアが割り当てられている）のうちの少なくとも１つから第２のユーザ・ノードまでソーシャル・グラフを横断する間、特性スコアを反復的に集約してもよい。例えば、第ｉ番目のユーザ・ノードの第ｋ回目の反復時の推定特性スコアＣｉ，ｋは、次の式（１）を用いて計算される：
【００４０】
【数１】
0006479762.tif 000002
式（１）において、Ｃｊ，ｋ−１は、第ｉ番目のユーザ・ノードの第ｊ番目の近隣ユーザ・ノードの第（ｋ−１）回目の反復（すなわち、その前の反復工程）時の推定特性スコアである。第ｉ番目のユーザ・ノードのすべての第ｊ番目の近隣ユーザ・ノードに対して合計が取られる。合計における各期間は、第ｉ番目のユーザ・ノードと、ソーシャル・グラフにおいて横断される少なくとも１つの特定の経路の一部である第ｊ番目の近隣ユーザ・ノードとの間のエッジに相当する。これに加えて、上述のように、第ｊ番目の近隣ユーザ・ノードは、選択された高い親和性の近隣ノードである。Ｏｊは、第ｊ番目の近隣ユーザ・ノードの接続の数である。すなわち、各第ｊ番目の近隣ユーザ・ノードの特性スコアは、その第ｊ番目の近隣ユーザ・ノードの接続の数によって（反比例するように）重み付けが行われる。ここで、第ｊ番目の近隣ユーザ・ノードの接続の数が多いほど、第ｊ番目の近隣ユーザ・ノードと第ｉ番目のユーザ・ノードとの間の対話または影響が少ないことを示してもよい。特定の実施形態では、ソーシャル・グラフにおいて横断される経路のユーザ・ノードの特性スコアの重み付けを行うために、任意の適切な方法が想定される。特定の実施形態では、コンピューティング・デバイスはソーシャル・グラフにおけるすべてのユーザ・ノードに式（１）を適用してもよい。コンピューティング・デバイスは、所定の回数のあいだ、すべてのユーザ・ノードに式（１）を反復的に適用してもよい（例えば、５回の反復）。
【００４１】
さらにまた、特定の実施形態では、第２のユーザ・ノードの特性スコアを推定するためにソーシャル・グラフにおいて横断される各経路は、１以上の指向性エッジに続く指向性の経路であってよい。特定の実施形態では、コンピューティング・デバイス（またはソーシャル・ネットワーキング・システムの別のコンピューティング・プロセス）は、２つのユーザ・ノード間のエッジの方向を決定してもよい。コンピューティング・デバイスは、ユーザＢがユーザＡに対しより大きな影響を有する（すなわち、ユーザＡがユーザＢの「フォロワー」である）場合、ユーザ・ノードＡ（ユーザＡの）とユーザ・ノードＢ（ユーザＢの）との間のエッジがユーザ・ノードＡからユーザ・ノードＢに向いていると決定してもよい。例えば、コンピューティング・デバイスは、ユーザＡがユーザＢのニュースフィードをサブスクライブし、Ｂによって生成されたコンテンツに対し頻繁にアクションを行う（例えば、ユーザＢのポストに対しコメントする、ユーザＢによってポストされた写真にタグ付けする）一方、ユーザＢがユーザＡの「受動的な」つながりである（例えば、ユーザＢは、過去３か月においてユーザＡによって生成されたコンテンツとの対話を有しない）場合、ユーザＢがユーザＡに対しより大きな影響を有すると決定する。この場合、ユーザＡはユーザＢのコンテンツに関してより高い係数値を有する一方、ユーザＢはユーザＡのコンテンツに関してより低い係数値を有してよい。コンピューティング・デバイスは、エッジに関連付けられている係数の非相称の値に基づき、エッジの方向を決定してもよい。特定の実施形態では、ソーシャル・グラフにおける２つのユーザ・ノード間のエッジの方向を決定するための任意の適切な方法が想定される。特定の実施形態では、コンピ
ューティング・デバイスは、各ユーザ・ノードに接続するエッジの方向に基づき、ソーシャル・グラフにおける各ユーザ・ノードに式（１）を適用してもよい。例えば、各第ｊ番目の近隣ユーザ・ノードから第ｉ番目のユーザ・ノードに向かうエッジ接続を各々有するすべての第ｊ番目の近隣ユーザ・ノードに対して、式（１）による合計が取られる。Ｏｊは、各エッジが第ｊ番目の近隣ユーザ・ノードから離れる方向の第ｊ番目の近隣ユーザ・ノード用エッジの数である。
【００４２】
図４には、方法３００および式（１）に基づく特性スコアの計算の一例を示す。図４では、一例のソーシャル・グラフ４００は、特定のユーザ挙動に対応して、１の割り当てられた特性スコアを各々有するユーザ・ノードＵＧ１，ＵＧ２（ユーザＵＧ１，ＵＧ２にそれぞれ対応する）を含む。一方、ユーザ・ノードＵ１，Ｕ２，・・・Ｕ７（ユーザＵ１，Ｕ２などにそれぞれ対応する）は、特性スコアが割り当てられていない。例えば、ＵＧ１，ＵＧ２は良いユーザである一方、Ｕ１，Ｕ２，・・・Ｕ７は、以前に良いユーザとしての質が知られていないユーザである。説明の目的のため、高い親和性の近隣ノードに対する接続に対応するエッジのみを図４に示す。これに加えて、エッジは指向性である。例えば、ノードＵＧ１とＵ１との間のエッジは、ＵＧ１からＵ１に向いており、ユーザＵＧ１がユーザＵ１のフォロワーであることを示す。ここで、特性スコアの計算は指向性のエッジに倣ってよい。
【００４３】
例えば、Ｕ１の推定特性スコアは、ＵＧ１から入るエッジが１つであるのに対し、ＵＧ１が２つの出るエッジを有するので、１／２の値を有するとして計算される。Ｕ３の推定特性スコアは、Ｕ１から入るエッジが１つであるのに対し、Ｕ１が３つの出るエッジを有するので、１／６の値を有するとして計算される。ここで、Ｕ３の推定特性スコアは、指向性の経路ＵＧ１−Ｕ１−Ｕ３に沿って計算される重み付けされ集約された特性スコアである。
【００４４】
同様に、Ｕ３の推定特性スコアは、Ｕ１から入るエッジが１つであるのに対し、Ｕ１が３つの出るエッジを有するので、１／６の値を有するとして計算される。ここで、Ｕ４の推定特性スコアは、指向性の経路ＵＧ１−Ｕ１−Ｕ４に沿って計算される重み付けされ集約された特性スコアである。なお、ＵＧ２に対する１の割当特性スコアは、Ｕ４とＵＧ２との間のエッジがＵ４からＵＧ２に向いているので、Ｕ４の特性スコアを推定する際には含まれないことも留意されたい。
【００４５】
Ｕ２の推定特性スコアは、ＵＧ１から入るエッジが１つであるのに対し、ＵＧ１が２つの出るエッジを有するので、１／２の値を有するとして計算される。Ｕ６の推定特性スコアは、Ｕ２から入るエッジが１つであるのに対し、Ｕ２が３つの出るエッジを有するので、１／６の値を有するとして計算される。ここで、Ｕ６の推定特性スコアは、指向性の経路ＵＧ１−Ｕ２−Ｕ６に沿って計算される重み付けされ集約された特性スコアである。同様に、Ｕ７の推定特性スコアは、指向性の経路ＵＧ１−Ｕ２−Ｕ７に沿った重み付けされ集約された特性スコアとして計算され、１／６の値となる。
【００４６】
Ｕ５の推定特性スコアは、Ｕ１から入るエッジが１つあり（３つの出るエッジを有する）、Ｕ２から入る別のエッジが１つある（３つの出るエッジを有する）ので、１／３の値を有するとして計算される。すなわち、Ｕ５の推定特性スコアは、指向性の経路ＵＧ１−Ｕ１−Ｕ５に沿って、また別の指向性の経路ＵＧ１−Ｕ２−Ｕ５に沿って計算される、重み付けされ集約された特性スコアである。
【００４７】
図４の例では、ユーザ・ノードの推定特性スコアの値は、ユーザ・ノードの対応するユーザが良いユーザであるとして特定のユーザ特性を有する見込みを示してもよい。例えば、Ｕ５の１／３の推定特性スコアは、ユーザＵ５が良いユーザである確率が１／３である
ことを示してもよい（良いユーザＵＧ１が１の割り当てられた特性スコアを有するとして）。図５における各推定特性スコアは１つ以上の指向性のエッジに沿って計算される一方、各指向性のエッジは「フォロワー」ユーザ・ノードから「インフルエンサ」ユーザ・ノードに向いているので、各推定特性スコアの値は各推定特性スコアの対応するユーザがソーシャル・グラフを離れる場合の効果を示してもよい。例えば、ユーザＵ５がソーシャル・グラフを（したがって、ソーシャル・ネットワーキング・システムを）離れる場合、良いユーザＵＧ１がソーシャル・ネットワーキング・システムを離れる１／３の確率がある。
【００４８】
特定の実施形態は、適切な場合、図３の方法の１または複数のステップを繰り返してもよい。この開示は、図３の方法の特定のステップを、特定の順番で発生するものとして記載し示しているが、この開示は、任意の好適な順番で発生する図３の方法の任意の好適なステップを企図する。さらに、この開示は、図３の方法の特定のステップを実施する特定の構成要素、デバイス、またはシステムについて記載し示しているが、この開示は、図３の方法の任意の好適なステップを実施する任意の好適な構成要素、デバイス、またはシステムの任意の好適な組合せを企図する。
【００４９】
図５は、例示的なコンピュータ・システム５００を示す。特定の実施形態では、１または複数のコンピュータ・システム５００は、本明細書に記載され、または示されている１または複数の方法の１または複数のステップを実施する。特定の実施形態では、１または複数のコンピュータ・システム５００は、本明細書に記載され、または示されている機能を提供する。特定の実施形態では、１または複数のコンピュータ・システム５００上で動作するソフトウェアは、本明細書に記載され、または示されている１または複数の方法の１または複数のステップを実施し、または本明細書に記載され、または示されている機能を提供する。特定の実施形態は、１または複数のコンピュータ・システム５００の１または複数の部分を含む。本明細書では、コンピュータ・システムに言及することは、適切な場合、コンピューティング・デバイスを包含してもよく、逆も同様である。さらに、コンピュータ・システムに言及することは、適切な場合、１または複数のコンピュータ・システムを包含してもよい。
【００５０】
この開示は、任意の好適な数のコンピュータ・システム５００を企図する。この開示は、任意の好適な物理形態をとるコンピュータ・システム５００を企図する。限定するものとしてではなく一例として、コンピュータ・システム５００は、組込みコンピュータ・システム、システム・オン・チップ（ＳＯＣ）、シングルボード・コンピュータ・システム（ＳＢＣ）（たとえば、コンピュータ・オン・モジュール（ＣＯＭ）またはシステム・オン・モジュール（ＳＯＭ）など）、デスクトップ・コンピュータ・システム、ラップトップもしくはノートブック・コンピュータ・システム、対話キオスク、メインフレーム、コンピュータ・システムのメッシュ、移動体電話、携帯情報端末（ＰＤＡ）、サーバ、タブレット・コンピュータ・システム、またはこれらの２以上の組合せであってよい。適切な場合、コンピュータ・システム５００は、１または複数のコンピュータ・システム５００を含んでもよく、一元的なものであっても分散型であってもよく、複数のロケーションに跨ってもよく、複数のマシンに跨ってもよく、複数のデータ・センタに跨ってもよく、クラウド内にあってもよく、クラウドは、１または複数のネットワーク内で１または複数のクラウド・コンポーネントを含んでもよい。適切な場合、１または複数のコンピュータ・システム５００は、実質的な空間的または時間的制限なしに、本明細書に記載され、または示されている１または複数の方法の１または複数のステップを実施してもよい。限定するものとしてではなく一例として、１つまたは複数のコンピュータ・システム５００は、リアルタイムで、またはバッチ・モードで、本明細書に記載され、または示されている１または複数の方法の１または複数のステップを実施してもよい。１または複数のコンピュータ・システム５００は、適切な場合、異なる時に、または異なるロケーションで、本明
細書に記載され、または示されている１または複数の方法の１または複数のステップを実施してもよい。
【００５１】
特定の実施形態では、コンピュータ・システム５００は、プロセッサ５０２、メモリ５０４、ストレージ５０６、入力／出力（Ｉ／Ｏ）インターフェース５０８、通信インターフェース５１０、およびバス５１２を含む。この開示は、特定の数の特定の構成要素を特定の構成で有する特定のコンピュータ・システムについて記載し示しているが、この開示は、任意の好適な数の任意の好適な構成要素を任意の好適な構成で有する任意の好適なコンピュータ・システムを企図する。
【００５２】
特定の実施形態では、プロセッサ５０２は、コンピュータ・プログラムを構成するものなど命令を実行するためのハードウェアを含む。限定するものとしてではなく一例として、命令を実行するために、プロセッサ５０２は、内部レジスタ、内部キャッシュ、メモリ５０４、またはストレージ５０６から命令を取り出し（またはフェッチし）、それらを復号および実行し、次いで、１または複数の結果を内部レジスタ、内部キャッシュ、メモリ５０４、またはストレージ５０６に書き込む。特定の実施形態では、プロセッサ５０２は、データ、命令、またはアドレス用に１または複数の内部キャッシュを含んでもよい。この開示は、適切な場合、任意の好適な数の任意の好適な内部キャッシュを含むプロセッサ５０２を企図する。限定するものとしてではなく一例として、プロセッサ５０２は、１または複数の命令キャッシュ、１または複数のデータ・キャッシュ、および１または複数の変換索引バッファ（ＴＬＢ）を含んでもよい。命令キャッシュ内の命令は、メモリ５０４またはストレージ５０６内の命令のコピーであってもよく、命令キャッシュは、プロセッサ５０２によるこれらの命令の取り出しを高速化する。データ・キャッシュ内のデータは、プロセッサ５０２にて実行される命令が操作するための、メモリ５０４またはストレージ５０６内のデータのコピー、プロセッサ５０２で実行される後続の命令によるアクセスための、またはメモリ５０４もしくはストレージ５０６に書き込むための、プロセッサ５０２で実行された以前の命令の結果、あるいは他の好適なデータであってもよい。データ・キャッシュは、プロセッサ５０２による読出しまたは書込み動作を高速化する。ＴＬＢは、プロセッサ５０２のために仮想アドレス変換を高速化する。特定の実施形態では、プロセッサ５０２は、データ、命令、またはアドレス用に１または複数の内部レジスタを含む。この開示は、適切な場合、任意の好適な数の任意の好適な内部レジスタを含むプロセッサ５０２を企図する。適切な場合、プロセッサ５０２は、１または複数の算術論理演算ユニット（ＡＬＵ）を含むことができ、マルチコア・プロセッサであってもよく、１または複数のプロセッサ５０２を含んでもよい。この開示は、特定のプロセッサについて記載し示しているが、この開示は、任意の好適なプロセッサを企図する。
【００５３】
特定の実施形態では、メモリ５０４は、プロセッサ５０２が実行するための命令、またはプロセッサ５０２が操作するためのデータを記憶するための主記憶装置を含む。限定するものとしてではなく一例として、コンピュータ・システム５００は、ストレージ５０６または別のソース（たとえば、別のコンピュータ・システム５００など）からメモリ５０４に命令をロードする。次いで、プロセッサ５０２は、メモリ５０４から内部レジスタまたは内部キャッシュに命令をロードする。命令を実行するために、プロセッサ５０２は、内部レジスタまたは内部キャッシュから命令を取り出し、それらを復号する。命令の実行中、または実行後、プロセッサ５０２は、１または複数の結果（中間結果であることも最終結果であることもある）を内部レジスタまたは内部キャッシュに書き込む。次いで、プロセッサ５０２は、それらの結果の１または複数をメモリ５０４に書き込む。特定の実施形態では、プロセッサ５０２は、１もしくは複数の内部レジスタもしくは内部キャッシュ内、または（ストレージ５０６もしくは他の場所ではなく）メモリ５０４内の命令だけを実行し、１もしくは複数の内部レジスタもしくは内部キャッシュ内、または（ストレージ８０６もしくは他の場所ではなく）メモリ５０４内のデータだけを操作する。１または複
数のメモリ・バス（それぞれがアドレス・バスとデータ・バスを含むことがある）がプロセッサ５０２をメモリ５０４に結合してもよい。バス５１２は、下記に記載されているように、１または複数のメモリ・バスを含んでもよい。特定の実施形態では、１または複数のメモリ管理ユニット（ＭＭＵ）が、プロセッサ５０２とメモリ５０４との間に存在し、プロセッサ５０２によって要求されるメモリ５０４へのアクセスを容易にする。特定の実施形態では、メモリ５０４は、ランダム・アクセス・メモリ（ＲＡＭ）を含む。このＲＡＭは、適切な場合、揮発性メモリであり得る。適切な場合、このＲＡＭは、ダイナミックＲＡＭ（ＤＲＡＭ）またはスタティックＲＡＭ（ＳＲＡＭ）であってよい。さらに、適切な場合、このＲＡＭは、シングルポート型またはマルチポート型ＲＡＭであってよい。この開示は、任意の好適なＲＡＭを企図する。メモリ５０４は、適切な場合、１または複数のメモリ５０４を含んでもよい。この開示は、特定のメモリについて記載し示しているが、この開示は、任意の好適なメモリを企図する。
【００５４】
特定の実施形態では、ストレージ５０６は、データまたは命令用のマス・ストレージを含む。限定するものとしてではなく一例として、ストレージ５０６は、ハード・ディスク・ドライブ（ＨＤＤ）、フロッピー（登録商標）ディスク・ドライブ、フラッシュ・メモリ、光ディスク、光磁気ディスク、磁気テープ、もしくはユニバーサル・シリアル・バス（ＵＳＢ）ドライブ、またはこれらの２以上の組合せを含んでもよい。ストレージ５０６は、適切な場合、取外し式または非取外し式（または固定）媒体を含んでもよい。ストレージ５０６は、適切な場合、コンピュータ・システム５００に対して内部であっても外部であってもよい。特定の実施形態では、ストレージ５０６は、不揮発性のソリッドステート・メモリである。特定の実施形態では、ストレージ５０６は、読出し専用メモリ（ＲＯＭ）を含む。適切な場合、このＲＯＭは、マスクプログラムドＲＯＭ、プログラマブルＲＯＭ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、電気的消去可能ＰＲＯＭ（ＥＥＰＲＯＭ）、電気的書き換え可能ＲＯＭ（ＥＡＲＯＭ）、もしくはフラッシュ・メモリ、またはこれらの２以上の組合せであってよい。この開示は、任意の好適な物理形態をとるマス・ストレージ５０６を企図する。ストレージ５０６は、適切な場合、プロセッサ５０２とストレージ５０６の間の通信を容易にする１または複数のストレージ制御ユニットを含んでもよい。適切な場合、ストレージ５０６は、１または複数のストレージ５０６を含んでもよい。この開示は、特定のストレージについて記載し示しているが、この開示は、任意の好適なストレージを企図する。
【００５５】
特定の実施形態では、Ｉ／Ｏインターフェース５０８は、コンピュータ・システム５００と１または複数のＩ／Ｏデバイスとの間の通信のために１または複数のインターフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。コンピュータ・システム５００は、適切な場合、これらのＩ／Ｏデバイスの１または複数を含んでもよい。これらのＩ／Ｏデバイスの１または複数は、人とコンピュータ・システム５００の間の通信を可能にする。限定するものとしてではなく一例として、Ｉ／Ｏデバイスは、キーボード、キーパッド、マイクロフォン、モニタ、マウス、プリンタ、スキャナ、スピーカ、スチル・カメラ、スタイラス、タブレット、タッチ・スクリーン、トラックボール、ビデオ・カメラ、別の好適なＩ／Ｏデバイス、またはこれらの２以上の組合せを含んでもよい。Ｉ／Ｏデバイスは、１または複数のセンサを含んでもよい。この開示は、任意の好適なＩ／Ｏデバイス、およびそれらのための任意の好適なＩ／Ｏインターフェース５０８を企図する。適切な場合、Ｉ／Ｏインターフェース５０８は、プロセッサ５０２がこれらのＩ／Ｏデバイスの１または複数を駆動することを可能にする１または複数のデバイスまたはソフトウェア・ドライバを含む。Ｉ／Ｏインターフェース５０８は、適切な場合、１または複数のＩ／Ｏインターフェース５０８を含んでもよい。この開示は、特定のＩ／Ｏインターフェースについて記載し示しているが、この開示は、任意の好適なＩ／Ｏインターフェースを企図する。
【００５６】
特定の実施形態では、通信インターフェース５１０は、コンピュータ・システム５００と１もしくは複数の他のコンピュータ・システム５００または１もしくは複数のネットワークとの間の通信（たとえば、パケットベースの通信など）のために１または複数のインターフェースを提供するハードウェア、ソフトウェア、またはその両方を含む。限定するものとしてではなく一例として、通信インターフェース５１０は、ＥＴＨＥＲＮＥＴ（登録商標）もしくは他の有線ベースのネットワークとの通信のためのインターフェース・コントローラ（ＮＩＣ）もしくはネットワーク・アダプタ、またはＷＩ−ＦＩネットワークなど無線ネットワークとの通信のための無線ＮＩＣ（ＷＮＩＣ）もしくは無線アダプタを含んでもよい。この開示は、任意の好適なネットワーク、およびそのための任意の好適な通信インターフェース５１０を企図する。限定するものとしてではなく一例として、コンピュータ・システム５００は、アドホック・ネットワーク、パーソナル・エリア・ネットワーク（ＰＡＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、またはインターネットの１もしくは複数の部分、あるいはこれらの２以上の組合せと通信する。これらのネットワークの１または複数のうちの１または複数の部分は、有線であっても無線であってもよい。一例として、コンピュータ・システム５００は、無線ＰＡＮ（ＷＰＡＮ）（たとえば、ＢＬＵＥＴＯＯＴＨ（登録商標）ＷＰＡＮなど）、ＷＩ−ＦＩネットワーク、ＷＩ−ＭＡＸネットワーク、携帯電話ネットワーク（たとえば、グローバル移動体通信システム（ＧＳＭ（登録商標））ネットワークなど）、もしくは他の好適な無線ネットワーク、またはこれらの２以上の組合せと通信する。コンピュータ・システム５００は、適切な場合、これらのネットワークのいずれかのための任意の好適な通信インターフェース５１０を含んでもよい。通信インターフェース５１０は、適切な場合、１または複数の通信インターフェース５１０を含んでもよい。この開示は、特定の通信インターフェースについて記載し示しているが、この開示は、任意の好適な通信インターフェースを企図する。
【００５７】
特定の実施形態では、バス５１２は、コンピュータ・システム５００の構成要素を互いに結合するハードウェア、ソフトウェア、またはその両方を含む。限定するものとしてではなく一例として、バス５１２は、アクセラレィティッド・グラフィックス・ポート（ＡＧＰ）もしくは他のグラフィックス・バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、フロントサイド・バス（ＦＳＢ）、ＨＴ（ＨＹＰＥＲＴＲＡＮＳＰＯＲＴ）相互接続、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、インフィニバンド相互接続、ＬＰＣ（ｌｏｗ−ｐｉｎ−ｃｏｕｎｔ）バス、メモリ・バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バス、ＰＣＩエクスプレス（ＰＣＩｅ）バス、ＳＡＴＡ（ｓｅｒｉａｌ  ａｄｖａｎｃｅｄ  ｔｅｃｈｎｏｌｏｇｙ  ａｔｔａｃｈｍｅｎｔ）バス、ＶＬＢ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ  ｌｏｃａｌ）バス、もしくは別の好適なバス、またはこれらの２以上の組合せを含んでもよい。バス５１２は、適切な場合、１または複数のバス５１２を含んでもよい。この開示は、特定のバスについて記載し示しているが、この開示は、任意の好適なバスまたは相互接続を企図する。
【００５８】
本明細書では、１または複数の非一時的コンピュータ可読記憶媒体は、適切な場合、１または複数の半導体ベースの、もしくは他の集積回路（ＩＣ）（たとえば、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）または特定用途向けＩＣ（ＡＳＩＣ））、ハード・ディスク・ドライブ（ＨＤＤ）、ハイブリッド・ハード・ドライブ（ＨＨＤ）、光ディスク、光ディスク・ドライブ（ＯＤＤ）、光磁気ディスク、光磁気ドライブ、フロッピー（登録商標）・ディスケット、フロッピー（登録商標）・ディスク・ドライブ（ＦＤＤ）、磁気テープ、ソリッドステート・ドライブ（ＳＳＤ）、ＲＡＭドライブ、セキュア・デジタル・カードもしくはセキュア・デジタル・ドライブ、任意の他の好適な非一時
的コンピュータ可読記憶媒体、またはこれらの２以上の組合せを含んでもよい。非一時的コンピュータ可読記憶媒体は、適切な場合、揮発性、不揮発性、または揮発性と不揮発性の組合せであってよい。
【００５９】
本明細書では、「または（もしくは）」は、別段明確に示されていない限り、または別段文脈によって示されない限り、包括的（ｉｎｃｌｕｓｉｖｅ）であり、排他的なものではない。したがって、本明細書では、「ＡまたはＢ」は、別段明確に示されていない限り、または別段文脈によって示されない限り、「Ａ、Ｂ、またはその両方」を意味する。さらに、「および」は、別段明確に示されていない限り、または別段文脈によって示されない限り、共同であり、個別的でもある。したがって、本明細書では、「ＡおよびＢ」は、別段明確に示されていない限り、または別段文脈によって示されない限り、「ＡおよびＢを共同で、または個別的に」意味する。
【００６０】
この開示の範囲は、当業者であれば理解するであろう、本明細書に記載され、または示されている例示的な実施形態に対する変更、置換、変形、代替、および修正すべてを包含する。この開示の範囲は、本明細書に記載され、または示されている例示的な実施形態に限定されない。さらに、この開示は、それぞれの実施形態について、本明細書では、特定の構成要素、要素、機能、動作、またはステップを含むものとして記載し示しているが、これらの実施形態のいずれも、当業者であれば理解するであろう、本明細書のどこかに記載され、または示されている構成要素、要素、機能、動作、またはステップのいずれかの任意の組合せまたは並べ替えを含んでもよい。さらに、添付の特許請求の範囲において、特定の機能を実施するように適合された、するように配置された、することが可能な、するように構成された、することが可能である、するように動作可能である、またはするように動作する装置もしくはシステム、または装置もしくはシステムの構成要素に言及することは、その装置、システム、または構成要素がそのように適合され、配置され、動作可能であり、構成され、可能であり、動作可能であり、動作する限り、それ、またはその特定の機能が作動される、オンにされる、またはロック解除されるか否かにかかわらず、その装置、システム、構成要素を包含する。
【図１】
0006479762.tif 000003
【図２】
0006479762.tif 000004
【図３】
0006479762.tif 000005
【図４】
0006479762.tif 000006
【図５】
0006479762.tif 000007