(57)【要約】【課題】グラフ構造のデータを、その構造情報を失うことなく適切に間引いて表示する。【解決手段】データ取得部3は、各ノードにつき接続先ノードを対応づけた情報としてメタデータを取得する。構造分析部4は、メタデータを解析して、隣接関係にあるノードの間にエッジを設けたグラフを構築すると共に、構築されたグラフを分析して部分グラフに分類し、分類された部分グラフを単位としてノードを間引いてグラフを修正する。表示制御部5は、修正されたグラフにおけるノードを表示する。【選択図】図１
2015032298.tif 000002
【特許請求の範囲】
【請求項１】
各ノードにつき接続先ノードを対応づけた情報としてメタデータを取得するデータ取得部と、
前記メタデータを解析して、接続関係にあるノードの間にエッジを設けたグラフを構築すると共に、当該構築されたグラフを分析して部分グラフに分類し、当該分類された部分グラフを単位としてノードを間引いてグラフを修正する構造分析部と、
前記生成されたグラフにおけるノードを表示するに際して、前記修正されたグラフにおけるノードを表示する表示制御部と、を備えることを特徴とする表示制御装置。
【請求項２】
前記構造分析部が、前記構築されたグラフを連結成分に分割することにより部分グラフに分類することを特徴とする請求項１に記載の表示制御装置。
【請求項３】
前記構造分析部が、二重連結成分分解によって前記連結成分へと分割することを特徴とする請求項２に記載の表示制御装置。
【請求項４】
前記構造分析部が、強連結成分分解によって前記連結成分へと分割することを特徴とする請求項２に記載の表示制御装置。
【請求項５】
前記構造分析部は、前記分類された部分グラフを構成するノードの数に基づき、当該部分グラフからノードを間引くか否かを決定することを特徴とする請求項１ないし４のいずれかに記載の表示制御装置。
【請求項６】
前記メタデータにおいては、各ノードの座標情報が対応づけられており、
前記構造分析部は、前記分類された部分グラフを単位として、且つ、当該部分グラフに属するノードの座標情報から定まる各座標領域におけるノードの密度に基づいて、ノードを間引いてグラフを修正し、
前記表示制御部は、前記修正されたグラフにおけるノードを、対応づけられた座標情報に従って配置して表示することを特徴とする請求項１ないし５のいずれかに記載の表示制御装置。
【請求項７】
前記メタデータにおいては、各ノードの種類を特定するレイヤの情報が対応づけられており、
前記構造分析部は、前記分割された部分グラフを単位として、且つ、前記対応づけられたレイヤを単位として、ノードを間引いてグラフを修正することを特徴とする請求項１ないし６のいずれかに記載の表示制御装置。
【請求項８】
コンピュータを請求項１ないし７のいずれかに記載の表示制御装置として機能させることを特徴とする表示制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、１つ以上のレイヤから構成され、グラフ構造を取るグラフィックデータを重畳することによって実現されるコンテンツにおいて、それらコンテンツを見やすく表示するための仕組みを提供する表示制御装置及びプログラムに関する。
【背景技術】
【０００２】
特許文献1では、背景地図や複数の地理関連情報をそれぞれレイヤとして保持し、それらレイヤを表すドキュメント(SVG：Scalable Vector Graphics)をハイパーリンクで接続することにより、各レイヤを重畳する仕組みを提案している。
【０００３】
一般のHTTPサーバ上に置いたドキュメントのURIを、他のドキュメントからハイパーリンクで参照するだけで、様々なレイヤが重畳できる。HTTPサーバであるため、サーバの構築が容易であり、重畳するデータを変更する際にも、ドキュメント中で参照しているURIを変更するだけで可能である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2006-293146号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら，上記特許文献1に記載の従来技術では、様々なレイヤをハイパーリンクで重畳して表示できるが、表示画像の見やすさについては考慮されていなかった。そのため、例えば、地図において縮小表示を行った際に、背景地図に大量の点データが表示される場合があるが、各点データが重なって表示されるため、データの理解が困難であった。
【０００６】
図１１は、当該従来技術において、縮小表示により地図上に大量の点データが表示され、ほぼ地図を埋め尽くしてしまっている例を示す図である。このような状態で表示されてしまうと、データの概形を把握することは不可能であり、上述のようにデータの理解が困難となる。
【０００７】
ここで、単純にランダムサンプリングでデータを間引く方法も考えられるが、その場合は、データの構造に関係なく、間引く対象が決定されるため、意味のあるデータ概形が失われてしまう可能性があった。縮小表示を行った場合には、そのデータ群が持つ適切な概形（俯瞰情報）が得られることが望ましい。
【０００８】
本発明の目的は、上記の従来技術の課題を解決し、大量データを表示する場合であっても、データのメタデータに基づきその概形をできるだけ見やすくし、且つこの際、データの特徴が失われないようにして表示する、表示制御装置及びプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明は、表示制御装置であって、各ノードにつき接続先ノードを対応づけた情報としてメタデータを取得するデータ取得部と、前記メタデータを解析して、接続関係にあるノードの間にエッジを設けたグラフを構築すると共に、当該構築されたグラフを分析して部分グラフに分類し、当該分類された部分グラフを単位としてノードを間引いてグラフを修正する構造分析部と、前記生成されたグラフにおけるノードを表示するに際して、前記修正されたグラフにおけるノードを表示する表示制御部と、を備えることを特徴とする。
【００１０】
また、本発明は、表示制御プログラムであって、コンピュータを上記表示制御装置として機能させることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、データをそのグラフ構造に基づいて適切に間引いて表示するので、データが大量に存在する場合であっても、データの特徴を失わずに見やすい形に修正して表示することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】一実施形態に係る表示制御装置の機能ブロック図である。
【図２】取得されるデータの概念的な例を示す図である。
【図３】構造分析部の機能ブロック図である。
【図４】構造分析部の各部によって取得データが処理されていく状態を、状態(1)〜(4)として模式的に示す図である。
【図５】グラフ修正部により間引かれ修正された例を示す図である。
【図６】2つ以上のレイヤを含んでグラフが構築された場合の間引きの例を示す図である。
【図７】グラフの二重連結成分分解の例を示す図である。
【図８】グラフの二重連結成分分解の例を示す図である。
【図９】グラフの二重連結成分分解の例を示す図である。
【図１０】グラフの強連結成分分解の例を示す図である。
【図１１】従来技術において、縮小表示により地図上に大量の点データが表示され、ほぼ地図を埋め尽くしてしまっている例を示す図である。
【発明を実施するための形態】
【００１３】
図１は、一実施形態に係る表示制御装置の機能ブロック図である。表示制御装置1は、アプリ取得部2、データ取得部3、構造分析部4及び表示制御部5を備える。なお、図１では配信サーバ10が表示制御装置1に並んで描かれているが、これは表示制御装置1にて必要なプログラムその他の情報を取得するための外部構成である。
【００１４】
表示制御装置1は、一実施形態においては、ブラウザのようなクライアントソフトを実行する端末から、配信サーバ10等のサーバ上にあるWebアプリをダウンロードして、当該端末においてそのWebアプリが実行されることによって、実現可能である。
【００１５】
以下、表示制御装置1の各部を説明する。
【００１６】
アプリ取得部2は、上記一実施形態を実現すべく、配信サーバ10より、当該サーバ上にあるWebアプリを取得する。当該Webアプリは、何らかの用途のためにグラフ構造を有するデータをユーザに閲覧させる機能を少なくとも有するものであり、当該Webアプリが実行されることによって、以下説明する後段のデータ取得部3以降が実現される。従って、データ取得部3以降については、当該Webアプリの種類（例えば、地図上に店舗を表示するものや、ソーシャルグラフを表示するものなど）に応じてそれぞれ実現可能である。
【００１７】
データ取得部3は、取得したWebアプリの処理に基づき、配信サーバ10よりデータ（当該Webアプリが扱う所定形式のデータ）を取得する。なお、当該データ取得については、必ずしもWebアプリを配信しているのと同一の配信サーバ10から取得される必要はなく、Webアプリの処理に応じて、その他のサーバから取得されてもよい。
【００１８】
図２は、当該取得されるデータの概念的な例である。取得データは、レイヤL1のデータM1及びレイヤL2のデータM2といったように、レイヤの区別と共に取得される。レイヤには、レストランのレイヤL1やガソリンスタンドのレイヤL2といったように、セマンティクス（意味合い）が割り当てられており、レイヤのセマンティクスは、当該レイヤのノードが何を表しているのかを特定するものである。すなわち、例えばレイヤL1の各ノードは、レストランを表している。
【００１９】
当該レイヤ毎のデータは、図２に示すように、座標情報と、メタデータとを含んで構成される。メタデータは、当該レイヤのノードのIDと、当該ノードの接続先ノードのIDと、を含んで構成される。なお、接続先ノードについては、必ずしも当該レイヤと同一である必要はない。
【００２０】
例えば、図２ではレイヤL1のデータM1内にはノードIDが1,2,3で与えられる3つのノードが存在するが、ノード3の隣接ノード1,2,4のうち隣接ノード4については、レイヤL1ではなくレイヤL2である。同様に、逆にレイヤL2のノード4の隣接ノード3,5,6のうち隣接ノード3については、レイヤL2ではなくレイヤL1である。
【００２１】
ここで、ノードの隣接関係は、周知のグラフ理論における用語を用いると、ノード間にエッジが存在すると言い換えることができる。エッジの存在は、当該取得データにて予め定義されている所定の関係が、ノード間に存在することを意味している。
【００２２】
例えば、レイヤL1の各ノードはレストランの店舗である場合に、その間のエッジが、近接している同系列のレストラン同士ということを意味するよう、取得データが予め定義されている。また例えば、何らかのレイヤにおける各ノードが建物を表す場合に、その間のエッジは、建物間に配置された水道管を意味するよう、取得データが定義されていてもよい。
【００２３】
また、座標情報とは、メタデータで与えられる当該レイヤの各ノードの座標情報として与えられるものである。図２では例えば、レイヤL1のノード1の座標情報は、(x, y)=(0, 0)である。ノードがレイヤL1におけるレストランやレイヤL2におけるガソリンスタンドであれば、座標情報はこれら建物の所在地を特定するものとして、取得データにおいて予め定義され座標値が与えられている。
【００２４】
なお、図２ではデータM1, M2と並べてグラフG10が描かれているが、当該取得データを次に説明する構造分析部4において解析することにより、各ノードの接続関係を反映して構築されるグラフの例が、当該グラフG10である。取得データの段階では、メタデータとして、個別のノードとその接続先ノードの情報がレイヤ毎に与えられているのみで、グラフは構築されていない。一般に、Webアプリの処理に応じて、取得データにおけるレイヤの種類も異なるため、構築されるグラフも異なることとなる。
【００２５】
構造分析部4は、データ取得部3の取得データに付属するメタデータに基づき、データに構造関係を持たせてグラフを構築すると共に、当該グラフの構造を保った形でノードを間引く修正を実施してから、表示制御部5に当該間引かれたグラフ構造データを渡す。
【００２６】
表示制御部5は、当該間引かれ修正されたグラフにおけるノードを表示する。具体的な表示の態様は、Webアプリの実装に従い、種々のものが可能である。例えば、当該表示の際、ノードに座標情報が与えられていれば、当該座標情報に従う位置に配置して表示してもよい。この際、所定の地図上に表示してもよい。ノード間のエッジは表示してもよいし表示しなくてもよい。ノードの表示は、そのレイヤの種類に応じて所定のアイコンなどを用いて表示してもよいし、予め付随している情報（ノードが店舗であれば店舗名など）を併せて表示してもよい。エッジを表示する場合も同様に、単純に線として表示する他、装飾等を伴う所定の表示形式で表示してよい。
【００２７】
なお、表示制御部5にて座標情報を利用しないで表示する場合には、修正されたグラフの提示手法自体については、エッジの表示有無に関わらず、ソーシャルグラフ等の表示にて利用されている周知手法を利用してよい。当該周知手法はWebアプリ内に実装しておけばよい。
【００２８】
以下、構造分析部4の詳細と、対応する表示制御部5の詳細とを説明する。
【００２９】
図３は、構造分析部4の機能ブロック図である。構造分析部4は、グラフ構築部41、グラフ分析部42及びグラフ修正部43を含む。図４は、構造分析部4の当該各部によって取得データが処理されていく状態を、状態(1)〜(4)として模式的に示す図である。以下、図４を適宜参照しつつ、当該各部を説明する。
【００３０】
グラフ構築部41は、取得データにおけるメタデータを解析して、各ノードにつきその隣接ノードとの間にエッジを設けることで、グラフを生成する。図４では、各ノードが○で描かれており、メタデータ内の各ノードが個別に存在する状態(1)からエッジが設けられグラフが構築された状態(2)へと移行させるのが、グラフ構築部41である。
【００３１】
ここで、取得データが図２で説明したように複数のレイヤから構成されている場合には、レイヤ毎に区別してグラフを構築してもよいし、異なるレイヤ間でもノード間に接続関係があれば、異なるレイヤのノード同士の間にエッジを設けてグラフを構築してもよい。前述の図２のグラフG10は、異なるレイヤL1, L2のノード3, 4の間にエッジが設けられて構築されたグラフの例である。
【００３２】
また、構築されるグラフの種類は、無向グラフ又は有向グラフのいずれでもよい。無向グラフは、エッジが向きを持たない（エッジに向きの情報がない）グラフであり、有向グラフは、エッジが向きを有する（エッジに向きの情報がある）グラフである。なお、無向グラフは、向きを持たないエッジを双方向に往来可能な向きを持つエッジとして捉えれば、有向グラフとしてもデータ構造を表現できる。
【００３３】
なお、有向グラフを構築する場合は、エッジに向きの情報を含める必要があるが、当該向きの情報は、取得データにおけるノード間の隣接関係における追加情報として、予め与えておけばよい。あるいは、追加情報として与える代わりに、メタデータ自体を、向きを特定可能なように定義しておいてもよい。例えば、メタデータにおいてノードAに接続先ノードA1, A2, ...が与えられている場合は、当該ノードAから接続先ノードA1, A2, ...に向かう向きのエッジA→A1, A→A2, ...が存在することを意味しているものとして、メタデータを定義しておき、当該定義されたメタデータから向きの情報を取得してもよい。この場合、メタデータのノード間において両方向の情報（例えばノードA及びA1の間に対してA→A1及びA1→A）がある場合に、当該ノード間は双方向エッジとなる。
【００３４】
グラフ分析部42は、グラフ構築部41により当該構築されたグラフを対象として、グラフ理論的な分析を行い、その接続構造を反映した部分グラフへと分類する。構築されたグラフの各ノードは、当該分類された部分グラフのいずれかに必ず属することとなる。図４の例では、状態(2)のグラフを分類して、状態(3)のようにすることを、グラフ分析部42が実行する。状態(3)では、グラフが3つの部分グラフG1, G2, G3に分類されている。
【００３５】
部分グラフへの分類は、構築されたグラフの連結成分への分割として実施することができる。当該分割する具体的な手法として例えば、無向グラフについては、二重連結成分分解によって連結成分への分割が可能であり、有向グラフについては、強連結成分分解によって連結成分への分解が可能である。なお、無向グラフにおける全エッジを双方向エッジとみなすことで、無向グラフを有向グラフとして解釈するようにすれば、強連結成分分解は無向グラフについても適用可能である。これらの詳細については後述する。
【００３６】
グラフ修正部43は、グラフ分析部42により部分グラフに分類されたグラフより、当該部分グラフを単位に、ノードの間引きを実施することで、グラフを修正する。当該修正されたグラフは、表示制御部5へと渡される。図４の例では、状態(3)の部分グラフの中から、状態(4)に斜線で示す部分グラフG3の1つのノードが間引き対象として決定されている。
【００３７】
当該間引きを実施するに際して、次の2つのステップ(a), (b)に従う。ステップ(a)では、どの部分グラフを間引きの対象とするかを決定する。続くステップ(b)では、当該間引き対象とされた部分グラフの中で実際に間引くノードを決定し、間引きを実施する。
【００３８】
ステップ(a)の間引き対象部分グラフの決定は、部分グラフに属するノードの数が所定閾値以上の部分グラフを対象としてもよいし、あるいは、部分グラフに属するノードの数が最大となる部分グラフを対象としてもよい。すなわち、部分グラフに属するノード数によって、当該部分グラフ内のノードを間引き対象とするか否かを決定してもよい。
【００３９】
あるいは、ステップ(a)では、上記ノード数の閾値判定又は最大値による決定に代えて、ノード密度の閾値判定又は最大値によって決定してもよい。各部分グラフのノード密度は、属するノードの座標情報を参照して、部分グラフに属するノード個数を部分グラフの占める領域の面積で割って算出すればよい。部分グラフの占める領域は、当該部分グラフに属する全ノードを囲む最小多角形、あるいは最小矩形などとして定めればよい。
【００４０】
ステップ(b)の間引き対象ノードの決定は、当該部分グラフ内からランダムサンプリングで決定すればよい。間引きの個数は、当該部分グラフの間引き前のノード数に対する所定割合として決定してもよいし、固定値としてもよい。
【００４１】
あるいは、ステップ(b)では、座標情報を利用して、部分グラフ内を座標上における碁盤の目状の単位領域（座標領域）に区分けし、ステップ(a)で説明したのと同様に算出されるノード密度（単位領域内のノード数に比例）が高い単位領域から、優先的に間引くようにしてもよい。例えば、ランダムサンプリングの際に間引かれる対象として決定される確率を、各ノードにつき、属する単位領域におけるノード密度に比例させて設定するようにしてもよい。なお、単位領域への区分けは碁盤の目状以外の形状でなされてもよい。
【００４２】
なお、以上のステップ(a)及び(b)については、その全体を繰り返し実施して、部分グラフ単位の間引きを逐次的に実施するようにしてもよい。繰り返し処理の終了判定には、繰り返し回数が閾値に達したこと、または、間引かれたノードの総数が当初のデータにおけるノード総数の所定割合に達したこと、を用いればよい。
【００４３】
図５は、当該グラフ修正部43により間引かれ修正された例である。図５では、[1]に間引き前のグラフとして、部分グラフG11, G12, G13に分類されノード1〜11からなるグラフが示され、[2]に間引きを実施して部分グラフG13のノード8が間引かれ修正されたグラフが示されている。[2]では、間引いたノード8と隣接関係にあったノード6,10間に新たなエッジが設けられている。表示制御部5でエッジを表示する場合は、このように新たに設けたエッジを用いればよい。
【００４４】
なお、表示制御部5でエッジを表示する場合、当該図５の例で部分グラフG13のノード6が間引かれると、ノード5,8間とノード5,7間に新たなエッジを設けることとなり、部分グラフG12,G13が一体化して部分グラフの構造が大きく変化（部分グラフが各々個別に変化するだけではなく、部分グラフ同士の関係も変化）してしまう。従って、表示制御部5でエッジを表示する場合には、グラフ修正部43による間引き対象のノードは、部分グラフの構造を大きくは変化させないものから選ぶようにしてよい。
【００４５】
当該部分グラフの構造を大きくは変化させないノードとしては、例えば、部分グラフG11内のノード1,2,3や部分グラフG13内のノード7,8,9,10,11といったように、自身の隣接ノードが2つのみであり、且つ当該2つの隣接ノードが共に自身と同一の部分グラフに属するようなノードを用いればよい。
【００４６】
また、グラフ構築部41で2つ以上のレイヤを含んで1つのグラフを構築した場合、グラフ修正部43では、第一手法として、レイヤの区別を特に考慮せずに間引きを実施してもよいし、第二手法として、部分グラフ内で、区別されたレイヤごとに間引きを実施してもよい。すなわち、第二手法では、部分グラフ内に複数のレイヤがあれば、当該レイヤ毎に部分グラフが構成されているものとみなしたうえで、第一手法と同様の間引きを実施してもよい。
【００４７】
図６は、2つ以上のレイヤを含んでグラフが構築された場合の間引きの例を示す図である。図６の例では2つのレイヤL1及びL2のそれぞれのノード1〜11及びノード12〜16を併せて、1つのグラフが構築された後、部分グラフG21, G22及びG23に分類されている。部分グラフG21, G22はレイヤL1のみで構成されるが、部分グラフG23はレイヤL1及びL2で構成されている。
【００４８】
図６のような場合に、上記第二手法では、2つのレイヤL1, L2で構成された部分グラフG23を、それぞれのレイヤに対応する2つの部分グラフP231及びP232であるとみなして、間引きを実施し、例えば、(1)に示すように、「みなし部分グラフ」P231からノード13が間引かれてみなし部分グラフP2320へと修正される。
【００４９】
当該第二手法によれば、部分グラフG23のように複数のレイヤで構成された部分グラフにおいて、いずれかのレイヤのノードが間引きによって完全に消失し、表示制御部5で表示する際に特徴的な情報が失われて表示されてしまうことを防止することができる。
【００５０】
なお、表示制御部5の表示を見るユーザに対するインターフェースとしての構成として、次を採用してもよい。すなわち、構造分析部4において利用されるパラメータ、例えば、上記ステップ(a), (b)を繰り返す回数や、各回におけるノードの間引き割合などを、周知のスライドバーなどの形式でユーザに入力可能とさせ、表示制御部5では、当該ユーザに入力されたパラメータにおいて構造分析部4が修正したグラフ構成のデータを表示する。ユーザはパラメータを調整しながら、見やすい状況を自身で作ることができるようになる。
【００５１】
以下、グラフ分析部42における（Ａ）二重連結成分分解及び（Ｂ）強連結成分分解につきそれぞれ説明する。
【００５２】
（Ａ）二重連結成分分解について
グラフが2連結（二重連結）であるということは、任意の2ノード以外のノード（及びそれに接続されるエッジ）を削除した際に、あるノードから別のノードへたどり着く道が必ず存在することである。2連結で極大な部分グラフとは、2連結である部分グラフが2連結である小さな部分グラフを包含するような場合に、最もノード数が多くなるような部分グラフのことを指す。ここでは、グラフからあるエッジを取り除くとグラフが非連結となるようなエッジ（ブリッジ、橋）に基づく2連結成分分解について述べる。
【００５３】
図７から図９に、グラフの2連結成分分解（二重連結成分分解）を例で示す。ここでは図７の(1)に示すノードa〜gで構成されるグラフを例とする。2連結成分分解は、まず、手順[1]として、任意に始点となるノードを選択し、その始点ノードから深さ優先探索を行う。深さ優先探索において、探索順に、各ノードに対して、オーダーを割り当てる。グラフに存在するが、深さ優先で探索されなかったエッジについては、バックエッジ（後退辺）として扱う。始点ノードをaとした場合のここまでの処理が、図７の(3)であり、バックエッジが点線で示されている。
【００５４】
次に手順[2]として、グラフ中からブリッジを検出するため、以下の操作を行う（図８を参照）。各ノードに対して、ローリンクという値を求める。[2a]深さ優先探索で、ルートからリーフの向きへ進む。または、[2b]バックエッジを1つ以下辿って、リーフからルートの向きへ進む。[2a]、[2b]の方法でたどり着けるノードのオーダーの最小値が、ローリンクの値となる。図８では、当該逐次的に計算されるローリンクの値が[1]などとして示されており、(1)の初期状態から(2)以降の逐次計算を経て、最終的に求まる一連のローリンクの値が(5)に示されている。
【００５５】
さらに手順[3]として、あるノードNcのローリンクの値と、そのノードの親Npのノードのオーダーの値とを比較し、親のノードのオーダーの値の方が小さければ、ノードNcとNpの間のエッジがブリッジとなる。図８の(5)より、(6)に太線で示すノードd-e間がブリッジとなる。そして、ブリッジを削除した際に、たどれる範囲が、2連結成分となる。すなわち、図９の(1)からd-e間のブリッジを削除した(2)に示す範囲D10(ノードa〜cで構成)及び範囲D20(ノードe〜fで構成)が、それぞれ2連結成分となる。
【００５６】
なお、当該削除されるブリッジは、2連結成分を特定するために削除される。表示制御部5でエッジを表示する場合は、当該エッジが削除されたブリッジに該当していても、削除はせずに表示する。
【００５７】
（Ｂ）強連結成分分解について
グラフが強連結であるということは、グラフ中の任意の2ノードを選択した際に、あるノードから別のノードへたどり着く道が必ず存在することである。強連結で極大な部分グラフとは、強連結である部分グラフが強連結である小さな部分グラフを包含するような場合に、最もノード数が多くなるような部分グラフのことを指す。
【００５８】
図１０に、グラフの強連結成分分解を各段階(1)〜(3)に分けて例で示す。当該各段階は以下の通りである。
【００５９】
(1)まず、任意に始点となるノードを選択し、その始点ノードから深さ優先探索を行う。深さ優先探索において、葉ノードまでたどり着いた後に葉ノードから順次親ノードに戻る際に、当該ノードの全ての子ノードが既に探索済みであれば、もしくは子ノードが存在しなければ、当該ノードに通し番号（ポストオーダー、順番）を割り当て、当該ノードの親ノードに戻り、深さ優先探索を進める。これにより、全てのノードに対して、ポストオーダーが割り当てられる。
【００６０】
(1)ではポストオーダー割り当て前の状態のノードa〜lに対して、ノードaを始点としてポストオーダー1〜8が割り当てられ、次に割り当てられていないeから探索してeにポストオーダ9が割り当てられ、最後にまだ割り当てられていないiから探索して10〜12が割り当てられている。
【００６１】
(2)次に、グラフのエッジの向きを反対にした逆グラフを作成する。
【００６２】
(3)この逆グラフにおいて、まだ探索されていない（強連結成分に含まれていない）ノードのうち、最もオーダーが大きいノードを始点として、そのノードから深さ優先探索を行う。深さ優先探索でたどることができたノードが1つの強連結成分であり、これを全ノードが強連結成分に含まれるまで繰り返す。最終的に得られた強連結成分の集合が，強連結である極大な部分グラフである。当該部分グラフの例が(3)においてD1〜D6として示されている。
【００６３】
以上、本発明によれば、ユーザメリットとして、大量のデータがある際に、意味を持つデータのみに絞り込んで表示できるため、データの概形をよりつかみやすくなる。この際、グラフ構造を考慮しない単純なランダムサンプリングによりデータを間引く場合と比べて、特定の箇所に集まったデータがすべて失われてしまうということを避けることができる。
【００６４】
なお、本発明は、コンピュータに読み込まれ、当該コンピュータを図１（及び図３）の表示制御装置1として機能させる、あるいは当該コンピュータに図１（及び図３）の各部に対応する手順を実行させる、表示制御プログラムとして提供されてもよい。この際、表示機能そのものについてはコンピュータの外部機器として提供されるモニタなどを介して実現され、コンピュータは表示の制御のみを担うようにしてもよい。
【符号の説明】
【００６５】
1…表示制御装置、2…アプリ取得部、3…データ取得部、4…構造分析部、5…表示制御部、10…配信サーバ、41…グラフ構築部、42…グラフ分析部、43…グラフ修正部
【図１】
2015032298.tif 000003
【図２】
2015032298.tif 000004
【図３】
2015032298.tif 000005
【図４】
2015032298.tif 000006
【図５】
2015032298.tif 000007
【図６】
2015032298.tif 000008
【図７】
2015032298.tif 000009
【図８】
2015032298.tif 000010
【図９】
2015032298.tif 000011
【図１０】
2015032298.tif 000012
【図１１】
2015032298.tif 000013