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