(57)【要約】  ソーシャル・ネットワークと、どのユーザーにソーシャル・ネットワークにアクセスすることを許可するかを示すアクセス制御リストのような、関連するアクセス情報と共に用いる技法について記載する。ソーシャル・ネットワークは、ユーザー間の関係を表す。ソーシャル・ネットワークおよびアクセス制御リストは、グラスで表すことができ、ソーシャル・ネットワークを用いて異なる動作を実行することに関連して、このグラフを通行する。【選択図】      図３
2011504255.tif 000002
【特許請求の範囲】
【請求項１】
ソーシャル・ネットワーキング・ウェブサイトの第１ユーザーおよび第２ユーザーが接続されているか否か判定するための、コンピューターにより実行される方法であって、
ソーシャル・ネットワーク（２３４）と、複数のユーザーのうちどの１つ以上が、ユーザー間の関係を定める前記ソーシャル・ネットワーク（２３４）へのアクセスを許可されているかを示すアクセス情報（２３６）とを表すグラフ（２００、２５０、３００）を受信するステップであって、前記グラフ（２００、２５０、３００）が、前記複数のユーザーの各々に１つのノードと、前記ソーシャル・ネットワークの１つに含まれるものとして２つのノード間における関係を示す、前記グラフの２つのノード間にあるエッジ（２０４ａ）とを含み、前記第１ユーザーおよび前記第２ユーザーが、それぞれ、前記グラフにおいて第１ノードおよび第２ノードとして表される、ステップと、
前記第１ノードから前記第２ノードまでのパスが存在するか否か判定する（３６６）ために前記グラフ（２００、２５０、３００）を通行する（３５０）ステップであって、前記第１ユーザーが前記アクセス情報（２３６）に従って前記パスにおける各ノードを見るためにアクセスを有し、前記パスが２つ以上のエッジを含む、ステップと、
を含む、方法。
【請求項２】
請求項１記載の方法において、前記通行するステップは、幅方向優先技法を用いて、前記グラフのノードを通行する、方法。
【請求項３】
請求項１記載の方法において、前記グラフの前記エッジは、２つのノード間にある第１種類のエッジであって、前記２つのノードの一方が、前記２つのノードの他方と関連のあるソーシャル・ネットワークに含まれることを示す、方法。
【請求項４】
請求項３記載の方法において、前記グラフは、２つのノード間に第２種類のエッジを含んで、前記２つのノードの一方が、前記２つのノードの他方と関連のあるアクセス制御リストに含まれており、前記一方のノードに、前記他方のノードの１つ以上のソーシャル・ネットワークへのアクセスを与えることを示す、方法。
【請求項５】
請求項４記載の方法において、２つのノード間における前記第１種類のエッジを通行する前に、前記第１ユーザーが、前記第１種類の前記エッジによって表される関係を見るためにアクセスを有するか否か判定する、方法。
【請求項６】
請求項５記載の方法において、前記第１ユーザーを表す前記第１ノードと、前記アクセス制御リストのユーザーに対応するアクセス制御リストと関連のあるノードとの間に、前記第２種類の他のエッジがある場合、前記第１ユーザーは、前記第１種類のエッジによって表される関係を見るためにアクセスを有する、方法。
【請求項７】
請求項１記載の方法において、前記通行するステップは、更に、
前記第１ノードから特定の距離以内にある、前記第１ノードからの全てのパスを判定するステップを含む、方法。
【請求項８】
請求項７記載の方法であって、更に、
前記第２ノードが、前記パスの１つにノードとして含まれているか否か判定するステップを含む、方法。
【請求項９】
請求項１記載の方法において、前記第１ユーザーが、別のユーザーのソーシャル・ネットワークに対するアクセスを、前記別のユーザーのアクセス制御リストによって示されるとおりに有しない場合、前記通行するステップは、前記ソーシャル・ネットワークを構成員を含まないものとして扱って処理を実行する、方法。
【請求項１０】
請求項１記載の方法において、前記アクセス情報は、前記アクセス制御リストに含まれる各ユーザーを明示的にリストすることによって定められた少なくとも１つのアクセス制御リストを含む、方法。
【請求項１１】
請求項１記載の方法において、前記アクセス情報は、前記ソーシャル・ネットワークの一部を用いて暗示的に定められた少なくとも１つのアクセス制御リストを含む、方法。
【請求項１２】
請求項１記載の方法において、第１ユーザーが、第１構成員を含む第１ソーシャル・ネットワークを定め、更に前記第１構成員と、前記第１ソーシャル・ネットワークの前記第１構成員の各々の第２ソーシャル・ネットワークに含まれる他の構成員とを含むアクセス制御リストを暗示的に定める、方法。
【請求項１３】
請求項１記載の方法において、第１ユーザーが、第１構成員を含む第１ソーシャル・ネットワークを定め、更にアクセス制御リストを暗示的に定め、前記アクセス制御リストは、前記第１構成員を含まず、前記第１ソーシャル・ネットワークの前記第１構成員の各々の第２ソーシャル・ネットワークの他の構成員を含む、方法。
【請求項１４】
ソーシャル・ネットワーキング・ウェブサイトの第１ユーザーに関係したソーシャル・ネットワーキング・ウェブサイトの１つ以上のユーザーを判定するための、コンピューターにより実行される方法であって、
ソーシャル・ネットワーク（２３４）と、複数のユーザーのうちどれが、ユーザー間の関係を定める前記ソーシャル・ネットワーク（２３４）へのアクセスを許可されているかを示すアクセス情報（２３６）とのグラフ（２００、２５０、３００）を受信するステップであって、前記グラフ（２００、２５０、３００）が、前記複数のユーザーの各々に１つのノードと、前記ソーシャル・ネットワークの１つに含まれるものとして２つのノード間における関係を示す、前記グラフの２つのノードの間にあるエッジとを含み、前記第１ユーザーが、前記グラフの第１ノードによって表される、ステップと、
前記第１ノードから発する任意のパスを判定するために前記グラフ（２００、２５０、３００）を通行するステップであって、前記パスの各々が前記第１ノードから特定の距離以内にあり、前記第１ユーザーが前記アクセス情報に従って前記パスにおける各ノードを見るためにアクセスを有する、ステップと、
前記パスに含まれる前記グラフ（２００、２５０、３００）のノードの集合を判定するステップであって、前記集合の各ノードが、前記特定の距離以内にある前記第１ノードに関係する前記ソーシャル・ネットワーキング・ウェブサイトのユーザーに対応する、方法。
【請求項１５】
請求項１４記載の方法において、前記通行するステップは、前記グラフのノードを幅方向優先様式で通行する、方法。
【請求項１６】
請求項１４記載の方法において、前記グラフは、２つのノードの一方が、前記２つのノードの他方と関連のあるソーシャル・ネットワークに含まれることを示すために、前記２つのノード間に第１種類のエッジを含む、方法。
【請求項１７】
請求項１６記載の方法において、前記グラフは、２つのノードの一方が、該２つのノードの他方と関連のあるアクセス制御リストに含まれており、前記一方のノードに、前記他方のノードの１つ以上のソーシャル・ネットワークへのアクセスを与えることを示すために、前記２つのノード間に第２種類のエッジを含む、方法。
【請求項１８】
ソーシャル・ネットワーキング・ウェブサイトの第１ユーザーおよび第２ユーザーが関係付けられているか否か判定するためのコードが格納されているコンピューター読み取り可能媒体であって、
前記ソーシャル・ネットワーキング・ウェブサイトのユーザーに対し定めたソーシャル・ネットワーク（２３４）と、前記ユーザーのどれに、ユーザー間の関係を定めた前記ソーシャル・ネットワーク（２３４）に対するアクセスを許可するかを示すアクセス情報（２３６）とを記述するデーター構造（２００、２５０、３００）を受信し、
前記第１ユーザーが、前記アクセス情報（２３６）に従って前記ユーザーのうち他のものを通じて、前記第１ユーザーおよび前記第２ユーザーを接続する全ての介在する関係を見るためにアクセスを有する関係が、前記第１ユーザーから前記第２ユーザーに存在するか否か判定するために、前記データー構造（２００、２５０、３００）を通行する、
ためのコードを含む、コンピューター読み取り可能媒体。
【請求項１９】
請求項１８記載のコンピューター読み取り可能媒体において、前記アクセス情報は、前記アクセス制御リストに含まれる各ユーザーを明示的にリストすることによって定められた少なくとも１つのアクセス制御リストを含む、コンピューター読み取り可能媒体。
【請求項２０】
請求項１８記載のコンピューター読み取り可能媒体において、前記アクセス情報は、
第１ユーザーの第１ソーシャル・ネットワークと、第２ユーザーの第２ソーシャル・ネットワークとの間の少なくとも１つの接続を用いて暗示的に定められた、前記第１ユーザーの少なくとも１つのアクセス制御リストを含む、コンピューター読み取り可能媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
ソーシャル・ネットワーキング・ウェブサイトは、ユーザーに情報を交換することを許可するウェブサイトの一カテゴリとして特徴付けることができる。また、ソーシャル・ネットワーキング・ウェブサイトは、オンライン・プロファイルおよびソーシャル・ネットワークを作成することも、ユーザーに許可する。ソーシャル・ネットワークは、個人によって、他のユーザーのリストとして定めることができ、このリストは、当該個人とリストに含まれる他のユーザーとの間における個人的な１組の関係または職業に関する１組の関係を表す。既存のソーシャル・ネットワーキング・ウェブサイトは、個々の地理的領域、作業現場、または学校系列からのユーザーを含む公衆ソーシャル・ネットワークを定める。この公衆ソーシャル・ネットワークは、ウェブサイトの全てのユーザーにアクセス可能である。これらの公衆ソーシャル・ネットワークへの所属は、ユーザー・プロファイルに入力されている情報に基づいてというようにして、各ユーザーによって自己申告すればよい。自己申告による入会に基づく個々の公衆ソーシャル・ネットワークに対する会員の地位(membership)は、特定の従業員のために働くことを宣告したユーザーに、その従業員に関係するドメイン・ネームを含む電子メール・アドレスを供給することを要求することによって、検証することができる。また、ユーザーが彼／彼女が特定の都市または州に居住することを示すというようにして、会員の地位を検証しなくてもよい場合もある。定められた公衆ソーシャル・ネットワークは、ウェブサイトの異なるユーザー間における間接的な関係を発見するために、集合的に用いることができる。第１ユーザーは、彼／彼女はどのようにすれば他の第２ユーザーに接続できるか問い合わせることができる。ソーシャル・ネットワーキング・サイトは、公衆ソーシャル・ネットワークを用いて、第１ユーザーに、どのようにして第１ユーザーが第２ユーザーに接続されるのかを示す情報を提供することができる。例えば、第１および第２ユーザー双方が同じ学校に通っていることもあり得るし、同じ雇用者のために働いていることもあり得る。また、ソーシャル・ネットワーキング・サイトは、ユーザーに個人ソーシャル・ネットワークを定めることも許可し、この場合、友人リストのような、個人ソーシャル・ネットワークを表すユーザーのリストが、そのリストを定めた所有者およびリストの構成員によって目視可能にすることもできる。また、ユーザーは、公衆または個人ソーシャル・ネットワークにおける会員の地位に基づいて、ブログ・エントリのような、電子コンテンツをフィルタにかけることもできる。
【発明の概要】
【課題を解決するための手段】
【０００２】
この摘要は、詳細な説明において以下で更に説明する概念から選択したものを、簡略化した形態で紹介するために設けられている。この摘要は、特許請求する主題の主要な特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を判断する際に補助として用いることも意図していない。
【０００３】
ソーシャル・ネットワークと、どのユーザーにソーシャル・ネットワークにアクセスすることを許可するかを示すアクセス制御リストのような、関連するアクセス情報と共に用いる技法について記載する。ソーシャル・ネットワークは、ユーザー間の関係を表す。ソーシャル・ネットワークおよびアクセス制御リストは、グラフで表すことができ、ソーシャル・ネットワークを用いて異なる動作を実行することに関連して、このグラフを通行（traverse）する。
【図面の簡単な説明】
【０００４】
本発明の特徴および利点は、添付図面と関連付けた以下の実施形態例の詳細な説明から一層明らかとなろう。
【図１】図１は、本明細書において記載する技法と共に利用することができる環境を示す一実施形態の一例である。
【図２】図２は、図１のデバイスを備えることができるコンポーネントの一実施形態の一例である。
【図３】図３は、ソーシャル・ネットワークおよびアクセス制御リストを利用するグラフィック図の第１の例である。
【図４】図４は、第２の例に関する、ソーシャル・ネットワークおよび関連するアクセス制御リストを表す表である。
【図５】図５は、図４からの情報のグラフィック図である。
【図５Ａ】図５Ａは、図５からのグラフの変形を用いる一例である。
【図６】図６は、ソーシャル・ネットワークおよびアクセス制御リストを利用するグラフィック図の別の例である。
【図６Ａ】図６Ａは、図６からのグラフの変形を利用する一例である。
【図７】図７は、２つのノード間にパスがあるか否か判定するときに、ソーシャル・ネットワークおよびアクセス制御リストを利用する処理ステップのフローチャートである。
【図８】図８は、問い合わせ元ノードから特定の距離以内にあるノードのリストを決定するときに、ソーシャル・ネットワークおよびアクセス制御リストを利用する処理ステップのフローチャートである。
【発明を実施するための形態】
【０００５】
図１を参照すると、ソーシャル・ネットワーキング・サイトと共に、本明細書に記載する技法を利用する実施形態を実現することができる、適した計算環境の一例が示されている。図１に示す計算環境は、適した計算環境の一例に過ぎず、アクセス制御リストをソーシャル・ネットワークと共に用いることに関して、本明細書において記載する技法の使用範囲や機能に対して何の限定を示唆することも意図しない。
【０００６】
ソーシャル・ネットワーキング・ウェブサイトは、ユーザーに情報を交換することを許可するウェブサイトの一カテゴリとして特徴付けることができる。また、ソーシャル・ネットワーキング・ウェブサイトは、オンライン・プロファイルおよびソーシャル・ネットワークを作成することも、ユーザーに許可する。ソーシャル・ネットワークは、個人によって、他のユーザーのリストとして定めることができ、このリストは、ソーシャル・ネットワークを定めた個人とリストに含まれる他のユーザーとの間における個人的な１組の関係または職業に関する１組の関係を表す。ソーシャル・ネットワークは、特定のソーシャル・ネットワークによって表される関係のコンテキストにおける人間間の結びつきの集合体、およびこれらの結びつきの強さの双方を表す。例えば、ソーシャル・ネットワークは、友人、家族、同僚等を表すために作成することができる。ソーシャル・ネットワーク、および本明細書における技法と関連付けたそれらの使用について、以下の章において説明する。
【０００７】
本明細書に記載する技法は、１つ以上のコンピューターまたはその他のデバイスによって実行するプログラム・モジュールのような、コンピューター実行可能命令という一般的なコンテキストにおいて記載することができる。一般に、プログラム・モジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データー構造等を含み、特定のタスクを実行するか、または特定の抽象データー・タイプを実現する。通例、プログラム・モジュールの機能は、種々の実施形態において所望通りに組み合わせるまたは分散させることができる。本明細書において記載する技法は、他の汎用または特殊目的計算環境およびコンフィギュレーションとの使用にも適することができることは、当業者には認められよう。周知の計算システム、環境、および／またはコンフィギュレーションの例には、限定ではなく、パーソナル・コンピューター、サーバー・コンピューター、ハンドヘルドまたはラップトップ・デバイス、マルチプロセッサ・システム、マイクロプロセッサベースのシステム、プログラマブル消費者電子機器、ネットワークＰＣ、ミニコンピューター、メインフレーム・コンピューター、分散型計算環境等が含まれる。分散型計算環境は、以上のシステムまたはデバイスのうち任意のものを含む。
【０００８】
図１には、デバイス１２、ネットワーク１４、およびサーバー１５が含まれる。デバイス１２は、例えば、パーソナル・コンピューターのようなコンピューターとすることができ、表示出力デバイスと、そのユーザーとの対話型Ｉ／Ｏを備える入力デバイスとを有する。以下の章では、デバイス１２に関して更に詳細に説明する。しかしながら、同じ詳細は、一実施形態においてネットワーク１４に接続することができる１つ以上の他のデバイスにも応用することができる。図１の例１０は１つのデバイスおよび１つのサーバーのみを含むが、本明細書における技法を利用する実施形態は、任意の数のデバイスおよびその他のコンポーネントを含むことができる。
【０００９】
図１に含まれるデバイス１２は、ソフトウェア・コンポーネントと関係付けて、本明細書に記載する技法を例示する目的のための一例である。一実施形態では、本明細書に記載する機能を提供する任意のデバイス１２を実施形態に含めることができる。デバイス１２は、１つ以上のプログラム・モジュールに含まれるコードを実行するために用いられるプロセッサを含むことができる。本明細書に記載する技法に関してデバイス１２によって実行することができるプログラム・モジュールについて、本明細書の別のところで更に詳しく説明する。デバイス１２は、ネットワーク接続環境で動作し、サーバー１５および図１には示されていないその他のコンピューターまたはコンポーネントと通信することができる。本明細書において記載する場合、デバイス１２はパーソナル・コンピューターとするとよい。他の実施形態では、デバイス１２の機能、またはデバイス１２自体が、当該デバイス１２が利用される個々の環境に従って、別のコンポーネントに含まれていてもよい。
【００１０】
尚、デバイス１２は、ネットワーク接続環境において通信するものとしてこの例では示されているが、デバイス１２は異なる通信媒体を利用して他のコンポーネントと通信してもよいことは、当業者には認められよう。例えば、デバイス１２は、ネットワーク接続、および／またはその他の種類のリンクを利用して、１つ以上のコンポーネントと通信することもできる。リンクには、インターネット、イントラネット、あるいはサーバー１５および／またはその他のコンポーネントへのその他のワイヤレスおよび／またはハードワイヤ接続（１つ又は複数）が含まれるが、これらに限定されるのではない。
【００１１】
尚、デバイス１２は、サーバー１５への接続手段(connectivity)を有するように例示されているが、本明細書において記載する技法は、ネットワークを用いずにサーバー１５に直接接続されているデバイスと共に用いることもできることは、記してしかるべきであろう。
【００１２】
図２を参照すると、デバイス１２に含むことができるコンポーネントの一例が示されており、本明細書において記載する技法の種々の実施形態の実行と関係付けて用いることができる。デバイス１２は、１つ以上の処理ユニット２０、メモリー２２、ネットワーク・インターフェース・ユニット２６、ストレージ３０、１つ以上のその他の通信接続２４、およびデバイス１２のコンポーネント間における通信を容易にするために用いられるシステム・バス３２を含むことができる。
【００１３】
デバイス１２のコンフィギュレーションおよび種類に依存して、メモリー２２は、揮発性（ＲＡＭのような）、不揮発性（ＲＯＭ、フラッシュ・メモリー等のような）、またはこれら２つの何らかの組み合わせとすることができる。加えて、デバイス１２は追加の機構／機能も有することができる。例えば、デバイス１２は、追加のストレージ（リムーバブルおよび／または非リムーバブル）を含むことができ、この追加のストレージにはＵＳＢデバイス、磁気または光ディスク、あるいはテープが含まれるが、これらに限定されるのではない。このような追加のストレージは、図２において、ストレージ３０によって示されている。図２のストレージ３０は、１つ以上のリムーバブルおよび非リムーバブル記憶デバイスを含むことができ、これらのデバイスには、デバイス１２によって利用することができるコンピューター読み取り可能媒体が関連付けられている１つ以上のリムーバブルおよび非リムーバブル記憶デバイスを含むことができる。この例において例示するコンピューター読み取り可能媒体の説明は、ハード・ディスクまたはＣＤ−ＲＯＭドライブのような大容量記憶デバイスに言及することができるが、コンピューター読み取り可能媒体は、デバイス１２によってアクセスできるのであれば任意の入手可能な媒体とすればよいことは当業者には認められよう。
【００１４】
一例として、そして限定ではなく、コンピューター読み取り可能媒体は、コンピューター記憶媒体および通信媒体を含むことができる。メモリー２２およびストレージ３０は、コンピューター記憶媒体の例である。コンピューター記憶媒体は、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含み、コンピューター読み取り可能命令、データー構造、プログラム・モジュール、またはその他のデーターといような情報の記憶のために、任意の方法または技術で実現される。コンピューター記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリーまたはその他のメモリー技術、ＣＤ−ＲＯＭ、（ＤＶＤ）またはその他の光ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージまたはその他の磁気記憶デバイス、あるいは所望の情報を格納するために用いることができてデバイス１２によってアクセスすることができる任意のその他の媒体を含むが、これらに限定されるのではない。
【００１５】
また、デバイス１２は、通信接続（１つ又は複数）２４も内蔵することができ、コンピューターは、一例として、入力デバイスおよび出力デバイスのような他のデバイスおよびコンポーネントと通信することが可能になる。
【００１６】
一実施形態では、デバイス１２は、図１に示すようなネットワーク接続環境において、ネットワークを通じたリモート・コンピューターとの論理接続を用いて動作することができる。デバイス１２は、図１のネットワーク１４に、バス３２に接続されているネットワーク・インターフェース・ユニット２６を通じて接続することができる。また、ネットワーク・インターフェース・ユニット２６は、他の種類のネットワークおよび／またはリモート・システムおよびコンポーネントと共に利用することもできる。
【００１７】
１つ以上のプログラム・モジュールおよび／またはデーター・ファイルをストレージ３０に含ませることもできる。デバイス１２の動作の間、ストレージ３０に含まれるこれらのエレメントの１つ以上は、例えば、ユーザー・コンピューター１２の動作を制御するためのＲＡＭのような、メモリー２２の一部に常駐することもできる。図２の例は、オペレーティング・システム４０、ウェブ・ブラウザ４６、ならびにその他のコンポーネント、入力、および／または出力４８を含む種々のコンポーネントを示す。
【００１８】
オペレーティング・システム４０は、種々の市販のオペレーティング・システムまたは企業固有のオペレーティング・システムのうち任意の１つとすればよい。例えば、デバイス１２の動作を制御することに関して、オペレーティング・システム４０をメモリーにロードすることができる。
【００１９】
ウェブ・ブラウザ４６は、デバイス１２にインストールされているソフトウェア・アプリケーションとすることができる。このウェブ・ブラウザを用いると、ユーザーは、インターネットまたはその他のローカル・エリア・ネットワークのウェブ・サイトにおけるウェブ・ページからの情報にアクセスすることができる。デバイス１２のユーザーは、ウェブ・ブラウザ４６を用いてサーバー１５に接続することができる。
【００２０】
本明細書における技法に関して、デバイス１５はソーシャル・ネットワーキング・ウェブサイトをホストするために用いることもできる。サーバー１５は、デバイス１２のユーザーのようなユーザーが、プロファイルを作成し、ソーシャル・ネットワークを定めて利用する等のことを行うことを可能にするソフトウェアを含むことができる。ユーザーは、当該ユーザーとその他のユーザーとの間の関係を表すソーシャル・ネットワークを定めることができる。ソーシャル・ネットワークは、他のユーザーのリストとして表すことができる。このリストは、当該リストを定めた個々の所有者と、そのソーシャル・ネットワークの構成員との間の関係のコンテキストを示すタイトルまたはラベルを有することができる。例えば、ソーシャル・ネットワークは、友人、家族、同僚、同級生、特定の組織の会員(membership)等の各々について定めることができる。
【００２１】
ユーザーは、彼女のソーシャル・ネットワークのアクセスを特定の個人に制限することまたは制御することができる。以下の章で説明するが、アクセス制御リストは、他のユーザーのうち誰にアクセスを付与し、第１ユーザーが定めた１つ以上のソーシャル・ネットワークを見ることを許可するか指定するために、第１ユーザーによって定めることができる。
【００２２】
尚、図１のサーバー１５は、図２に関して説明したコンポーネントと同様のコンポーネントを有する１つ以上のコンピューターを含むこともできることは、記してしかるべきであろう。ウェブ・ブラウザ・アプリケーションを含む代わりに、サーバーは、サーバー１５にホストされている種々のサービスを提供するための１つ以上のソフトウェア・コンポーネントを含んでもよい。例えば、サーバー１５は、ユーザーにアクセス制御リストを定めさせるソフトウェア・コンポーネントを含むこともできる。アクセス制御リストは、ウェブサイトの他のユーザーの誰に、ユーザーのソーシャル・ネットワークの１つ以上へのアクセスを許可するかを示すアクセス情報を指定するために用いることができる。また、サーバー１５は、アクセス制御リストを利用して１つ以上の異なる動作を実行するためのソフトウェア・コンポーネントを含むこともできる。例えば、サーバー１５は、ユーザーが他のユーザーと関係付けられているか否か問い合わせることを、当該ユーザーに行わせることができる。別の一例として、第１ユーザーは、ウェブサイトの他のユーザーの誰が、ある距離またはある数のホップ以内で、第１ユーザーに関係付けられているかについて問い合わせることができる。各ホップは、２人のユーザー間における異なる関係を表す。以上のことについて、以下の章において更に詳しく説明する。
【００２３】
ユーザーによって定められたソーシャル・ネットワークは、リストとして表すことができる。ソーシャル・ネットワークは、ユーザー間の関係を追跡するために用いることができ、ユーザー間の間接的な関係を発見するためにも用いることができる。ソーシャル・ネットワークは、グラフ形態で表されているユーザー間のこれら直接的関係および間接的関係を定めるために用いることができる。
【００２４】
図３を参照すると、ユーザー間の関係を図式化して例示した例が示されている。この例２００において、各ユーザーはグラフにおけるノードとして表されている。ユーザー間のソーシャル関係は、実線エッジによって示されている。例２００における第１ノードと第２ノードとの間にある実線は、第１ノードおよび第２ノードが同じソーシャル・ネットワークに含まれていることを示す。この例では、ソーシャル・ネットワークは、双方向実線エッジを用いて例示されており、ユーザー間のパスを、双方向のリンクを用いて形成できることを示す。他の例に関しても後に例示するが、ソーシャル・ネットワークは、ソーシャル・ネットワークが実施形態において実現される際の特異性(particulars)に依存して、単一方向の実線を用いて表すこともできる。第１ノードから第２ノードへの破線であるエッジは、第２ノードが第１ノードのアクセス制御リストに含まれることを示すために用いられる。言い換えると、第２ノードは、第１ノードのソーシャル・ネットワーク・リスト（１つ又は複数）によって示される、第１ノードの関係を見ることを許可されている。図３を参照すると、例２００は５つのノードＡ、Ｂ、Ｃ、Ｄ、およびＥを含み、各々のノードは異なるユーザーを表す。ユーザーＢにはソーシャル・ネットワークが定められており、２０４ｂおよび２０４ａでそれぞれ示すように、ノードＡおよびＤを含む。ユーザーＢは、彼女のアクセス制御リストによって、ＣおよびＥのみしか彼女の関係を見ることができないことを指定している。エレメント２０２ａおよび２０２ｂは、それぞれ、ＣおよびＥが、Ｂのソーシャル・ネットワーク・リストによって示されるように、Ｂの関係を見ることまたはＢの関係にアクセスすることができることを表す。
【００２５】
例２００において表されるようなソーシャル・ネットワークは、種々の異なる理由のために、社会的関連性(social connectedness)を測定するために用いることができる。例えば、ユーザーは、彼女が他のユーザーに接続されているか、または関係付けられているか否か問い合わせることができる。例２００を参照すると、２人のユーザー間に接続があると、そのグラフにおけるパスは、その２人のユーザーを表すノードを接続する。このような情報は、例えば、どの個人に別のユーザーへの紹介または参照を依頼すればよいか判断する際に有用となり得る。開始ノードから目標ノードまでパスが存在することを判定することによって、開始ノード（ユーザー）は、目標ノードまでのパスを形成する他の介在ノードがどれであるか判定することができる。介在ノードによって表されるユーザーは、目標ノードによって表されるユーザーに対する紹介または参照を得るために用いることができる。本明細書における技法に関して、パスを形成する際に用いられた他のノードのソーシャル・ネットワークに含まれるノードを見ることを、開始ノードが許可されているか否か判定するために、アクセス制御リストを用いることができる。
【００２６】
ユーザーが実行することができる別の種類の動作は、ある程度または距離以内において接続されている他の全てのユーザー（ノード）を判定することである。言い換えると、ユーザーは、ある数のホップというような、ある距離の範囲内にある他の全てのユーザーを判定することができる。例えば、各ユーザーに「友人」リストが定められている場合、あるユーザーは全ての他のユーザーに関して、２ホップ以内にいるのは誰か問い合わせることができる。２ホップ以内にいる場合、「友人」の「友人」を表す。第１ユーザーが第２ユーザーに近い程、ソーシャル・ネットワークにおける接続度または緊密度が高くなる。ユーザーは、ソーシャル・ネットワークにおける他のユーザーとの近接度を利用して、他のユーザーとの相互作用に関する信頼性(trustworthiness)、信用度(confidence)等を判断することができる。このような相互作用は、例えば、他人とトランザクションを実行すること、他人にあるサービスを実行させること、他人がオンラインで行った言明の有効性または信頼度を判断すること等を含むことができる。本明細書における技法に関して、以上の動作は、どのパスが問い合わせ元のユーザーに見ることができるか判定する際に、アクセス制御リストを用いて実行することができる。
【００２７】
例２００を参照して、ユーザーＡが、ＡはＤに関係付けられているか否か、つまりＡからＤまでの経路を有するか否か判定したいと仮定する。例２００の情報を用いると、ＡからＤまでのパス（例えば、Ａ−Ｂ−Ｄ）がある。しかしながら、Ａの問い合わせに応答して、ＡとＤとの間のパスまたは接続に関する情報はＡには伝達されない。何故なら、ＡはＢのソーシャル・ネットワークにアクセスできないからである。
【００２８】
アクセス制御リストをソーシャル・ネットワークと共に用いて、本明細書における技法を例示するために、更に詳しい例について説明する。図４、図５、図５Ａ、図６、および図６Ａの例に関して、ソーシャル・ネットワークは、実線エッジ、即ちノード間の線を用いて表すことができる。この場合、実線エッジは単一方向である。これについて、以下の章で更に詳しく説明し図示する。
【００２９】
図４を参照すると、ユーザーについて定められたソーシャル・ネットワークの表が示されている。この表２３０は、２３２において定められているソーシャル・ネットワークを有するユーザーを示す第１列２３２を含む。行毎に、２３２のソーシャル・ネットワークに対するアクセス制御リストが、２３６において示されている。この例では、図示を簡素化する目的で、各ユーザーＡ、Ａ１、およびＢ２に対して、１つのソーシャル・ネットワークのみが定められている（例えば、列２３２において）。しかしながら、本明細書における技法は、ユーザーの各ソーシャル・ネットワーク・リストや、各ユーザーのソーシャル・ネットワーク・リストの集合体にも個々に適用できることは、当業者には認められよう。
【００３０】
表２３０を参照すると、ユーザーＡは、ユーザーＡ１、Ａ２、およびＡ３を含むソーシャル・ネットワーク・リストを有する。ユーザーＡは、表２３０の第１行における列２３６によって示されるように、Ａ自体のソーシャル・ネットワークに対するアクセスを有する。ユーザーＡ１は、ユーザーＢ１、Ｂ２、およびＢ３を含むソーシャル・ネットワークを有する。ユーザーＡおよびＡ１は、表２３０の第２行における列２３６によって示されるように、Ａ１のソーシャル・ネットワークに対するアクセスを有する。ユーザーＢ２は、ユーザーＣ１、Ｃ２、およびＣ３を含むソーシャル・ネットワークを有する。ユーザーＡおよびＢ２は、表２３０の第３行における列２３６によって示されるように、Ｂ２のソーシャル・ネットワークに対するアクセスを有する。
【００３１】
図４のソーシャル・ネットワークおよびこれらのソーシャル・ネットワークへのアクセスによって定められる関係を、ソーシャル・ネットワークに対する単一方向リンクを用いて、図５に表す。
【００３２】
図５を参照すると、図３に関して説明したような凡例を用いて、図４のソーシャル・ネットワークおよびアクセス制御リストを表すグラフが示されているが、定められたソーシャル・ネットワークを表す実線エッジが単一方向であることが異なる。ソーシャル・ネットワークの単一方向表現に関して、第１ノードから第２ノードまでの実線は、第１および第２ノードが同じソーシャル・ネットワークに含まれていることを示す。更に具体的には、第２ノードは、第１ノードのソーシャル・ネットワークに含まれており、ユーザー間のパスは、示された方向に、リンクを用いて形成することができる。破線エッジは、アクセス制御リストを表し、どのノードが、他のノードの定められたソーシャル・ネットワークにアクセスできるかを示す。この例２５０において、エッジ２５２および２５４は、ＡがノードＡ１およびノードＢ２のソーシャル・ネットワークを見るためにアクセスできることを示す。図５における各ノードは、それ自体のソーシャル・ネットワーク・リストに対するアクセスを有する。簡素化のために、これは図５のグラフには示されていない。
【００３３】
アクセス制御リストを利用すると、ソーシャル・ネットワークによって異なる動作を実行することもできる。前述のように、ユーザーは、彼女が他のユーザーに関係付けられているか否かについて問い合わせることができる。一例として、Ａは、ＡがどのようにしてユーザーＢ１に関係付けられているのか問い合わせることができる。このような関係の存在は、ソーシャル・ネットワークと関連のあるアクセス制御リストを利用して、ＡからＢ１までの経路を判定することによって、判断することができる。別の動作例として、ユーザーＡは、２ホップ以内にいる全てのユーザーを判定したい場合がある。これらの動作の双方に関して、問い合わせ元のユーザーＡは、Ａに許可が付与されているソーシャル・ネットワークしか見ることを許可されていない。ノードＡからのパスが、Ａが見るまたはアクセスする許可を有していない接続を含む場合、いずれのパスも用いられない。処理は、Ａがあるノードのソーシャル・ネットワークを見る許可を有していない場合、そのノードのソーシャル・ネットワークを用いるいずれの接続も省略するように実行される。問い合わせ元のノードは、当該問い合わせ元のノードから終点までのパスを形成するために用いられる各接続リストまたは介在リストのアクセス制御リスト上になければならない。問い合わせ元ノードが、ソーシャル・ネットワークを表すリストを見る許可を有していない場合、そのリストは空として扱われるかまたは構成員を有していないものとして扱われる。以上のことを、以下の章において更に詳しく説明する。
【００３４】
図５を参照すると、Ａは、ＡがＣ３に関係付けられているか否か問い合わせることができる。一実施形態では、３ホップのデフォルト値を用いることができ、Ａから３ホップ以内にある全てのパスについて検索が行われることを示す。他の実施形態では、実行する検索を制限するためのパラメータとして他のデフォルト値を用いることもできる。３ホップ以内にあり、ノードＡから発する実線エッジによって形成される全てのパスを核にするために、グラフの幅方向優先通行 (breadth first traversal)を実行することができる。一旦このような３ホップ以下のパス全てを判定したなら、これらのパスの１つが、ＡからＣ３までのパスを含むか否かについて、更に別の判定を行うことができる。幅方向優先通行は、同じレベルまたは距離にあるノードを探査し、その後下位ノード(descendant node)の次のレベルに進む。下位ノードからのソーシャル・ネットワーク関係（実線エッジ）を表すエッジを通行する前に、Ａがその下位ノードのアクセス制御リスト上にあるか否か判定する。Ａが下位ノードのアクセス制御リスト上にある場合、その下位ノードから延びる実線エッジも通行する。そうでなければ、下位ノードから延びる実線エッジを通行しない。ＡからＣ３までのパスがあるか否か判定するための、例２５０の幅方向優先検索に関して、ノードＡ１、Ａ２、およびＡ３（Ａから１ホップ離れているノード）を最初に考慮する。ノードＡ１について、ＡがＡ１のアクセス制御リスト上にあるか否か判定する。２５４で示すように、ＡはＡ１のアクセス制御リスト上にあるので、ノードＢ１、Ｂ２、およびＢ３について考慮する。Ａ２およびＡ３は子を有していないので、通行は、幅方向優先検索における次のレベルに進み、Ｂ１、Ｂ２、およびＢ３（即ち、Ａから２ホップ離れているノード）を処理する。ノードＢ２のみが任意の子を有する。Ｂ２に関して、ＡがＢ２のアクセス制御リスト上にあるか否か判定する。２５２で示すように、ＡはＢ２のアクセス制御リスト上にあるので、ノードＣ１、Ｃ２、およびＣ３について考慮する（即ち、Ａから３ホップ離れているノード）。３ホップ以下の全ての経路についての通行に関して、ノードＣ１、Ｃ２、およびＣ３は考慮対象の最大距離にあるので、処理を停止する。丁度説明したばかりの幅方向優先通行に関して、ＡからＣ３までの１本のパスが判定され、そのパスは、Ａ−Ａ１−Ｂ２−Ｃ３である。
【００３５】
更に別の例として、ＡがＢ２に関係付けられているか否か、Ａが問い合わせる場合もある。前述のような幅方向優先検索を実行すれば、Ａから３以下の距離を有するパスを判定することができる。次いで、ＡからＢ２までのパスがあるか否かについて判定することができる。この場合、ＡからＢ２までのパスがあり、そのパスがＡ−Ａ１−Ｂ２であることを判定する。目標ノードＢ２は、通行するパスの終点である必要はない。むしろ、問い合わせの目標ノードが介在ノードであってもよく、開始ノード（問い合わせ元ノード）からその介在ノードまでのパスを指定してもよい。
【００３６】
図５Ａを参照すると、図５のグラフの変形である例２６０が示されている。例２６０は、図５のグラフを含むが、破線エッジ２５４が削除されている。エッジ２５４を削除することによって、例２６０は、ＡがＡ１のアクセス制御リストにない、即ち、ＡはＡ１のリストを見ることができないという事例を表すグラフを示す。２６０の表現に従って、ここでＡがＣ３に関係付けられているか否かＡが問い合わせると、ＡはＡ１のリストを見ることができないので、答えは否定となる。この実例で幅方向優先検索を実行する際、ノードＡ１、Ａ２、およびＡ３（距離がＡから１）について考慮する。ＡがＡ１のソーシャル・ネットワーク・リストにアクセスできないので、下位ノードＢ１、Ｂ２、およびＢ３を考慮しないことを判定する。ノードＡ２およびＡ３には子がないので、通行は終了し、ＡからＣ３までのパスは見出されない。
【００３７】
図６を参照すると、別の例３００が示されている。例３００は、グラフ３１０を含む。グラフ３１０は、図５に示されているグラフと同一であるが、新たな実線エッジ３０２が１本、および新たな破線エッジ３０４が１本追加されている。エレメント３０６は、３０２で表されている追加のソーシャル・ネットワーク関係、および３０４で示されているアクセスを示す。３０６において、ユーザーＡ２は、エッジ３０２で表されるように、Ｂ２のソーシャル・ネットワークが定められている。ＡはノードＡ２のアクセス制御リスト上にあり、ＡはＡ２のソーシャル・ネットワークを見ることができる。前述のように、ノードＡ２はそれ自体のソーシャル・ネットワークに対するアクセスを有し、これは３１０には表されていない。例３１０において、ＡはＡ１、Ａ２、およびＢ２のソーシャル・ネットワークを表すリストに対するアクセスを有する。この場合、ＡはＡがＢ２に関係付けられているか否か問い合わせる。答えは肯定であり、ＡをＢ２に接続するパスは２本、即ち、第１パスＡ−Ａ１−Ｂ２および第２パスＡ−Ａ２−Ｂ２がある。Ａについて図６に示すアクセス制御リストを用いると、実施形態は、ＡがどのようにＢ２に関係付けられているかという問い合わせに応答して、前述の２本のパスのいずれかでも示すことができる。一実施形態では、判定した第１パスを返すことができる。１本よりも多いパスがある場合、実施形態は、最初の２本のパスのような、所定数のパスを返すこともできる。
【００３８】
要約すると、丁度説明したように、第１ノードを第２ノードに接続するパスは１本よりも多くてもよい。第１ノードが、第２ノードに至る少なくとも１本のパス上にある全てのノードを見ることができれば（即ち、第１ノードは、各リストにアクセスする許可を有し、パス内にあるノード間にリンクを提供する）、第１ノードが第２ノードに接続されていることが、第１ノードに伝えられる。逆に、第１ノードが、第２ノードに至る少なくとも１本のパス上にある全てのノードを見るためにしかるべきアクセスを有しない場合、第１ノードは第２ノードに対する関係がないことが伝えられる。
【００３９】
図６Ａを参照すると、図６のグラフに対する変形である例３２０が示されている。例３２０は、図６のグラフ３１０を含み、破線エッジ２５４が削除されている。エッジ２５４を削除することにより、例３２０は、ＡがＡ１のアクセス制御リスト上になく、ＡはＡ１のリストを見ることができない事例を表すグラフを示す。Ａは、Ａ２およびＢ２のソーシャル・ネットワーク・リストを見ることだけを許可されている。例３２０によれば、ＡがＢ２に関係付けられているか否かＡが問い合わせると、答えは肯定となる。Ａは、パスＡ−Ａ１−Ｂ２を通じてＢ２に接続されていても、ＡはＡ１のソーシャル・ネットワークを見ることができない。何故なら、この情報はＡに露出されていないからである。つまり、パスＡ−Ａ１−Ｂ２はＡには伝えられない。しかしながら、ＡはパスＡ−Ａ２−Ｂ２を通じてＢ２に接続されていることを、Ａには伝えられる。パスＡ−Ａ２−Ｂ２を判定するために実行される幅方向優先検索に関して、問い合わせ元ノードＡから１ホップのところにあるノードを評価するときに、ノードＡ２を処理する。Ａ１の下位ノードについては考慮しない。何故なら、ＡはＡ１のアクセス制御リスト上になく、ノードＡ３には子がないからである。Ａ２を評価するとき、ＡがＡ２のアクセス制御リスト上にないことが判定されるので、ノードＢ２については考慮しない。Ｂ２はノードＡから２ホップのところにある。Ａは、ノードＢ２のアクセス制御リスト上にあるので、Ａから３ホップのところにあるノードを評価するときに、Ｂ２の子、ノードＣ１、Ｃ２、およびＣ３について考慮する。Ａから３ホップ以内にある全てのパスについてのグラフの通行に関して、ノードＣ１、Ｃ２、およびＣ３は、３ホップの最大距離にあるので、処理は停止する。この時点において、通行したパスが調べられ、前述のようにＡからＢ２までのパスがあることが判定される。
【００４０】
図６Ａのグラフを参照して（例えば、エッジ２５４を削除した場合）、次に３ホップの距離以内においてＡに関係付けられている全てのユーザーを判定する問い合わせをＡが行ったと仮定する。これに応答して、ＡはＡ１、Ａ２、Ａ３（直接）、Ｂ２、ならびにＣ１、Ｃ２およびＣ３に関係付けられていると、Ａに伝えられる。この問い合わせに関して、前述したのと同じ幅方向優先検索を、第１ステップとして実行することができる。第２ステップとして、幅方向優先検索の間に通行したパスを検査する。３ホップというような、要求距離以内に位置する全てのノードを判定し、結果として出力することができる。
【００４１】
本明細書における技法と共に最大距離として用いられるホップ数に関して、ホップ数は暗示的または明示的に定めることができる。前述のように、３ホップのようなデフォルト距離を用いることができる。また、ホップ数は、本明細書に記載する任意の動作、あるいはアクセス制御リストと共に本明細書における技法を用いて実行することができる動作に関する設定可能なパラメータ(configurable parameter)として指定することもできる。
【００４２】
本明細書に記載するソーシャル・ネットワークと共に用いられるアクセス制御リストに関して、アクセス制御リストは種々の異なる方法で定めることができる。第１の技法を用いると、アクセス制御リスト上の各ユーザーを列挙することによって、アクセス制御リストを明示的に定めることができる。別の技法を用いると、ユーザーは、１つ以上の既存のソーシャル・ネットワークを用いて、アクセス制御リストを定めることができる。例えば、ユーザーＡ２は、Ａ２の既存のソーシャル・ネットワークおよび／またはその他の公衆ソーシャル・ネットワーク（特定の会社で働く全てのユーザー、特定の領域に住む全てのユーザー、特定の学校に行っていた全てのユーザー等）を用いて、アクセス制御リストの構成員を定めることができる。
【００４３】
別の例として、Ａは、ある距離（例えば、ある数のホップだけ離れている）以内にあるノードまたはユーザーに基づいて、アクセス制御リストを暗示的に定めることができる。この後者の場合、アクセス制御リストを顧慮するソーシャル・ネットワークを用いて、ノードＡから指定距離以内にあるノードの集合を判定することができる。このようなノードは全て、暗示的にＡのアクセス制御リストに含まれており、Ａのソーシャル・ネットワークを見ることを許可されている。このアクセス制御リストの構成員を定めるための暗示的な技法は、アクセス制御リストの各ユーザーを明示的に指名する代替案として実行することができる。更に例示するために、図４において定められ、図５における実線エッジによって表されているソーシャル・ネットワークを参照する。Ａは、Ａから２ホップ以内、または２以下の距離以内にあるユーザーを含めるように、そのアクセス制御リストを定めることができる。このような実例では、Ａのアクセス制御リストは、Ａ１、Ａ２、Ａ３、Ｂ１、Ｂ２、およびＢ３を含む。Ａは、例えば、Ａ１、Ａ２、およびＡ３を含むように定めた「友人」ソーシャル・ネットワークを有することができる。Ａ２は、Ｂ１、Ｂ２、およびＢ３を含むように定めた「友人」ソーシャル・ネットワークを有することができる。Ａのアクセス・リストは、Ａの「友人」（例えば、Ａ１、Ａ２、およびＡ３）、およびＡの「友人」の「友人」（例えば、Ａ１、Ａ２、およびＡ３の「友人」）であるユーザーを含むように定められる。尚、既存のソーシャル・ネットワークを通じてあるノードまで特定の距離以内において関係付けられている全てのユーザーを含むようにアクセス制御リストを暗示的に定める代わりに、アクセス制御リストは、２の距離のところにあるノードというような、１つ以上の選択した距離のところにあるユーザーを含むが、１の距離のところにあるノードをアクセス制御リストに含めないように定めることもできる。
【００４４】
図７を参照すると、２つのノードが互いに関係付けられているか否か判定するために、一実施形態において実行することができる処理ステップのフローチャートが示されている。前述のように、ノードは、当該ノードが他のノードに関係付けられているか否かについて問い合わせることができる。この問い合わせには、２つのノードを接続するパスがあるか否か、そのパスを形成するために用いられたソーシャル・ネットワークについてのアクセス制御リストにしたがって判定することによって、回答することができる。図７を参照すると、その問い合わせは、開始ノードから目標ノードまでパスがあるか否か、そして当該パス上にある全てのノードが開始ノードにとって可視であるか、可視か否かがアクセス制御リストにおいて示されているか否かについて行われる。３５０のステップ群は、開始ノード即ち問い合わせ元ノードから発するソーシャル・ネットワーク関係のグラフの幅方向優先通行を実行する実施形態において、先の図３、図４、図５、図５Ａ、図６、および図６Ａの例に関して説明したような処理を要約する。続いて、通行したパスを検査して、開始ノードから目標ノードまでのパスがあるか否か判定する。フローチャート３５０のステップ群は、ソーシャル・ネットワークに関する双方向エッジ表現（例えば、図３におけるような）または単一方向エッジ表現（例えば、図５、図５Ａ、図６、および図６Ａにおけるような）を利用する実施形態において実行することができる。
【００４５】
ステップ３５２において、開始ノードに直接接続されている（１の距離）ノードの集合が判定される。ステップ３５２の一部として、ステップ３５２において判定したノードの集合を含むように、通行したノードのリストを更新する。通行したノードのリストは、幅方向優先通行に関連して通行されたノードを表すことができる。ステップ３５４において、ステップ３５２からの集合における最初のノードとして指定された現ノードから、通行を開始する。また、現行深さカウンタを１にセットして、通行の現在のレベルを示す。ステップ３５６において、距離１のところにある全てのノードというように、現在のレベルまたは距離について処理が完了したか否か判断する。ステップ３５６、３５８、３６０、および３６２によって形成されるループが、グラフにおける現在の深さレベルまたは距離にある全てのノードを検査する。開始ノードが現在のレベルにおけるノードのアクセス制御リスト上にある場合、そのノードを通行リストに追加し、幅方向優先通行における次のレベルを通行するときに、その子も探査できるようにする。
【００４６】
ステップ３５６において評価した結果否定であった場合、制御はステップ３５８に進み、開始ノードが現在のノードのソーシャル・ネットワークにアクセスできるか否か判定する。開始ノードが現在のノードのアクセス制御リスト上にある場合、ステップ３５８における評価が肯定となり、制御はステップ３６０に進み、現在のノードを通行リストに追加する。通行リストは、通行における異なるレベルで訪問されたノードを含み、後続の距離またはレベルで幅方向優先検索を実行する場合には、それらの下位ノード(descendant)も更に探査することができる。ステップ３６２から、制御はステップ３６２に進み、現在のレベルまたは距離において、ノードの集合における次のノードに現在のノードを指定する。ステップ３５８において評価した結果否定であった場合、制御は直接３６２に進む。ステップ３６２から、制御はステップ３５６に進む。
【００４７】
ステップ３５６において評価した結果肯定であり、開始ノードから現在の深さレベルまたは距離における全てのノードを処理し終えていることを示す場合、制御はステップ３６４に進む。ステップ３６４において、通行リストに次のレベルに位置付けられているノードがあるか否か判定する。ある場合、ステップ３６４における評価で肯定となり、制御はステップ３７０に進み、グラフにおける次の深さレベルについての処理を開始する。ステップ３７０において、通行リスト内にあるノードの子から形成される集合を決定する。ステップ３７０において形成された集合は、次の深さレベルにおける距離を有するノードの集合であり、幅方向優先通行の一部として処理される。ステップ３７０の一部として、次の深さレベルにおいて決定されたノードの集合を含むように、通行されるノードのリストを更新する。また、ステップ３７０において深さカウンタを増分し、幅方向優先技法における次のレベルへの処理の前進を示す。ステップ３７２において、深さカウンタによって示される現在の深さレベルが考慮対象の最大距離であるか否か判断する。前述のように、最大距離は、幅方向優先検索の範囲を決定するために用いられる設定可能なまたはデフォルトの発見的方法を表す。ステップ３７２において評価した結果否定である場合、制御はステップ３５４に進み、現在の深さレベルにあるノードを処理する。ステップ３７２において評価した結果肯定である場合、制御はステップ３６６に進み、幅方向優先通行の終了を意味する。
【００４８】
ステップ３６４において評価した結果否定である場合、探査すべきノードが通行リストにないことを示し、この場合も制御はステップ３６６に進む。
【００４９】
ステップ３６６において、開始ノードから見える全てのノードが判定され、幅方向優先様式で通行され、目標ノードが、通行されたパスのうちの１つに含まれるか否か判断が行われる。このような判断は、例えば、目標ノードが幅方向優先検査通行の一部として通行されたノードであるか否か判定することによって下すことができる。既に通行されているノードの集合は、開始ノード、ステップ３５２からの集合を形成するノード、およびステップ３７０の繰り返し毎に集合を形成するノードの集合結合体(set  union)として表すことができる。フローチャート３５０に関して先に説明したように、この通行されたノードの集合は、ステップ３５２および３７０の処理に伴って更新されている。ステップ３６６における評価の結果肯定である場合、制御はステップ３６８に進んで処理を行い、開始ノードおよび目標ノードが関係付けられていることを示す。ステップ３６８の処理は、開始ノードおよび目標ノードをリンクする関係を示す特定のパスを出力することを含むことができる。ノードを通行する際にパス情報を出力するために、ノードを通行するに連れて、関係リンク、または親ノードおよび子ノードを接続するグラフの実線エッジ情報を示す情報を記録するとよい。ステップ３６８における評価の結果否定である場合、制御はステップ３７４に進み、処理を実行して、開始ノードおよび目標ノードが関係付けられていないことを示す。本明細書において記載する場合、２つのノードが関係付けられていないという結論は、開始ノードが見ることができるノード間にはパスがないことを意味する。ノード間にパスがある可能性はあるが、このような場合、開始ノードが必要なアクセス制御リストに含まれていないので、そのパスは開始ノードには見ることができない。
【００５０】
図８を参照すると、開始ノードから特定の距離以内にある全てのノードを判定するために実施形態において実行することができる処理ステップのフローチャートが示されている。４００の処理ステップ群は、３５０において説明したのと同様であり、図７におけるステップ３６６、３６８、および３７４の代わりに、図８ではステップ４０２を実行することが異なる。４００において、ソーシャル・ネットワークおよびアクセス制御リストから形成されたグラフの幅方向優先通行を実行して、開始ノードから特定の距離以内にある全てのノードを判定することができる。一旦幅方向優先通行が完了したなら、制御はステップ４０２に進み、通行したパス上に含まれるノードのリストを出力することができる。
【００５１】
本明細書における技法は、種々の異なる目的に合わせて、ユーザー間の関係を評価および判定するために用いることができる。例えば、ウェブサイトが、雇用者および被雇用者関係のような職業用ネットワーキングのために用いられる場合、本明細書において記載したソーシャル・ネットワーキング・リストおよびアクセス制御リストの使用は、潜在的な雇用者に対する紹介を得るために、どの個人を用いるべきか判断するために用いることができる。別の例として、本明細書における技法は、商品を販売するウェブサイトと合わせて用いることもでき、販売者の信頼性および評判を判断することができる。
【００５２】
本明細書における技法は、アクセス制御リストによって示されるアクセス保護を顧慮しつつソーシャル・ネットワークの関連性を表示および検索するために用いることもできる。尚、本明細書において記載したように、ソーシャル・ネットワークおよびアクセス制御リストを表すグラフを通行するために、実施形態では幅方向優先技法を用いることができることを記すべきであろう。また、深さ方向優先(depth-first)技法のような他の技法も、本明細書の記載以外の、定められたソーシャル・ネットワークの異なる表現として同様に利用できることは、当業者には認められよう。例示の目的のために、本明細書における技法は、グラフを用いて説明した。しかしながら、種々のデーター構造を用いる他の表現も利用することができる。
【００５３】
以上、構造的特徴および／または方法論的行為に特定的な文言で主題について説明したが、添付した特許請求の範囲に定められている主題は、以上に説明した具体的な特徴や行為に必ずしも限定される訳ではないことは言うまでもない。むしろ、前述したこれら具体的な特徴および行為は、請求項を実施する形態例として開示したのである。
【図１】
2011504255.tif 000003
【図２】
2011504255.tif 000004
【図３】
2011504255.tif 000005
【図４】
2011504255.tif 000006
【図５】
2011504255.tif 000007
【図５Ａ】
2011504255.tif 000008
【図６】
2011504255.tif 000009
【図６Ａ】
2011504255.tif 000010
【図７】
2011504255.tif 000011
【図８】
2011504255.tif 000012
【国際調査報告】
2011504255.tif 000013
2011504255.tif 000014