(57)【要約】  ソーシャルネットワークに基づいてグループを探索する方法は：クエリ端末から伝送されたグループ探索要求を受け取るステップであって、グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、グループ規模、及びグループコリティビティを含む、ステップと；予め生成されたソーシャルネットワークグラフを取得するステップと；クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張を行い、ソーシャルネットワークグラフ内で、決定されたグループメンバの数がグループ規模と等しくなるまで、各探索拡張層において最大数の隣接ノードを有するユーザノードを、グループメンバとして決定するステップであって；拡張層の第１のレベルは、クエリユーザの隣接ノードであるユーザノードを含み、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである、ステップと；探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であることを判定し、探索対象グループをクエリ結果としてクエリ端末に表示するために返すステップと、を含む。
2019513245.tif 000002
【特許請求の範囲】
【請求項１】
ソーシャルネットワークに基づいてグループを探索する方法であって：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、前記グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ステップと；
前記クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、ステップと；
前記決定されたグループメンバ及び前記クエリユーザによって探索対象グループを形成するステップと；
前記探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
を含むことを特徴とする方法。
【請求項２】
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得する前記ステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、前記複数のユーザノード、及び前記ユーザノードを接続するように構成された前記エッジ集合を含む、前記ステップの後、前記方法は：
前記クエリユーザＩＤに対応する前記ユーザノードを根ノードとして使用して幅優先探索（ＢＦＳ）ツリーを構築するステップであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内のすべてのユーザノードを前記クエリユーザＩＤから開始して逐次トラバースする、ステップと；
構築された前記ＢＦＳツリーに従って、各ユーザノードから前記根ノードまでの最短社会的距離を決定するステップと、
前記グループ規模と前記最短社会的距離との間の差を計算するステップであって、１以下の差に対応するユーザノードがプルーニングノードとして定められる、ステップと；
前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するステップと、
をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記グループ規模と前記最短社会的距離との間の前記差を計算し、１以下の差に対応するユーザノードが前記プルーニングノードとして定められ、前記ソーシャルネットワークグラフ内で前記プルーニングノード及び前記プルーニングノードに関連付けられた前記エッジ集合が除去され、前記プルーニング済ソーシャルネットワークグラフを生成した後、前記方法は：前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するステップであって、前記ノードコリティビティは、前記ユーザノードに隣接するノードの数である、ステップと、前記ユーザノードが存在する場合、探索された前記ユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するステップと、をさらに含むことを特徴とする、請求項２に記載の方法。
【請求項４】
前記クエリユーザＩＤに対応する前記ユーザノードを開始ノードとして使用して前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有する前記ユーザノードを各探索拡張層においてグループメンバとして決定する前記ステップであって、ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、前記ステップは：
前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するステップであって、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードである、ステップと；
前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するステップであって、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードである、ステップと；
前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するステップと、
を含むことを特徴とする、請求項１に記載の方法。
【請求項５】
複数の決定された探索対象グループが存在し、前記方法は：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定し、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するステップと；
各グループネットワークグラフの親密度を計算するステップと；
最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項６】
前記グループネットワークグラフの前記親密度を計算する式は：
【数１】
2019513245.tif 000006
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数２】
2019513245.tif 000007
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数である、
ことを特徴とする、請求項５に記載の方法。
【請求項７】
ソーシャルネットワークに基づいてグループを探索するデバイスであって：
クエリ端末によって伝送されるグループ探索要求を受け取るように構成された探索要求モジュールであって、前記グループ探索要求は、指定されたクエリユーザＩＤ、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、探索要求モジュールと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するように構成されたソーシャルネットワークグラフ取得モジュールであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ソーシャルネットワークグラフ取得モジュールと；
クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って、指定された数の層において探索拡張を行うように構成され、且つ、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するように構成され、決定されたグループメンバの数が指定されたグループ規模を満たすことを保証する、層探索モジュールであって；
ここで前記拡張プロセスにおいて拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、層探索モジュールと；
決定された前記グループメンバ及び前記クエリユーザによって探索対象グループを形成するように構成されたグループ決定モジュールと；
前記探索対象グループのグループコリティビティが前記指定されたグループコリティビティ以上であるか否かを判定するように構成され、且つ、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果としてクエリ端末に表示するためにフィードバックするように構成された、グループフィードバックモジュールと、
を含むことを特徴とする、デバイス。
【請求項８】
前記クエリユーザＩＤに対応するユーザノードを根ノードとして使用してＢＦＳツリーを構築するように構成された探索ツリー構築モジュールであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内で前記クエリユーザ識別から開始してすべてのユーザノードを逐次トラバースする、探索ツリー構築モジュールと；
構築された前記ＢＦＳツリーに従って各ユーザノードから前記根ノードまでの最短社会的距離を決定するように構成された最短社会的距離計算モジュールと；
前記グループ規模と前記最短社会的距離との間の差を計算するように構成されたプルーニングモジュールであって、１以下の差に対応するユーザノードは、プルーニングノードとして定められ、前記プルーニングモジュールは、前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するようにさらに構成された、プルーニングモジュールと、
をさらに含むことを特徴とする、請求項７に記載のデバイス。
【請求項９】
前記プルーニングモジュールは、前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するようにさらに構成され、ここで前記ノードコリティビティは、前記ユーザノードに隣接するノードの数であり、前記プルーニングモジュールは、前記ユーザノードが存在する場合、探索されたユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するようにさらに構成されることを特徴とする、請求項８に記載のデバイス。
【請求項１０】
前記層探索モジュールは、前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するようにさらに構成され、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードであり；前記層探索モジュールは、前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するようにさらに構成され、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードであり；前記層探索モジュールは、前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行うようにさらに構成され、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するように構成されることを特徴とする、請求項７に記載のデバイス。
【請求項１１】
複数の決定された探索対象グループが存在し、前記デバイスは：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定するように構成され、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するように構成された、グループネットワークグラフ構築モジュールと；
各グループネットワークグラフの親密度を計算するように構成された親密度計算モジュールと；
をさらに含み、
前記グループフィードバックモジュールは、最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするようにさらに構成されることを特徴とする、請求項７に記載のデバイス。
【請求項１２】
前記グループネットワークグラフの前記親密度を計算する式は：
【数３】
2019513245.tif 000008
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数４】
2019513245.tif 000009
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数であることを特徴とする、請求項１１に記載のデバイス。
【請求項１３】
プロセッサと、コンピュータ実行可能命令を格納したメモリとを含むサーバであって、前記コンピュータ実行可能命令は、前記プロセッサによって実行されたときに、前記プロセッサに：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、前記グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ステップと；
前記クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、ステップと；
前記決定されたグループメンバ及び前記クエリユーザによって探索対象グループを形成するステップと；
前記探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
を含むステップを行わせることを特徴とするサーバ。
【請求項１４】
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得する前記ステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、前記複数のユーザノード、及び前記ユーザノードを接続するように構成された前記エッジ集合を含む、前記ステップを実行した後、前記プロセッサは：
前記クエリユーザＩＤに対応する前記ユーザノードを根ノードとして使用してＢＦＳツリーを構築するステップであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内のすべてのユーザノードを前記クエリユーザＩＤから開始して逐次トラバースする、ステップと；
構築された前記ＢＦＳツリーに従って、各ユーザノードから前記根ノードまでの最短社会的距離を決定するステップと；
前記グループ規模と前記最短社会的距離との間の差を計算し、１以下の差に対応するユーザノードがプルーニングノードとして定められ、前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するステップと、
を含むステップをさらに実行することを特徴とする、請求項１３に記載のサーバ。
【請求項１５】
前記グループ規模と前記最短社会的距離との間の前記差を計算し、１以下の差に対応するユーザノードが前記プルーニングノードとして定められ、前記ソーシャルネットワークグラフ内で前記プルーニングノード及び前記プルーニングノードに関連付けられた前記エッジ集合が除去され、前記プルーニング済ソーシャルネットワークグラフを生成するステップを実行した後、前記プロセッサは：
前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するステップであって、前記ノードコリティビティは、前記ユーザノードに隣接するノードの数である、ステップと、
前記ユーザノードが存在する場合、探索された前記ユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するステップと、
を含むステップをさらに実行することを特徴とする、請求項１４に記載のサーバ。
【請求項１６】
前記プロセッサは、前記クエリユーザＩＤに対応する前記ユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有する前記ユーザノードを各探索拡張層においてグループメンバとして決定する前記ステップを実行し；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードであり、これは：
前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するステップであって、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードである、ステップと；
前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するステップであって、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードである、ステップと；
前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するステップと、
を含むことを特徴とする、請求項１３に記載のサーバ。
【請求項１７】
複数の決定された探索対象グループが存在し、前記プロセッサは、以下の：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定し、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するステップと；
各グループネットワークグラフの親密度を計算するステップと；
最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
をさらに実行することを特徴とする、請求項１３に記載のサーバ。
【請求項１８】
前記グループネットワークグラフの前記親密度を計算する式は：
【数５】
2019513245.tif 000010
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数６】
2019513245.tif 000011
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数であることを特徴とする、請求項１７に記載のサーバ。
【請求項１９】
コンピュータ実行可能命令を格納した少なくとも１つの非一時的コンピュータ可読媒体であって、前記コンピュータ実行可能命令は、少なくとも１つのプロセッサによって実行されたときに、前記少なくとも１つのプロセッサに：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、前記グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ステップと；
前記クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、ステップと；
前記決定されたグループメンバ及び前記クエリユーザによって探索対象グループを形成するステップと；
前記探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
を含むステップを行わせることを特徴とする、非一時的コンピュータ可読媒体。
【請求項２０】
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得する前記ステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、前記複数のユーザノード、及び前記ユーザノードを接続するように構成された前記エッジ集合を含む、前記ステップを実行した後、前記プロセッサは：
前記クエリユーザＩＤに対応する前記ユーザノードを根ノードとして使用してＢＦＳツリーを構築するステップであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内のすべてのユーザノードを前記クエリユーザＩＤから開始して逐次トラバースする、ステップと；
構築された前記ＢＦＳツリーに従って、各ユーザノードから前記根ノードまでの最短社会的距離を決定するステップと；
前記グループ規模と前記最短社会的距離との間の差を計算し、１以下の差に対応するユーザノードがプルーニングノードとして定められ、前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するステップと、
を含むステップをさらに実行することを特徴とする、請求項１９に記載の非一時的コンピュータ可読媒体。
【請求項２１】
前記グループ規模と前記最短社会的距離との間の前記差を計算し、１以下の差に対応するユーザノードが前記プルーニングノードとして定められ、前記ソーシャルネットワークグラフ内で前記プルーニングノード及び前記プルーニングノードに関連付けられた前記エッジ集合が除去され、前記プルーニング済ソーシャルネットワークグラフを生成する前記ステップを実行した後、前記プロセッサは：
前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するステップであって、前記ノードコリティビティは、前記ユーザノードに隣接するノードの数である、ステップと、
前記ユーザノードが存在する場合、探索された前記ユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するステップと、
を含むステップをさらに実行することを特徴とする、請求項２０に記載の非一時的コンピュータ可読媒体。
【請求項２２】
前記プロセッサは、前記クエリユーザＩＤに対応する前記ユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有する前記ユーザノードを各探索拡張層においてグループメンバとして決定する前記ステップを実行し；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードであり、これは：
前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するステップであって、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードである、ステップと；
前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するステップであって、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードである、ステップと；
前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するステップと、
を含むことを特徴とする、請求項１９に記載の非一時的コンピュータ可読媒体。
【請求項２３】
複数の決定された探索対象グループが存在し、前記プロセッサは、以下の：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定し、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するステップと；
各グループネットワークグラフの親密度を計算するステップと、
最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
をさらに実行することを特徴とする、請求項１９に記載の非一時的コンピュータ可読媒体。
【請求項２４】
前記グループネットワークグラフの前記親密度を計算する式は：
【数７】
2019513245.tif 000012
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数８】
2019513245.tif 000013
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数であることを特徴とする、請求項２３に記載の非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、コンピュータアプリケーション技術の分野に関し、より具体的には、ソーシャルネットワークに基づいてグループを探索する方法、デバイス、サーバ及び記憶媒体に関する。
【０００２】
関連技術の相互参照
本出願は、２０１７年４月７日に出願された「ソーシャルネットワークに基づいてグループを探索する方法及びデバイス（英訳：ＭＥＴＨＯＤ  ＡＮＤ  ＤＥＶＩＣＥ  ＯＦ  ＳＥＡＲＣＨＩＮＧ  Ａ  ＧＲＯＵＰ  ＢＡＳＥＤ  ＯＮ  ＳＯＣＩＡＬ  ＮＥＴＷＯＲＫ）」と題する中国特許出願番号第２０１７１０２２４８８４．２号に基づく優先権を主張し、その内容は参照によりその全体が本明細書に明示的に組み入れられる。
【背景技術】
【０００３】
オンラインのソーシャルネットワークは、人々の生活にとって不可欠なものとなってきており、このことはソーシャルネットワーク解析に大きな課題を生じさせている。グループメント（ｇｒｏｕｐｍｅｎｔ、グループ性）は、ソーシャルネットワークの最も重要な属性の１つであり、それゆえソーシャルネットワークに基づいてグループメントを研究することが徐々にトレンドになってきている。
【０００４】
生活及び仕事において、夕食会を準備するといった作業のために、ソーシャルネットワークからグループを探索する必要がある。グループを探索する従来の方法は、最初にグループの数に従ってソーシャルネットワークデータ内のノードのすべての可能な組合せを決定し、次いで探索されたすべての組合せをグループの他の条件によって１つ１つスキャンすることである。計算は非常に膨大であり、探索効率は極めて低い。
【発明の概要】
【０００５】
本開示の種々の実施形態によれば、ソーシャルネットワークに基づいてグループを探索する方法、デバイス、サーバ及び記憶媒体が提供される。
【０００６】
ソーシャルネットワークに基づいてグループを探索する方法は、
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード（頂点）、及びユーザノードを接続するために用いられるエッジ（枝）集合を含む、ステップと；
クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数がグループ規模と等しくなるまで、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである、ステップと；
決定されたグループメンバ及びクエリユーザによって探索対象グループを形成するステップと；
探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上である場合、探索対象グループをクエリ結果としてクエリ端末に表示するためにフィードバックするステップと、
を含む。
【０００７】
ソーシャルネットワークに基づいてグループを探索するデバイスは：
クエリ端末によって伝送されるグループ探索要求を受け取るために使用される探索要求モジュールであって、グループ探索要求は、指定されたクエリユーザＩＤ、指定されたグループ規模、及びグループコリティビティを含み、グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、探索要求モジュールと；
グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するために使用されるソーシャルネットワークグラフ取得モジュールであって、ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するために用いられるエッジ集合を含む、ソーシャルネットワークグラフ取得モジュールと；
ソーシャルネットワークグラフに従って、クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、指定された数の層において探索拡張を行うために使用され、且つ、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するために使用され、決定されたグループメンバの数が指定されたグループ規模を満たすことを保証する、層探索モジュールであって；
拡張プロセスにおいて拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである、層探索モジュールと；
決定された前記グループメンバ及びクエリユーザによって探索対象グループを形成するために使用されるグループ決定モジュールと；
探索対象グループのグループコリティビティが前記指定されたグループコリティビティ以上であるか否かを判定するために使用され、且つ、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上である場合、探索対象グループをクエリ結果としてクエリ端末に表示するためにフィードバックするために使用される、グループフィードバックモジュールと、
を含む。
【０００８】
サーバは、プロセッサと、コンピュータ実行可能命令を格納したメモリとを含み、コンピュータ実行可能命令は、前記プロセッサによって実行されたときに、プロセッサに：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード、及びユーザノードを接続するために使用されるエッジ集合を含む、ステップと；
クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数がグループ規模と等しくなるまで、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである、ステップと；
決定されたグループメンバ及びクエリユーザによって探索対象グループを形成するステップと；
探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上である場合、探索対象グループをクエリ結果としてクエリ端末に表示するためにフィードバックするステップと、
を含むステップを行わせる。
【０００９】
コンピュータ実行可能命令を格納した少なくとも１つの非一時的コンピュータ可読媒体であって、コンピュータ実行可能命令は、少なくとも１つのプロセッサによって実行されたときに、少なくとも１つのプロセッサに：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するために用いられるエッジ集合を含む、ステップと；
クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数がグループ規模と等しくなるまで、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである、ステップと；
決定されたグループメンバ及びクエリユーザによって探索対象グループを形成するステップと；
探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であることを判定し、探索対象グループをクエリ結果としてクエリ端末に表示するために返すステップと、
を含むステップを行わせる。
【００１０】
本開示の１つ又はそれより多くの実施形態の詳細は、以下の図面及び説明を参照して提示される。本開示の他の特徴、目的及び利点は、明細書、図面及び特許請求の範囲からより明白になるであろう。
【図面の簡単な説明】
【００１１】
【図１】一実施形態によるソーシャルネットワークに基づいてグループを探索する方法の実装環境の模式図である。
【図２】一実施形態によるサーバのブロック図である。
【図３】一実施形態によるソーシャルネットワークに基づいてグループを探索する方法のフローチャートである。
【図４】一実施形態によるソーシャルネットワークグラフの模式図である。
【図５Ａ】一実施形態によるクエリユーザを開始ノードとして使用する層探索を示す模式図である。
【図５Ｂ】一実施形態によるクエリユーザを開始ノードとして使用する層探索を示す模式図である。
【図６Ａ】一実施形態による層探索による探索対象グループを示す模式図である。
【図６Ｂ】一実施形態による層探索による探索対象グループを示す模式図である。
【図６Ｃ】一実施形態による層探索による探索対象グループを示す模式図である。
【図７】一実施形態によるソーシャルネットワークグラフにおけるノードプルーニングに伴うフローチャートである。
【図８】一実施形態によるソーシャルネットワークグラフにおけるノードプルーニングを示す模式図である。
【図９】一実施形態によるクエリ条件を満たす複数のグループが存在するときに最適化グループを選択することを伴うフローチャートである。
【図１０】一実施形態によるソーシャルネットワークに基づいてグループを探索するデバイスのブロック図である。
【図１１】別の実施形態によるソーシャルネットワークに基づいてグループを探索するデバイスのブロック図である。
【図１２】さらに別の実施形態によるソーシャルネットワークに基づいてグループを探索するデバイスのブロック図である。
【発明を実施するための形態】
【００１２】
本開示は、本開示の目的、技術的解決策及び利点がより明らかになるように、添付の図面及び実施形態を参照して詳細に説明される。しかしながら、本発明の種々の実施形態は、多くの異なる形態で具体化することができ、本明細書で述べられる実施形態に限定されるものと解釈すべきではない。むしろこれらの実施形態は、この開示が完全且つ包括的であるように、及び、本開示の範囲を当業者に完全に伝えるように提供される。
【００１３】
図１は、ソーシャルネットワークに基づいてグループを探索する方法の実装環境の模式図であり、これはクエリ端末１１０及びサーバ１２０を含む。クエリ端末１１０は、ネットワークを介してサーバ１２０と通信することができる。クエリ端末１１０は、スマートフォン、タブレットコンピュータ、ノートブックコンピュータ、及びデスクトップコンピュータのうちの少なくとも１つであり得るが、これらに限定されない。サーバ１２０は、独立した物理サーバ、又は複数の物理サーバのサーバクラスタであり得る。クエリ端末１１０は、クエリユーザ、グループ規模、及びグループコリティビティ（ｃｏｒｉｔｉｖｉｔｙ）を指定するグループ探索要求をサーバ１２０へ伝送する。サーバ１２０は、クエリユーザを中心として使用して、クエリ端末の指定されたグループクエリ要求（グループ規模及びグループコリティビティ）に従って、データソース（ソーシャルネットワークグラフ）に対して階層的探索拡張を行う。サーバ１２０は、ソーシャルネットワークグラフ内に最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定し、グループ規模要件は、決定プロセス中に保証される。グループの初期決定後、決定されたグループのコリティビティ検証が行われる。コリティビティ要件が満たされている場合、探索されたグループに対応するグループ情報がクエリ端末に返される。
【００１４】
図２を参照すると、一実施形態により、サーバ１２０が提供される。サーバ１２０は、プロセッサ、非一時的記憶媒体、ランダムアクセスメモリ（ＲＡＭ）、ネットワークインタフェース、ディスプレイスクリーン、及び入力デバイスを含み、これらはシステムバスを介して結合されている。サーバ１２０の非一時的記憶媒体は、オペレーティングシステム、データベース及びコンピュータ可読命令を格納し、これはプロセッサによって実行されたとき、図３に示すソーシャルネットワークに基づいてグループを探索する方法をプロセッサに行わせる。データベースは、データを格納するため、例えば、ソーシャルネットワークグラフ、及びソーシャルネットワークに基づいてグループを探索する方法を実行するプロセスに関連した他のデータを格納する、などのために用いられる。プロセッサは、計算及び制御能力を提供してサーバ１２０の全体の動作をサポートするために用いられる。サーバ内のＲＡＭは、非一時的記憶媒体の中のオペレーティングシステム、データベース、及びコンピュータ可読命令のために、高速キャッシュを伴う動作環境を提供する。ネットワークインタフェースは、クエリ端末１１０と通信するために用いられる。当業者は、図２に示すサーバの構造が本開示の解決策の構造の一部に過ぎず、サーバに制限を課すものではないことを理解することができる。詳細には、サーバは、図中に示したものよりも多くの若しくは少ない構成要素を含むことができ、又はいくつかの構成要素を組み合わせることができ、又は異なる構成要素配置を有することができる。
【００１５】
図３を参照すると、一実施形態により、図２に示すサーバに適用することができる、ソーシャルネットワークに基づいてグループを探索する方法が提供される。上記方法は、以下のようなステップを含む。
【００１６】
ステップＳ２０２において、クエリ端末によって伝送されたグループ探索要求を受け取る。グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含む。グループコリティビティは、グループメンバに隣接する他のグループメンバの最小数を定める。
【００１７】
クエリ端末内にクエリインタフェースが表示され、ユーザは、クエリインタフェース内でクエリ条件を設定することができる。詳細には、クエリ条件は、グループ規模及びグループコリティビティを含む。本明細書においては、グループ規模は、グループメンバの数を意味し、グループコリティビティは、決定されたグループメンバの中の各グループメンバに隣接する他のグループメンバの最小数である。
【００１８】
クエリ条件を特定の状況において説明する。アリス（Ａｌｉｃｅ）が１０人（アリスを含む）の夕食会を主催することを望んでいると仮定し、参加者同士の馴染みが薄いせいで夕食会がぎこちないものになることを避けるために、アリスは以下のようなクエリ要件を作成するものとする：１）夕食会の規模は１０人（アリスを含む）；２）各参加者は少なくとも他の３人の参加者を知っている。要件１）はグループ規模であり、要件２）はグループコリティビティである。
【００１９】
図４を参照すると、６グループメンバを含むグループがあり、その各々は少なくとも３つの他のグループメンバと隣接しており、それゆえグループはグループコリティビティ３を有する。
【００２０】
ユーザは、クエリインタフェースにおける入力制御によって、グループ規模及びグループコリティビティを設定することができる。加えて、クエリユーザは、クエリインタフェースによって指定され得る。クエリユーザは、指定されたグループメンバであり、すなわち必ず含まれなければならないグループメンバである。例えば、アリスは、この例示的な状況におけるクエリユーザである。
【００２１】
一実施形態によれば、クエリユーザを指定する前に、微博（ウェイボー）、マイクロソフトネットワーク（ＭＳＮ（登録商標））などのクエリソーシャルネットワークサイトを設定する必要がある。サーバは、選択されたソーシャルネットワークサイトに従って、クエリユーザに対応する端末制御に対して、対応するクエリユーザＩＤをプッシュし、それはユーザが端末制御を通じてクエリユーザＩＤを選択することを可能にする。
【００２２】
デフォルト状態において、クエリユーザは、選択されたデータベースにおけるクエリ端末ユーザのユーザＩＤである。例えば、選択されたソーシャルネットワークサイトが微博であり、クエリ端末のユーザＩＤがＬｉｔｃｈであるとする。デフォルト状態において、クエリユーザは、微博におけるＬｉｔｃｈのＩＤ、例えばＬｉｔｃｈｓｗｅｅｔｙである。
【００２３】
一実施形態によれば、指定されたソーシャルウェブサイトにおけるクエリ端末ユーザのユーザＩＤを、登録情報中の登録された識別情報（例えば、電話番号、実名、識別番号等）によって自動的にクエリすることができる。
【００２４】
ステップＳ２０４において、グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフが取得される。ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード（頂点）、及びユーザノードを接続するために用いられるエッジ（枝）集合を含む。
【００２５】
ソーシャルネットワークグラフは、予め指定されたソーシャルネットワークサイトにおける社会的関係データに従って生成される。ソーシャルネットワークにおける社会的関係は、友人、相互関心（ｍｕｔｕａｌ  ａｔｔｅｎｔｉｏｎ）及び互いに関連付けられた関係であり得る。社会的関係は、２つの要素を含み、それらはユーザ、及びそれに関連付けられた関係である。社会的関係に従って生成されたソーシャルネットワークグラフは、ノード（頂点）を通じてユーザを識別し、ノード間のエッジ（枝）を通じてそれらに関連付けられた関係を識別するものであり、すなわち図４はソーシャルネットワークグラフである。
【００２６】
ソーシャルネットワークの社会的関係に従って生成されたソーシャルネットワークグラフは、巨大で精巧なソーシャルネットワークイメージである。従来の方式によれば、クエリ条件を満たすグループをスクリーニングすることが主要なプロジェクトであり、それはより多くの時間及びより多大な計算リソースを費やすことになる。例証される実施形態において、クエリ条件を満たすグループを探索するという目的は、１層ごとに中心ノードを決定することによって迅速且つ正確に達成され、その具体的なステップは後述する。
【００２７】
ステップＳ２０６において、クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張が行われる。ソーシャルネットワークグラフ内で決定されたグループメンバの数がグループ規模と等しくなるまで、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定する。拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接するユーザノードである。
【００２８】
最初に、ソーシャルネットワークグラフ内でクエリユーザＩＤの位置を特定し、位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフを生成する。
【００２９】
詳細には、第１の拡張層に含まれるユーザノードは、クエリユーザに対応するユーザノードに隣接するユーザノードである。図５Ａのソーシャルネットワークグラフを参照して、クエリ端末によって指定されたクエリユーザがユーザノードｖ４であると仮定すると、したがって第１の拡張層に含まれるユーザノードはユーザノードｖ４に隣接するノードであり、それらは、図５Ｂの拡張サブグラフにそれぞれ示すように、ｖ２、ｖ５、及びｖ６である。
【００３０】
第１の拡張層内のユーザノードが決定された後、第１の拡張層に含まれるユーザノードから、あるユーザノードをグループメンバとして決定する。詳細には、最大数の隣接ノードを有するユーザノードをグループメンバとして決定する。第１の拡張層において、ソーシャルネットワークグラフ内のユーザノードｖ２の隣接ノードは６であり、ソーシャルネットワークグラフ内のユーザノードｖ５の隣接ノードは７であり、ソーシャルネットワークグラフ内のユーザノードｖ６の隣接ノードは４である。従って、ｖ５がグループメンバとして選択される。
【００３１】
新たなグループメンバが決定された後、新たなグループメンバに対応するユーザノードを中心ノードとして使用して、拡張層の次のレベルの拡張が行われる。第２の拡張層は、ｖ５を新たな中心ノードとして使用して拡張される。同様に、第２次拡張層に含まれるユーザノードは、ｖ５に隣接する隣接ノードである。決定されたグループメンバのユーザノードは、新たな拡張層には含まれないことに留意されたい。図５Ｂを参照すると、ノードｖ４はノードｖ５に隣接しているが、ｖ４はすでにグループメンバとして決定されたユーザノードであり、それゆえノードｖ４は第２の拡張層に含まれない。第２の拡張層に含まれるユーザノードは、それぞれ、ｖ１、ｖ２、ｖ３、ｖ６、ｖ７及びｖ９である。第２の拡張層に従って、最大数の隣接するユーザノードを有するノードはｖ２（隣接ノードの数は６）であると決定される。従って、ｖ２がグループメンバとして決定される。
【００３２】
指定されたグループ規模が４である場合、決定する必要があるのは最後のグループメンバのみであり、すなわち第３の拡張層に拡張するだけで充分である。同様に、第３の拡張層に含まれるユーザノードは、ｖ１、ｖ８、ｖ３、及びｖ６である。ソーシャルネットワークグラフ内で、ｖ１、ｖ８、ｖ３、ｖ６の隣接ノードは、３、４、４、及び４である。それゆえ、決定されたグループメンバは、ｖ８、ｖ３、又はｖ６であり得る。
【００３３】
ステップＳ２０８において、決定されたグループメンバ及びクエリユーザによって探索対象グループが形成される。
【００３４】
ステップＳ２０６によれば、決定された探索対象グループは、｛ｖ４，ｖ５，ｖ２，ｖ６｝、｛ｖ４，ｖ５，ｖ２，ｖ３｝、又は｛ｖ４，ｖ５，ｖ２，ｖ８｝であり得る。
【００３５】
グループメンバ及びその関係（関連付けられた関係は、社会的関係グラフから決定することができる）に従って、探索対象グループのグループネットワークグラフが構築される。
【００３６】
｛ｖ４，ｖ５，ｖ２，ｖ６｝、｛ｖ４，ｖ５，ｖ２，ｖ３｝、｛ｖ４，ｖ５，ｖ２，ｖ８｝のグループネットワークグラフを、それぞれ、図６Ａ、図６Ｂ、及び図６Ｃに示す。
【００３７】
ステップＳ２１０において、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かが判定され、以上である場合、探索対象グループは、クエリ結果として表示されるためにクエリ端末へフィードバックされる。
【００３８】
探索対象グループのコリティビティは、図６Ａ〜図６Ｃに従って判定することができる。｛ｖ４，ｖ５，ｖ２，ｖ６｝のコリティビティは３であり、｛ｖ４，ｖ５，ｖ２，ｖ３｝のコリティビティは２であり、｛ｖ４，ｖ２，ｖ２，ｖ３｝のコリティビティは２であり、｛ｖ４，ｖ５，ｖ２，ｖ８｝のコリティビティは１である。クエリ端末によって指定されたグループコリティビティが３である場合、｛Ｖ４，ｖ５，ｖ２，ｖ６｝がクエリ条件を満たすグループである。クエリ端末によって指定されたグループコリティビティが２である場合、｛Ｖ４，ｖ５，ｖ２，ｖ６｝及び｛ｖ４，ｖ５，ｖ２，ｖ３｝がクエリ条件を満たすグループである。クエリ条件を満たすグループがクエリ端末へプッシュされる。
【００３９】
例示された実施形態のソーシャルネットワークに基づいてグループを探索する方法によれば、クエリユーザを中心として使用して層拡張を行い、それはソーシャルネットワークデータ内の各ノードの接続関係にのみ依存する。拡張プロセスは、単純且つ迅速であり、探索され得るすべての可能な組合せを１つずつスクリーニングする必要はなく、それによりクエリ効率が改善される。加えて、選択されたグループメンバは、より高いコリティビティを有し、これは探索されたグループがより高い親密度を有することを保証する。
【００４０】
一実施形態によれば、Ｓ２０４において、グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフが取得される。ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成される。ソーシャルネットワークグラフは、複数のユーザノード、及びユーザノードを接続するために用いられるエッジ集合を含む。ステップＳ２０４の後、上記方法は、取得されたソーシャルネットワークグラフに対してプルーニングプロセスが行われるステップをさらに含む。ステップＳ２０６において、クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って探索拡張が行われる。決定されたグループメンバの数が指定されたグループ規模を満たすまで、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定する。拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接するユーザノードである。
【００４１】
詳細には、図７を参照して、取得したソーシャルネットワークグラフに対してプルーニング（剪定）プロセスが行われ、これは以下のステップを含む。
【００４２】
ステップＳ３０２において、クエリユーザＩＤに対応するユーザノードを根ノード（ルートノード）として使用して幅優先探索（ＢＦＳ）ツリーが構築され、ＢＦＳツリーは、ソーシャルネットワークグラフ内のすべてのユーザノードをクエリユーザＩＤから開始して逐次トラバースする。
【００４３】
ＢＦＳは、グラフの頂点ｖ０から開始し、頂点ｖ０がアクセスされた後、まだアクセスされていないｖ０の隣接する頂点ｗ１、ｗ２が逐次的にアクセスされる。そして次に、ｗ１の未探査の各隣接ノード及びｗ２の未探査の各隣接ノードが逐次的に探索され、アクセスされる。接続したグラフ中のすべての頂点が１回はアクセスされるまで、ｖ０と連通し且つ長さ１、２の経路を有する頂点が、ｖ０から開始して近くから遠くへ階層的且つ逐次的にアクセスされる。
【００４４】
図８（ａ）のソーシャルネットワークグラフに従って、クエリユーザｖ１を根ノードとして使用して、ＢＦＳツリーが構築される。図８（ｂ）は、クエリユーザｖ１に基づいて、ソーシャルネットワークグラフに従って構築されたＢＦＳツリーの模式図である。
【００４５】
ステップＳ３０４において、構築されたＢＦＳツリーに従って、各ユーザノードから根ノードまでの最短社会的距離が決定される。
【００４６】
各ユーザノードから根ノード（クエリユーザ）までの社会的距離は、構築されたＢＦＳツリーに従って決定することができる。ＢＦＳツリーによって決定される社会的距離は、最短社会的距離である。図８（ｂ）を参照すると、Ｖ２、Ｖ３及びＶ５の最短社会的距離は１であり、Ｖ４、Ｖ６、Ｖ８の最短社会的距離は２であり、Ｖ７の最短社会的距離は３である。
【００４７】
ステップＳ３０６において、グループ規模と最短社会的距離との間の差が計算される。１以下の差に対応するユーザノードが、プルーニングノードとして定められる。プルーニングノード及びプルーニングノードに関連付けられたエッジ集合は、ソーシャルネットワークグラフから除去され、プルーニング済ソーシャルネットワークグラフが生成される。
【００４８】
指定されたグループ規模が４であると仮定すると、その最短社会的距離が３であるｖ７のユーザノードに関して、グループ規模４と最短社会的距離３との間の差は１以下であり、それゆえｖ７のユーザノードは、プルーニングノードである。３より大きい最短社会的距離に対応するユーザノードもまたプルーニングノードである。
【００４９】
ステップＳ３０８において、プルーニング済ソーシャルネットワークグラフのユーザノードの中にコリティビティ要件を満たさないユーザノードが存在するか否かが探索される。上記ユーザノードが存在する場合、プルーニング済ソーシャルネットワーク内の該ユーザノードは除去され、プルーニング済ソーシャルネットワークグラフが更新される。
【００５０】
クエリ条件中にグループコリティビティに対する要件が存在するので、グループのコリティビティは、実際にはグループメンバのコリティビティである。もし探索されたソーシャルネットワーク内のユーザノードのコリティビティが要件を満たさなければ、これがグループメンバとして使用された場合、グループにおけるコリティビティは、もはや要件を満たさないことになる。従って、プルーニング済みのネットワークグラフ内のユーザノードのコリティビティを検査すべきである。コリティビティ要件を満たさないユーザノードが存在する場合、そのユーザノードは、再びプルーニングされるべきである。
【００５１】
探索されるグループのコリティビティが３であると仮定すると、その最短社会的距離が条件を満たさないノードｖ７がプルーニングされた後、ノードｖ８のコリティビティは２であり、これはグループのコリティビティ未満である。従って、ｖ８のノードは、プルーニング済ソーシャルネットワークグラフに基づいて再びプルーニングされる。最終的に、プルーニング後のソーシャルネットワークを図８（ｃ）に示す。
【００５２】
プルーニング済ソーシャルネットワークグラフに基づいて層拡張を行うことはより簡単になり、生成されるサブグラフは単純化され、それによりグループクエリの効率が改善される。
【００５３】
一実施形態によれば、図９を参照すると、複数のグループがクエリ条件（グループ規模及びグループコリティビティ）を満たし、層拡張によって探索された場合、ソーシャルネットワークに基づいてグループを探索する方法は、以下も含む。
【００５４】
ステップＳ４０２において、ソーシャルネットワークグラフに従って、探索対象グループ内の各グループメンバ間のエッジ集合が決定され、決定されたエッジ集合に従って、グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフが構築される。
【００５５】
グループメンバ情報は、層拡張によって決定された探索対象グループに従って決定することができる。グループメンバ間の関係は、グループメンバ情報及びソーシャルネットワークグラフ（ソーシャルネットワークグラフがすでにプルーニングされている場合は、プルーニング済ソーシャルネットワークグラフ）に従って決定することができる。グループメンバは、ユーザノードとして使用され、グループメンバ間の関係は、エッジ集合として使用され、それにより探索対象グループのネットワークグラフを生成することができる。
【００５６】
指定されたコリティビティが１である場合、決定されたグループ｛ｖ４，ｖ５，ｖ２，ｖ６｝、｛ｖ４，ｖ５，ｖ２，ｖ３｝、及び｛ｖ４，ｖ５，ｖ２，ｖ８｝のグループネットワークグラフは、それぞれ、図６Ａ、図６Ｂ、及び図６Ｃに示される。
【００５７】
ステップＳ４０４において、各グループネットワークグラフの親密度が計算される。
【００５８】
各探索対象グループに対応するグループの親密度は、生成されたグループネットワークグラフに従って計算される。最初に、グループネットワークグラフ内で、いずれか２つのノード間の親密度が計算される。そして次に、ノード親密度のすべての可能な組合せを合計して、グループの親密度を得る。図６Ａを参照すると、｛ｖ２，ｖ６｝、｛ｖ２，ｖ４｝、｛ｖ２，ｖ５｝、｛ｖ４，ｖ６｝、｛ｖ４，ｖ５｝、｛ｖ５，ｖ６｝のノード親密度が、逐次的に計算される。次いで６つのノード親密度を合計して、グループの親密度を得る。
【００５９】
詳細には、ノード親密度を計算する式は下記の通りである。
【００６０】
指定されたグラフＧ＝（Ｖ，Ｅ）、ｕ，ｖ∈Ｖ、（ｕ，ｖ）∈Ｅ、について、ｕ及びｖの親密度は
【数１】
2019513245.tif 000003
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数である。親密度の計算において、分子は、ノードｕ及びノードｖの共通ノードの数プラス１であり、これは主として、２つのノード間のエッジが存在するのに親密度が０になるという状況を避けるためのものである。グラフＧ＝（Ｖ，Ｅ）の親密度は、そのノード間のエッジの親密度の合計であり、これは
【数２】
2019513245.tif 000004
である。
【００６１】
例えば、ソーシャルネットワークグラフの親密度は、
Ｃｏ（ＧA）＝ω（ｖ2，ｖ4）＋ω（ｖ2，ｖ5）＋ω（ｖ2，ｖ6）＋ω（ｖ4，ｖ5）＋ω（ｖ4，ｖ6）＋ω（ｖ5，ｖ6）＝３／４＋３／４＋３／４＋３／４＋３／４＋３／４＝９／２；Ｃｏ（ＧB）＝ω（ｖ2，ｖ3）＋ω（ｖ2，ｖ5）＋ω（ｖ2，ｖ4）＋ω（ｖ4，ｖ5）＋ω（ｖ4，ｖ3）＋ω（ｖ5，ｖ3）＝１／２＋３／４＋１／２＋１／２＋３／２＋１／２＝１７／４；Ｃｏ（ＧC）＝ω（ｖ2，ｖ4）＋ω（ｖ2，ｖ5）＋ω（ｖ2，ｖ8）＋ω（ｖ4，ｖ5）＋ω（ｖ4，ｖ8）＋ω（ｖ5，ｖ8）＝１／２＋１／２＋１／４＋２／３＋１＋１＝４７／１２
である。
【００６２】
比較によって、Ｃｏ（ＧA）＞Ｃｏ（ＧB）＞Ｃｏ（ＧC）であることが分かる。それゆえ、クエリ端末へプッシュされるグループは図６Ａに示すグループである。
【００６３】
ステップＳ４０６において、最高度の親密度を有するグループネットワークグラフに対応する探索対象グループがクエリ端子へフィードバックされ、クエリ結果として表示される。
【００６４】
一実施形態によれば、クエリ条件（グループサイズ及びグループコリティビティ）を満たす層拡張によって探索された複数のグループが存在する場合、各々の決定された探索対象グループのコリティビティを計算することもまた可能である。最大コリティビティが存在する場合、最大コリティビティを有する探索対象グループが、表示されるクエリ結果としてクエリ端末に返される。図６Ａ〜図６Ｃを参照すると、グループコリティビティは、それぞれ３、２、１である。クエリ条件によって定められるグループコリティビティが１である場合、３つの探索対象グループはすべてクエリ条件を満たし、その場合、結果はグループコリティビティの値に従ってプッシュされる。換言すれば、最大グループコリティビティを有する探索対象グループが、クエリ端末に表示するためにプッシュされる。
【００６５】
一実施形態によれば、図１０を参照すると、ソーシャルネットワークに基づいてグループを探索するデバイスが提供され、それは以下を含む。
【００６６】
探索要求モジュール５１０は、クエリ端末によって伝送されるグループ探索要求を受け取るために使用される。グループ探索要求は、指定されたクエリユーザＩＤ、指定されたグループ規模、及びグループコリティビティを含む。グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める。
【００６７】
ソーシャルネットワークグラフ取得モジュール５２０は、グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するために用いられる。ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、ソーシャルネットワークグラフは、複数のユーザノード、及びユーザノードを接続するために用いられるエッジ集合を含む。
【００６８】
層探索モジュール５３０は、クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、ソーシャルネットワークグラフに従って、指定された数の層において探索拡張を行うために使用される。層探索モジュール５３０は、ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するために使用され、これは決定されたグループメンバの数が指定されたグループ規模を満たすことを保証する。
【００６９】
拡張プロセスにおいて拡張層の第１のレベルに含まれるユーザノードは、クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、拡張層の上位レベルによって決定されたグループメンバに隣接したユーザノードである。
【００７０】
グループ決定モジュール５４０は、決定されたグループメンバ及びクエリユーザによって探索対象グループを形成するために使用される。
【００７１】
グループフィードバックモジュール５５０は、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定するために使用され、且つ、探索対象グループのグループコリティビティが指定されたグループコリティビティ以上である場合、探索対象グループをクエリ結果としてクエリ端末に表示するためにフィードバックするために使用される。
【００７２】
一実施形態によれば、図１１を参照して、ソーシャルネットワークに基づいてグループを探索するデバイスは、以下を含む。
【００７３】
探索ツリー構築モジュール６１０は、クエリユーザＩＤに対応するユーザノードを根ノードとして使用してＢＦＳツリーを構築するために使用される。ＢＦＳツリーは、ソーシャルネットワークグラフ内でクエリユーザ識別から開始して逐次すべてのユーザノードをトラバースする。
【００７４】
最短社会的距離計算モジュール６２０は、構築されたＢＦＳツリーに従って各ユーザノードから根ノードまでの最短社会的距離を決定するために使用される。
【００７５】
プルーニングモジュール６３０は、グループ規模と最短社会的距離との間の差を計算するために使用される。１以下の差に対応するユーザノードがプルーニングノードとして定められ、ソーシャルネットワークグラフ内のプルーニングノード及びプルーニングノードに関連付けられたエッジ集合が除去され、プルーニング済ソーシャルネットワークグラフが生成される。
【００７６】
一実施形態によれば、プルーニングモジュール６３０は、プルーニング済ソーシャルネットワークグラフのユーザノードの中にグループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索及び判定するためにさらに使用され、ノードコリティビティは、ユーザノードに隣接するノードの数である。プルーニングモジュール６３０は、上記ユーザノードが存在する場合、探索されたユーザノードをプルーニング済みのソーシャルネットワークから除去し、プルーニング済ソーシャルネットワークグラフを更新するために使用される。
【００７７】
一実施形態によれば、図１２を参照すると、複数の決定された探索対象グループが存在し、デバイスはさらに以下を含む。
【００７８】
グループネットワークグラフ構築モジュール７１０は、ソーシャルネットワークグラフに従って探索対象グループ内のグループメンバ間のエッジ集合を決定するために使用される。グループネットワークグラフ構築モジュール７１０は、決定されたエッジ集合に従って、グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するために使用される。
【００７９】
親密度計算モジュール７２０は、各グループネットワークグラフの親密度を計算するために使用される。
【００８０】
グループフィードバックモジュール５５０は、最大親密度を有するグループネットワークグラフに対応する探索対象グループを、クエリ結果としてクエリ端末に表示するためにフィードバックするために、さらに使用される。
【００８１】
一実施形態によれば、グループネットワークグラフの親密度を計算するための式は、下記の通りである。
【００８２】
Ｃｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）はグループネットワークグラフであり、Ｖはグループネットワークグラフ内の頂点の集合であり、Ｅはグループネットワークグラフ内のエッジ集合である。
【００８３】
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数３】
2019513245.tif 000005
である。
【００８４】
Ｎ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数である。
【００８５】
ネットワークアクセス挙動認識デバイスの種々のモジュールは、ソフトウェア、ハードウェア又はそれらの組合せによって、一部が又は全体として実装することができる。その中でも、ネットワークインタフェースは、イーサネット（登録商標）カード又は無線カードであり得る。上記モジュールは、サーバのプロセッサに埋め込まれてもよく、若しくはプロセッサから独立したものであってもよく、又はサーバのメモリ内にソフトウェアの形態で格納されてもよく、プロセッサが上記種々のモジュールの対応するステップを実行することを促進するようになっている。プロセッサは、中央処理ユニット（ＣＰＵ）、マイクロプロセッサ、マイクロコントローラ等であり得る。
【００８６】
当業者は、上記実施形態における方法のプロセスは、下層のハードウェアに命令するコンピュータプログラムによって全部又は一部を実装することができることを理解するはずである。プログラムは、コンピュータ可読記憶媒体に格納することができ、コンピュータオペレーティングシステム内の少なくとも１つのプロセッサによって実行することができる。プログラムは、これが実行されているとき、種々の方法の実施形態のプロセスを含むことができる。記憶媒体は、ディスク、ＣＤ、読み出し専用メモリ（ＲＯＭ）であり得る。
【００８７】
それぞれの実施形態を１つずつ説明してきたが、それぞれの実施形態は孤立したものではないことを理解されたい。当業者は、本出願の開示を読むと、それぞれの実施形態に関与するそれぞれの技術的特徴は、それらが互いに抵触しない限り、それぞれの実施形態間で任意に併合され得ることを明白に認識することができる。もちろん、同じ実施形態において言及されたそれぞれの技術的特徴もまた、それらが互いに抵触しない限り任意に併合され得る。
【００８８】
本発明は、本明細書において特定の実施形態を参照して例証され説明されが、本発明は、示した詳細に限定されることを意図したものではない。当業者によって容易に想到される、本発明において開示される技術範囲内のいずれの変形又は置換も、すべて本発明の保護範囲内に入るべきものであることに留意されたい。したがって、本発明の保護範囲は、添付の請求項の保護範囲に従うものである。
【符号の説明】
【００８９】
１１０：クエリ端末
１２０：サーバ
【図１】
2019513245.tif 000014
【図２】
2019513245.tif 000015
【図３】
2019513245.tif 000016
【図４】
2019513245.tif 000017
【図５Ａ】
2019513245.tif 000018
【図５Ｂ】
2019513245.tif 000019
【図６Ａ】
2019513245.tif 000020
【図６Ｂ】
2019513245.tif 000021
【図６Ｃ】
2019513245.tif 000022
【図７】
2019513245.tif 000023
【図８】
2019513245.tif 000024
【図９】
2019513245.tif 000025
【図１０】
2019513245.tif 000026
【図１１】
2019513245.tif 000027
【図１２】
2019513245.tif 000028
【手続補正書】
【提出日】平成29年12月28日(2017.12.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ソーシャルネットワークに基づいてグループを探索する方法であって：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、前記グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ステップと；
前記クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、ステップと；
前記決定されたグループメンバ及び前記クエリユーザによって探索対象グループを形成するステップと；
前記探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
を含むことを特徴とする方法。
【請求項２】
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得する前記ステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、前記複数のユーザノード、及び前記ユーザノードを接続するように構成された前記エッジ集合を含む、前記ステップの後、前記方法は：
前記クエリユーザＩＤに対応する前記ユーザノードを根ノードとして使用して幅優先探索（ＢＦＳ）ツリーを構築するステップであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内のすべてのユーザノードを前記クエリユーザＩＤから開始して逐次トラバースする、ステップと；
構築された前記ＢＦＳツリーに従って、各ユーザノードから前記根ノードまでの最短社会的距離を決定するステップと、
前記グループ規模と前記最短社会的距離との間の差を計算するステップであって、１以下の差に対応するユーザノードがプルーニングノードとして定められる、ステップと；
前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するステップと、
をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記グループ規模と前記最短社会的距離との間の前記差を計算し、１以下の差に対応するユーザノードが前記プルーニングノードとして定められ、前記ソーシャルネットワークグラフ内で前記プルーニングノード及び前記プルーニングノードに関連付けられた前記エッジ集合が除去され、前記プルーニング済ソーシャルネットワークグラフを生成した後、前記方法は：前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するステップであって、前記ノードコリティビティは、前記ユーザノードに隣接するノードの数である、ステップと、前記ユーザノードが存在する場合、探索された前記ユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するステップと、をさらに含むことを特徴とする、請求項２に記載の方法。
【請求項４】
前記クエリユーザＩＤに対応する前記ユーザノードを開始ノードとして使用して前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有する前記ユーザノードを各探索拡張層においてグループメンバとして決定する前記ステップであって、ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、前記ステップは：
前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するステップであって、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードである、ステップと；
前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するステップであって、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードである、ステップと；
前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するステップと、
を含むことを特徴とする、請求項１に記載の方法。
【請求項５】
複数の決定された探索対象グループが存在し、前記方法は：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定し、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するステップと；
各グループネットワークグラフの親密度を計算するステップと；
最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項６】
前記グループネットワークグラフの前記親密度を計算する式は：
【数１】
2019513245.tif 000029
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数２】
2019513245.tif 000030
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数である、
ことを特徴とする、請求項５に記載の方法。
【請求項７】
コンピュータ実行可能命令を格納した少なくとも１つの非一時的コンピュータ可読媒体であって、前記コンピュータ実行可能命令は、少なくとも１つのプロセッサによって実行されたときに、前記少なくとも１つのプロセッサに：
クエリ端末から伝送されたグループ探索要求を受け取るステップであって、前記グループ探索要求は、指定されたクエリユーザ識別（ＩＤ）、指定されたグループ規模、及びグループコリティビティを含み、前記グループコリティビティは、他のメンバに隣接するグループメンバの最小数を定める、ステップと；
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得するステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、複数のユーザノード、及び前記ユーザノードを接続するように構成されたエッジ集合を含む、ステップと；
前記クエリユーザＩＤに対応するユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードを各探索拡張層においてグループメンバとして決定するステップであって；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードである、ステップと；
前記決定されたグループメンバ及び前記クエリユーザによって探索対象グループを形成するステップと；
前記探索対象グループのグループコリティビティが指定されたグループコリティビティ以上であるか否かを判定し、前記探索対象グループの前記グループコリティビティが前記指定されたグループコリティビティ以上である場合、前記探索対象グループをクエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
を含むステップを行わせることを特徴とする、非一時的コンピュータ可読媒体。
【請求項８】
前記グループ探索要求に応答して、予め生成されたソーシャルネットワークグラフを取得する前記ステップであって、前記ソーシャルネットワークグラフは、ソーシャルネットワークサイトにおける社会的関係データに従って生成され、前記ソーシャルネットワークグラフは、前記複数のユーザノード、及び前記ユーザノードを接続するように構成された前記エッジ集合を含む、前記ステップを実行した後、前記プロセッサは：
前記クエリユーザＩＤに対応する前記ユーザノードを根ノードとして使用してＢＦＳツリーを構築するステップであって、前記ＢＦＳツリーは、前記ソーシャルネットワークグラフ内のすべてのユーザノードを前記クエリユーザＩＤから開始して逐次トラバースする、ステップと；
構築された前記ＢＦＳツリーに従って、各ユーザノードから前記根ノードまでの最短社会的距離を決定するステップと；
前記グループ規模と前記最短社会的距離との間の差を計算し、１以下の差に対応するユーザノードがプルーニングノードとして定められ、前記ソーシャルネットワークグラフ内の前記プルーニングノード及び前記プルーニングノードに関連付けられたエッジ集合を除去し、プルーニング済ソーシャルネットワークグラフを生成するステップと、
を含むステップをさらに実行することを特徴とする、請求項７に記載の非一時的コンピュータ可読媒体。
【請求項９】
前記グループ規模と前記最短社会的距離との間の前記差を計算し、１以下の差に対応するユーザノードが前記プルーニングノードとして定められ、前記ソーシャルネットワークグラフ内で前記プルーニングノード及び前記プルーニングノードに関連付けられた前記エッジ集合が除去され、前記プルーニング済ソーシャルネットワークグラフを生成する前記ステップを実行した後、前記プロセッサは：
前記プルーニング済ソーシャルネットワークグラフのユーザノードの中に前記グループコリティビティ未満のノードコリティビティに対応するユーザノードが存在するか否かを探索するステップであって、前記ノードコリティビティは、前記ユーザノードに隣接するノードの数である、ステップと、
前記ユーザノードが存在する場合、探索された前記ユーザノードを前記プルーニング済みのソーシャルネットワークから除去し、前記プルーニング済ソーシャルネットワークグラフを更新するステップと、
を含むステップをさらに実行することを特徴とする、請求項８に記載の非一時的コンピュータ可読媒体。
【請求項１０】
前記プロセッサは、前記クエリユーザＩＤに対応する前記ユーザノードを開始ノードとして使用して、前記ソーシャルネットワークグラフに従って探索拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有する前記ユーザノードを各探索拡張層においてグループメンバとして決定する前記ステップを実行し；
ここで拡張層の第１のレベルに含まれるユーザノードは、前記クエリユーザの隣接ノードであり、拡張層の次のレベルに含まれるユーザノードは、前記拡張層の上位レベルによって決定された前記グループメンバに隣接したユーザノードであり、これは：
前記ソーシャルネットワークグラフにおいて前記クエリユーザＩＤが位置する前記ユーザノードの位置を特定し、前記位置特定されたユーザノードを開始ノードとして使用して層拡張を行って、拡張サブグラフの第１の拡張層を生成するステップであって、前記第１の拡張層に含まれるユーザノードは、前記クエリユーザに隣接するユーザノードである、ステップと；
前記拡張サブグラフの前記第１の拡張層からグループメンバを決定するステップであって、前記グループメンバに対応するユーザノードは、前記ソーシャルネットワークグラフ内で最大数の隣接ノードを有するユーザノードである、ステップと；
前記第１の拡張層の前記グループメンバに対応するユーザノードを開始ノードとして使用して、前記拡張サブグラフの拡張層の次のレベルの拡張を行い、決定されたグループメンバの数が前記グループ規模と等しくなるまで、対応する拡張層において新たなグループメンバを決定するステップと、
を含むことを特徴とする、請求項７に記載の非一時的コンピュータ可読媒体。
【請求項１１】
複数の決定された探索対象グループが存在し、前記プロセッサは、以下の：
前記ソーシャルネットワークグラフに従って前記探索対象グループ内の前記グループメンバ間のエッジ集合を決定し、決定された前記エッジ集合に従って、前記グループメンバをユーザノードとして使用して、各探索対象グループのグループネットワークグラフを構築するステップと；
各グループネットワークグラフの親密度を計算するステップと、
最大親密度を有するグループネットワークグラフに対応する探索対象グループを、前記クエリ結果として前記クエリ端末に表示するためにフィードバックするステップと、
をさらに実行することを特徴とする、請求項７に記載の非一時的コンピュータ可読媒体。
【請求項１２】
前記グループネットワークグラフの前記親密度を計算する式は：
【数３】
2019513245.tif 000031
であり、ここでＣｏ（Ｇ）はグループの親密度であり、Ｇ＝（Ｖ，Ｅ）は前記グループネットワークグラフであり、Ｖは前記グループネットワークグラフ内の頂点の集合であり、Ｅは前記グループネットワークグラフ内のエッジ集合であり、
ノードｕ，ｖ∈Ｖ、及び（ｕ，ｖ）∈Ｅであり、
【数４】
2019513245.tif 000032
であり、ここでＮ（ｕ）は、ノードｕの隣接ノード集合であり、｜Ｎ（ｕ）∩Ｎ（ｖ）｜は、ノードｕ及びノードｖの共通ノードの数であることを特徴とする、請求項１１に記載の非一時的コンピュータ可読媒体。
【国際調査報告】
2019513245.tif 000033
2019513245.tif 000034
2019513245.tif 000035
2019513245.tif 000036