(57)【要約】【課題】  従来に比べて、Ｂｌｏｇの機能により配信されるウェブページの検索性能をより向上することができる、ウェブページグルーピング装置を提供する。【解決手段】  互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、ウェブページの配信元情報、配信元において設定されたウェブページの分類情報、ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得し、そのノード構成情報を構成する各情報の関連に基づいて、無向グラフを生成する。そして、無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定する。【選択図】    図１
2006072600.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置のコンピュータに実行させるプログラムであって、
互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得処理と、
前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成処理と、
前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング処理と、
をコンピュータに実行させるプログラム。
【請求項２】
請求項１に記載の処理に加え、
前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録する処理を有し、
前記グルーピング処理における、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出する
ことを特徴とする請求項１に記載のコンピュータに実行させるプログラム。
【請求項３】
請求項１または請求項２の処理に加え、
ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ処理と、
をコンピュータに実行させるプログラム。
【請求項４】
通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置であって、
互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得手段と、
前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成手段と、
前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング手段と、
を備えることを特徴とするウェブページグルーピング装置。
【請求項５】
前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録手段に記録するグルーピング結果記録手段と、
前記グルーピング手段において、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出する
ことを特徴とする請求項４に記載のウェブページグルーピング装置。
【請求項６】
ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ手段と、
を備えることを特徴とする請求項４または請求項５に記載のウェブページグルーピング装置。
【請求項７】
通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置におけるウェブページグルーピング方法であって、
互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得過程と、
前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成過程と、
前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング過程と、
を有することを特徴とするウェブページグルーピング方法。
【請求項８】
前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録手段に記録するグルーピング結果記録過程を有し、
前記グルーピング過程において、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出する
ことを特徴とする請求項７に記載のウェブページグルーピング方法。
【請求項９】
ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ過程と、
を有することを特徴とする請求項７または請求項８に記載のウェブページグルーピング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページのうち、特にウェブログ（または、Ｂｌｏｇとも呼ばれる）と呼ばれるウェブページの動的な整理により、配信されている前記ウェブページの広範囲なグルーピングを行なう、ウェブページグルーピング装置及びウェブページグルーピング方法ならびにそのプログラム。
【背景技術】
【０００２】
Ｂｌｏｇは、ウェブページを通信ネットワークを介して配信するウェブサーバとしての機能に、記事などを表示するウェブページを容易に作成するためのインターフェース機能と、記事の要約情報の配信を行なう機能とを付加した技術の総称である。記事の要約情報の規格としてはＲＳＳ（非特許文献１参照）やＡｔｏｍ（非特許文献２参照）などが存在する。Ｂｌｏｇではこの要約情報のアクセスポイントをＲＳＳフィードとして公開し、読み手がこのアクセスポイントを定期的にチェックすることにより最新の記事へのアクセスが容易になる。Ｂｌｏｇは記事を容易に作成できることと、最新記事へのアクセスが容易であることから、個人が頻繁かつ容易に情報を発信できるメディアとして広く普及しつつある。この反面、Ｂｌｏｇはその記述の容易さからなる数の多さと更新頻度の高さから、複数のＢｌｏｇ間の関係を把握して利用する労力は従来のＷｅｂに比べて、多くなっている。通常、Ｂｌｏｇの読み手は興味を持ったＢｌｏｇのみを定期的に観察し、それ以外はリンク、バックやコメントなどを一段程度たどる程度であり、それ以上たどり様々な情報を探すことはしないことが多い。これにより、個人が意見の表明を行ない、それらを読み手が把握して多面的な物の見方を体験することができるというＢｌｏｇがもつ多様な可能性を阻害することとなる。
このような問題を解決し、複数の関連するウェブページをグループ化して情報を有効利用する方法としてウェブページ間のリンクをグラフ理論によるグラフ構造として捉え、これを強連結成分分解することによりグループ化する手法が提案されている（例えば非特許文献３参照）。この技術により、Ｗｅｂ検索の性能が向上され、また短時間に多数のウェブページの閲覧を可能となる。
【非特許文献１】“RSS1.0 Specification”、「online」、「平成１６年８月２５日検索」、インターネット＜ＵＲＬ：http://web.resource.org/rss/1.0/spec＞
【非特許文献２】“The Atom Syndication Format 0.3(RPE-DRAFT) draft-nottingham-atom-format-02”、「online」、「平成１６年８月２５日検索」、インターネット＜ＵＲＬ：http://www.mnot.net/drafts/draft-nottingham-atom-format-02.html＞
【非特許文献３】正田備也、他２名、“パラーメタ化された連結成分分解を用いたＷｅｂ情報の有効利用”信学技法 TECHNICAL REPORT OF IEICE DE2003-78(2003-07)、社団法人電子情報学会
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上述の技術の様に単純に強連結成分分解を行なうと、非常に大きなグループができてしまうので、パラメータにより制限する方法が行なわれている。しかしながら、Ｂｌｏｇにより配信されるウェブページの記述は、通常のウェブサーバによって配信されるウェブページのそれに比べて短く、関連づけされているリンクも少ないと考えられる。このためリンク以外の情報も用いてグループ化することが必要となる。
また、Ｂｌｏｇに関してこのような問題を解決する別の方法として、Ｂｌｏｇの検索エンジンである＜http://bulkfeeds.com＞などがある。これらはＢｌｏｇの記事単位で語彙検索を行ない、ある語彙を合むＢｌｏｇの記事の集団を読み手に提示する。しかしながら、Ｂｌｏｇの記事は短いことが多く、語彙に関する解釈の違いを複数の語彙の組合せで解決するといった手法がとりにくい。このため、多様な意味を持つ語彙を用いて検索した場合、語彙の共通性だけで多数の結果が出力され、これから選択するのが難しいという問題点がある。
【０００４】
また、Ｂｌｏｇの検索エンジンとしてＢｌｏｇ中のｌｉｎｋを検索する＜http://www.technorati.com＞のような技術も存在する。しかし、ｌｉｎｋとの関係の検索では近い情報として挙げられている様々なｌｉｎｋがＢｌｏｇ中に分散して記述されていた場合に、これらを関連する物としてまとめて検索することができない問題がある。
【０００５】
そこでこの発明は、従来に比べて、Ｂｌｏｇの機能により配信されるウェブページの検索性能をより向上することができる、ウェブページグルーピング装置及びウェブページグルーピング方法ならびにそのプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００６】
本発明は、上述の課題を解決すべくなされたもので、通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置のコンピュータに実行させるプログラムであって、互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得処理と、前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成処理と、前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング処理と、をコンピュータに実行させるプログラムである。
【０００７】
また本発明は、上記プログラムが、前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録する処理を有し、前記グルーピング処理における、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出することを特徴とする。
【０００８】
また本発明は、上記プログラムが、ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ処理とをコンピュータに実行させるプログラムである。
【０００９】
また本発明は、通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置であって、互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得手段と、前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成手段と、前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング手段と、を備えることを特徴とするウェブページグルーピング装置である。
【００１０】
また本発明は、上述のウェブページグルーピング装置が、前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録手段に記録するグルーピング結果記録手段と、前記グルーピング手段において、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出することを特徴とする。
【００１１】
また本発明は、上述のウェブページグルーピング装置が、ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ手段と、を備えることを特徴とする。
【００１２】
また本発明は、通信ネットワーク上に接続された各サーバそれぞれから配信されるウェブページをグルーピングするウェブページグルーピング装置におけるウェブページグルーピング方法であって、互いに関連づけされている、ユーザ端末で登録されたウェブページのカテゴリ情報、前記ウェブページの配信元情報、前記配信元において設定された前記ウェブページの分類情報、前記ウェブページの記事情報、のうちの少なくとも複数または全てにより構成されたノード構成情報を取得するノード構成情報取得過程と、前記ノード構成情報を構成する各情報の前記関連に基づいて、グラフ理論のグラフ化により前記各情報の無向グラフを生成するグラフ生成過程と、前記無向グラフを所定のパラメータに基づき二連結成分分解し、その結果抽出した二連結成分と所定の条件とに基づいて極大な二連結成分を抽出し、当該極大な二連結成分をグルーピング単位と設定するグルーピング過程と、を有することを特徴とするウェブページグルーピング方法である。
【００１３】
また本発明は、上述のウェブページグルーピング方法において、前記グルーピング単位の新たなノードに対するアークの情報と二連結成分分解における計算結果を記録手段に記録するグルーピング結果記録過程とを有し、前記グルーピング過程において、次回の二連結成分分解の際に、前記記録された前記アークの情報と前記計算結果とを用いて前記極大な二連結成分を抽出することを特徴とする。
【００１４】
また本発明は、上述のウェブページグルーピング方法において、ノード構成情報を構成する前記各情報のうち、自装置で保持していない情報のノードへのアークを探索する場合に、当該アークの存在を他装置に問合せするアーク問合せ過程を有することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、従来のＢｌｏｇでは発見しにくかった自身の話題に近接しているが直接はリンクされておらず手動で探すのが難しかった話題を自動的に発見することが可能になり、ある話題に対する複数の視点からの解釈を読むというＢｌｏｇでは従来難しかった読み方が可能となる。また、リンクのみをグラフのアークとみなすグルーピングよりもより多くのグループの発見が可能となる。また、断片的な記述が多いＢｌｏｇをグループ化することにより、グループで使用されている語彙を対象に検索するなど、Ｂｌｏｇの性質を補って検索するための予備処理として用いることも可能である。さらに計算量削減と分散処理を可能とし、更新頻度が高く配信元の数が多いＢｌｏｇに対するグルーピングの計算量の問題に対処することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の一実施形態によるウェブページグルーピング装置を図面を参照して説明する。図１は同実施形態によるＢｌｏｇ配信システム構成を示すブロック図である。なお、本実施形態においてはウェブページグルーピング装置の機能がＢｌｏｇサーバに備えられているものとする。図１において、符号１はＢｌｏｇ記事を記載したウェブページを配信するＢｌｏｇサーバである。また２はＰＣ（Personal Computer）などの端末である。また３はインターネットなどの通信ネットワークである。このＢｌｏｇ配信システムにおいては、Ｂｌｏｇサーバ１は、作成されたウェブページを通信ネットワーク３に配信するウェブサーバの機能と、ＲＳＳファイルを配信する機能を備えている。このＲＳＳファイルには、Ｂｌｏｇサーバ１が作成した各Ｂｌｏｇ記事を記載したウェブページの配信単位となる配信者（ウェブページの配信元情報）、配信者において設定されたウェブページの分類情報、アドレス、見出し、更新時刻などの情報が記述されており、当該ＲＳＳファイルを読み込んだ端末２は、ＲＳＳファイル用いることで、多数のＷｅｂサイトの更新情報を統一的な方法で効率的に把握することできる。またＢｌｏｇサーバは自身で作成されたウェブページを記憶しており、このウェブページを、記事情報を保持したファイルとして記憶している。
【００１７】
また、端末２はユーザの指示に基づいて、Ｂｌｏｇサーバ１にウェブページ配信要求を送信し、その返信として上記ウェブページのファイルを通信ネットワーク３経由で取得してブラウザの機能によりウェブページを表示画面に出力している。そして、ユーザが表示されたウェブページを「お気に入り」として登録するよう端末２に指示すると、端末２は当該ウェブページを配信しているＢｌｏｇサーバ１のアクセス先となるＵＲＬ（Uniform Resource Locator）を自装置に備える記憶手段に記録する。また、ユーザは「お気に入り」として登録した各ＵＲＬをカテゴリ別に分類している。例えば、「コンピュータ関連」、「経済ニュース関連」、「社会ニュース関連」などのカテゴリ別にＵＲＬを記録する。ここで、端末２はカテゴリ別に「お気に入り」として記録したＵＲＬをＯＰＭＬ（Outline Processior Markup Language）ファイルに記述している。このＯＰＭＬファイルは、「お気に入り」登録したＵＲＬとそのカテゴリ別の情報が記述されている。そして端末２はＯＰＭＬファイルをＢｌｏｇサーバ１に配信する処理を行なっている。
【００１８】
そして、Ｂｌｏｇサーバ１は、他のＢｌｏｇサーバ１や自装置の配信するＲＳＳファイルや、端末２から受信したＯＰＭＬファイルや、ウェブページの記事情報などを収集して記憶し、それらの情報からノード構成情報となる情報を取得し、それらノード構成情報を構成する情報のうちの全てまたは幾つかの情報をノードとして、グラフ理論のグラフ化により無向グラフを生成する。そして、無向グラフから後述する二連結成分分解などの処理によって、極大な二連結成分抽出し、その極大な二連結成分をグルーピング単位として設定し、記憶する。このグルーピンにより、通信ネットワーク３上に配信されるウェブページのグループ化を精度良く行うことができ、これにより、Ｂｌｏｇの機能により配信されるウェブページの端末２における検索性能をより向上することができる。
上述したように、本実施形態においては、Ｂｌｏｇサーバ１にウェブページグルーピング装置の機能が備えられているものとしているが、通信ネットワーク上に接続された他の専用の装置となるウェブページグルーピング装置が存在しており、これによって後述する処理が行なわれるようにしても良い。またＲＳＳファイルを専用に配信するサーバや、専用のウェブサーバ自体がウェブページグルーピング装置の機能を備えるようにしても良い。
【００１９】
図２はＢｌｏｇサーバに備えられたウェブページグルーピング装置の機能構成を示すブロック図である。
この図において、符号１１は、通信ネットワークを介して他の装置と情報の送受信を行なう通信処理部である。また１２はＢｌｏｇサーバ１の各処理部を制御する制御部である。また１３は各種情報を記憶するデータベースである。また１４はノード構成情報を取得するノード構成情報取得部である。また１５はノード構成情報を構成する各情報をノードとしてグラフ理論における無向グラフを生成するグラフ生成部である。また１６はグラフ生成部１５において生成された無向グラフから二連結成分分解などの処理によって、極大な二連結成分を抽出し、その極大な二連結成分をグルーピング単位として設定するグルーピング処理部である。なおＢｌｏｇサーバ１は、図２における各処理部以外にも、ウェブページを配信するためのウェブサーバ処理部や、Ｂｌｏｇ記事の作成の処理を行なうＢｌｏｇ記事簡易作成処理部などを備えているが、本実施形態においては省略する。
【００２０】
次に、本実施形態による、Ｂｌｏｇサーバの処理フローについて説明する。
まず、Ｂｌｏｇサーバ１のノード構成情報取得部１４が、予めＲＳＳファイルやＯＰＭＬファイルを取得してデータベース１３に記録しておく。このＲＳＳファイルにおいては、ウェブページの配信元の情報や、当該配信元において設定された前記ウェブページの分類情報、が関連づけられてＸＭＬの形式で記述されている。またＯＰＭＬファイルにおいては、各ウェブページについてユーザが登録したカテゴリの情報と当該カテゴリに属するウェブページのＵＲＬなどが記述されている。
【００２１】
そして、Ｂｌｏｇサーバ１のグラフ生成部１５がＲＳＳファイルに記述されたウェブページの配信元の情報や、配信元において設定された前記ウェブページの分類情報や、ＯＰＭＬファイルに記述されたカテゴリの情報や、ウェブページの記事情報をノードとしてグラフ理論における無向グラフを生成する。なお、ウェブページの配信元の情報や、配信元において設定された前記ウェブページの分類情報や、ユーザにより登録されたカテゴリの情報や、ウェブページの記事情報はノードを構成するための情報であるので、これらの情報の総称をノード構成情報と呼ぶこととする。また、後述する無向グラフの作成においては、ウェブページの配信元の情報や、配信元において設定された前記ウェブページの分類情報や、ユーザにより登録されたカテゴリの情報や、ウェブページの記事情報のうちの少なくとも複数または全てを利用する。そしてノード構成情報として他の情報を含んでも良いし、上述のノード構成情報のうちの幾つかを利用するようにしても良い。
【００２２】
図３はノード構成情報から生成された無向グラフと各ノードのグルーピングの概略を示す図である。
図３に示すように、グラフ生成部１５は、Ｂｌｏｇ記事を記載したウェブページの配信単位となる配信元（ｃｈａｎｎｅｌ）情報と、配信元において設定されたＢｌｏｇ記事の分類情報（ｄｃ：ｓｕｂｊｅｃｔ）と、ウェブページに記載されたＢｌｏｇ記事情報と、ユーザが登録したＢｌｏｇ記事のカテゴリ（ＯＰＭＬカテゴリ）とをノードとした無向グラフを生成する。ここで、グラフ生成部１５は、配信元情報とＢｌｏｇ記事の分類情報との間でグラフ化を行ないアークを形成する。またＢｌｏｇ記事の分類情報とその分類に属するＢｌｏｇ記事情報との間でグラフ化を行ないアークを形成する。またＢｌｏｇ記事情報の中に他のＢｌｏｇ記事情報のＵＲＬを示す記述があれば、異なるＢｌｏｇ記事情報の間でグラフ化を行ないアークを形成する。またユーザが登録したＢｌｏｇ記事のカテゴリと配信元情報との間のでグラフ化を行ないアークを形成する。またユーザが登録したＢｌｏｇ記事のカテゴリがＯＰＭＬファイルの記述において階層構造になっている場合には、階層構造となっている各カテゴリがノードとなり、アークを形成する。なお、本来向きを持っているＢｌｏｇ記事情報間のリンクについても向きを考えずにアークとすることにより無向グラフが生成される。そして、グルーピング処理部１６がこれらノードとアークによって形成された無向グラフを基に二連結成分分解を行ないグループを抽出する。
【００２３】
図４はグルーピング処理部の処理フローを示す第１の図である。
次に、図４を用いて、グルーピング処理部の処理フローを説明する。
まず、グルーピング処理部１６は、グラフ生成部１５によって生成された無向グラフ上の任意のノードを二連結成分分解を開始するノードと決定する（ステップＳ１０１）。そして、決定したノードに接しているアークを全てリストアップし、このリストの最初のアークの先のノードについて、ノード数をカウントするパラメータを増加させて、そのパラメータの数値が制限範囲内か否かを判断する（ステップＳ１０２）。そして、パラメータの数値が制限範囲内であれば、当該アークの先のノードの情報を取得する（ステップＳ１０３）。
【００２４】
そして、ノードスタック中のノードと比較して（ステップＳ１０４）、当該ノードスタック中のノードの中に取得したノードと同一ノードの情報があるか否かを判断する（ステップＳ１０５）。ここで同一ノードがあれば、ノードスタックからループをなすノードのリストを出力し、グループリストにそのリストへのポインタを記録する（ステップＳ１０６）。そしてステップＳ１０６の後、またはノードスタック中のノードと比較して、当該ノードスタック中のノードの中に前記取得したノードと同一ノードの情報がない場合、そのノードの情報をノードスタックに入力する（ステップＳ１０７）。そしてパラメータを増加させる（ステップＳ１０８）。そして上述のステップＳ１０２〜Ｓ１０８の処理をパラメータが制限の数値に達するまで繰り返す。なお経路探索は深さ優先で行なっていく。
【００２５】
次にステップＳ１０２において、パラメータが制限範囲を超えた場合には、途中で取得してまだ検索していないノードがあるか否かを判断する（ステップＳ１０９）。そして、検索していないノードがあればそのノードをスタートポイントし、その時点のパラメータから再度ステップＳ１０２以降のフローチャートを実行する（ステップＳ１１０）。またステップＳ１０９において、検索していないノードが無ければ、グループリストから極大なグループ群を選んで出力する（ステップＳ１１１）。
【００２６】
つまり、上述のステップＳ１０１〜ステップＳ１１１のフローにおいては、通過したノードの数をパラメータとし、一定数のノードの通過で発見できる範囲で極大な二連結成分をグループとして抽出する。そして、まず図１で作成されたグラフ上の任意のノードをスタートポイントとし、スタートポイントになったノードに接しているアークを全てリストアップし、このリストの最初のアークをたどって次のノードに到達し、この時の経路を記録する。以下これを深さ優先で行ない、経路上に既に存在するノードに達した段階で二連結成分を検知する。この二連結成分を記録し、更に深さ優先探索を行ないつつ更に二連結成分を発見すれば、これと既に発見した二連結成分を比較し、後から発見した二連結成分か前の二連結成分を全て合んでいればこれを新しい極大な二連結成分として記録する。これをあるスタートポイントから通過したノードの数が一定以下で到達できる範囲の全てのノードに対して行ない、発見した極大な二連結成分をグループとして抽出する。発見されたグループはグループという属性を持った新たなノードとして記録し、二連結成分を構成するループの大きさと、グループ内のノードのリストを保持する。
【００２７】
ここで、パラメータの範囲で極大な二連結成分とは、発見動作をパラメータの制限下において行なった上で発見したグラフの二連結成分のうち、もっとも多くのノードを合むといった外部から与えられた条件を満たす物の事をいう。この条件としては様々な可能性があり得るが、二連結成分分解を基礎とする限りにおいていずれも本発明からの容易な類推とみなせる事を主張する。
【００２８】
そして、本発明により、一記事辺りの記述が少なく、リンクの記述も少ないと考えられるＢｌｏｇの記事をグループ化するために、Ｂｌｏｇの要約情報中に記述されている書き手によるＢｌｏｇの分類情報と記事内のリンク、および読み手による分類であるブックマーク内の分類を組み合わせてこれを無向グラフ構造にモデル化し、このグラフに対してパラメータで制限された二連結成分分解を行なうことでグループを抽出することを特徴としている。この時、パラメータとはグラフ中の通過したアークの数等幾つかの要素があり得る。これによって分解された二連結成分の中で更に与えられた条件を満たす物をグループとして読み手に提示することにより、読み手は複数のリンクやＢｌｏｇ内の関係を通じて結び付いたグループを一つの物として認識し、これを関連付けられた情報として読むことが可能になる。また、この時書き手および読み手による様々な視点において作られたＢｌｏｇの分類情報やブックマーク内の分類をリンクにより組み合わせることで、情報の分類体系の全体を定義することなく分類していくことが可能になる。
【００２９】
また、グループ化するための情報として書き手によるＢｌｏｇの分類や読み手による分類と記事内のリンクを用いることにより、分散して行なわれている小規模な分類を統合してグループとして提示する事が可能となり、これと前述した二連結成分分解によるグループの抽出と組み合わせて自動的に大きな分類をあらかじめ全体で使用する分類体系を構築し、これを読み手と書き手の双方に使用する事を強制せずとも、大規模なＢｌｏｇを分類して利用する事が可能となる。
【００３０】
図５は発見したグループを特殊なノードとした場合の無向グラフを示す図である。
図６はグルーピング処理部の処理フローを示す第２の図である。
次に、図５、６を用いてグルーピング処理部における計算量の削減を行う為に上述の処理によって発見したグループを特殊なノード（以下グループノード）として、再度無向グラフにおけるノードのグルーピングを行なう際の処理について説明する。
【００３１】
まずグルーピング処理部１６は、グラフ生成部１５によって生成された無向グラフ上の任意のノードを、二連結成分分解を開始するノードと決定する（ステップＳ２０１）。そして、決定したノードに接しているアークを全てリストアップし、このリストの最初のアークの先のノードについて、ノード数をカウントするパラメータを増加させて、そのパラメータの数値が制限範囲内か否かを判断する（ステップＳ２０２）。そして、パラメータの数値が制限範囲内であれば、当該アークの先のノードの情報を取得していく（ステップＳ２０３）。このノードの取得は深さ優先で行なわれる。
【００３２】
次に、取得したノードの中にグループノードがあるか否かを判断する（ステップＳ２０４）。ステップＳ２０４においてグループノードがある場合には、ノードスタック中のノードと比較し（ステップＳ２０５）、同一グループノードがあるか否かを判断する（ステップＳ２０６）。そしてステップＳ２０６において同一グループノードがある場合には、パラメータが許容範囲内か否かを判断し（ステップＳ２０７）、許容範囲内であれば、ノードスタックからループをなすノードのリストを出力し、グループリストにそのリストへのポインタを記録する（ステップＳ２０８）。そしてステップＳ２０８の後、またはステップＳ２０６において同一グループノードがない場合、またはステップＳ２０７においてパラメータが許容範囲内でない場合には、グループノードをノードスタックに入力し（ステップＳ２０９）、パラメータを増加させる（ステップＳ２１０）。そして上述のステップＳ２０２〜Ｓ２１０の処理をパラメータが制限の数値に達するまで繰り返す。なお経路探索は深さ優先で行なっていく。
【００３３】
またステップＳ２０４において、グループノードが無い場合、上述のステップＳ１０４〜ステップＳ１０８と同様の、ステップＳ２１１〜ステップＳ２１５の処理を行なう。
またステップＳ２０２において、パラメータが制限範囲を超えた場合には、上述のステップＳ１０９〜ステップＳ１１１と同様の、ステップＳ２１６〜ステップＳ２１８の処理を行なう。
【００３４】
上述のステップＳ２０１〜ステップＳ２１８の処理において、グループノードは、二連結成分分解時にノードからのリンクで最初に探索するのに用いられ、グループノードを経由して既にグループとして記述されているノードを経由して深さ優先探索が行なわれる。ここで、再び当該グループとして記述されているノードに到達すればこれでループの存在が確認できる。このループがパラメータの制限範囲内であるなら、新たにグループが発見できたことになる。図５中ではグループノードは点線で表された四角で、グループに属するノードのリストは点線で掛かれたアークでそれぞれ表現されている。
【００３５】
そして上述のステップＳ２０１〜ステップＳ２１８のフローにより、既に計算されて発見されている二連結成分に２つの接続点を持つか、あるいは二連結成分間を２つ接続するノードが新たに付け加えられた場合には、既存の計算結果を用いて計算することが可能となり、その分の計算量を削減することができる。新たに発見したループの中で従来のループと重なる部分があるものをグループとしてどのように扱うかについては幾つかの可能性がある。新たに発見したループと従来のループを比較し、より大きな物をグループと認める方法や、新たに発見したループを別グループとして認める方法がある。また、前述した極大な二連結成分の定義中に合まれて定義されている場合もあり得る。
【００３６】
また上述のステップＳ２０１〜ステップＳ２１８の処理では、グラフのノードとアークの数の和に比例する計算時間を要する二連結成分分解の計算を節約するために、既に行なわれた二連結成分分解の結果として抽出されたグループをグラフ上の特殊なノードとして記述し、グループとされたノードとの間にと特殊なアークを形成しており、またグループを示すノードの属性として、このグループが抽出された際のパラメータを記述している。この後で新たに記述された記事をノードとしてグラフに追加した際、二連結成分分解を行なう際に、あるノードを指しているグループがあればそちらの属性を参照することにより、既存のグラフに関して再計算を行なう必要が無くなり、その分だけ計算量が削減できる。これによってノードがグループに属すると判別した場合(既存グループに２つのアークが存在し、このアークをパラメータとして追加してもなおパラメータの制限を越えない場合)には、グループ記述に変更を加えてそのノードをグループに追加すれば良い。この計算量の節約は特に更新頻度の激しいＢｌｏｇ記事のグルーピング化においては有効である。
【００３７】
図７は複数の装置で保持される無向グラフを示す図である。
図８はグルーピング処理部の処理フローを示す第２の図（その１）である。
図９はグルーピング処理部の処理フローを示す第２の図（その２）である。
次に、図７、８、９を用いて、無向グラフが他装置で分散された際の、グルーピング処理部におけるノードのグルーピング処理について説明する。
【００３８】
まず、グルーピング処理部１６は、グラフ生成部１５によって生成された無向グラフ上の任意のノードを二連結成分分解を開始するノードと決定する（ステップＳ３０１）。そして、決定したノードに接しているアークを全てリストアップし、このリストの最初のアークの先のノードについて、ノード数をカウントするパラメータを増加させて、そのパラメータの数値が制限範囲内か否かを判断する（ステップＳ３０２）。そして、パラメータの数値が制限範囲内であれば、当該アークの先のノードを問い合わせる情報を作成する（ステップＳ３０３）。そして、ノードの問合せ情報を基に、自装置のデータベース１３を検索して（ステップＳ３０４）ノードの情報が存在するか否かを判断する。またノードの問合せ情報を基に、他装置に通信ネットワークを介してノードの情報が存在するか否かを問い合わせる（ステップＳ３０５）。
【００３９】
次に、グルーピング処理部１６は、ステップＳ３０４の結果、またはステップＳ３０５での他装置への問合せの応答の受信（ステップＳ３０６）に基づいて、現在注目しているノードとアークで結ばれたノードを発見したか否かを確認し（ステップＳ３０７）、発見した場合には、ノードスタック中のノードと比較し（ステップＳ３０８）、当該ノードスタック中のノードの中に前記取得したノードと同一ノードの情報があるか否かを判断する（ステップＳ３０９）。ここで同一ノードがあれば、ノードスタックからループをなすノードのリストを出力し、グループリストにそのリストへのポインタを記録する（ステップＳ３１０）。そしてステップＳ３１０の後、またはノードスタック中のノードと比較して、当該ノードスタック中のノードの中に前記取得したノードと同一ノードの情報がない場合、そのノードの情報をノードスタックに入力する（ステップＳ３１１）。そしてパラメータを増加させる（ステップＳ３１２）。そして上述のステップＳ３０２〜Ｓ３１２の処理をパラメータが制限の数値に達するまで繰り返す。なお経路探索は深さ優先で行なっていく。
【００４０】
次にステップＳ３０２において、パラメータが制限範囲を超えた場合、またはステップＳ３０７において、現在注目しているノードとアークで結ばれたノードを発見しなかった場合には、途中で取得してまだ検索していないノードがあるか否かを判断する（ステップＳ３１３）。そして、検索していないノードがあればそのノードをスタートポイントし、その時点のパラメータから再度ステップＳ１０２以降のフローチャートを実行する（ステップＳ３１４）。またステップＳ１０９において、検索していないノードが無ければ、グループリストから極大なグループ群を選んで出力する（ステップＳ３１５）。
【００４１】
また図９より、他装置が、ノードの情報が存在するか否かの問い合わせを受信した際の処理について説明する。
まず、他装置におけるグルーピング処理部１６は、ノードを問い合わせる情報を受信し（ステップＳ４０１）、その問い合わせ内容に該当するノードの情報をデータベース１３から検索する（ステップＳ４０２）。なおノードの問合せの情報にはパラメータの値などが格納されている。そして当該ノードがあるか否かを判断し（ステップＳ４０３）、存在すればそのノードからパラメータの範囲でアークで結ばれている他のノードがあるか否かを判断する（ステップＳ４０４）。そして、ステップＳ４０４において、パラメータの範囲でアークで結ばれている他のノードがある場合には、それら該当ノードとパラメータの範囲でアークで結ばれている他のノードを通知する応答情報を作成する（ステップＳ４０５）。また、ステップＳ４０４において、パラメータの範囲でアークで結ばれている他のノードがなる場合には、該当ノードのみを通知する応答情報を作成する（ステップＳ４０６）。またステップＳ４０３において該当ノードが無い場合には、その旨を示す応答情報を作成する（ステップＳ４０７）。そして他装置におけるグルーピング処理部１６は、作成した応答情報を、ノードの情報が存在するか否かの問い合わせを行なった装置へ送信する（ステップＳ４０８）。
【００４２】
なお他装置でのグラフの分散のさせ方には、
・各Blog記事の作成し、配信している装置が自身の記事についてグラフを持つ場合。
・多数の読み手が自身で探してチェックしている記事についてのグラフを持つ場合。
・分類サービスを提供する企業の装置が、複数の装置で分担させて集めた記事についてのグラフを持つ場合。
のような多様なポリシーがあり得る。
【００４３】
そして、上述の処理によれば、複数装置がそれぞれ自身の保持するＢｌｏｇ記事および要約情報から作成されたグラフを持ち、ある装置が自身の保持するＢｌｏｇ情報のグラフに対する二連結成分分解を行なう際に、あるノードから自装置が保持しないが他装置が保持するノードヘのアークが存在する場合か、あるいはあるノードから自装置が保持していないが他装置が保持しているかもしれないノードヘのアークを探索して発見しようとする場合に他装置へのノードの取得ないし関連するアークを持つノードの探索通信を行なうことを特徴とする。これにより、複数のノードで分散してグルーピングを行なう処理を行なうことが可能になる。またＢｌｏｇ記事の書き手がそれぞれの装置で自身のＢｌｏｇ記事およびその配信情報を基にグラフ化したデータを持ち他装置からの問い合わせに応答することにより、Ｂｌｏｇ記事の更新と同時にグルーピングに反映することも可能となる。
【００４４】
以上、本発明の実施形態について説明したが、従来のＢｌｏｇでは発見しにくかった自身の話題に近接しているが直接はリンクされておらず手動で探すのが難しかった話題を自動的に発見することが可能になり、ある話題に対する複数の視点からの解釈を読むというＢｌｏｇでは従来難しかった読み方が可能となる。また、リンクのみをグラフのアークとみなすグルーピングよりもより多くのグループの発見が可能となる。また、断片的な記述が多いＢｌｏｇ記事を記載したウェブページをグループ化することにより、グループで使用されている語彙を対象に検索するなど、Ｂｌｏｇの性質を補って検索するための予備処理として用いることも可能である。さらに計算量削減と分散処理を可能とし、更新頻度が高く配信元の数が多いＢｌｏｇ記事を記載したウェブページに対するグルーピングの計算量の問題に対処することができる。
【００４５】
上述の各装置は内部に、コンピュータシステムを有している。そして、上述した処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記処理が行われる。ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。
【００４６】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００４７】
【図１】Ｂｌｏｇ配信システム構成を示すブロック図である。
【図２】Ｂｌｏｇサーバに備えられたウェブページグルーピング装置の機能構成を示すブロック図である。
【図３】ノード構成情報から生成された無向グラフと各ノードのグルーピングの概略を示す図である。
【図４】グルーピング処理部の処理フローを示す第１の図である。
【図５】発見したグループを特殊なノードとした場合の無向グラフを示す図である。
【図６】グルーピング処理部の処理フローを示す第２の図である。
【図７】複数の装置で保持される無向グラフを示す図である。
【図８】グルーピング処理部の処理フローを示す第２の図（その１）である。
【図９】グルーピング処理部の処理フローを示す第２の図（その２）である。
【符号の説明】
【００４８】
１・・・Ｂｌｏｇサーバ（ウェブページグルーピング装置）
２・・・端末
３・・・通信ネットワーク
１１・・・通信処理部
１２・・・制御部
１３・・・データベース
１４・・・ノード構成情報取得部
１５・・・グラフ生成部
１６・・・グルーピング処理部
【図１】
2006072600.tif 000003
【図２】
2006072600.tif 000004
【図３】
2006072600.tif 000005
【図４】
2006072600.tif 000006
【図５】
2006072600.tif 000007
【図６】
2006072600.tif 000008
【図７】
2006072600.tif 000009
【図８】
2006072600.tif 000010
【図９】
2006072600.tif 000011