(57)【要約】【課題】従来のグラフ構造のデータ処理技術によれば、時間の経過とともに変化するノード間の関係に着目した部分グラフの切り出しができなかい、という課題があった。【解決手段】ノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得部と、取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断部と、部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得部と、部分グラフ情報に基づいて処理を行う部分グラフ情報処理部を具備する情報処理装置により、ノードとリンクで構成されるグラフ構造を有するデータの時間変化を検出できる。【選択図】図１
2006228162.tif 000002
【特許請求の範囲】
【請求項１】
ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得部と、
前記リンク強度情報取得部が取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断部と、
前記部分グラフ判断部が、前記部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得部と、
前記部分グラフ情報に基づいて処理を行う部分グラフ情報処理部を具備する情報処理装置。
【請求項２】
前記リンク強度情報取得部が取得した１以上のリンク強度情報に基づいて、部分グラフの結合度を算出し、部分グラフ結合強度情報を取得する部分グラフ結合強度情報取得部をさらに具備し、
前記部分グラフ判断部は、
前記リンク強度情報、および前記部分グラフ結合強度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断する請求項１記載の情報処理装置。
【請求項３】
前記部分グラフを構成する２以上のノードのうちの一のノードと他のノードとのリンク強度情報に基づいて、当該一のノードの前記部分グラフ内における結合の貢献度を示す情報である結合貢献度を算出し、結合貢献度情報を取得する結合貢献度情報取得部をさらに具備し、
前記部分グラフ判断部は、
前記リンク強度情報および前記結合貢献度情報、または前記リンク強度情報および前記部分グラフ結合強度情報および前記結合貢献度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断する請求項１記載の情報処理装置。
【請求項４】
前記リンク強度情報取得部は、
格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応するノード間のリンク強度情報を取得し、
前記部分グラフ判断部は、
前記リンク強度情報取得部が取得したリンク強度情報が所定以上の結合度を示す情報であるか否かを判断する請求項１記載の情報処理装置。
【請求項５】
前記リンク強度情報取得部は、
格納している１以上の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応する第二のノードの間のリンク強度情報を取得し、
前記部分グラフ判断部は、
前記リンク強度情報取得部が取得したリンク強度情報と、前記第一のノードを有する部分グラフの部分グラフ結合強度情報が所定の条件を満たす場合に、当該部分グラフに前記第二のノードが加わった部分グラフが所定の結合度に関する条件を満たすと判断する請求項２記載の情報処理装置。
【請求項６】
前記リンク強度情報取得部は、
格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している他の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第二のノードの間のリンク強度情報を取得し、
前記部分グラフ判断部は、
前記リンク強度情報取得部が取得したリンク強度情報と前記一の部分グラフ情報に対応する第一部分グラフの部分グラフ結合強度情報が所定の条件を満たし、かつ前記リンク強度情報取得部が取得したリンク強度情報と前記他の部分グラフ情報に対応する第二部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、
前記部分グラフ判断部が前記所定の条件を満たすと判断した場合に、前記リンク強度情報取得部に前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示し、または前記リンク強度情報取得部に前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示しかつ前記部分グラフ結合強度情報取得部に部分グラフ結合強度情報を取得するように指示し、続いて、前記部分グラフ判断部に所定の条件を満たすか否かを判断するように指示する部分グラフ再構築制御部をさらに具備する請求項２記載の情報処理装置。
【請求項７】
前記部分グラフ判断部は、
格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードの結合貢献度情報と前記部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、
前記部分グラフ情報取得部は、
前記部分グラフ判断部が、前記所定の条件を満たすと判断した場合に、前記部分グラフから前記第一のノードの除いた部分グラフに関する情報である部分グラフ情報を取得する請求項３記載の情報処理装置。
【請求項８】
コンピュータに、
ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得ステップと、
前記リンク強度情報取得ステップで取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断ステップと、
前記部分グラフ判断ステップで、前記部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得ステップと、
前記部分グラフ情報に基づいて処理を行う部分グラフ情報処理ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ構造を有するグラフデータを構成するノードを結合するリンクの結合度合いの時間的な変化から、部分的なグラフである部分グラフを切り出す情報処理装置等に関するものである。
【背景技術】
【０００２】
従来の動画等を要約する動画要約方法において、動画内の意味的に重要なイベントを自動抽出することが可能な動画要約方法が存在する（例えば、特許文献１参照）。本動画要約方法は、動画の特徴を抽出する特徴抽出器４０と、特徴をインテグレートし境界を決定するための隠れマルコフモデルなどのモデルを使用する確率モデル４２と、コマーシャル及び非コマーシャルスローモーション再生セグメントを区別するコマーシャル／非コマーシャルフィルタ４４と、検出したスローモーション再生セグメントに基づき要約を生成する要約生成器４６とを含む。本動画要約方法における特徴抽出器４０は、ブロック５０でカラーヒストグラムから特徴を抽出し、ブロック５２で画素に基づく差から３つの特徴を抽出する。ブロック５２で抽出した特徴は、再生セグメントのスローモーション，静止フィールド，及び／又はノーマル速度再生の各構成成分を特徴づける。本動画要約方法におけるブロック５０で抽出した特徴は編集効果成分を特徴付ける。
【０００３】
また、グラフ構造から関連性の強いノードの集合を抽出するためのアルゴリズムを開発する研究は従来から行われてはいた（非特許文献２、非特許文献３参照）。かかる研究は、例えば、Ｗｅｂコミュニティやソーシャルネットワークといった、時間に伴って変化することのない、いわば普遍的なコミュニティを検出したり、時間に依存した情報を扱う場合は時間の成分を圧縮、もしくは排除してコミュニティを推定するものである。
また、本実施の形態で述べるビデオの要約を行う情報処理装置に与えるコンテンツの取得方法に関して、非特許文献１において開示されている。
【特許文献１】特開２００２−２３２８４０号公報（第１頁、第１図等）
【非特許文献１】角  康之他９名、"ユビキタス環境における体験の記録と共有"、システム／制御／情報（システム制御情報学会誌）、２００４年１１月、Ｖｏｌ．４８，Ｎｏ．１，ｐｐ．４５８−４６３
【非特許文献２】Ｊ．  Ｋｌｅｉｎｂｅｒｇ．「Ａｕｔｈｏｒｉｔａｔｉｖｅ  ｓｏｕｒｃｅｓ  ｉｎ  ａ  ｈｙｐｅｒｌｉｎｋｅｄ  ｅｎｖｉｒｏｎｍｅｎｔ」、Ｐｒｏｃ．  ９ｔｈ  ＡＣＭ−ＳＩＡＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｄｉｓｃｒｅｔｅ  Ａｌｇｏｒｉｔｈｍｓ，  １９９８
【非特許文献３】Ｃｈｒｉｓ  Ｄｉｎｇ、他４名、「Ｓｐｅｃｔｒａｌ  Ｍｉｎ−Ｍａｘ  Ｃｕｔ  ｆｏｒ  Ｇｒａｐｈ  Ｐａｒｔｉｔｉｏｎｉｎｇ  ａｎｄ  Ｄａｔａ  Ｃｌｕｓｔｅｒｉｎｇ．」、Ｐｒｏｃ．  ｏｆ  １ｓｔ  ＩＥＥＥ  Ｉｎｔ  Ｃｏｎｆ．  Ｄａｔａ  Ｍｉｎｉｎｇ．  Ｓａｎ  Ｊｏｓｅ，  ＣＡ，  ２００１．  ｐｐ．１０７−１１４
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の動画要約方法を実現する情報処理装置においては、動画に現れる人や物（以下、適宜、総称して「オブジェクト」という。）の相互作用に着目していないために、適切な動画の要約ができなかった、という課題があった。
また、従来のグラフ構造のデータ処理研究によれば、時間の概念を導入しておらず、時間の経過とともに変化するノード間の関係に着目した部分グラフの切り出しができなかった。
【課題を解決するための手段】
【０００５】
本第一の発明の情報処理装置は、ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得部と、前記リンク強度情報取得部が取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断部と、前記部分グラフ判断部が、前記部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得部と、前記部分グラフ情報に基づいて処理を行う部分グラフ情報処理部を具備する情報処理装置である。
【０００６】
また、本第二の発明の情報処理装置は、第一の発明に対して、前記リンク強度情報取得部が取得した１以上のリンク強度情報に基づいて、部分グラフの結合度を算出し、部分グラフ結合強度情報を取得する部分グラフ結合強度情報取得部をさらに具備し、前記部分グラフ判断部は、前記リンク強度情報、および前記部分グラフ結合強度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断する情報処理装置である。
【０００７】
かかる構成により、ノードとリンクで構成されるグラフ構造を有するデータの時間変化を検出し、時間的に変化する部分グラフ（ノードの結合によりできるグラフ）を検出でき、意味のあるひとまとまりの部分グラフ情報を取得できる。
【０００８】
また、本第三の発明の情報処理装置は、第一の発明に対して、前記部分グラフを構成する２以上のノードのうちの一のノードと他のノードとのリンク強度情報に基づいて、当該一のノードの前記部分グラフ内における結合の貢献度を示す情報である結合貢献度を算出し、結合貢献度情報を取得する結合貢献度情報取得部をさらに具備し、前記部分グラフ判断部は、前記リンク強度情報および前記結合貢献度情報、または前記リンク強度情報および前記部分グラフ結合強度情報および前記結合貢献度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断する情報処理装置である。
かかる構成により、部分グラフからノードが削除されるべき状態を検出し、新たな部分グラフの構成が可能となる。
【０００９】
また、本第四の発明の情報処理装置は、第一の発明に対して、前記リンク強度情報取得部は、格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応するノード間のリンク強度情報を取得し、前記部分グラフ判断部は、前記リンク強度情報取得部が取得したリンク強度情報が所定以上の結合度を示す情報であるか否かを判断する情報処理装置である。
かかる構成により、新たな部分グラフの生成を検知できる。
【００１０】
また、本第五の発明の情報処理装置は、第二の発明に対して、前記リンク強度情報取得部は、格納している１以上の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応する第二のノードの間のリンク強度情報を取得し、前記部分グラフ判断部は、前記リンク強度情報取得部が取得したリンク強度情報と、前記第一のノードを有する部分グラフの部分グラフ結合強度情報が所定の条件を満たす場合に、当該部分グラフに前記第二のノードが加わった部分グラフが所定の結合度に関する条件を満たすと判断する情報処理装置である。
かかる構成により、部分グラフへの新たなノードの追加を検出できる。
【００１１】
また、本第六の発明の情報処理装置は、第二の発明に対して、前記リンク強度情報取得部は、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している他の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第二のノードの間のリンク強度情報を取得し、前記部分グラフ判断部は、前記リンク強度情報取得部が取得したリンク強度情報と前記一の部分グラフ情報に対応する第一部分グラフの部分グラフ結合強度情報が所定の条件を満たし、かつ前記リンク強度情報取得部が取得したリンク強度情報と前記他の部分グラフ情報に対応する第二部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、前記部分グラフ判断部が前記所定の条件を満たすと判断した場合に、前記リンク強度情報取得部に前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示し、または前記リンク強度情報取得部に前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示しかつ前記部分グラフ結合強度情報取得部に部分グラフ結合強度情報を取得するように指示し、続いて、前記部分グラフ判断部に所定の条件を満たすか否かを判断するように指示する部分グラフ再構築制御部をさらに具備する情報処理装置である。
かかる構成により、部分グラフを構成するノード同士の干渉を検知し、その干渉の検知により、部分グラフの再構成ができる。
【００１２】
また、本第七の発明の情報処理装置は、第三の発明に対して、前記部分グラフ判断部は、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードの結合貢献度情報と前記部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、前記部分グラフ情報取得部は、前記部分グラフ判断部が、前記所定の条件を満たすと判断した場合に、前記部分グラフから前記第一のノードの除いた部分グラフに関する情報である部分グラフ情報を取得する情報処理装置である。
かかる構成により、部分グラフからのノードの削除が検知できる。
【００１３】
また、本第八の発明の情報処理装置は、第一から第七いずれかの発明に対して、前記部分グラフ情報は、部分グラフを構成するノードのノード情報と、前記ノード間のリンクを示すリンク情報を有し、前記リンク情報は、有向リンクである情報処理装置である。
【００１４】
また、本第九の発明の情報処理装置は、第一から第八いずれかの発明に対して、前記ノード情報は、オブジェクトを識別するオブジェクト識別子あり、前記相互作用は、オブジェクト間の会話であり、オブジェクト識別子と、音声を有する音声情報と前記オブジェクト識別子で識別されるオブジェクトに対向しているオブジェクトを識別する１以上のオブジェクト識別子を含むコンテンツを１以上格納しているコンテンツ格納部をさらに具備し、前記リンク強度情報取得部は、前記１以上のコンテンツが有する音声に基づいて、一のオブジェクト識別子で識別されるオブジェクトから他のオブジェクトに対する発話を検出する発話検出手段と、前記発話検出手段が検出した発話の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得手段を具備し、前記部分グラフ処理部は、前記部分グラフが前記所定の条件を満たすと、前記部分グラフ判断部が判断した場合に、当該部分グラフを構成する発話の箇所を、前記コンテンツから抽出する要約抽出手段と、前記要約抽出手段が抽出したコンテンツの部分であり、当該コンテンツの部分の音声を有する要約コンテンツを蓄積する要約蓄積手段を具備する情報処理装置である。
かかる構成により、発話に着目したビデオの要約が自動的に取得できる。
【００１５】
また、本第十の発明の情報処理装置は、第一から第八いずれかの発明に対して、前記ノード情報は、オブジェクトを識別するオブジェクト識別子あり、前記相互作用は、オブジェクト間の対向であり、オブジェクト識別子と、映像を有する映像情報と前記オブジェクト識別子で識別されるオブジェクトに対向しているオブジェクトを識別する１以上のオブジェクト識別子を含むコンテンツを２以上格納しているコンテンツ格納部をさらに具備し、前記リンク強度情報取得部は、前記２以上のコンテンツが有するオブジェクト識別子であり、対向しているオブジェクトを識別する１以上のオブジェクト識別子に基づいて、一のオブジェクトと他のオブジェクトの対向を検出する対向検出手段と、前記対向検出手段が検出した対向の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得手段を具備し、前記部分グラフ処理部は、前記部分グラフが前記所定の条件を満たすと、前記部分グラフ判断部が判断した場合に、当該部分グラフを構成する対向の箇所を、前記コンテンツから抽出する要約抽出手段と、前記要約抽出手段が抽出したコンテンツの部分であり、当該コンテンツの部分の映像を有する要約コンテンツを蓄積する要約蓄積手段を具備する情報処理装置である。
かかる構成により、対向に着目したビデオの要約が自動的に取得できる。
【発明の効果】
【００１６】
本発明による情報処理装置によれば、ノードとリンクで構成されるグラフ構造を有するデータの時間変化を検出できる。
【発明を実施するための最良の形態】
【００１７】
以下、情報処理装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
（実施の形態１）
図１は、本実施の形態における情報処理装置のブロック図である。
【００１８】
情報処理装置は、ノード情報格納部１０１、リンク強度情報取得部１０２、部分グラフ結合強度情報取得部１０３、結合貢献度情報取得部１０４、部分グラフ判断部１０５、部分グラフ再構築制御部１０６、部分グラフ情報取得部１０７、部分グラフ情報処理部１０８を具備する。
リンク強度情報取得部１０２は、相互作用取得手段１０２１、リンク強度情報取得手段１０２２を具備する。
【００１９】
ノード情報格納部１０１は、ノードに関する情報であるノード情報を２以上格納している。ノード情報は、例えば、ノードを識別するノード識別子である。ノード情報は、例えば、ノード識別子と当該ノードにリンクされた他のノード識別子の組の情報でも良い。ノードとは、グラフを構成するものである。所定の相互作用がノード間であった場合に、当該２つのノードは、リンクにより結合される。ここで、リンクは、通常、向きを有するリンクであるが、向きを有さないリンクでも良い。なお、ノードとは、ここでは、抽象化した概念のものであり、例えば、人、データ、機器などである。ノードが人の場合、リンクは、人の間の会話や握手などの相互作用を示す情報であり、リンクによりノードが結合された、と考える。また、ノードが人または物（展示物や展示されている情報など）の場合、リンクは、例えば、ノードである人が、ノードである人やノードである物と向かい合っている（対向している）ことを示す情報である。なお、対向も相互作用の一種である。また、相互作用は、一方から他方に作用を及ぼし、他方は作用を受けるだけの片方向のもの（例えば、先生が生徒に行う説明など）でも良いし、一方が他方に作用を及ぼし、他方も一方に作用を及ぼす（会話など）でも良い。また、ノードが、ハイパーテキスト構造を有するデータ群の中の一データであり、リンクがハイパーテキスト構造を構成するデータ間のリンクであっても良い。また、ノードが、電子掲示板に投函される一意見を示すデータであり、リンクは、データ（意見）間の関連（応答した関係や、ある意見に賛成した関係や、ある意見に反対した関係など）を示す情報であっても良い。さらに、ノードが電子機器の場合、リンクは、無線または有線のネットワークであっても良い。ノード情報格納部１０１は、ハードディスクやＲＯＭ等の不揮発性の記録媒体が好適であるが、ＲＡＭ等の揮発性の記録媒体でも実現可能である。
【００２０】
リンク強度情報取得部１０２は、ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得する。なお、所定時間とは、通常、一定であるが、一定であるとは限らない。相互作用とは、上述した会話や対向などである。また、相互作用とは、機器間のデータ伝送や、ハイパーテキストにおけるデータ間のジャンプなどでも良い。また、対向とは、真正面から向き合っている必要はなく、２つのノードが所定の距離以内に存在している状態等も含む。
【００２１】
また、リンク強度情報取得部１０２は、例えば、定期的に、全ノード間のリンク強度情報を取得しても良い。また、リンク強度情報取得部１０２は、例えば、定期的に、以下で述べる一の部分グラフをお互い構成しない２つのノード間のリンク強度情報を取得しても良い。かかる場合、リンク強度情報取得部１０２は、例えば、格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応するノード間のリンク強度情報を取得できる。なお、部分グラフ情報は、部分グラフ判断部１０５が、部分グラフが所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である。部分グラフ情報は、例えば、部分グラフを構成するノードのノード情報と、ノード間のリンクを示すリンク情報を有し、リンク情報は、有向リンクである。ただし、リンク情報は、向きを有さない情報でも良い。
【００２２】
また、リンク強度情報取得部１０２は、例えば、格納している１以上の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応する第二のノードの間のリンク強度情報を取得できる。また、リンク強度情報取得部１０２は、例えば、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、格納している他の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第二のノードの間のリンク強度情報を取得できる。リンク強度情報は、ノード間の所定時間あたりの相互作用の頻度であるので、時間を考慮したノード間のリンクの強度である、と言える。リンク強度情報を取得する算出式等は問わない。リンク強度情報のデータ構造は問わない。リンク強度情報取得部１０２は、通常、ＭＰＵやメモリ等から実現され得る。リンク強度情報取得部１０２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００２３】
部分グラフ結合強度情報取得部１０３は、リンク強度情報取得部１０２が取得した１以上のリンク強度情報に基づいて、部分グラフの結合度を算出し、部分グラフ結合強度情報を取得する。部分グラフとは、２以上のノードが結合されたグラフである。部分グラフ結合強度情報取得部１０３は、例えば、部分グラフを構成する全ノードのうちの、全２つのノード間のリンク強度情報の和を部分グラフ結合強度情報として算出する。また、部分グラフ結合強度情報取得部１０３は、例えば、部分グラフを構成する全ノードのうちの、全２つのノード間のリンク強度情報の平均値を部分グラフ結合強度情報として算出しても良い。つまり、部分グラフ結合強度情報の算出方法は問わない。また、部分グラフ結合強度情報のデータ構造も問わない。部分グラフ結合強度情報取得部１０３は、通常、ＭＰＵやメモリ等から実現され得る。部分グラフ結合強度情報取得部１０３の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００２４】
結合貢献度情報取得部１０４は、部分グラフを構成する２以上のノードのうちの一のノードと他のノードとのリンク強度情報に基づいて、当該一のノードの前記部分グラフ内における結合の貢献度を示す情報である結合貢献度を算出し、結合貢献度情報を取得する。ここで、「他のノード」とは、部分グラフを構成するノードのうちの、一のノードを除く全ノードである。結合貢献度情報を取得する算出式等は問わない。結合貢献度情報のデータ構造は問わない。結合貢献度情報取得部１０４は、通常、ＭＰＵやメモリ等から実現され得る。結合貢献度情報取得部１０４の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００２５】
部分グラフ判断部１０５は、リンク強度情報取得部１０２が取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件（以下、適宜「第一条件」という。）を満たすか否かを判断する。第一条件は、例えば、２つのノード間の結合の強さが、予め決められた結合の強さより強いという条件である。部分グラフ判断部１０５は、リンク強度情報、および部分グラフ結合強度情報に基づいて、部分グラフが所定の結合度に関する条件（以下、適宜「第二条件」という。）を満たすか否かを判断しても良い。第二条件は、例えば、リンク強度情報が示すリンク間の結合の強さが、部分グラフ結合強度情報が示す部分グラフ（本部分グラフは２以上のノードを有する）全体の結合の度合いの強さの平均（１ノードに対する値）以上であること、である。部分グラフ判断部１０５は、リンク強度情報および結合貢献度情報、またはリンク強度情報および部分グラフ結合強度情報および結合貢献度情報に基づいて、部分グラフが所定の結合度に関する条件（以下、適宜「第三条件」という。）を満たすか否かを判断する。第三条件は、例えば、結合貢献度情報が示す結合の度合いであり、一のノードの部分グラフ全体の結合に対する貢献の割合が、全体の平均の１／２以下であることである。
【００２６】
また、部分グラフ判断部１０５は、どの部分グラフをも構成しないノード間のリンクの強さを示す情報であるリンク強度情報が、所定以上の結合度を示す情報であるか否かを判断する。かかる判断の結果、当該リンク強度情報が、所定以上の結合度を示す情報であると判断した場合は、新しい部分グラフが生成されたと判断することとなる。
【００２７】
また、部分グラフ判断部１０５は、部分グラフを構成する第一のノードと、どの部分グラフをも構成しない第二のノードの間のリンク強度情報と、第一のノードを有する部分グラフの部分グラフ結合強度情報が所定の条件を満たす場合に、当該部分グラフに第二のノードが加わった部分グラフが所定の結合度に関する条件を満たすと判断する。
【００２８】
また、部分グラフ判断部１０５は、第一部分グラフを構成する第一のノードと、第二部分グラフを構成する第二のノード間のリンク強度情報と第一部分グラフの部分グラフ結合強度情報が所定の条件を満たし、かつ第一部分グラフを構成する第一のノードと、第二部分グラフを構成する第二のノード間のリンク強度情報と第二部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断する。かかる判断の結果、上記所定の条件を満たす場合は、第一部分グラフと第二部分グラフを構成する全ノード内において、部分グラフを構成するために、後述する部分グラフ再構築制御部１０６が動作する。つまり、本判断は、部分グラフを再構築するための判断である。
【００２９】
また、部分グラフ判断部１０５は、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードの結合貢献度情報であり、結合貢献度情報取得部１０４が取得した結合貢献度情報と、部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断する。所定の条件とは、例えば、第一のノードの部分グラフにおける結合の貢献度が低いことを決定するための条件である。かかる判断は、部分グラフから当該第一のノードを除外するための判断である。
【００３０】
なお、部分グラフ情報は、部分グラフ判断部１０５が、部分グラフが所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である。部分グラフ情報は、例えば、部分グラフを構成するノードのノード情報と、ノード間のリンクを示すリンク情報を有し、リンク情報は、有向リンクである。ただし、リンク情報は、向きを有さない情報でも良い。
【００３１】
部分グラフ判断部１０５は、通常、ＭＰＵやメモリ等から実現され得る。部分グラフ判断部１０５の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００３２】
部分グラフ再構築制御部１０６は、部分グラフ判断部１０５が所定の条件を満たすと判断した場合に、部分グラフを再構築するための制御を行う。ここでの所定の条件とは、リンク強度情報取得部１０２が取得したリンク強度情報と一の部分グラフ情報に対応する第一部分グラフの部分グラフ結合強度情報が所定の条件を満たし、かつリンク強度情報取得部１０２が取得したリンク強度情報と他の部分グラフ情報に対応する第二部分グラフの部分グラフ結合強度情報が所定の条件を満たすことである。ここで、リンク強度情報取得部１０２が取得したリンク強度情報は、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、格納している他の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第二のノードの間のリンク強度情報である。
【００３３】
部分グラフを再構築するための制御の具体例として、以下の動作がある。例えば、部分グラフ再構築制御部１０６は、リンク強度情報取得部１０２に第一部分グラフおよび第二部分グラフを構成するノード間のリンク強度情報を取得するように指示し、またはリンク強度情報取得部１０２に第一部分グラフおよび第二部分グラフを構成するノード間のリンク強度情報を取得するように指示しかつ部分グラフ結合強度情報取得部に部分グラフ結合強度情報を取得するように指示し、続いて、前記部分グラフ判断部に所定の条件を満たすか否かを判断するように指示する。
【００３４】
部分グラフ情報取得部１０７は、部分グラフ判断部１０５が、部分グラフが所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する。部分グラフ情報は、例えば、部分グラフを構成するノードのノード情報と、ノード間のリンクを示すリンク情報を有し、リンク情報は、有向リンクである。ただし、リンク情報は、向きを有さない情報でも良い。部分グラフ情報取得部１０７は、通常、取得した部分グラフ情報を、少なくとも、一時的に蓄積しておく。かかる蓄積媒体は、ハードディスクやＲＯＭ等の不揮発性の記録媒体でも、ＲＡＭ等の揮発性の記録媒体でも良い。
【００３５】
部分グラフ情報処理部１０８は、部分グラフ情報取得部１０７が取得した部分グラフ情報に基づいて処理を行う。処理とは、以下のように種々ある。つまり、処理とは、ビデオの要約を自動的に取得する処理、電子掲示板に投函されるデータ（意見）から話題を想定する処理、電子掲示板に投函されるデータ（意見）の一部のデータを自動抽出する処理、ＷｅｂのＨＰを自動取得する処理などである。つまり、グラフ構造を有するデータや機器などのうち、時間的な相互作用があるかたまりの部分グラフを取得することが有効な処理をすべて含み得る。部分グラフ情報処理部１０８は、例えば、ＭＰＵやメモリ等から実現され得る。部分グラフ情報処理部１０８の処理手順は、例えば、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。ただし、部分グラフ情報処理部１０８の実現手段は、処理内容によって異なる場合があることは言うまでもない。
【００３６】
相互作用取得手段１０２１は、２つのノード間の相互作用を取得する。ここで、相互作用とは、例えば、会話や対向などである。また、相互作用とは、機器間のデータ伝送や、ハイパーテキストにおけるデータ間のジャンプなどでも良い。
【００３７】
リンク強度情報取得手段１０２２は、相互作用取得手段１０２１が取得したノード間の相互作用に基づいて、リンク強度情報を取得する。リンク強度情報は、ノード間の所定時間あたりの相互作用の頻度を示す情報である。リンク強度情報は、例えば、ノードである二人が１分間の間に会話をしていた時間（例えば、４５秒）である。また、リンク強度情報は、例えば、ノードである人が、ノードである展示物を見ていた（対向していた）時間（例えば、５３秒）である。
次に、情報処理装置の動作について図２から図９のフローチャートを用いて説明する。
【００３８】
（ステップＳ２０１）部分グラフ情報取得部１０７は、カウンタｉに１を代入する。このカウンタｉは、ウィンドウ幅の番号である。なお、ウィンドウ幅のずらし方は、例えば、以下のようにする。部分グラフを構成できない場合には、１秒ずつずらし、部分フラグを構成できた場合は、ウィンドウ幅の分だけずらす。ウィンドウ幅は、部分グラフを構築しているか否かを判断する時間幅であり、例えば、１００秒である。ただし、ウィンドウ幅のずらし方や長さは、問わない。
（ステップＳ２０２）部分グラフ情報取得部１０７は、ｉ番目のウィンドウ幅の区間における部分グラフを取得する。この部分グラフ取得処理について、その動作の詳細は、図３のフローチャートを用いて説明する。
（ステップＳ２０３）部分グラフ情報処理部１０８は、ステップＳ２０２で取得した部分グラフの部分グラフ情報に基づいて処理を行う。かかる処理の具体例は、実施の形態２で述べる。
【００３９】
（ステップＳ２０４）部分グラフ情報取得部１０７は、カウンタｉを１、インクリメントする。つまり、ここで、次のウィンドウ幅を示す始点（時刻ｔ）、および終点（時刻ｔ）を決定する。かかる決定のための処理は、上記のウィンドウ幅のずらし方の処理が、例となる。
（ステップＳ２０５）部分グラフ判断部１０５は、部分グラフの変化を検出する。この変化検出処理について、その動作の詳細は、図４のフローチャートを用いて説明する。
【００４０】
（ステップＳ２０６）部分グラフ情報取得部１０７は、ステップＳ２０５で部分グラフの変化を検出したか否かを判断する。部分グラフの変化を検出すればステップＳ２０７に行き、部分グラフの変化を検出しなければステップＳ２０９に飛ぶ。
【００４１】
（ステップＳ２０７）部分グラフ情報取得部１０７は、部分グラフを更新する。かかる部分グラフの更新は、上記の部分グラフの変化に基づく、部分グラフ情報の更新処理である。かかる部分グラフの更新処理の詳細は、図９のフローチャートを用いて説明する。
（ステップＳ２０８）部分グラフ情報処理部１０８は、ステップＳ２０７で更新した部分グラフの部分グラフ情報に基づいて処理を行う。かかる処理の具体例は、実施の形態２で述べる。
（ステップＳ２０９）部分グラフ情報取得部１０７は、カウンタｉを１、インクリメントする。
【００４２】
（ステップＳ２１０）部分グラフ情報取得部１０７は、処理を終了するか否かを判断する。具体的には、部分グラフ情報取得部１０７は、ｉ番目のウィンドウ幅を有するグラフの時間的遷移の情報が存在するか否かを判断する。処理を終了しないとの判断であれば、ステップＳ２０５に戻る。処理を終了するとの判断であれば、処理を終了する。
次に、部分グラフ取得処理の動作について図３のフローチャートを用いて説明する。
（ステップＳ３０１）リンク強度情報取得部１０２は、カウンタｉに１を代入する。
【００４３】
（ステップＳ３０２）リンク強度情報取得部１０２は、ｉ番目のノードの組が存在するか否かを判断する。ｉ番目のノードの組が存在すればステップＳ３０３に行き、ｉ番目のノードの組が存在しなければステップＳ３０７に飛ぶ。具体的には、例えば、以下の処理により、リンク強度情報取得部１０２は、ｉ番目のノードの組が存在するか否かを判断する。ノード情報格納部１０１は、全ノードのノード識別子（ここでは、例えば、ノード識別子は、オブジェクト識別子である、とする）を格納している。そして、リンク強度情報取得部１０２は、全ノード識別子中の２つのノード識別子の組み合わせを順に決定し、その組み合わせの情報を取得する。かかる場合、すべての組み合わせの情報が取得し終わったか否かにより、リンク強度情報取得部１０２は、ｉ番目のノードの組が存在するか否かを判断する。つまり、ノード情報格納部１０１が、３つのノード識別子を格納している場合、ｉの最大値は「３」である。
【００４４】
（ステップＳ３０３）相互作用取得手段１０２１は、ｉ番目のノードの組の間の、本ウィンドウ幅における相互作用に関する情報を取得する。相互作用取得手段１０２１は、例えば、１００秒（ウィンドウ幅）における、ユーザ「Ａ」からユーザ「Ｂ」への発話の区間、ユーザ「Ｂ」からユーザ「Ａ」への発話の区間を取得する。具体的には、例えば、リンク強度情報取得部１０２は、取得した音声を解析し、所定の大きさ以上の音声を発話していると判断し、かかる発話の区間を取得する等の処理を行う。
【００４５】
（ステップＳ３０４）リンク強度情報取得手段１０２２は、ｉ番目のノードの組を構成する一方のノードから他方のノードへの所定時間（いわゆるウィンドウ幅）あたりの相互作用（例えば、発話）の頻度（ここでは、時間である）であるリンク強度情報を取得する。具体的には、リンク強度情報取得手段１０２２は、ユーザ「Ａ」からユーザ「Ｂ」への発話の時間（例えば、６０秒）を取得する。
【００４６】
（ステップＳ３０５）リンク強度情報取得手段１０２２は、ｉ番目のノードの組を構成する他方のノードから一方のノードへの所定時間あたりの相互作用の頻度であるリンク強度情報を取得する。具体的には、リンク強度情報取得手段１０２２は、ユーザ「Ｂ」からユーザ「Ａ」への発話の時間（例えば、５０秒）を取得する。
【００４７】
（ステップＳ３０６）リンク強度情報取得部１０２は、カウンタｉを１、インクリメントする。ステップＳ３０２に戻る。なお、ステップＳ３０１からステップＳ３０６までの処理により、全ノード間のリンク強度情報が取得できたことになる。
（ステップＳ３０７）部分グラフ判断部１０５は、カウンタｉに０を代入する。
【００４８】
（ステップＳ３０８）部分グラフ判断部１０５は、ノード情報格納部１０１から全ノード数を取得する。なお、全ノード数は、例えば、相互作用取得手段１０２１で相互作用を検出する際に、取得するようにしても良い。かかる場合、情報処理装置は、ノード情報格納部１０１を有さなくても良い。
（ステップＳ３０９）部分グラフ判断部１０５は、カウンタｊに１を代入する。
【００４９】
（ステップＳ３１０）部分グラフ判断部１０５は、ｊ番目の（Ｎ−ｉ）個のノードの組み合わせが存在するか否かを判断する。ｊ番目の（Ｎ−ｉ）個のノードの組み合わせが存在すればステップＳ３１１に行き、ｊ番目の（Ｎ−ｉ）個のノードの組み合わせが存在しなければステップＳ３１２に飛ぶ。
（ステップＳ３１１）部分グラフ判断部１０５は、ｊ番目の（Ｎ−ｉ）個のノード情報を取得する。ステップＳ３１４に行く。
（ステップＳ３１２）部分グラフ判断部１０５は、カウンタｉを１、インクリメントする。
（ステップＳ３１３）部分グラフ判断部１０５は、（Ｎ−ｉ）が２以上であるか否かを判断する。（Ｎ−ｉ）が２以上であればステップＳ３０９に戻り、（Ｎ−ｉ）が２以上でなければ上位関数にリターンする。
【００５０】
（ステップＳ３１４）部分グラフ判断部１０５は、ステップＳ３１１で取得したｊ番目の（Ｎ−ｉ）個のノード情報（複数のノード情報を有するので、適宜、「ノード情報群」という）の全ノードを含む部分グラフが、ステップＳ３１７ですでに取得した部分グラフ情報に対応する部分グラフの中に存在するか否かを判断する。かかる部分グラフが存在しなければステップＳ３１５に行き、存在すればステップＳ３１８に飛ぶ。
（ステップＳ３１５）部分グラフ判断部１０５は、本ノード情報群の部分グラフ情報を取得し、かつ部分グラフ情報を構成する全２つのノード間のリンク強度情報をすべて取得する。
【００５１】
（ステップＳ３１６）部分グラフ判断部１０５は、ステップＳ３１５で取得した全リンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する。条件を満たせばステップＳ３１７に行き、条件を満たさなければステップＳ３１８に飛ぶ。かかる所定の条件の具体例は、後述する。所定の条件の概念を説明すれば以下のようになる。つまり、２以上のノード間のリンクで構成される部分グラフの結合度合いが、所定の結合度合いよりも大きいか否かである。所定の結合度合いより大きければ、所定のウィンドウ幅において、取り出した２以上のノードが、部分グラフを構成する、こととなる。
【００５２】
（ステップＳ３１７）部分グラフ情報取得部１０７は、本ノード情報群を構成するノードに対応する部分グラフ情報を取得する。かかる部分グラフ情報は、ノード識別子の集合のみの情報とウィンドウ幅を構成する時間（始点、終点）の情報の組み合わせでも良いし、ノード識別子の集合とウィンドウ幅を構成する時間の情報と全リンク強度情報でも良い。
（ステップＳ３１８）部分グラフ判断部１０５は、カウンタｊを１、インクリメントする。ステップＳ３１０に戻る。
次に、情報処理装置の変化検出処理の動作について図４のフローチャートを用いて説明する。
（ステップＳ４０１）相互作用取得手段１０２１は、所定の時点における、ノード間の全相互作用を取得する。
【００５３】
（ステップＳ４０２）部分グラフ判断部１０５は、ステップＳ４０１で相互作用が取得されたか否かを判断する。相互作用が取得されればステップＳ４０３に行き、相互作用が取得されなければ上位関数にリターンする。なお、相互作用が取得されなければ、変化検出処理において変化が検出されなかった、ということとなる。
【００５４】
（ステップＳ４０３）部分グラフ判断部１０５は、新たに部分グラフが生成され得るか否かの判断である部分グラフ生成判断を行う。かかる部分グラフ生成判断の処理について、図５のフローチャートを用いて説明する。
（ステップＳ４０４）部分グラフ判断部１０５は、部分グラフが生成され得ればステップＳ４１２に行き、部分グラフが生成され得なければステップＳ４０５に行く。
【００５５】
（ステップＳ４０５）部分グラフ判断部１０５は、部分グラフに新たなノードが追加され得るか否かの判断であるノード追加判断を行う。かかるノード追加判断の処理について、図６のフローチャートを用いて説明する。
（ステップＳ４０６）部分グラフ判断部１０５は、ノードが追加され得ればステップＳ４１２に行き、ノードが追加され得なければステップＳ４０７に行く。
【００５６】
（ステップＳ４０７）部分グラフ判断部１０５は、一の部分グラフを構成するノードと、他の部分グラフを構成するノード間に、相互作用が存在するか否かを判断する。かかる相互作用を部分グラフ間干渉という。かかる部分グラフ間干渉の判断処理について、図７のフローチャートを用いて説明する。
（ステップＳ４０８）部分グラフ判断部１０５は、部分グラフ間の干渉があればステップＳ４１１に行き、部分グラフ間の干渉がなければステップＳ４０９に行く。
【００５７】
（ステップＳ４０９）部分グラフ判断部１０５は、一の部分グラフからノードを削除するか否かを判断する。かかる判断をノード削除判断という。ノード削除判断の処理について、図８のフローチャートを用いて説明する。
【００５８】
（ステップＳ４１０）部分グラフ判断部１０５は、ステップＳ４０９における判断の結果、ノードを削除する部分グラフが存在するか否かを判断する。ノードを削除する部分グラフが存在するならばステップＳ４１１に行き、存在しないなら上位関数にリターンする。
（ステップＳ４１１）部分グラフ情報取得部１０７は、干渉のあった２つの部分グラフを構成する全ノード間において、部分グラフ情報を取得する処理を行う。かかる処理は、図３のフローチャートの処理である。
【００５９】
（ステップＳ４１２）新たに生成した部分グラフ、またはノードが追加された部分グラフ、またはノードが削除された部分グラフのノード情報を有する部分グラフ情報を構成し、取得する。上位関数にリターンする。なお、かかる場合には、変化を検出した旨のリターン値を上位関数にリターンする。
なお、図４のフローチャートにおいて、通常、相互作用の検出のたびに、上記処理を繰り返して行うものとする。
次に、情報処理装置の部分グラフ生成判断の動作について図５のフローチャートを用いて説明する。
（ステップＳ５０１）部分グラフ判断部１０５は、カウンタｉに１を代入する。なお、ここでは、相互作用の対象の２つのノードを一方のノード、他方のノードという呼び方をする。
【００６０】
（ステップＳ５０２）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報が存在するか否かを判断する。ｉ番目の部分グラフ情報は、現在、少なくとも一時的に格納されている部分グラフ情報（現在、部分グラフを構成しているとして格納されている部分グラフ情報であり、既に消滅した部分グラフの情報は除く）のうちのｉ番目の部分グラフ情報である。ｉ番目の部分グラフ情報が存在すればステップＳ５０３に行き、ｉ番目の部分グラフ情報が存在しなければステップＳ５０７に飛ぶ。
【００６１】
（ステップＳ５０３）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報の中に、一方のノードのノード情報が存在するか否かを判断する。一方のノードのノード情報が存在すればステップＳ５０６に行き、一方のノードのノード情報が存在しなければステップＳ５０４に行く。
【００６２】
（ステップＳ５０４）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報の中に、他方のノードのノード情報が存在するか否かを判断する。他方のノードのノード情報が存在すればステップＳ５０６に行き、他方のノードのノード情報が存在しなければステップＳ５０５に行く。
（ステップＳ５０５）部分グラフ判断部１０５は、カウンタｉを１、インクリメントする。ステップＳ５０２に戻る。
（ステップＳ５０６）部分グラフ判断部１０５は、リターン値に、部分グラフを生成しない旨の情報を代入する。上位関数にリターンする。
【００６３】
（ステップＳ５０７）リンク強度情報取得部１０２は、相互作用の対象の２つのノード間のリンク強度情報を取得する。なお、リンク強度情報取得部１０２がすでに、２つのノード間のリンク強度情報を取得しており、一時的に格納している場合は、部分グラフ判断部１０５はかかるリンク強度情報を読み出す。
【００６４】
（ステップＳ５０８）部分グラフ判断部１０５は、ステップＳ５０７で取得したリンク強度情報が所定以上の結合度を示す情報であるか否かを判断する。所定以上の結合度を示す情報であればステップＳ５０９に行き、所定以上の結合度を示す情報でなければステップＳ５０６に行く。
（ステップＳ５０９）部分グラフ判断部１０５は、リターン値に、部分グラフを生成する旨の情報を代入する。上位関数にリターンする。
次に、情報処理装置のノード追加判断の動作について図６のフローチャートを用いて説明する。
（ステップＳ６０１）部分グラフ判断部１０５は、カウンタｉに１を代入する。
【００６５】
（ステップＳ６０２）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報が存在するか否かを判断する。ｉ番目の部分グラフ情報は、現在、少なくとも一時的に格納されている部分グラフ情報のうちのｉ番目の部分グラフ情報である。ｉ番目の部分グラフ情報が存在すればステップＳ６０３に行き、ｉ番目の部分グラフ情報が存在しなければステップＳ６１０に飛ぶ。
【００６６】
（ステップＳ６０３）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報の中に、一方のノードのノード情報が存在するか否かを判断する。一方のノードのノード情報が存在すればステップＳ６０６に行き、一方のノードのノード情報が存在しなければステップＳ６１２に行く。
【００６７】
（ステップＳ６０４）部分グラフ判断部１０５は、他方のノードが、いずれかの部分グラフに属するか否かを判断する。かかる判断処理については以下のように判断する。少なくとも一時的に格納されている部分グラフ情報の中に、他方のノードのノード情報を有する部分グラフ情報が存在するか否かを検査する。
【００６８】
（ステップＳ６０５）部分グラフ判断部１０５は、ステップＳ６０４における検査の結果、他方のノードが、いずれかの部分グラフに属するか、いずれの部分グラフにも属さないかを判断する。いずれの部分グラフに属さない場合にはステップＳ６０６に行き、いずれかの部分グラフに属する場合はステップＳ６１２に行く。
【００６９】
（ステップＳ６０６）リンク強度情報取得部１０２は、相互作用の対象の２つのノード間のリンク強度情報を取得する。なお、リンク強度情報取得部１０２がすでに、２つのノード間のリンク強度情報を取得しており、一時的に格納している場合は、部分グラフ判断部１０５はかかるリンク強度情報を読み出す。
（ステップＳ６０７）部分グラフ結合強度情報取得部１０３は、ｉ番目の部分グラフ情報に対応する部分グラフ結合強度情報を取得する。
【００７０】
（ステップＳ６０８）部分グラフ判断部１０５は、ステップＳ６０６で取得したリンク強度情報と、ステップＳ６０７で取得した部分グラフ結合強度情報が、所定の条件を満たすか否かを判断する。所定の条件を満たせばステップＳ６０９に行き、所定の条件を満たさなければステップＳ６１２に飛ぶ。なお、所定の条件の概念は、以下のようなものである。つまり、所定の条件とは、追加されるノードの、部分グラフに対する結合度合いが所定の度合いより大きいことである。
（ステップＳ６０９）部分グラフ判断部１０５は、ノードを追加する旨のリターン値を構成する。上位関数にリターンする。
（ステップＳ６１０）部分グラフ判断部１０５は、ノードを追加しない旨のリターン値を構成する。上位関数にリターンする。
【００７１】
（ステップＳ６１１）部分グラフ判断部１０５は、部分グラフ判断部１０５は、ｉ番目の部分グラフ情報の中に、他方のノードのノード情報が存在するか否かを判断する。他方のノードのノード情報が存在すればステップＳ６０４に行き、他方のノードのノード情報が存在しなければステップＳ６１２に行く。
（ステップＳ６１２）部分グラフ判断部１０５は、カウンタｉを１、インクリメントする。ステップＳ６０２に戻る。
次に、情報処理装置の部分グラフ干渉判断の動作について図７のフローチャートを用いて説明する。
（ステップＳ７０１）部分グラフ判断部１０５は、カウンタｉに１を代入する。なお、ここでは、相互作用の対象の２つのノードを一方のノード、他方のノードという呼び方をする。
【００７２】
（ステップＳ７０２）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報が存在するか否かを判断する。ｉ番目の部分グラフ情報は、現在、少なくとも一時的に格納されている部分グラフ情報のうちのｉ番目の部分グラフ情報である。ｉ番目の部分グラフ情報が存在すればステップＳ７０３に行き、ｉ番目の部分グラフ情報が存在しなければステップＳ７１２に飛ぶ。
【００７３】
（ステップＳ７０３）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報の中に、一方のノードのノード情報が存在するか否かを判断する。一方のノードのノード情報が存在すればステップＳ７０４に行き、一方のノードのノード情報が存在しなければステップＳ７１３に行く。
（ステップＳ７０４）部分グラフ判断部１０５は、カウンタｊに「ｉ＋１」を代入する。なお、ここで、部分グラフ情報は、順に並んで格納されている、とする。
【００７４】
（ステップＳ７０５）部分グラフ判断部１０５は、ｊ番目の部分グラフ情報が存在するか否かを判断する。ｊ番目の部分グラフ情報が存在すればステップＳ７０６に行き、ｊ番目の部分グラフ情報が存在しなければステップＳ７１３に行く。
【００７５】
（ステップＳ７０６）部分グラフ判断部１０５は、ｊ番目の部分グラフ情報の中に、他方のノード情報が存在するか否かを判断する。他方のノード情報が存在すればステップＳ７０７に行き、他方のノード情報が存在しなければステップＳ７１４に行く。
（ステップＳ７０７）部分グラフ結合強度情報取得部１０３は、ｉ番目の部分グラフ情報が示す部分グラフの部分グラフ結合強度情報を取得する。
（ステップＳ７０８）部分グラフ結合強度情報取得部１０３は、ｊ番目の部分グラフ情報が示す部分グラフの部分グラフ結合強度情報を取得する。
（ステップＳ７０９）リンク強度情報取得部１０２は、相互作用を行った２つのノード間のリンク強度情報を取得する。
【００７６】
（ステップＳ７１０）部分グラフ判断部１０５は、ステップＳ７０７、およびステップＳ７０８で取得した２つの部分グラフ結合強度情報、ステップＳ７０９で取得したリンク強度情報が所定の条件を満たすか否かを判断する。所定の条件を満たせばステップＳ７１１に行き、所定の条件を満たさなければステップＳ７１３に行く。
（ステップＳ７１１）部分グラフ判断部１０５は、リターン値に、部分グラフ間干渉がある旨の値を代入する。上位関数にリターンする。
（ステップＳ７１２）部分グラフ判断部１０５は、リターン値に、部分グラフ間干渉がない旨の値を代入する。上位関数にリターンする。
（ステップＳ７１３）部分グラフ判断部１０５は、カウンタｉを１、インクリメントする。ステップＳ７０２に行く。
（ステップＳ７１４）部分グラフ判断部１０５は、カウンタｊを１、インクリメントする。ステップＳ７０５に行く。
次に、情報処理装置のノード削除判断の動作について図８のフローチャートを用いて説明する。
（ステップＳ８０１）部分グラフ判断部１０５は、カウンタｉに１を代入する。なお、ここでは、相互作用の対象の２つのノードを一方のノード、他方のノードという呼び方をする。
【００７７】
（ステップＳ８０２）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報が存在するか否かを判断する。ｉ番目の部分グラフ情報が存在すればステップＳ５０３に行き、ｉ番目の部分グラフ情報が存在しなければ上位関数にリターンする。
（ステップＳ８０３）部分グラフ結合強度情報取得部１０３は、ｉ番目の部分グラフ情報に対応する部分グラフの部分グラフ結合強度情報を取得する。
（ステップＳ８０４）部分グラフ判断部１０５は、カウンタｊに１を代入する。
【００７８】
（ステップＳ８０５）部分グラフ判断部１０５は、ｉ番目の部分グラフ情報に対応する部分グラフの中にｊ番目のノードが存在するか否かを判断する。ｊ番目のノードが存在すればステップＳ８０６に行き、ｊ番目のノードが存在しなければステップＳ８１４に行く。
（ステップＳ８０６）部分グラフ判断部１０５は、カウンタｋに１を代入する。
（ステップＳ８０７）部分グラフ判断部１０５は、ｊ番目のノードを除くｋ番目のノードが存在するか否かを判断する。
（ステップＳ８０８）リンク強度情報取得部１０２は、上記ｊ番目のノードと上記ｋ番目のノードの間のリンク強度情報を取得する。
（ステップＳ８０９）部分グラフ判断部１０５は、カウンタｋを１、インクリメントする。ステップＳ８０７に戻る。
（ステップＳ８１０）結合貢献度情報取得部１０４は、ｊ番目のノードの結合貢献度情報を取得する。かかる結合貢献度情報は、ステップＳ８０８で取得された１以上のリンク強度情報に基づいて取得される。
【００７９】
（ステップＳ８１１）部分グラフ判断部１０５は、ステップＳ８１０で取得した結合貢献度情報が所定の条件を満たすか否かを判断する。なお、かかる条件は、ｊ番目のノードが、ｉ番目の部分グラフ情報に対応する部分グラフの結合に対する、貢献度が所定の貢献度より高いことを示す条件である。条件を満たせばステップＳ８１２に行き、条件を満たさなければステップＳ８１３に行く。
【００８０】
（ステップＳ８１２）部分グラフ情報取得部１０７は、ｉ番目の部分グラフ情報に対応する部分グラフからｊ番目のノードを削除するための処理を行う。かかる処理は、例えば、ｉ番目の部分グラフ情報からｊ番目のノードに対応するノード情報を削除して、新しい部分グラフ情報を構成する処理である。
（ステップＳ８１３）部分グラフ判断部１０５は、カウンタｊを１、インクリメントする。ステップＳ８０５に行く。
（ステップＳ８１４）部分グラフ判断部１０５は、カウンタｉを１、インクリメントする。ステップＳ８０２に行く。
次に、情報処理装置の部分グラフ情報の更新処理の動作について図９のフローチャートを用いて説明する。
【００８１】
（ステップＳ９０１）部分グラフ情報取得部１０７は、部分グラフを生成する、という変化があったか否かを判断する。部分グラフを生成する、という変化があればステップＳ９０２に行き、かかる変化がなければステップＳ９０４に行く。
（ステップＳ９０２）部分グラフ情報取得部１０７は、相互作用を行った２つのノードのノード情報に基づいて、生成する部分グラフの部分グラフ情報を構成する。
【００８２】
（ステップＳ９０３）部分グラフ情報取得部１０７は、ステップＳ９０２で構成した部分グラフ情報を追記する。かかる追記は、例えば、部分グラフ情報管理表（詳細は後述する）に対して行う。上位関数にリターンする。
【００８３】
（ステップＳ９０４）部分グラフ情報取得部１０７は、部分グラフにノードを追加する、という変化があったか否かを判断する。部分グラフにノードを追加する、という変化があればステップＳ９０５に行き、かかる変化がなければステップＳ９０７に行く。
（ステップＳ９０５）部分グラフ情報取得部１０７は、追加するノードのノード情報を加えた部分グラフ情報を構成する。
（ステップＳ９０６）部分グラフ情報取得部１０７は、ステップＳ９０５で構成した部分グラフ情報を、元の部分グラフの部分グラフ情報に上書き更新する。上位関数にリターンする。
【００８４】
（ステップＳ９０７）部分グラフ情報取得部１０７は、部分グラフ間の干渉が存在するか否かを判断する。部分グラフ間の干渉が存在すればステップＳ９０８に行き、部分グラフ間の干渉が存在しなければステップＳ９１１に行く。
（ステップＳ９０８）部分グラフ情報取得部１０７は、元の２つの部分グラフの部分グラフ情報を削除する。かかる削除は、例えば、部分グラフ情報管理表からの削除である。
【００８５】
（ステップＳ９０９）部分グラフ情報取得部１０７は、生成した部分グラフ情報が存在するか否かを判断する。生成した部分グラフ情報が存在すればステップＳ９１０に行き、生成した部分グラフ情報が存在しなければ上位関数にリターンする。
（ステップＳ９１０）部分グラフ情報取得部１０７は、すべての部分グラフ情報を、例えば、部分グラフ情報管理表に追記する。上位関数にリターンする。
（ステップＳ９１１）部分グラフ情報取得部１０７は、ノードの削除があるか否かを判断する。ノードの削除があればステップＳ９１２に行き、ノードの削除がなければ上位関数にリターンする。
（ステップＳ９１２）部分グラフ情報取得部１０７は、ノード情報を削除した部分グラフ情報を構成する、または、すでに構成しているノード情報を削除した部分グラフ情報を読み出す。
（ステップＳ９１３）部分グラフ情報取得部１０７は、ステップＳ９１２で取得した部分グラフ情報を、上書き更新する。上位関数にリターンする。
【００８６】
なお、図９のフローチャートにおいて、新たに取得した部分グラフ情報を更新せずに、必ず追記するようにしても良い。かかる場合、部分グラフ情報の中に、当該部分グラフが有効な時間帯の情報（例えば、後述する始点、終点の情報）を有することが望ましい。
また、上記の全フローチャートにおいて説明した各種の処理は、一例であることはいうまでもない。
以下、本実施の形態における情報処理装置の動作の概念について説明する。
【００８７】
情報処理装置は、ノードとリンクにより形成されたグラフ構造から、リンクに付与された重みに基づいてグラフの部分である部分グラフを抽出する処理を行う。また、特に、本情報処理装置は、時間の概念を導入し、時間の経過に応じて変化するノード間の結合度合いに基づいて、まとまりのある時間の、まとまりのある部分グラフを抽出する処理を行う。また、本情報処理装置において、空間内のオブジェクトを、グラフを構成するノードとして捕らえているので、グラフ構造は空間内に配置され、空間内を移動したりする。
【００８８】
ここでは、ノードとは、例えば、人や物といったオブジェクトである。リンクは、オブジェクト間の相互作用により生まれる。相互作用とは、例えば、会話や対向である。つまり、二人が会話していると、二人の間でリンクが張られ、その会話の頻度（単位時間あたりの二人の会話時間）がリンク強度を示す。また、リンク強度は、リンクの強度を示すリンク強度情報により示される。
以上の状況において、本情報処理装置が、図２から図９を用いて説明した動作により、部分グラフを抽出する処理の概念について述べる。
まず、図１０を用いて、本情報処理装置の処理における基本的な概念である、リンクの強度、部分グラフの強度、部分グラフへの貢献度について説明する。
【００８９】
まず、図１０（ａ）は、リンクの強度を説明する概念図である。図１０（ａ）において、ノード「Ｂ」がノード「Ａ」に対して相互作用を及ぼしている。具体的には、人「Ｂ」が人「Ａ」に発話している、という状態である。かかる場合、リンク強度情報は、例えば、以下の数式１により算出する。つまり、リンク強度情報は、単位時間あたり（例えば、１０分）の相互作用（たとえば、発話）が行われている時間である。なお、相互作用は、発話や説明などのように、一方が他方に一方的に作用することでも良いし、相互に作用を及ぼしあう会話などでも良い。
【数１】
2006228162.tif 000003
【００９０】
数式１において、ＬＡＢ（ｔ）が、リンク強度情報である。また、ＩＡＢ（ｔ１，ｔ２）は、時刻ｔ１から時刻ｔ２の区間においてＡがＢに対して行った相互作用（たとえば、発話）の総時間である。ｗ１は、ウィンドウ幅である。ウィンドウ幅とは、相互作用の強度を判断する際の単位時間である。
【００９１】
図１０（ｂ）は、２以上のノードを有する部分グラフ全体の強度を説明する概念図である。図１０（ｂ）において、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」が相互に相互作用を及ぼしている。具体的には、各人（「Ａ」「Ｂ」「Ｃ」「Ｄ」）が、他の人に話しをすることにより、議論している、という状態である。かかる場合、部分グラフ結合強度情報は、例えば、以下の数式２により算出する。つまり、部分グラフ結合強度情報は、２つのノード間のすべてのリンク強度情報をパラメータとして算出される。また、さらに具体的には、例えば、部分グラフ結合強度情報は、２つのノード間のすべてのリンク強度情報の和を、ノード数で割った値である。
【数２】
2006228162.tif 000004
【００９２】
数式２において、Ｃｘ（ｔ）が部分グラフ結合強度情報である、また、Ｎｘは、部分グラフを構成するノードの数である。Ｔｘ（ｔ）（ｉ，ｊ）は、部分グラフＸを表すグラフ構造の隣接行列に対して、各要素をノード間の結びつきの強さに変えたものとし，そのｉ，ｊ成分の値をＴｘ（ｔ）（ｉ，ｊ）として表す。また、ｔｓは、部分グラフが生成された時刻を示す。また、ｗ２は、ウィンドウ幅である。
【００９３】
図１０（ｃ）は、一のノードの部分グラフ内における結合の貢献度を示す情報である結合貢献度を説明する概念図である。図１０（ｃ）において、ノード「Ａ」が他者に対して作用を及ぼしている、またはノード「Ａ」が他者から作用を受けている。かかるノード「Ａ」を中心として見た場合の、部分グラフに対するノード「Ａ」の作用の度合いを示す情報が結合貢献度情報である。結合貢献度情報は、例えば、以下の数式３により算出する。
【数３】
2006228162.tif 000005
【００９４】
数式３において、ＣＯｓｘ（ｔ）は、結合貢献度情報である。また。ＮＸを部分グラフＸ内に存在するノードの数とし、ＵＸ（ｔ）を、部分グラフＸを表すグラフ構造の隣接行列に対して、各要素をノードＳが部分グラフＸに寄与しているリンクの結びつきの強さに変えたものである。また、ｗ３は、ウィンドウ幅である。
本情報処理装置は、以上のリンク強度情報、部分グラフ結合強度情報、結合貢献度情報のうちのいずれかの情報、またはそれらの組み合わせの情報を用いて、部分グラフを構成する。
次に、情報処理装置が部分グラフを生成する場合の処理の概念について、図１１の概念図を用いて説明する。
【００９５】
情報処理装置は、ノード「Ａ」とノード「Ｂ」の間のリンク強度情報を取得する。なお、ノード「Ａ」とノード「Ｂ」が、いずれの部分グラフにも属していないとする。そして、ノード「Ａ」とノード「Ｂ」の間のリンク強度情報が、予め決められたリンク強度情報（例えば、１分）以上のリンク強度情報である場合に、ノード「Ａ」とノード「Ｂ」をノード情報として有する部分グラフを有する。そして、情報処理装置は、少なくとも一時的には、図１２に示す「ＩＤ＝１」のレコードである部分グラフ情報を蓄積する。図１２は、部分グラフ情報を格納している部分グラフ情報管理表である。部分グラフ情報管理表は、「ＩＤ」「部分グラフ情報」を有するレコードを１以上保持している。「ＩＤ」は、レコードを識別する情報であり、表におけるレコード管理のために存在する。「部分グラフ情報」は、「ノード情報１」「ノード情報２」「リンク強度情報」を有する。「ノード情報１」「ノード情報２」は、ノード情報であり、ここではノードを識別する識別子である。「部分グラフ情報」は、ノード情報１のノードからノード情報２のノードに対して、作用が及ぼされ、有向のリンクにより結合されていることを示す。また、「リンク強度情報」は、ノード情報１のノードからノード情報２のノードに対するリンクの強度を示す値である。ここでは、リンク強度情報が１以上の値の場合に、部分グラフを構成する、とする。つまり、ノードを人、相互作用を発話であるとすれば、１分以上お話している状態を、部分グラフを構成する状態であると、情報処理装置が認識する、とする。なお、図１２の「ＩＤ＝１」のレコードにおいて、ユーザ「Ａ」は、ユーザ「Ｂ」に２．５分の間発話し、ユーザ「Ｂ」は、ユーザ「Ａ」に１．８分の間発話したことを示す。なお、１分以上お話している状態をいかに判断するか等の具体例は、後述する。
次に、部分グラフに、ノードを追加して、新しい部分グラフを構成する処理であるノード追加処理について、その概念を図１３の概念図を用いて説明する。
【００９６】
図１３において、ノード「Ａ」「Ｂ」「Ｃ」を有する部分グラフが構成されており、当該グラフにノード「Ｄ」が追加される態様である。かかる場合、情報処理装置は、ノード「Ｄ」とノード「Ｃ」の相互作用を検出し、当該相互作用によってリンク強度情報を算出する。そして、情報処理装置は、ノード「Ａ」「Ｂ」「Ｃ」を有する部分グラフの部分グラフ結合強度情報を算出する。そして、情報処理装置は、算出したリンク強度情報と算出した部分グラフ結合強度情報に基づいて、ノード「Ａ」「Ｂ」「Ｃ」の部分グラフに、ノード「Ｄ」を追加するか否かを決定する。ここで、情報処理装置は、例えば、算出したリンク強度情報が、算出した部分グラフ結合強度情報の２倍以上の大きさである場合に、例えば、部分グラフに、ノード「Ｄ」を追加すると決定する。なお、図１３において、「>>」は、十分大きい、という意義であり、十分大きいと判断されえるための元になる値は、情報処理装置が予め保持している。ここでは、十分大きいと判断されえるための元になる値は、例えば、「２倍」である。
【００９７】
次に、部分グラフ間の干渉によって、部分グラフを再構成する処理である部分グラフ間干渉処理について、その概念を図１４の概念図を用いて説明する。図１４において、ノード「Ａ」「Ｂ」「Ｃ」を有する第一部分グラフと、ノード「Ｄ」「Ｅ」を有する第二部分グラフが存在する。つまり、ある時点で、ノード「Ａ」「Ｂ」「Ｃ」を有する第一部分グラフに基づく第一の部分グラフ情報、ノード「Ｄ」「Ｅ」を有する第二部分グラフに基づく第二の部分グラフ情報を、情報処理装置が生成し、保持している。かかる状況において、情報処理装置は、ノード「Ｄ」からノード「Ｃ」への相互作用を検出した、とする。そして、情報処理装置は、かかる相互作用に基づいて、ノード「Ｄ」とノード「Ｃ」の間のリンク強度情報を算出する。また、情報処理装置は、第一部分グラフの部分グラフ結合強度情報を算出する。さらに、情報処理装置は、第二部分グラフの部分グラフ結合強度情報を算出する。そして、情報処理装置は、算出したリンク強度情報が、第一部分グラフの部分グラフ結合強度情報、および第二部分グラフの部分グラフ結合強度情報と所定の関係にあるかどうか判断する。ここで、所定の関係とは、例えば、リンク強度情報の示す値が第一部分グラフの部分グラフ結合強度情報の示す値より十分大きく、かつリンク強度情報の示す値が第二部分グラフの部分グラフ結合強度情報の示す値より十分大きいことである。なお、十分大きいとは、上述と同様、例えば、所定の値の差以上の差であることである。情報処理装置は、上記の所定の関係を有すると判断した場合、新たな部分グラフが構成されている可能性があると判断し、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」「Ｅ」のうちの部分グラフが存在するか否か、最初のステップに立ち戻り、新しい部分グラフを検出する処理を行う。なお、かかる場合、部分グラフを再構成するのは、ノード「Ｄ」が第二部分グラフから抜けて第一部分グラフに結合したのか、ノード「Ｃ」が第一部分グラフから抜けて第二部分グラフに結合したのか、ノード「Ｃ」およびノード「Ｄ」が、それぞれ各部分グラフを抜けて、新たな部分グラフを構成したのかが、この時点では判断できないからである。したがって、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」「Ｅ」の中の新しい部分グラフを検出する処理を行えば、本時点での新たな部分グラフが正確に検出できる。
【００９８】
次に、部分グラフから１以上のノードを削除する処理であるノード削除処理について、その概念を図１５の概念図を用いて説明する。図１５において、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」を有する部分グラフが存在する。つまり、情報処理装置は、ある時点で、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」を有する部分グラフに基づく部分グラフ情報を保持している。そして、情報処理装置は、例えば、定期的に、格納している部分グラフ情報を検査し、上述した処理により、部分グラフから抜けるべきノードが存在するか否かを判断する。具体的には、情報処理装置は、例えば、図１５の部分グラフにおいて、ノード「Ｄ」の結合貢献度情報を算出する。そして、算出した結合貢献度情報の値が、当該部分グラフの部分グラフ結合強度情報の値に対して、十分小さければ、情報処理装置は、本部分グラフから、ノード「Ｄ」を削除すべきであると判断する。そして、新たな当該部分グラフ情報（ノード「Ｄ」を削除した部分グラフ情報）を構成する。そして、情報処理装置は、新たな当該部分グラフ情報を、元の部分グラフ情報に上書き更新する。
【００９９】
以上が、部分グラフの切り出しアルゴリズムの例である。時間の経過に伴って、部分グラフを構成するノード群が変化するが、本情報処理装置は、かかる変化を検出し、部分グラフ情報取得部が変化するまでの一連の部分グラフ情報を取得し、部分グラフ情報処理部が当該部分グラフ情報に基づいて、種々の処理を行う。
【０１００】
以上、本実施の形態によれば、ノードとリンクで構成されるグラフ構造を有するデータの時間変化を検出し、時間的に変化する部分グラフ（ノードの結合によりできるグラフ）を検出でき、意味のあるひとまとまりの部分グラフ情報を取得できる。そして、取得した部分グラフ情報に基づいて、所定の処理を行えば、種々の効果のある情報処理が可能になる。かかる情報処理の具体例については、後述する。
【０１０１】
なお、本実施の形態における処理は、ソフトウェアで実現しても良い。そして、このソフトウェアをソフトウェアダウンロード等により配布しても良い。また、このソフトウェアをＣＤ−ＲＯＭなどの記録媒体に記録して流布しても良い。なお、このことは、本明細書における他の実施の形態においても該当する。なお、本実施の形態における情報処理装置を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、コンピュータに、ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得ステップと、前記リンク強度情報取得ステップで取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断ステップと、前記部分グラフ判断ステップで、前記部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得ステップと、前記部分グラフ情報に基づいて処理を行う部分グラフ情報処理ステップを実行させるためのプログラム、である。
【０１０２】
また、上記プログラムにおいて、コンピュータに、前記リンク強度情報取得ステップで取得した１以上のリンク強度情報に基づいて、部分グラフの結合度を算出し、部分グラフ結合強度情報を取得する部分グラフ結合強度情報取得ステップをさらに実行させ、前記部分グラフ判断ステップにおいて、前記リンク強度情報、および前記部分グラフ結合強度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断するプログラム、でも良い。
【０１０３】
また、上記プログラムにおいて、前記部分グラフを構成する２以上のノードのうちの一のノードと他のノードとのリンク強度情報に基づいて、当該一のノードの前記部分グラフ内における結合の貢献度を示す情報である結合貢献度を算出し、結合貢献度情報を取得する結合貢献度情報取得ステップをさらに実行させ、前記部分グラフ判断ステップにおいて、前記リンク強度情報および前記結合貢献度情報、または前記リンク強度情報および前記部分グラフ結合強度情報および前記結合貢献度情報に基づいて、前記部分グラフが所定の結合度に関する条件を満たすか否かを判断するプログラム、でも良い。
【０１０４】
また、上記プログラムにおいて、前記リンク強度情報取得ステップにおいて、格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応するノード間のリンク強度情報を取得し、記部分グラフ判断ステップにおいて、前記リンク強度情報取得ステップで取得したリンク強度情報が所定以上の結合度を示す情報であるか否かを判断するプログラム、でも良い。
【０１０５】
また、上記プログラムにおいて、前記リンク強度情報取得ステップにおいて、格納している１以上の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している１以上の部分グラフ情報が有するノード情報の中に存在しないノード情報に対応する第二のノードの間のリンク強度情報を取得し、前記部分グラフ判断ステップにおいて、前記リンク強度情報取得ステップで取得したリンク強度情報と、前記第一のノードを有する部分グラフの部分グラフ結合強度情報が所定の条件を満たす場合に、当該部分グラフに前記第二のノードが加わった部分グラフが所定の結合度に関する条件を満たすと判断するプログラム、でも良い。
【０１０６】
また、上記プログラムにおいて、前記リンク強度情報取得ステップにおいて、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードと、前記格納している他の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第二のノードの間のリンク強度情報を取得し、前記部分グラフ判断ステップにおいて、前記リンク強度情報取得ステップで取得したリンク強度情報と前記一の部分グラフ情報に対応する第一部分グラフの部分グラフ結合強度情報が所定の条件を満たし、かつ前記リンク強度情報取得ステップで取得したリンク強度情報と前記他の部分グラフ情報に対応する第二部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、前記部分グラフ判断で前記所定の条件を満たすと判断した場合に、前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示し、または前記第一部分グラフおよび前記第二部分グラフを構成するノード間のリンク強度情報を取得するように指示しかつ部分グラフ結合強度情報を取得するように指示し、続いて、所定の条件を満たすか否かを判断するように指示する部分グラフ再構築制御ステップをさらに、コンピュータに実行させるプログラム、でも良い。
【０１０７】
また、上記プログラムにおいて、前記部分グラフ判断ステップにおいて、格納している一の部分グラフ情報が有するノード情報の中の一のノード情報に対応する第一のノードの結合貢献度情報と前記部分グラフの部分グラフ結合強度情報が所定の条件を満たすか否かを判断し、前記部分グラフ情報取得ステップにおいて、前記部分グラフ判断ステップで、前記所定の条件を満たすと判断した場合に、前記部分グラフから前記第一のノードの除いた部分グラフに関する情報である部分グラフ情報を取得するプログラム、でも良い。
（実施の形態２）
【０１０８】
本実施の形態において、実施の形態１で説明した情報処理装置における処理の具体例について説明する。本情報処理装置は、ビデオの要約を自動的に作成する装置である。本実施の形態において、ノード情報は、オブジェクトを識別するオブジェクト識別子あり、前記相互作用は、オブジェクト間の会話である。オブジェクトとは、ここでは、人である。なお、オブジェクトは、展示物や展示パネルなどでも良い。また、ここでの相互作用は、発話と対向である。発話とは、一方の人から他方の人に話をすることである。対向とは、一方の人が、他方の人または物（展示物など）と向かい合うことである。
【０１０９】
図１６は、本実施の形態における情報処理装置のブロック図である。本情報処理装置は、コンテンツ格納部１６０１、リンク強度情報取得部１６０２、部分グラフ結合強度情報取得部１０３、結合貢献度情報取得部１０４、部分グラフ判断部１０５、部分グラフ再構築制御部１０６、部分グラフ情報取得部１０７、部分グラフ情報処理部１６０８を具備する。
【０１１０】
リンク強度情報取得部１６０２は、発話検出手段１６０２１、対向検出手段１６０２２、リンク強度情報取得手段１６０２３を具備する。部分グラフ情報処理部１６０８は、要約抽出手段１６０８１、要約蓄積手段１６０８２を具備する。
【０１１１】
コンテンツ格納部１６０１は、コンテンツを１以上格納している。コンテンツは、オブジェクト識別子と、映像を有する映像情報と、音声を有する音声情報とオブジェクト識別子で識別されるオブジェクトに対向しているオブジェクトを識別する１以上のオブジェクト識別子を含む。
【０１１２】
なお、コンテンツ格納部１６０１のコンテンツの取得方法は、問わない。例えば、コンテンツは、図１７に示す以下の情報取得装置により取得する。図１７において、情報取得装置は、「ＣＣＤカメラ」「赤外線ＩＤタグ」「赤外線センサ」「ＩＲトラッカ」「マイク」「スロート・マイク」「ＨＭＤ（ヘッド・マウント・ディスプレイ）」を具備する。また、ユーザの耳の上部に「ＣＣＤカメラ」「赤外線ＩＤタグ」「赤外線センサ」を具備する。「ＣＣＤカメラ」は、映像を取得する。「赤外線ＩＤタグ」は、本ユーザのオブジェクト識別子を示す信号を重畳した赤外線信号を発信する。「赤外線センサ」は、外部からの赤外線信号を受信する。つまり、「赤外線センサ」は、上記の「ＩＲトラッカ」である。そして、口元に「マイク」、および喉元に「スロート・マイク」を有する。また、目の前にＨＭＤ（ヘッド・マウント・ディスプレイ）を具備する。そして、「ＣＣＤカメラ」の信号は、ユーザの背中の背負われたＰＣが取得し、ＰＣから、本情報処理装置に送信される構成である。さらに、ＨＭＤはユーザの居る位置や、閲覧した展示物や対向した人（オブジェクト）に関する情報を出力するために利用する。なお、情報取得の方法として、図１７の情報取得装置は、一例であることは言うまでもない。
【０１１３】
ここで、本具体例の状況について説明する。ここでは、情報取得装置を装着した２以上のユーザが、例えば、展示パネルが多数存在する学会の会場に居る。この展示パネルは、タッチパネルを具備するディスプレイに、発表するパネル（技術解説した情報）が表示されている。そして、展示パネルの見学者（ユーザ）が多数、会場に居る。各ユーザは、図１７の情報取得装置を装着し、自分が見た映像、自分に対向するオブジェクト（人や展示パネルなど）を識別するオブジェクト識別子、発声した音声（かかる情報の集合は、コンテンツである）を取得する。そして、コンテンツは、情報処理装置に送られる。
【０１１４】
オブジェクト識別子は、例えば、各見学者に付与されたＩＤであり、各見学者が装着している情報取得装置（図１７参照）の赤外線ＩＤタグから発信される。また、オブジェクト識別子は、各見学者が装着している情報取得装置から情報処理装置に送信されるコンテンツに含まれる、という構成である。つまり、ＣＣＤカメラで取得した映像、マイクで取得した音声、ＩＲトラッカで取得したオブジェクト識別子（見学者に対向する人の識別子）などは、見学者を識別するオブジェクト識別子により関連付けられる。なお、各見学者が装着している情報取得装置が有するＩＲトラッカが、対向する者が装着している情報取得装置の赤外線ＩＤタグから発信されるＩＤ（オブジェクト識別子）を取得する。
コンテンツ格納部１６０１は、ハードディスクやＲＯＭ等の不揮発性の記録媒体が好適であるが、ＲＡＭ等の揮発性の記録媒体でも実現可能である。
【０１１５】
発話検出手段１６０２１は、１以上のコンテンツが有する音声に基づいて、一のオブジェクト識別子で識別されるオブジェクトから他のオブジェクトに対する発話を検出する。発話検出手段１６０２１が、１以上のコンテンツが有する音声と、対向するオブジェクトを識別するオブジェクト識別子に基づいて、一のオブジェクト識別子で識別されるオブジェクトから他のオブジェクトに対する発話を検出することは好適である。発話検出手段１６０２１の具体的な発話検出アルゴリズムについては、後述する。発話検出手段１６０２１は、通常、ＭＰＵやメモリ等から実現され得る。発話検出手段の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【０１１６】
対向検出手段１６０２２は、２以上のコンテンツが有するオブジェクト識別子であり、対向しているオブジェクトを識別する１以上のオブジェクト識別子に基づいて、一のオブジェクトと他のオブジェクトの対向を検出する。対向検出手段１６０２２は、通常、ＭＰＵやメモリ等から実現され得る。対向検出手段の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【０１１７】
リンク強度情報取得手段１６０２３は、発話検出手段１６０２１が検出した発話の頻度を示す情報であるリンク強度情報を取得する。また、リンク強度情報取得手段１６０２３は、対向検出手段１６０２２が検出した対向の頻度を示す情報であるリンク強度情報を取得する。リンク強度情報取得手段１６０２３は、発話の頻度を示す情報であるリンク強度情報と、対向の頻度を示す情報であるリンク強度情報の両方を取得しても良いし、一方を取得しても良い。リンク強度情報取得手段１６０２３は、通常、ＭＰＵやメモリ等から実現され得る。リンク強度情報取得手段１６０２３の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【０１１８】
要約抽出手段１６０８１は、部分グラフが所定の条件を満たすと、部分グラフ判断部１０５が判断した場合に、当該部分グラフを構成する発話の箇所を、コンテンツから抽出する。また、要約抽出手段１６０８１は、部分グラフが所定の条件を満たすと、部分グラフ判断部１０５が判断した場合に、当該部分グラフを構成する対向の箇所を、コンテンツから抽出する。要約抽出手段１６０８１は、通常、ＭＰＵやメモリ等から実現され得る。要約抽出手段１６０８１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【０１１９】
要約蓄積手段１６０８２は、要約抽出手段１６０８１が抽出したコンテンツの部分であり、当該コンテンツの部分の音声または／および映像を有する要約コンテンツを蓄積する。要約蓄積手段１６０８２が要約コンテンツを蓄積する蓄積先の記録媒体は、ハードディスクやＤＶＤ−ＲＡＭ等の不揮発性の記録媒体が好適である。なお、要約蓄積手段１６０８２は、かかる記録媒体を含むと考えても、含まないと考えても良い。
次に、本情報処理装置の動作について説明する。本情報処理装置の動作は、実施の形態１で述べた情報処理装置の動作と概ね同様であるので、フローチャートを用いた詳細な動作説明は省略する。
以下、本実施の形態における情報処理装置がビデオサマリを作成する具体的な動作について説明する。
【０１２０】
今、ユーザＡが情報取得装置を装着し、図１８（ａ）に示すコンテンツを取得し、情報処理装置に送信した、とする。また、ユーザＢが情報取得装置を装着し、図１８（ｂ）に示すコンテンツを取得し、情報処理装置に送信した、とする。
【０１２１】
本コンテンツは、ユーザを識別する「オブジェクト識別子」、ユーザが装着している情報取得装置のＣＣＤカメラが撮影した映像、ユーザが装着している情報取得装置のマイクが取得したユーザの音声、ユーザが装着している情報取得装置のＩＲトラッカが取得した、当該ユーザと対向するオブジェクト（ここでは、人や展示物）のオブジェクト識別子を有する。
【０１２２】
次に、情報処理装置は、図１８（ａ）（ｂ）の２つのコンテンツを解析する。ここで、ウィンドウ幅は「１００秒」である、とする。そして、情報処理装置は、他の人に向かって発声していることを相互作用であると認識する、とする。また、情報処理装置は、相互作用が、ウィンドウ幅の１００秒の間に「１０秒」以上あった場合に、部分グラフを構成する、とする。つまり、リンク強度情報が「１０（秒）」以上である場合に、新たな部分グラフができたと認識する、とする。
そして、図１８のコンテンツにおいて、情報処理装置は、時刻（ｔ）が「０」から「１００」までは、相互作用（ここでは、発話）を検知しない。
【０１２３】
次に、情報処理装置は、図１８（ａ）のコンテンツの時刻「１００」から「２００」の間において、「Ａ」から「Ｂ」への発話を検知し、リンク強度情報取得部１６０２は、リンク強度情報「８０」の情報を取得する。また、情報処理装置は、図１８（ｂ）のコンテンツの時刻「１６０」から「２６０」の間において、「Ｂ」から「Ａ」への発話を検知し、リンク強度情報取得部１６０２は、リンク強度情報「９０」の情報を取得する。
【０１２４】
そして、部分グラフ判断部１０５は、リンク強度情報「８０」および「９０」は、条件「リンク強度情報が「１０（秒）」以上」を満たすと判断する。つまり、部分グラフ判断部１０５は、ノード「Ａ」「Ｂ」が、図１９（ａ）の状態（相互作用なし）から、図１９（ｂ）の状態に移行したと判断する。
【０１２５】
次に、部分グラフ情報取得部１０７は、図２０に示す部分グラフ情報管理表の「ＩＤ＝１」のレコードを構成する。ここでは、部分グラフ情報管理表は、部分グラフ情報取得部１０７は取得または構成した、１以上の部分グラフ情報を格納している。部分グラフ情報は、「オブジェクト識別子」「対向オブジェクト識別子」「リンク強度情報」「始点（ｔ）」「終点（ｔ）」を有する。また、部分グラフ情報管理表の「ＩＤ」は、レコードを識別する情報であり、表におけるレコード管理のために存在する。「オブジェクト識別子」は、相互作用の起点のオブジェクト（ここでは、人）を識別する情報であり、「対向オブジェクト識別子」は相互作用を受けるオブジェクト（ここでは、人）を識別する情報である。「リンク強度情報」は、二人の間の発話の時間を示す。また、「始点（ｔ）」「終点（ｔ）」は、発話の開始時刻、終了時刻を示す。部分グラフ情報管理表の「ＩＤ＝１」のレコードにより、ユーザ「Ａ」「Ｂ」が、始点「１００」から終点「２５０」まで会話していたことが分かる。
【０１２６】
次に、部分グラフ情報処理部１６０８の要約抽出手段１６０８１は、部分グラフ情報管理表の「ＩＤ＝１」のレコードにより、図１８（ａ）の１８１の点線枠のコンテンツ（少なくとも映像と音声を有する）、図１８（ｂ）の１８２の点線枠のコンテンツ（少なくとも映像と音声を有する）を取得する。次に、要約蓄積手段１６０８２は、図１８（ａ）の１８１、１８２のコンテンツを蓄積する。かかる処理により、ユーザ「Ａ」とユーザ「Ｂ」が会話をしていた際のみの、ユーザ「Ａ」「Ｂ」にとって意味のあるコンテンツを自動蓄積できる。
次に、情報取得装置を装着したユーザ「Ａ」「Ｂ」「Ｃ」の３人のコンテンツが情報処理装置に送信され、情報処理装置のコンテンツ格納部１６０１に格納されている、とする。
【０１２７】
図２１は、かかるコンテンツを概念的に示した図である。図２１（ａ）は、ユーザ「Ａ」の情報取得装置が取得したコンテンツである。図２１（ｂ）は、ユーザ「Ｂ」の情報取得装置が取得したコンテンツである。図２１（ｃ）は、ユーザ「Ｃ」の情報取得装置が取得したコンテンツである。また、図２１は、３つのコンテンツの時刻「１２００」秒以降のコンテンツを示す。
そして、情報処理装置は、図２１のコンテンツを上述した動作により解析し、部分グラフを構成する、とする。
【０１２８】
つまり、情報処理装置は、図２１（ａ）の２１１のコンテンツ、図２１（ｂ）の２１２のコンテンツから、ユーザ「Ａ」とユーザ「Ｂ」の間の発話を検出する。そして、図２１（ａ）の２１１のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ａ」からノード「Ｂ」へのリンク強度情報「８０」を検出する。つまり、リンク強度情報取得部１６０２は、ユーザ「Ａ」がユーザ「Ｂ」に８０秒発話していたことを検出する。また、図２１（ｂ）の２１２のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ｂ」からノード「Ａ」へのリンク強度情報「６２」を検出する。つまり、リンク強度情報取得部１６０２は、ユーザ「Ｂ」がユーザ「Ａ」に６２秒発話していたことを検出する。また、「５０」「６２」は、部分グラフを構成するための上記の条件、「１０（秒）」以上を満たすので、部分グラフ情報取得部１０７は、図２２（ａ）に示す部分グラフを取得する。具体的には、部分グラフ情報取得部１０７は、図２３の「レコードＩＤ＝１」のレコードを構成し、記録する。なお、図２３は、部分グラフ情報管理表である。図２３の「レコードＩＤ＝１」のレコードは、図２１の区間（ｄ）の間に構成された部分グラフを示す情報である。
【０１２９】
次に、情報処理装置は、ユーザ「Ｃ」からユーザ「Ｂ」への発話を検知する。つまり、図２１（ｃ）のコンテンツ２１３から、リンク強度情報取得部１６０２は、ノード「Ｃ」からノード「Ｂ」へのリンク強度情報「３８」を検出する。また、図２１（ｂ）のコンテンツ２１４から、リンク強度情報取得部１６０２は、ノード「Ｂ」からノード「Ｃ」へのリンク強度情報「８０」を検出する。また、図２１（ｃ）のコンテンツ２１５から、リンク強度情報取得部１６０２は、ノード「Ｃ」からノード「Ａ」へのリンク強度情報「４７」を検出する。そして、リンク強度情報取得部１６０２は、かかるノード「Ｃ」が始点または終点になっているリンクのリンク強度情報をすべて取得する。次に、部分グラフ結合強度情報取得部１０３は、ノード「Ａ」「Ｂ」の部分グラフの部分グラフ結合強度情報を取得する。具体的には、部分グラフ結合強度情報取得部１０３は、ノード「Ａ」から「Ｂ」へのリンク強度情報「５０」とノード「Ｂ」から「Ａ」へのリンク強度情報「６２」の平均値「５６」を、部分グラフ結合強度情報として算出する。
【０１３０】
次に、部分グラフ判断部１０５は、ノード「Ｃ」が始点または終点になっているリンクのリンク強度情報の平均値を取得する。つまり、「８０」「３８」「８０」「４７」の平均値「６１．２５」を算出する。そして、「６１．２５」は、上記の部分グラフ結合強度情報「５２」より大きいので、部分グラフ判断部１０５は、ノード「Ｃ」が部分グラフに追加されるための条件に合致する、と判断する。なお、一のノードが部分グラフに追加されるための条件は、ここでは、部分グラフ結合強度情報より、当該一のノードが関与するリンク強度情報の平均値が大きい、ことである。
【０１３１】
次に、部分グラフ情報取得部１０７は、図２３の「ＩＤ＝２」のレコードを構成し、部分グラフ情報管理表に書き込む。図２３の「レコードＩＤ＝２」のレコードは、図２１の区間（ｅ）の間に構成された部分グラフを示す情報である。
【０１３２】
そして、部分グラフ情報処理部１６０８の、要約抽出手段１６０８１は、図２１のコンテンツ２１３、２１４、２１５、２１６を取得し、３人の会話と映像が含まれた要約コンテンツを自動抽出する。そして、要約蓄積手段１６０８２は、かかる要約コンテンツを蓄積する。
次に、情報取得装置を装着したユーザ「Ａ」「Ｂ」「Ｃ」「Ｄ」の４人のコンテンツが情報処理装置に送信され、情報処理装置のコンテンツ格納部１６０１に格納されている、とする。
【０１３３】
図２４は、かかるコンテンツを概念的に示した図である。図２４（ａ）（ｂ）（ｃ）（ｄ）は、それぞれユーザ「Ａ」「Ｂ」「Ｃ」「Ｄ」の情報取得装置が取得したコンテンツである。また、図２４は、４つのコンテンツの時刻「３２００」秒以降のコンテンツを示す。
そして、情報処理装置は、図２４のコンテンツを上述した動作により解析し、部分グラフを構成する、とする。
【０１３４】
つまり、情報処理装置は、図２４（ａ）の２４１のコンテンツ、図２４（ｂ）の２４２のコンテンツをから、ユーザ「Ａ」とユーザ「Ｂ」の間の発話を検出する。そして、図２４（ａ）の２４１のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ａ」からノード「Ｂ」へのリンク強度情報「５０」を検出する。つまり、リンク強度情報取得部１６０２は、ユーザ「Ａ」がユーザ「Ｂ」に５０秒発話していたことを検出する。また、図２４（ｂ）の２４２のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ｂ」からノード「Ａ」へのリンク強度情報「６０」を検出する。つまり、リンク強度情報取得部１６０２は、ユーザ「Ｂ」がユーザ「Ａ」に６０秒発話していたことを検出する。また、「５０」「６０」は、部分グラフを構成するための上記の条件、「１０（秒）」以上を満たすので、部分グラフ情報取得部１０７は、図２５（ａ）に示す部分グラフを取得する。具体的には、部分グラフ情報取得部１０７は、部分グラフ情報管理表に上記の情報を示すレコードを構成し、記録する。なお、部分グラフ情報の例は上述したので、ここでの詳細な説明は省略する。また、情報処理装置は、図２４（ｃ）の２４３、２４５のコンテンツ、図２４（ｄ）の２４４のコンテンツをから、ユーザ「Ｃ」とユーザ「Ｄ」の間の発話を検出する。そして、図２４（ｃ）の２４３、２４５のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ｃ」からノード「Ｄ」へのリンク強度情報「５０」（２４３、２４５のコンテンツの総時間）を検出する。また、図２４（ｄ）の２４４のコンテンツから、リンク強度情報取得部１６０２は、ノード「Ｄ」からノード「Ｃ」へのリンク強度情報「４０」を検出する。また、「５０」「４０」は、部分グラフを構成するための上記の条件、「１０（秒）」以上を満たすので、部分グラフ情報取得部１０７は、図２５（ｂ）に示す部分グラフを取得する。そして、部分グラフ情報取得部１０７は、部分グラフ情報管理表に上記の情報を示すレコードを構成し、記録する。
【０１３５】
次に、情報処理装置は、図２４（ｃ）のコンテンツ２４６から、ユーザ「Ｃ」からユーザ「Ｂ」への発話を検知する。そして、リンク強度情報取得部１６０２は、ノード「Ｃ」からノード「Ｂ」へのリンク強度情報「６５」を検出する。
【０１３６】
次に、部分グラフ結合強度情報取得部１０３は、ノード「Ａ」「Ｂ」の部分グラフの部分グラフ結合強度情報を取得する。具体的には、部分グラフ結合強度情報取得部１０３は、ノード「Ａ」から「Ｂ」へのリンク強度情報「５０」とノード「Ｂ」から「Ａ」へのリンク強度情報「６０」の平均値「５５」を、部分グラフ結合強度情報として算出する。また、部分グラフ結合強度情報取得部１０３は、ノード「Ｃ」「Ｄ」の部分グラフの部分グラフ結合強度情報を取得する。具体的には、部分グラフ結合強度情報取得部１０３は、ノード「Ｃ」から「Ｄ」へのリンク強度情報「５０」とノード「Ｄ」から「Ｃ」へのリンク強度情報「４０」の平均値「４５」を、部分グラフ結合強度情報として算出する。
【０１３７】
そして、部分グラフ判断部１０５は、ノード「Ｃ」からノード「Ｂ」へのリンク強度情報「６５」が、ノード「Ｂ」「Ａ」により構成される部分グラフの部分グラフ結合強度情報「５５」より大きく、ノード「Ｃ」「Ｄ」により構成される部分グラフの部分グラフ結合強度情報「４５」より大きいことを検知する。そして、部分グラフ再構築制御部１０６は、ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」の間で、新たな部分グラフの取得を、部分グラフ判断部１０５等に指示する。そして、部分グラフ情報取得部１０７は、例えば、「Ａ」「Ｂ」「Ｃ」を有する部分グラフに対応する部分グラフ情報を取得した、とする。かかる部分グラフ情報の例を図２６に示す。つまり、図２６は、再構成されて、新たに検出された部分グラフに対応する部分グラフ情報を格納している部分グラフ情報管理表の例である。図２６の「ＩＤ＝３８」のレコードは、再構成により新たに検出された部分グラフ情報である。
【０１３８】
次に、部分グラフ情報処理部１６０８の要約抽出手段１６０８１は、図２６の「ＩＤ＝３８」のレコードに対応する要約コンテンツを、コンテンツ格納部１６０１から取得し、要約蓄積手段１６０８２は、当該コンテンツを蓄積する。かかる処理により、部分グラフに変化が生じた後の、まとまりのあるコンテンツを自動蓄積できる。
次に、情報取得装置を装着したユーザ「Ａ」「Ｂ」「Ｃ」の３人のコンテンツが情報処理装置に送信され、情報処理装置のコンテンツ格納部１６０１に格納されている、とする。
【０１３９】
図２７は、かかるコンテンツを概念的に示した図である。図２７（ａ）（ｂ）（ｃ）は、それぞれユーザ「Ａ」「Ｂ」「Ｃ」の情報取得装置が取得したコンテンツである。また、図２７は、３つのコンテンツの時刻「５６００」秒以降のコンテンツを示す。
そして、情報処理装置は、図２７のコンテンツを上述した動作により解析し、部分グラフを構成する、とする。
【０１４０】
つまり、情報処理装置は、図２７（ａ）の２７１，２７２，２７３のコンテンツ、図２７（ｂ）の２７４、２７５のコンテンツ、図２７（ｃ）の２７６、２７７のコンテンツから、ユーザ「Ａ」「Ｂ」「Ｃ」の間の発話を検出する。つまり、情報処理装置は、図２８（ａ）に示す部分グラフを抽出する。かかる処理は、上述した処理と同様であるので、詳細な説明は省略する。
【０１４１】
次に、結合貢献度情報取得部１０４は、ノード「Ａ」「Ｂ」「Ｃ」で構成されている部分グラフにおける、５７００秒以降、５８００秒の間（ウィンドウ幅１００、とする）の各ノードの結合貢献度情報を取得する。つまり、結合貢献度情報取得部１０４は、図２７（ａ）のコンテンツ２７９より、ノード「Ａ」の結合貢献度情報を「５０＋７０」により「１２０」と算出する。また、同様にノード「Ｂ」の結合貢献度情報を１２０」と算出する。この「５０」はユーザ「Ａ」からユーザ「Ｂ」への発話の時間（秒）、「７０」はユーザ「Ｂ」からユーザ「Ａ」への発話の時間（秒）である。
次に、結合貢献度情報取得部１０４は、５７００秒以降、５８００秒の間のノード「Ｃ」の結合貢献度情報「０」を取得する。
そして、部分グラフ結合強度情報取得部１０３は、３つのノードから構成される部分グラフの部分グラフ結合強度情報「１２０／３＝４０」を取得する。
【０１４２】
次に、部分グラフ判断部１０５は、部分グラフ結合強度情報「４０」と結合貢献度情報「０」を比較し、部分グラフ結合強度情報の１／２倍より、結合貢献度情報「０」が小さいので、ノード「Ｃ」は部分グラフから削除される、と決定する。
【０１４３】
次に、部分グラフ情報取得部１０７は、ノード「Ａ」「Ｂ」「Ｃ」を有する部分グラフからノード「Ｃ」の除いた部分グラフに関する情報である部分グラフ情報を取得する。かかる部分グラフ情報は、図２９の「ＩＤ＝８０」のレコードである。そして、部分グラフ情報取得部１０７は、かかるレコードを、部分グラフ情報管理表に記録する。
【０１４４】
次に、部分グラフ情報処理部１６０８の要約抽出手段１６０８１は、図２９の「ＩＤ＝８０」のレコードに対応するコンテンツ（図２７のコンテンツ２７８、２７９）を抽出する。そして、要約蓄積手段１６０８２は、かかるコンテンツを蓄積する。
以上、本実施の形態によれば、実施の形態１で述べた処理の具体例として、ビデオサマリに利用することにより、非常に有効なまとまりのある要約ビデオを自動的に取得することができる。
なお、本実施の形態によれば、相互作用は、主として発話であった。しかし、対向やその他のインタラクションでも良い。
また、本実施の形態によれば、部分グラフ情報処理部１０８の処理は、ビデオサマリの作成であったが、他の処理でも良いことは上述した通りである。
【０１４５】
さらに、本実施の形態における情報処理装置を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、コンピュータに、ノードに関する情報であるノード情報と、ノード間の所定時間あたりの相互作用の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得ステップと、前記リンク強度情報取得ステップで取得した１以上のリンク強度情報に基づいて、２以上のノードと当該ノード間のリンクで構成される部分グラフが所定の結合度に関する条件を満たすか否かを判断する部分グラフ判断ステップと、前記部分グラフ判断ステップで、前記部分グラフが前記所定の条件を満たすと判断した場合に、当該部分グラフに関する情報である部分グラフ情報を取得する部分グラフ情報取得ステップと、前記部分グラフ情報に基づいて処理を行う部分グラフ情報処理ステップを実行させるためのプログラム、である。
【０１４６】
また、上記プログラムにおいて、前記ノード情報は、オブジェクトを識別するオブジェクト識別子あり、前記相互作用は、オブジェクト間の会話であり、前記リンク強度情報取得ステップにおいて、１以上のコンテンツが有する音声に基づいて、一のオブジェクト識別子で識別されるオブジェクトから他のオブジェクトに対する発話を検出する発話検出ステップと、前記発話検出ステップで検出した発話の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得ステップを具備し、前記部分グラフ処理ステップは、前記部分グラフが前記所定の条件を満たすと、前記部分グラフ判断ステップで判断した場合に、当該部分グラフを構成する発話の箇所を、前記コンテンツから抽出する要約抽出ステップと、前記要約抽出ステップで抽出したコンテンツの部分であり、当該コンテンツの部分の音声を有する要約コンテンツを蓄積する要約蓄積ステップを具備するプログラム、である。
【０１４７】
また、上記プログラムにおいて、前記ノード情報は、オブジェクトを識別するオブジェクト識別子あり、前記相互作用は、オブジェクト間の対向であり、前記リンク強度情報取得ステップにおいて、２以上のコンテンツが有するオブジェクト識別子であり、対向しているオブジェクトを識別する１以上のオブジェクト識別子に基づいて、一のオブジェクトと他のオブジェクトの対向を検出する対向検出ステップと、前記対向検出ステップで検出した対向の頻度を示す情報であるリンク強度情報を取得するリンク強度情報取得ステップを具備し、前記部分グラフ処理ステップにおいて、前記部分グラフが前記所定の条件を満たすと、前記部分グラフ判断ステップで判断した場合に、当該部分グラフを構成する対向の箇所を、前記コンテンツから抽出する要約抽出ステップと、前記要約抽出ステップで抽出したコンテンツの部分であり、当該コンテンツの部分の映像を有する要約コンテンツを蓄積する要約蓄積ステップを具備するプログラム、である。
【０１４８】
また、図３０は、本明細書で述べたプログラムを実行して、上述した種々の実施の形態の情報処理装置を実現するコンピュータの外観を示す。上述の実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムで実現され得る。図３０は、このコンピュータシステム３００の概観図であり、図３１は、システム３００のブロック図である。
【０１４９】
図３０において、コンピュータシステム３００は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）ドライブ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ドライブを含むコンピュータ３０１と、キーボード３０２と、マウス３０３と、モニタ３０４と、スピーカー３０５とを含む。
【０１５０】
図３１において、コンピュータ３０１は、ＦＤドライブ３０１１、ＣＤ−ＲＯＭドライブ３０１２に加えて、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１３と、ＣＰＵ３０１３、ＣＤ−ＲＯＭドライブ３０１２及びＦＤドライブ３０１１に接続されたバス３０１４と、ブートアッププログラム等のプログラムを記憶するためのＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０１５と、ＣＰＵ３０１３に接続され、アプリケーションプログラムの命令を一時的に記憶するとともに一時記憶空間を提供するためのＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０１６と、アプリケーションプログラム、システムプログラム、及びデータを記憶するためのハードディスク３０１７とを含む。ここでは、図示しないが、コンピュータ３０１は、さらに、ＬＡＮへの接続を提供するネットワークカードを含んでも良い。
【０１５１】
コンピュータシステム３００に、上述した実施の形態の情報処理装置の機能を実行させるプログラムは、ＣＤ−ＲＯＭ３１０１、またはＦＤ３１０２に記憶されて、ＣＤ−ＲＯＭドライブ３０１２またはＦＤドライブ３０１１に挿入され、さらにハードディスク２５１７に転送されても良い。これに代えて、プログラムは、図示しないネットワークを介してコンピュータ３０１に送信され、ハードディスク３０１７に記憶されても良い。プログラムは実行の際にＲＡＭ３０１６にロードされる。プログラムは、ＣＤ−ＲＯＭ３１０１、ＦＤ３１０２またはネットワークから直接、ロードされても良い。
【０１５２】
プログラムは、コンピュータ３０１に、上述した実施の形態の情報処理装置の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティープログラム等は、必ずしも含まなくても良い。プログラムは、制御された態様で適切な機能（モジュール）を呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいれば良い。コンピュータシステム３００がどのように動作するかは周知であり、詳細な説明は省略する。
【０１５３】
また、上記各実施の形態において、各処理（各機能）は、単一の装置（システム）によって集中処理されることによって実現されてもよく、あるいは、複数の装置によって分散処理されることによって実現されてもよい。
なお、上記プログラムを実行するコンピュータは、単数であってもよく、複数であってもよい。すなわち、集中処理を行ってもよく、あるいは分散処理を行ってもよい。
本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【０１５４】
以上のように、本発明にかかる情報処理装置は、ノードとリンクで構成されるグラフ構造を有するデータの時間変化を検出できるという効果を有し、例えば、ビデオサマリを自動作成する装置等として有用である。
【図面の簡単な説明】
【０１５５】
【図１】実施の形態１における情報処理装置のブロック図
【図２】同情報処理装置の動作について説明するフローチャート
【図３】同部分グラフ取得処理の動作について説明するフローチャート
【図４】同変化検出処理の動作について説明するフローチャート
【図５】同部分グラフ生成判断処理の動作について説明するフローチャート
【図６】同ノード追加判断処理の動作について説明するフローチャート
【図７】同部分グラフ間干渉判断処理の動作について説明するフローチャート
【図８】同ノード削除判断処理の動作について説明するフローチャート
【図９】同部分グラフ情報の更新処理の動作について説明するフローチャート
【図１０】同情報処理装置の処理概念を説明する図
【図１１】同情報処理装置の処理概念を説明する図
【図１２】同部分グラフ情報管理表を示す図
【図１３】同情報処理装置の処理概念を説明する図
【図１４】同情報処理装置の処理概念を説明する図
【図１５】同情報処理装置の処理概念を説明する図
【図１６】実施の形態２における情報処理装置のブロック図
【図１７】同情報取得装置を示す概観図
【図１８】同格納されているコンテンツを示す図
【図１９】同情報処理装置の処理概念を説明する図
【図２０】同部分グラフ情報管理表を示す図
【図２１】同格納されているコンテンツを示す図
【図２２】同情報処理装置の処理概念を説明する図
【図２３】同部分グラフ情報管理表を示す図
【図２４】同格納されているコンテンツを示す図
【図２５】同情報処理装置の処理概念を説明する図
【図２６】同部分グラフ情報管理表を示す図
【図２７】同格納されているコンテンツを示す図
【図２８】同情報処理装置の処理概念を説明する図
【図２９】同部分グラフ情報管理表を示す図
【図３０】同情報処理装置を実現するコンピュータの外観を示す図
【図３１】同情報処理装置を構成するシステムのブロック図
【符号の説明】
【０１５６】
１０１  ノード情報格納部
１０２、１６０２  リンク強度情報取得部
１０３  部分グラフ結合強度情報取得部
１０４  結合貢献度情報取得部
１０５  部分グラフ判断部
１０６  部分グラフ再構築制御部
１０７  部分グラフ情報取得部
１０８  部分グラフ情報処理部
１０２１  相互作用取得手段
１０２２、１６０２３  リンク強度情報取得手段
１６０１  コンテンツ格納部
１６０２１  発話検出手段
１６０２２  対向検出手段
１６０８１  要約抽出手段
１６０８２  要約蓄積手段
【図１】
2006228162.tif 000006
【図２】
2006228162.tif 000007
【図３】
2006228162.tif 000008
【図４】
2006228162.tif 000009
【図５】
2006228162.tif 000010
【図６】
2006228162.tif 000011
【図７】
2006228162.tif 000012
【図８】
2006228162.tif 000013
【図９】
2006228162.tif 000014
【図１０】
2006228162.tif 000015
【図１１】
2006228162.tif 000016
【図１２】
2006228162.tif 000017
【図１３】
2006228162.tif 000018
【図１４】
2006228162.tif 000019
【図１５】
2006228162.tif 000020
【図１６】
2006228162.tif 000021
【図１７】
2006228162.tif 000022
【図１８】
2006228162.tif 000023
【図１９】
2006228162.tif 000024
【図２０】
2006228162.tif 000025
【図２１】
2006228162.tif 000026
【図２２】
2006228162.tif 000027
【図２３】
2006228162.tif 000028
【図２４】
2006228162.tif 000029
【図２５】
2006228162.tif 000030
【図２６】
2006228162.tif 000031
【図２７】
2006228162.tif 000032
【図２８】
2006228162.tif 000033
【図２９】
2006228162.tif 000034
【図３０】
2006228162.tif 000035
【図３１】
2006228162.tif 000036