【手続補正書】
【提出日】平成27年6月5日(2015.6.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおいて関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記識別された複数のコネクションの内のコネクションの各ペアに対する親和性の尺度を決定するステップであって、親和性の各尺度は、前記ペアのコネクション間における共通の友達の数に少なくとも部分的に基づき決定される、親和性の尺度決定ステップと、
前記コネクションの少なくとも１つのサブセットを１つ以上のクラスタにグループ化するステップであって、前記コネクションは前記決定された親和性の尺度に基づきクラスタに割り当てられる、グループ化ステップと、
前記クラスタの識別子と、前記ユーザのコネクションのうちのどのコネクションが前記クラスタに割り当てられたかとを含む前記グループ化ステップの結果を出力する結果出力ステップと、を含む方法。
【請求項２】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が前記ソーシャルネットワーキングシステムにおいて互いに関係を確立したか否かを決定するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザの重なりの尺度を決定するステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザであって、前記コネクションのペアに密接に関連付けられたと決定された他のユーザの重なりの尺度を決定するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記ペアのコネクション同士が共通して関係を確立した前記他のユーザは、前記ソーシャルネットワーキングシステムにおける該他のユーザの過去の相互作用に基づき前記コネクションのペアに密接に関連付けられていると決定される、請求項４に記載の方法。
【請求項６】
前記グループ化ステップは、前記決定された親和性の尺度に基づき前記コネクションについて階層的クラスタ化アルゴリズムを実行するステップを含む、請求項１に記載の方法。
【請求項７】
前記グループ化ステップは、親和性の前記尺度の残りが閾値未満になるまで、
親和性の最も高い尺度により関連付けられた２つ以上のコネクションを識別するステップと、
前記識別されたコネクションを新たなクラスタに縮約するステップと、
前記新たなクラスタと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の親和性の新たな尺度を再計算するステップと、を繰り返すステップを含む、請求項１に記載の方法。
【請求項８】
前記再計算された親和性の新たな尺度は、前記識別されたコネクションと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の前記親和性の尺度の平均値に基づく、請求項７に記載の方法。
【請求項９】
前記親和性の尺度決定ステップは、前記ペアのコネクション間における前記共通の友達の数を、前記コネクションのペアの友達の総数により正規化するステップをさらに含む、請求項１に記載の方法。
【請求項１０】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおいて関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記コネクションのうちの少なくとも複数のペアの各々に対して、前記ペアのコネクション間における共通の友達の数に少なくとも部分的に基づき前記ペアのコネクション間における親和性の尺度を決定するステップと、
計算システムによって、
親和性の最も高い尺度により関連付けられた２つ以上のコネクションを識別することと、
前記識別されたコネクションを新たなクラスタに縮約することと、
前記新たなクラスタと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の親和性の新たな尺度を再計算することと、
前記残りの親和性の最も高い尺度が閾値未満になったときにクラスタ化を停止することと、を行うことによって前記コネクションを１つ以上のクラスタに繰り返しクラスタ化するステップと、
前記クラスタ化の結果を出力するステップであって、前記結果は前記クラスタの識別子と前記クラスタに割り当てられた前記ユーザのコネクションとを含む、結果出力ステップと、を含む方法。
【請求項１１】
前記親和性の尺度を決定するステップは、前記ペアのコネクション同士が前記ソーシャルネットワーキングシステムにおいて互いに関係を確立したか否かを決定するステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記親和性の尺度を決定するステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザの重なりの尺度を決定するステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記親和性の尺度を決定するステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザであって、前記コネクションのペアに密接に関連付けられていると決定された他のユーザの重なりの尺度
を決定するステップをさらに含む、請求項１０に記載の方法。
【請求項１４】
前記ペアのコネクション同士が共通して関係を確立した前記他のユーザは、前記ソーシャルネットワーキングシステムにおける該他のユーザの過去の相互作用に基づき前記コネクションのペアに密接に関連付けられていると決定される、請求項１３に記載の方法。
【請求項１５】
前記再計算された親和性の新たな尺度は前記識別されたコネクションと残りのコネクション、他のクラスタ、またはその両方のコネクションまたはクラスタの各々との間の前記親和性の尺度の平均値に基づく、請求項１０に記載の方法。
【請求項１６】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおける関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記識別された複数のコネクションの内のコネクションの各ペアに対する親和性の尺度を決定するステップであって、前記コネクションのペアに対する親和性の尺度は、前記ペアのコネクション間における共通の友達の数に基づき計算される、親和性の尺度を決定するステップと、
１つ以上のクラスタを生成するために前記決定された親和性に基づき前記コネクションをクラスタ化するステップであって、同一クラスタ内に存在するコネクション間の親和性の多数は、同一クラスタ内に存在しないコネクション間の親和性より高い、クラスタ化ステップと、
前記クラスタ化の結果を出力するステップであって、前記結果は前記クラスタの識別子と前記クラスタに割り当てられた前記ユーザのコネクションとを含む、結果出力ステップと、を含む方法。
【請求項１７】
ユーザの複数のコネクションを識別するステップであって、各コネクションは、前記ユーザがソーシャルネットワーキングシステムにおいて関係を確立した前記ソーシャルネットワーキングシステムの他のユーザを含む、コネクション識別ステップと、
前記識別された複数のコネクションの内のコネクションの各ペアに対する親和性の尺度を決定するステップであって、親和性の各尺度は、前記ペアのコネクション間における前記ソーシャルネットワーキングシステム内での相互連結性を表す、親和性の尺度決定ステップと、
前記コネクションの少なくとも１つのサブセットを１つ以上のクラスタにグループ化するステップであって、前記コネクションは前記決定された親和性の尺度に基づきクラスタに割り当てられる、グループ化ステップと、
前記クラスタの識別子と、前記ユーザのコネクションのうちのどのコネクションが前記クラスタに割り当てられたかとを含む前記グループ化ステップの結果を出力する結果出力ステップと、を含む方法。
【請求項１８】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が前記ソーシャルネットワーキングシステムにおいて互いに関係を確立したか否かを決定するステップをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザの重なりの尺度を決定するステップをさらに含む、請求項１７に記載の方法。
【請求項２０】
前記親和性の尺度決定ステップは、前記ペアのコネクション同士が共通して前記ソーシャルネットワーキングシステムにおいて関係を確立した他のユーザであって、前記コネクションのペアに密接に関連付けられたと決定された他のユーザの重なりの尺度を決定する
ステップをさらに含む、請求項１７に記載の方法。
【請求項２１】
前記コネクション同士が共通して関係を確立した前記他のユーザは、前記ソーシャルネットワーキングシステムにおける該他のユーザの過去の相互作用に基づき前記コネクションに密接に関連付けられていると決定される、請求項２０に記載の方法。