(57)【特許請求の範囲】
【請求項１】
エンティティー相互の社会的つながりを識別するコンピューターにより実現される方法であって、
コンピューティングデバイスを用いて、
エンティティー間の社会的つながりを識別する、社会的ネットワークまたは通信ネットワークの一部ではない二以上の一般のＷｅｂページのセットを受信するステップと、
前記Ｗｅｂページの各々の内容を解析して情報ブロックにするステップと、
各Ｗｅｂページの前記情報ブロックにある前記エンティティーの名前を識別するステップと、
各Ｗｅｂページの前記情報ブロックにある前記名前間の距離を考慮して、前記二以上の一般のＷｅｂページの各Ｗｅｂページの前記情報ブロックにある前記エンティティーの名前相互の社会的つながりをランク付けするステップと、
前記情報ブロックの全てから前記ランク付けされた社会的つながりを統合して、前記エンティティーの名前に関連する前記エンティティー間の前記つながりの強さを判定するステップと
前記二以上のＷｅｂページの各Ｗｅｂページ上の社会的つながりのランキングを用いて、前記エンティティーの名前に関連する前記エンティティー間の前記つながりの前記強さに基づいて、ソーシャルネットワーキンググラフを出力するステップと
を有し、
前記ソーシャルネットワーキンググラフは力学モデルとエネルギー最小化プロセスとを使用して生成される、
コンピューターにより実現される方法。
【請求項２】
前記力学モデルとエネルギー最小化プロセスとの使用は、
前記ソーシャルネットワーキンググラフの所有者を、２次元グラフの中心に中心点として配置し、
前記ランク付けされたリストにある各エンティティーに対し、前記ランク付けされたリストにあるエンティティーの名前を表す頂点を、前記中心点の周りの異なる軌道に配置し、前記軌道においては、前記軌道の半径がより短ければ、前記軌道にある前記頂点と前記中心点との間の前記社会的つながりはより強く、
前記頂点間のつながり度に準じて、前記頂点を異なるクラスターにクラスタリングし、
力学モデルを使用して２次元のレイアウトの均一性を最適化するように指示され、
前記力学モデルは、
各２つの頂点の間の斥力と、
辺相互の引力と、
隣接軌道間の斥力と、
互いにつながりを有さないクラスターを隔離する突き抜け不可の境界とを備える、
請求項１に記載のコンピューターにより実現される方法。
【請求項３】
前記エンティティーの名前相互の前記社会的つながりをランク付けするステップはさらに、つながりの重みを、エンティティーの名前に関連付けるステップを備える請求項１に記載のコンピューターにより実現される方法。
【請求項４】
前記Ｗｅｂページの各々の前記内容を解析するステップはさらに、ビジュアルパーサーを使用して前記内容を情報ブロックにするステップを備える請求項１に記載のコンピューターにより実現される方法。
【請求項５】
ソーシャルネットワークまたは通信アプリケーションに関連しない一般のＷｅｂページから抽出されるエンティティーの名前相互の社会的つながりを、名前を表す頂点のセットと、社会的つながりを表す辺のセットとを有する２次元グラフの形式で表示するシステムであって、
汎用コンピューティングデバイスと、
前記汎用コンピューティングデバイスにより実行可能なプログラムモジュールを備えるコンピュータープログラムとを備え、
前記汎用コンピューティングデバイスは、前記コンピュータープログラムのプログラムモジュールにより、
ソーシャルグラフの所有者と、ソーシャルネットワークまたは通信アプリケーションに関連しない前記一般のＷｅｂページから得られる追加エンティティーとの間の社会的つながりのランク付けされたリストを入力し、
前記ソーシャルグラフの所有者を、前記２次元グラフの中心に中心点として配置し、
前記ランク付けされたリストにある各エンティティーに対し、前記ランク付けされたリストにあるエンティティーの名前を表す頂点を、前記中心点の周りの異なる軌道に配置し、前記軌道においては、前記軌道の半径がより短ければ、前記軌道にある前記頂点と前記中心点との間の前記社会的つながりはより強く、
前記頂点間のつながり度に準じて、前記頂点を異なるクラスターにクラスタリングし、
力学モデルを使用して２次元のレイアウトの均一性を最適化するように指示され、
前記力学モデルは、
各２つの頂点の間の斥力と、
辺相互の引力と、
隣接軌道間の斥力と、
互いにつながりを有さないクラスターを隔離する突き抜け不可の境界とを備える
システム。
【請求項６】
各頂点、各辺、各軌道、および各突き抜け不可の境界は、力に準じて移動が可能となるように、放射状にもしくは接線方向のいずれかに自由であり、または放射状におよび接線方向の両方に自由であることを特徴とする請求項５に記載のシステム。
【請求項７】
ディスプレイ上に２次元のグラフを表示し、ユーザーに前記２次元グラフの操作を可能とさせるグラフィカルユーザーインターフェースをさらに備えることを特徴とする請求項５に記載のシステム。
【請求項８】
前記グラフィカルユーザーインターフェースはさらに、前記２次元グラフの前記頂点を色付きで表示し、互いに近接する頂点は近似する色で表示されることを特徴とする請求項７に記載のシステム。
【請求項９】
前記頂点の色は、０度から３６０度までの前記頂点の位置の極座標に準じて変化することを特徴とする請求項５に記載のシステム。
【請求項１０】
前記グラフィカルユーザーインターフェースはさらに、ユーザーが頂点を選択するときに新しい２次元グラフに変化しようとする２次元グラフを備える、アニメーションを備えることを特徴とする請求項７に記載のシステム。
【請求項１１】
エンティティー相互の社会的つながりを識別するコンピュータープログラムであって、
コンピューティングデバイスにより実行されると、前記コンピューティングデバイスに、請求項１に記載の方法のステップを実行させるコンピュータープログラム。
【発明の詳細な説明】
【背景技術】
【０００１】
近年、多くのソーシャルネットワーキングアプリケーションがインターネット上で生まれ、人々が社会的および専門的につながることが可能となった。主として、このようなソーシャルネットワーキングアプリケーションでは、ユーザーはユーザーＩＤおよびパスワードを作成し、当該ユーザーの友人を識別してプロファイルを作成することが要求される。しかしながら、ワールドワイドウェブ、すなわちインターネット上の多くのＷｅｂページ（例えば、ニュースサイト、ブログ、および批評など）は、人々およびその他のエンティティーの社会的活動（social activity）を記載するが、当該活動のような情報は、ソーシャルネットワーキングアプリケーションサイト上にはリストアップされない。
【０００２】
さらに、多くのソーシャルネットワーキングアプリケーションが存在するが、人々とその他のエンティティーとの間の社会的つながり（social connection）、または関係を容易に判定および参照することができる方法は、非常に多くは存在しない。
【発明の概要】
【０００３】
この「発明の概要」は、以下の「発明を実施するための形態」でさらに説明される概念の中から選択したものを簡略化した形式で紹介するものである。この「発明の概要」は、特許請求の範囲に記載された内容の重要な特徴または本質的な特徴を専ら特定することを意図としたものではなく、特許請求の範囲に記載された内容の範囲を限定することを意図としたものでもない。
【０００４】
本明細書で記載される自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、一般的な（必ずしもソーシャルアプリケーションに特有のものではない）Ｗｅｂページから、社会的つながりをマイニング（採掘）し、ソーシャルネットワーキングリレーションシップを視覚化することを可能とする。
【０００５】
特に一実施例では、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、エンティティーのソーシャルネットワーキンググラフのマイニングおよびレイアウトを自動的に行う。例えば、人、組織、またはキーワードさえもエンティティーとなることができる。この技術は、１または複数のＷｅｂページ上にあるエンティティー名と関連するエンティティー名との間の距離を使用して、エンティティー間のつながり、およびそのつながりの強さを判定する。
【０００６】
マイニングプロセスでは、入力は一般のＷｅｂページとなる。人々の名前またはその他のエンティティー名と、その人々やエンティティー相互の社会的つながりとが、自動的に抽出されかつ統合される。各エンティティー名に対して、１または複数のＷｅｂページにあるエンティティー名につながりのある名前の集合の組み合わせとして、およびＷｅｂから識別された、当該つながりのあるエンティティー名相互の社会的つながりの集合として、エンティティーのソーシャルネットワーキンググラフが定義される。これらの社会的つながりを、リレーションシップランキングプロシージャーにより重み付けすることができる。
【０００７】
一実施例では、ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、レイアウトプロシージャーを使用して、人の名前またはその他のエンティティー名の周りに２次元ソーシャルネットワーキンググラフを生成することができる。この技術の一実施例では、力学モデルおよびエネルギー最小化プロセスを使用することにより、レイアウトが自動的に生成される。このレイアウトでは、社会的つながりの重みは、そのつながりの２つの端の間の距離により表される。その距離がより短ければ、つながりの重みはより大きい。また一実施例では、レイアウトプロシージャーは、互いに密接なつながりのある人々の名前、またはその他のエンティティー名のクラスタリングをも同時に行う。
【図面の簡単な説明】
【０００８】
開示された特定の特徴、態様、および有利な点は、以下の詳細な説明、添付の特許請求の範囲および添付図面を考慮して、より理解されるであろう。
【図１】本明細書で説明する自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の一実施例を用いる例示的なアーキテクチャーである。
【図２】自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術を用いる例示的なプロセスのフローチャートを図示する。
【図３】自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術に準じて、ソーシャルネットワーキンググラフを作成する例示的なプロセスのフローチャートを図示する。
【図４】自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の実施例により、作成されたソーシャルネットワーキンググラフの例を図示する。
【図５】自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の実施例において採用されるグラフィカルユーザーインターフェースを図示する。
【図６】自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術を実施するのに使用することができる例示的なコンピューティングデバイスの概略図である。
【発明を実施するための形態】
【０００９】
自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の以下の詳細な説明では、本明細書の一部をなし、かつ例示の方法により、本明細書で記載する自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術が実施されうることを示す図面への参照がされる。その他のコンポーネントが利用され、特許請求の範囲に記載された内容の範囲から逸脱せずに構造的な変更がされてもよいことが理解される。
【００１０】
１．０  自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術
以下のセクションは、ソーシャルネットワーキンググラフマイニングおよび視覚化技術と、その技術を用いる例示的なアーキテクチャー、プロセス、およびユーザーインターフェースの概説を提供する。
【００１１】
１．１  技術の概説
最近では、ソーシャルネットワーキングが非常に関心を受けてきた。ソーシャルネットワーキングアプリケーションおよびサービス（例えば、Ｆａｃｅｂｏｏｋ（登録商標）およびＴｗｉｔｔｅｒ（登録商標））により、ユーザーは自身のプライベートなソーシャルネットワークを成長させることが可能となる。しかしながら、インターネットは実際には、一般のＷｅｂページにある文字列を基にしたパブリックなソーシャルネットワークを包含する。例えば、社会的活動を記載するＷｅｂページは、それらのページ上で言及される人々またはエンティティー相互の暗黙の社会的つながりを提供する。これらのパブリックな暗黙の社会的つながりを、巨大なソーシャルネットワーキンググラフとして見ることができる。ソーシャルネットワーキングアプリケーションのために特に設計がされていないＷｅｂページから、人々とその他のエンティティー相互の社会的つながりの識別および提示を自動的に行うことの研究はほとんどされなかった。
【００１２】
一実施例では、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、一般のＷｅｂページから自動的にソーシャルネットワーキングのつながりを識別し、２次元レイアウトのソーシャルネットワーキンググラフを提供する。当該グラフにより、ビューアは人々またはエンティティー間のつながりと、それらのつながりの強さを容易に識別することが可能となる。
【００１３】
一実施例では、その技術は２次元の視覚化レイアウトを作成する。当該レイアウトは、エンティティーとその他のエンティティーとの間のつながり、およびそのつながりの強さに基づいて放射状レイアウトで配列された頂点（名前）の集合、および辺（社会的つながり）の集合として、特定のエンティティーのソーシャルネットワーキンググラフを提供する。ソーシャルグラフの所有者（例えば、グラフが生成されるエンティティー）は、中心に配置される。上記説明したマイニングプロセスおよびレイアウトプロセスにより、Ｗｅｂからソーシャルネットワーキンググラフが自動的に生成され、かつ視覚化される。
【００１４】
１．２  例示的なアーキテクチャー
図１は、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の一実施例を用いる例示的なアーキテクチャー１００を提供する。図１で示すように、アーキテクチャー１００は、コンピューティングデバイス６００上に存在するソーシャルネットワーキンググラフマイニングおよび視覚化モジュール１０２を用いる。コンピューティングデバイス６００は、図６を考慮してより詳細に述べられるであろう。
【００１５】
ソーシャルネットワーキンググラフマイニングおよび視覚化モジュール１０２は、ソーシャルネットワーキンググラフ１０４をマイニングし、当該グラフを、ユーザー１０８がユーザーインターフェース１１０を介して操作することができるディスプレイ１０６上で、ユーザーに提示する。Ｗｅｂページ１１２は、ソーシャルネットワーキンググラフマイニングおよび視覚化モジュール１０２へ入力される。Ｗｅｂページビジュアルパーサー１１４は、Ｗｅｂページの各々からＷｅｐページの内容を構文解析し、情報ブロック１１６にする。情報ブロック１１６は、情報ブロックからエンティティー名を認識するネームエクストラクター１１８へ入力される。例えば、人々、組織、またはキーワードがこれらのエンティティーになることができる。
【００１６】
タグ付けされたエンティティー名を備える情報ブロック１２０は、タグ付けされた情報ブロック１１６で識別されたエンティティー間の１または複数のつながりを判定し、ランク付けをするソーシャルコネクションランカー１２２へ入力される。ソーシャルコネクションランカー１２２はまた、つながりの強さを識別し、その強さに重みを割り当てる。ランキングを判定する１の例示的なプロシージャーは、後により詳細に述べられるであろう。ソーシャルコネクションランカー１２２は、ランク付けされたエンティティー名およびそれらのつながりの重み１２４を出力する。これらのつながりの重み１２４は、ソーシャルコネクションインテグレーター１２６へ入力される。ソーシャルコネクションインテグレーター１２６は、ランク付けされたエンティティー名およびそれらのつながりの重み１２４の全てを統合し、力学モデルを使用して、ディスプレイ１０６上にソーシャルネットワーキンググラフ１０４の作成および出力を行う。一旦、ソーシャルネットワーキンググラフ１０４の一部がディスプレイ１０６上に表示されると、ユーザー１０８はソーシャルネットワーキンググラフ１０４を操作して、ユーザーインターフェース１１０を介して、ソーシャルネットワーキンググラフ１０４のその他の部分を示すことができる。ユーザーインターフェース１１０は、後により詳細に述べられるであろう。
【００１７】
１．３  自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術により用いられた例示的なプロセス
以下の段落は、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術を用いる例示的なプロセスの説明を提供する。一部の動作の順序を入れ替えることができる場合もあり、一部の動作を省略しさえもできる場合があることを理解されるべきである。
【００１８】
１．３．１  自動ソーシャルネットワーキンググラフマイニング
自動ソーシャルネットワーキンググラフマイニングおよび視覚化の一実施例を用いるプロセスの高レベルフローチャートが図２で示される。この技術の実施例は、社会的つながりとそのつながりの強さとを一般のＷｅｂページからマイニングする。図２のブロック２０２で示すように、これらのＷｅｂページはプロセスに入力される。これらの入力されたＷｅｂページを、例えば、インターネットをクローリング（crawling）するＷｅｂクローラーにより見出すことができる。
【００１９】
ブロック２０４で示すように、入力されたＷｅｂページの各々の内容が、構文解析され、情報ブロックにされる。例えば、文字列のブロックまたはその他の連続ブロックを識別するビジュアルパーサーを使用して、Ｗｅｂページの内容を構文解析することができる。種々の従来からの技術を使用して、この文字列またはデータのその他の連続ブロックの識別および構文解析を行うことができる。ブロック２０６で示すように、情報ブロック内で見出された人々の名前またはエンティティー名は、それから識別される。例えば、当該識別は、従来からのネームファインダーによりなされる。ここで、従来からのネームファインダーとは、情報ブロックからエンティティー名を自動的に見出すことができる任意のコンピュータールゴリズムに言い及ぶ。
【００２０】
ブロック２０８で示すように、情報ブロックにあるエンティティー名相互の社会的つながりは、それからランク付けされる。この技術の一実施例では、情報ブロックにある名前の位置と周囲の文字列（例えば、名前の位置、および文字列にある名前を分離する単語の特定の距離もしくは数）とを考慮する。２つの名前が互いにより近接すると、つながりがより強いとみなされる。この技術の一実施例により用いられるランキングプロシージャーに関する詳細は、後に与えられる。ブロック２１０で示すように、全ての情報ブロックからのランク付けされた社会的つながりは、それから統合され、Ｗｅｂページ上で見出されたエンティティー間の社会的つながりが判定される。自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術の一実施例では、統合は、各情報ブロックに対して見出されるつながりの強さを判定する際に、同一の名前の集合がＷｅｂページ上で見出される頻度と、情報ブロックにある名前の近さとが考慮される。ブロック２１２で示すように、それから社会的つながりの強さを種々の目的のために使用することができる（例えば、ある人の友人が誰であるかを判定するため、またはこれらの社会的つながりをグラフ化して、人々とその他のエンティティーとの間の社会的つながりを判定する際のビジュアル的な補助を提供するため）。
【００２１】
１．３．２  社会的つながりの視覚化
図３は、社会的つながりを視覚化するために、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術により用いられる１の例示的なプロセス３００のフローチャートを提供する。この技術の実施例では、一般のＷｅｂページから抽出された人々の名前／エンティティー名相互の社会的つながりが、名前を表す頂点の集合と、社会的つながりを表す辺の集合とともに２次元の形式で表される。力学モデルを使用して２次元グラフを表し、エネルギー最小化プロシージャーを使用して２次元グラフのレイアウトを大幅に最適化し、または向上させる。
【００２２】
ブロック３０２で示すように、ランク付けされた社会的つながりのリストが入力される。ブロック３０４で示すように、ソーシャルグラフの所有者（グラフが表示される人）が、中心点として２次元グラフの中心に配置される。ブロック３０６で示すように、ソーシャルグラフの所有者との社会的つながりを有する人々の名前、またはその他のエンティティー名を表す頂点は、頂点の周りの異なる軌道（ランキングに基づく中心点の周りの軌道）に配置される。軌道の半径がより短ければ、軌道にある頂点と中心点との間の社会的つながりはより強い。中心点の周りの１の軌道が、中心点に最も近接する所有者との最も強い社会的つながりを有する頂点（エンティティー）とともに、社会的つながりの各々に対して作成される。ブロック３０８で示すように、それから、頂点間のつながり度に準じて、頂点を異なるクラスターへクラスタリングすることができる（例えば、頂点間のつながり、および下記でより詳細に記載されるであろうエネルギー最小化プロシージャーに準じてクラスタリングされる）。同一クラスターの頂点（例えば、これらの頂点は、その頂点間の２以上のつながりを有する）は、互いに近接して配置される。ブロック３１０で示すように、頂点のクラスターはまた、当該頂点のクラスターが互いに重なり合わないように配置される。ブロック３１２で示すように、それから力学モデルを使用して、２次元グラフのレイアウトの均一性を大幅に最適化する。
【００２３】
図４は、この技術の一実施例により創作される２次元グラフのレイアウト４００の例を提供する。ソーシャルネットワーキンググラフマイニングおよび視覚化技術のこの実施例において、力学モデルは力の集合およびエネルギー最小化プロシージャーを用いることにより、レイアウトが均一になるように大幅に最適化する。
１）各２つの頂点の間の斥力４０２（図４で示す例）
２）頂点に沿った引力４０４（例えば、頂点間の社会的つながりの間）
３）隣接軌道間の斥力４０６
４）互いにつながりを有さないクラスターを隔離するよう形付けられる突き抜け不可の境界４０８
５）グラフにあるオブジェクトの各々（例えば、各頂点、辺、軌道、および突き抜け不可の境界）は、力学モデルの力に準じて移動できるように、放射状に／接線方向にのいずれか、またはその両方に自由となる。
したがって各頂点では、力学モデルにおける４つの種類の異なる力が存在する。
【００２４】
【数１】
0005905450.tif 000002
【００２５】
ｉは、第ｉ番目の頂点を表し、ｊは、第ｊ番目の頂点を表す。ｄは、距離を表す。Ｏkは、第ｋ番目の軌道を
表す。Ｕmは、第ｍ番目の突き抜け不可の境界を表す。Ｃ1,2,3は、定数を表す。θは、頂点および中心点を通る線の正の交角、ならびに突き抜け不可の境界を表す。τは、一定の閾値を表す。上記定義が与えられ、１の頂点での集中した力は、
【００２６】
【数２】
0005905450.tif 000003
【００２７】
１の頂点で力が均衡しているときは、その頂点の集中した力はゼロである。したがって、この技術は頂点全ての集中した力の合計を最小化しようとする。それから、レイアウトアルゴリズムが頂点の適切な位置を見出し、そこでは、
【００２８】
【数３】
0005905450.tif 000004
【００２９】
【数４】
0005905450.tif 000005
【００３０】
は、レイアウトのエネルギーとしてみなすことができ、レイアウトアルゴリズムは、実際に力学モデルのエネルギーの総量を減少させる。この技術の一実施例では、エネルギー最小化プロセスが反復する方法で実行される。各反復では、各頂点が集中した力の方向に沿って移動される。このプロセスは、エネルギーが、あるレベルに集まるときに停止する。特に、エネルギーが下がるにつれて、頂点の変位の総量も減少する。この技術は、一定の閾値を設定する。この値よりも頂点の変位の総量が少ないときに、反復プロセスは停止する。このポイントまでは、頂点は各反復で移動し続け、すなわち、頂点の位置が変化する。
【００３１】
１．３．３  社会的なつながりのランク付け
前に述べたように、ソーシャルネットワーキンググラフマイニングおよび視覚化技術の一部の実施例は、ランキングプロシージャーを用いて、エンティティー間の社会的つながりをランク付けする。以下のセクションは、この技術の一実施例において使用されるランキングプロシージャーに関する追加の情報を与える。
【００３２】
この技術の一実施例により用いられるランク付けを、以下のように説明することができる。エンティティー名Ｘ＝｛ｘ0，ｘ1，．．．｝のリスト、およびＷｅｂページＷ＝｛ｗ0，ｗ1，．．．｝のリストが与えられると、各Ｗｅｂページは情報ブロックＢ＝｛ｂ0，ｂ1，．．．｝を有し、１の情報ブロックでｘiおよびｘjが発生する場合は、情報ブロックにあるこれら２つの名前の間の関係の重みは、
【００３３】
【数５】
0005905450.tif 000006
【００３４】
として定義される。
Ｒdは、関係の距離測度を表し、Ｒcは、関係のコンテキスト測度を表す。これら２つの測度の定義は、以下のように、
【００３５】
【数６】
0005905450.tif 000007
【００３６】
ここで、ｄ（ｘi，ｘj）は、情報ブロックにあるｘiとｘjとの間の文字の距離を表す。情報ブロックにあるｘiおよびｘjが同時に出現しない場合は、ｄ（ｘi，ｘj）は無限となる。すなわち、Ｒdはゼロとなる。変数Ｋ（ｘi，ｘj）は、情報ブロックにある２つの名前の間で発見されていた関係キーワードの集合（例えば、「妻」および「友人」など）を表す。変数ｋmは、所定のキーワードの重み（Ｋm＞１．０）を表す。一実施例では、各関係キーワードは、所定の重み（例えば、２．０の重みを有する「妻」、および１．６の重みを有する「友人」）を有する。Ｋ（ｘi，ｘj）は、２つの名前に対する関係のキーワードに対応する重みの集合である。ｘiおよびｘjに対し、関係キーワードがない場合は、Ｋ（ｘi，ｘj）は空集合であり、「φ」により表される。一方、Ｋ（ｘi，ｘj）は、１または複数の値（例えば、｛１．６，２．０，．．．｝を有する。一実施例では、キーワードの集合は手動で収集される。この集合からのキーワードが、２つのエンティティー名とともに情報ブロックに存在する場合、プロシージャーを使用して、２つのエンティティー名の間の関係を記載するのにこのキーワードを使用するかを決定する。それから、ｘiおよびｘjのグローバルな関係の重みは、
【００３７】
【数７】
0005905450.tif 000008
【００３８】
として定義される。
ランキングプロシージャーは、したがって、情報ブロックにある全てのエンティティー間の関係の重みを算出することができ、併せてエンティティーと、そのエンティティーの関連する関係の重みとをランク付けすることができる。
【００３９】
ソーシャルグラフは、Ｇ＝（Ｖ，Ｅ）として定義され、Ｖは頂点の集合であり、Ｅは辺の集合であることに留意する。Ｗｅｂから発見される各一意なエンティティー名、および人の名前は、グラフにおける頂点であり、すなわち、Ｖ＝｛ｘ0，ｘ1，．．．｝となる。ゼロでない重みを有するｘiとｘjとの各ペアの間では、辺ｅijが定義される。それから、Ｅ＝｛ｅij｝ではＲ（ｘi，ｘj）＞０となる。
【００４０】
１．４  例示的なユーザーインターフェース
図５は、自動ソーシャルネットワーキンググラフマイニングおよび可視化技術の一実施例に準じて、ソーシャルグラフを表示し、操作する例示的なユーザーインターフェース５００を示す。この実施例では、ユーザーは、サーチボックス５０２に名前（例えば、この例では「Ｃ」）を入力することにより、エンティティー名（例えば、人、組織、またはキーワード）を検索することができる。エンティティー名（例えば、Ｃ）は、中心点５０４として示され、その他のつながりのあるエンティティーは中心点５０４の周りの頂点５０６として示される。頂点５０６間の社会的つながりの強さは、辺５０８として示される。２つの頂点５０６の間の辺５０８がより短いと、つながりのある頂点により表されるエンティティー間の関係はより強い。２つの頂点５０６の間の辺５０８がより長いと、つながりのある頂点により表されるエンティティー間の関係はより弱い。一実施例では、頂点５０６の色と、随意にその頂点の後方の背景は、虹状の色のシーケンス（例えば、赤５１０、オレンジ５１２、黄５１４、緑５１６、青５１８、および紫５２０）で０度から３６０度まで変わる。さらに、ノードまたは頂点５０６がより近接すると、ノードの色（また、随意に、ノードの後方の背景）がより近似する。一実施例では、ノード／頂点の色は、０度から３６０度までの極座標に準じて変化する。
【００４１】
一実施例では、例示的なユーザーインターフェース５００はまた、アニメーション（動画）を提供する。例えばユーザーが、ユーザー入力デバイスにより１の頂点５０６をクリック（例えば、選択）するときに、ソーシャルグラフ／マップ５２２全体が、頂点上にクリックされた（例えば、選択された）上の中心にある新しいマップに変化する。このスイッチ遷移の最中に、３つの種類のアニメーションがあり、
ａ）当初は表示され、新しいマップ上にはない頂点は、もはや表示されない。
ｂ）当初は表示され、新しいマップ上にいまだにある頂点は、新しい場所に移動する。
ｃ）当初のマップにはない新しい頂点は、現れ、かつ移動して位置あわせをする。
【００４２】
ユーザーインターフェース５００はまた、カーソルコントロール５２４を含むことができる。カーソルコントロール５２４により、ユーザーはマップ５２２の周りを移動して、グラフの追加部分を表示することが可能となる。ユーザーはまた、種々の頂点５０６を選択して、その頂点に関する追加情報を調査することができる。例えば一実施例では、ユーザーがマウスまたはその他の入力デバイスにより頂点を選択する場合、選択された頂点に関連するエンティティーに関する追加情報とともに、ポップアップウインドウまたはディスプレイスクリーンが表示される。
【００４３】
２．０  コンピューティング環境
自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術が設計され、コンピューティング環境で動作する。以下の説明は、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術を実装することができる適切なコンピューティングコンピューティング環境の簡易かつ一般的な説明を提供することを意図する。その技術は、数々の汎用もしくは専用コンピューティングシステム環境または構成により動作する。適切となりうる既知のコンピューティングシステム、環境、および／または構成は、パーソナルコンピューター、サーバーコンピューター、ハンドヘルドデバイスもしくはラップトップデバイス（例えば、メディアプレイヤー、ノートブックコンピューター、携帯電話、携帯情報端末（ＰＤＡ）、およびボイスレコーダ）、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム制御が可能な家庭用電化製品、ネットワークＰＣ、ミニコンピューター、メインフレームコンピューター、および上記任意のシステムもしくはデバイスを含む分散型コンピューティング環境などを含むが、これらに限定されない。
【００４４】
図６は、適切なコンピューティングシステム環境の例を明らかにする。コンピューティングシステム環境は、適切なコンピューティング環境の１例にすぎず、本技術の使用または機能の範囲に関して、いかなる限定を示唆することを意図しない。コンピューティング環境は、例示的な動作環境において明らかとされるコンポーネントの任意の１つまたはその組み合わせに関して、いかなる依存または必須要件を有するとして解釈されるべきではない。図６を参照すると、自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術を実装する例示的なシステムは、コンピューティングデバイス６００のようなコンピューティングデバイスを含む。最も基本的な構成においては、コンピューティングデバイス６００は主として、少なくとも１つのプロセッシングユニット６０２、およびメモリ６０４を含む。コンピューティングデバイスの的確な構成およびタイプに応じて、メモリ６０４は、揮発性（例えば、ＲＡＭ）、不揮発性（例えば、ＲＯＭ、フラッシュメモリなど）、またはその２つの一部の組み合わせであってもよい。この最も基本的な構成は、図６の波線６０６により明らかにされる。さらに、デバイス６００はまた、追加の特徴／機能を有してもよい。例えば、デバイス６００はまた、磁気もしくは光学のデバイスもしくはテープを含む（これらに限定されない）追加の記憶装置（着脱可能および／または着脱不能）を含んでもよい。このような追加の記憶装置は、図６の着脱可能記憶装置６０８および着脱不能記憶装置６１０により明らかにされる。コンピューター記憶媒体は、揮発性および不揮発性、着脱可能および着脱不能媒体を含む。当該媒体は、コンピューター可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を格納する任意の手段および技術により実装される。メモリ６０４、着脱可能記憶装置６０８、および着脱不能記憶装置６１０は、コンピューター記憶媒体の全ての例となる。コンピューター記憶媒体は、所望の情報を記憶するのに使用することができ、デバイス６００によりアクセスすることができるＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくはその他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置もしくはその他の磁気記憶デバイス、またはその他の媒体を含むが、これらに限定されない。コンピューター可読媒体は、一過性信号および伝播信号の両方、およびコンピューター可読記憶媒体を含む。任意のこのようなコンピューター記憶媒体は、デバイス６００の一部であってもよい。
【００４５】
デバイス６００はまた、当該デバイスがその他のデバイスおよびネットワークと通信することを可能とさせる通信コネクション６１２を包含してもよい。通信コネクション６１２は、通信メディアの例となる。通信メディアは主として、変調データ信号（例えば、搬送波やその他の搬送メカニズムなど）におけるコンピューター可読命令、データ構造、プログラムモジュール、またはその他のデータを具象化し、かつ情報伝送媒体を含む。「変調データ信号」の用語は、信号における情報をエンコードする形式で設定または変更される１または複数の特性を有する信号を意味し、その信号により信号の受信デバイスの構成または状態を変更する。例として、通信媒体は、有線ネットワークもしくは直接配線接続のような有線媒体、ならびに音声、ＲＦ、赤外線およびその他の無線媒体のような無線媒体を含むが、これらに限定されない。本明細書で使用されるコンピューター可読媒体の用語は、記憶媒体および通信媒体の両方を含む。
【００４６】
デバイス６００は、種々の入力デバイス６１４（例えば、ディスプレイ、キーボード、マウス、ペン、カメラ、およびタッチ入力デバイスなど）を有してもよい。出力デバイス６１６（例えば、ディスプレイ６２２、スピーカー、およびプリンターなど）が含まれてもよい。これらのデバイスの全てが当分野において既知であり、これ以上述べる必要はない。
【００４７】
自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、コンピューティングデバイスにより実行されるプログラムモジュールのようなコンピューター実行可能命令の一般的なコンテキストで説明されてもよい。一般に、プログラムモジュールは、特定のタスクを実行し、特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、およびデータ構造などを含む。自動ソーシャルネットワーキンググラフマイニングおよび視覚化技術は、分散型コンピューティング環境で実装されてもよい。分散型コンピューティング環境では、通信ネットワークを通じてリンクされるリモートプロセッシングデバイスにより、タスクが実行される。また、分散型コンピューティング環境では、プログラムモジュールはメモリ記憶デバイスを含むローカルおよびリモートのコンピューター記憶媒体の両方に位置してもよい。
【００４８】
本明細書で説明した上記代替の実施例のうちのいくらかまたは全てが、追加的に混合した実施形態を形成するのに望ましい任意の組み合わせで使用されてもよいことに留意すべきである。上記明細書、例、およびデータは、実施例の組成物の製造および使用の完全な説明を提供する。請求対象は、構造的特長および／または方法論的動作に特有の言語において説明されてきたが、添付の請求項において定義される請求対象は、必ずしも説明された特定の特長または動作に限定されないことを理解されたい。そうではなく、上記説明した特定の特長および動作は、請求項を実装する例示的な形態として開示される。
【図１】
0005905450.tif 000009
【図２】
0005905450.tif 000010
【図３】
0005905450.tif 000011
【図４】
0005905450.tif 000012
【図５】
0005905450.tif 000013
【図６】
0005905450.tif 000014