一貫性を保つことは、ウェブサイトのユーザビリティを向上するためにもっとも重要なものの一つであると言われている田.これは,読者はサイトを渡り歩いた経験則に従って直感的に行動することが多いため,ウェブサイトが一貫性を保つことによって読者の航行を助ける必要があるからである.しかし,データ量の増大に伴い一貫性の維持が難しくなり,ウェブサイトのリンク構造が難解になる傾向が出てきた.この一貫性に従わないリンクや,この様なリンクを持つぺージを不規則構造と呼ぶ.このような不規則構造があるウェブサイトの場合,読者は今どこを読んでいるのか,次にどこへ進めばいいのかがわからない様な状態に簡単に陥いる可能性がある,ウェブサイトには各ページを辿ってみるまで構造がわからないといった特徴があるため,読者が迷うことのないウェブサイトを作成するためには不規則構造のないウェブサイトが必要となる.そこで,本研究では不規則構造の検出を目的とした.

本研究ではウェブサイト作成中,または,作成後に,ウェブのリンク構造を分析し不規則構造を探し出す手法を提案している.前もって構造を決めてしまうのではなく、ウェブサイト作成後である理由としては次の2点があげられる.ウェブサイトに適した構造はウェブサイトの内容によって定まるために,書いているうちに適した構造が変化してしまうことがある.また,複数の著者でウェブサイトを作成する場合,各著者によって適していると思う構造が違うために,共通の構造を限定することができない可能性がある.

Broderら[2]はウェブをグラフとみなして分析を行ったが,対象はインターネット全体であり,ウェブサイトの構造については議論していない.WangとLiu[4]はウェブサイトの構造の出現頻度によって典型的な構造を調査したが,不規則構造の検出は行わなかった.BotafogoとShneiderman[3]は"Lost in Hyperspace"問題解決のためにハイパーテキストの構造分析を行った.しかし,数値的指標を用いて分析を行ったために,求める構造や数値的指標の特定を前もって行わねばならなかった.

本研究では不規則構造発見のために集合論の外延性の公理に着目し,ウェブサイトを集合を用いて表現する方法を採用した.外延性の公理を用いることにより,同じ構造を持つページを同一視することができるため,分析対象となるウェブ構造自身を基準にして分析が行えるようになるからである.この特徴のおかげで,ウェブサイト作成後に基準となる構造や値を必要とせず,不規則構造の発見ができるようになった.

しかし,ウェブは循環構造を含むので,基礎の公理によって循環を明示的に禁止している従来の集合論を採用することができない.それで,本研究では循環を認める反基礎の公理(AFA)[5,6]に基づいた非有基的集合論を採用した.

非有基的集合論では,集合は頂点によって,b∈αの所属関係は弧α→bとみなすことによって,所属関係を有向グラフで表すことが多い.グラフの頂点はAFAに従って矛盾が起こらない範囲でできるだけ同一にされる.この同一視された後の構造のことをAFA構造と呼ぶ.例えば,図1(A)の集合a,b,cは,a={b,c}と記述することができるが,集合論ではb(={})とc(={})は等しくなる.要素のない集合である葉は,0(={})と一致する.図1(B)の集合d,eはそれぞれd={e}={b}=a,e=0=b=cとなり,図1(C)は,AFAの定義によりx=yとなる.図1(D)のzは,図1(C)のx,yに等しくなる.これは最も単純な循環集合であり,Ωと呼ぶ.本研究では,ウェブをAFA構造に変換したものに対して分析を行う.

不規則構造を持つウェブサイトは非有基的集合論で表すと頂点数の多いより複雑なAFA構造になる傾向がある,例えば,図2(A)は不規則構造を持たないウェブサイトであり,図2(B)は典型的な構造に従わないリンク(破線リンク)を持つウェブサイトである.これらのAFA構造はそれぞれ,図2(C),図2(D)であり,不規則なリンクを持つウェブサイトのAFA構造(図2(D))は,不規則構造を持たないウェブサイトのAFA構造(図2(C))より頂点数の多い複雑なものとなる.本研究ではこのAFA構造の性質を基に不規則構造を探し出す手法として,簡約度分析(図3)と高階ランク分析(図4)を提案した.

簡約度分析は,弧検出,弧選択,簡約化の3つの操作からなり(図3),典型的な構造に従わないリンクを不規則構造として検出する.AFA構造から弧を一本抜くことによってAFA構造が単純化される場合,その弧を不規則構造の候補であると定義する.この様にして弧検出は不規則なリンクの候補を探し出す図3(B)のAFA構造の場合,点線で示された4つの不規則構造の弧の候補(図3(C)を見付け出した.そこで数を絞りこみ不規則構造を見つけ出す方法として弧選択を考案した.弧選択では,各不規則構造の候補弧を削除した時に等しくなる頂点に着目した.そこで,弧選択では,他の弧を削除した時に等しくなる頂点を含み,さらに,等しくなった頂点数が最大のものを不規則構造として選び出す.そして,弧選択で選択された不規則構造を削除し,再度同一化を行うことにより,簡約化されたAFA構造を作成する操作を簡約化と呼ぶ.

高階ランク分析(図4)では,各頂点の周りの構造を示す指標である高階ランクを用い,不規則構造を検出する.リンクを辿って,そこから先がない葉と辿るべき弧を持つ頂点は構造上異なると考えられる.また,子として葉を持つ頂点と,葉を子として持たない頂点も構造上異なる.この構造上の違いを表す指標として,頂点から葉までの最短距離を示すランク1を導入する.図4(A)に示したウェブサイトのAFA構造は図4(B)のようになる.頂点の右上の数字は0次ランクを表す.弧を持たない頂点hのランクは0,ランクが0の頂点を持つ頂点aのランクは1,ランクが1の頂点を持つ頂点b,c,d,e,fのランクは2となる.弧を持たない頂点へパスを持たない自己参照型の頂点gのランクは∞となる.この例から,同じランクを持つ頂点の子は,同じランクを持つことがわかる.

ランクは,組み合わせることでさらに頂点を分類することができる,ランク1の頂点は,必ずランク0の頂点を子として持つが,その他にランク1やランク2の頂点を子に持つことができる.ランク1の頂点を子に持つ頂点と,ランク1の頂点を子に持たない頂点を区別するために,高階ランクを導入する.同じn次ランクを持つ頂点の集合を,数学的用語を用いてπ次ランクの同値類と呼ぶ.

本研究では不規則構造を見つけるために,ランクの同値類が分割される過程に着目した.同じ構造を持つ頂点は同じランクを持つが,次数をあげることによって子のランクの影響を受け,要素数が1の単一集合が分離されることがある.単一集合は他に同じ構造を持つ頂点がないことを意味する.よって,本研究ではこの高階ランクの同値類として得られる単一集合の頂点は,不規則構造と関係があると仮定し,この仮定のもとで不規則構造を発見した.図4(C)では,a,c,g,hが不規則な頂点となる.

1子孫に葉を持たない頂点のランクは∞とす

本研究ではこれら2つの分析をそれぞれ実際に使用されているウェブサイトに適用し,それぞれで不規則構造の抽出に成功した.選び出された不規則構造に該当するリンクやウェブページを調べたところ,著者が単なるミスで間違って張ってしまったリンクや,著者の趣味やウェブサイトの内容に影響を受けて作成された異質なリンク構造2などがあった.また,サイドメニューを持つ典型的な構造と異なり,サイドメニュ0を持たないページや,サブカテゴリ0のトップページ,スタイルが確立される前に作成された古い資料なども見つかった.また,二つの分析手法はどちらも不規則構造を検出するが,高階ランク分析の方が簡約度分析に比べて効率がよく,簡約度分析は高階ランク分析で検出できない不規則構造間の関係が検出できたり,構造の概略図を作成できることがわかった.

以上のように,ウェブサイトを非有基的集合論で表現し,不規則構造を発見する方法として,簡約度分析と高階ランク分析を提案し,それぞれの手法を実際のウェブサイトに適用し,不規則構造を発見することに成功した.本研究では対象となるウェブ自身を基準として用いたために,ウェブサイト作成後に,あらゆるウェブサイトの構造に対して不規則構造を発見できるようになった.この結果は従来の構造分析手法では得られないものであり,画期的な成果である.

2例えば,サブサブシーケンスや,階層的構造とシーケンシャル構造の合併版などであった.

図1:集合の標準的なグラフ表示

図2:不規則構造とそのAFA構造への影響

図3:簡約度分析:弧検出,弧選択

図4:高階ランク分析:ウェブ,0次ランク,1次ランク

よいウェブサイトを構築するためには、一貫性を維持することが重要であると指摘されている。リンク構造の一貫性に着目し、一貫性を乱す不規則構造を発見する方法を研究したのが本研究である。これまでのリンク構造の研究が、特定の構造とのずれを発見したり、全体構造に関する指標を発見するものであるのに対して、特定の構造を定めずに、個々の不規則構造を発見する方法を提案していることが、本研究の特徴である。

本研究は、6章からなる。第1章では、ウェブサイトにおいて、一貫性が重要であることを文献により示した上で、リンク構造の一貫性に着目し、その一貫性を乱す不規則構造を検出することを本研究の目的とすることを述べている。第2章では、ウェブのリンク構造を有向グラフで表現したウェブグラフ、集合の所属関係をグラフで表現した所属関係グラフを説明した後で、ウェブグラフを集合の所属関係グラフとみなすことで、集合の外延性公理をウェブグラフの頂点の同値性の判定に適用することを提案している。これは大胆な飛躍である。このように適用することの正しさは、証明できる性質のものではないが、このように適用することに意味のある例が示され、また、これに基づいた分析方法により第5章で有効な結果を得ていることから、一定の妥当性があると認められる。第3章は数学的な説明に充てられている。ウェブグラフには循環構造があるため、ウェブグラフを集合の所属関係グラフと見なすことを一般のウェブグラフに適用可能とするためには、循環構造を許す集合論、つまり集合AがAの要素であるようなことが可能な集合論が必要となる。そのような集合論は非有基的集合論と呼ばれるが、代表的なものとして、4つの定式化が知られている。そのなかから、ウェブグラフをそれぞれの所属関係グラフとみなした時の妥当性の検討により、Aczelの非有基的集合論を採用したことが説明され、Aczelの非有基的集合論を本研究の目的のために十分な範囲で簡略化したものが定義されている。次に、集合のまわりの構造を近似的に表す高階ランクと呼ばれる指標が提案される。高階ランクは近似の極限がAczelの非有基的集合論と一致する指標であり、その提案は評価できる。第4章では、ウェブ構造を分析する具体的な方法として、簡約度分析と高階ランク分析の2つの方法を提案している。簡約度分析は、弧に関する不規則構造を発見する方法であり、高階ランク分析は頂点に関する不規則構造を発見する方法である。これらの分析方法のなかで、第1章で直感的に説明された不規則構造に、厳密な定義を与えている。第5章では、第4章で導入した2つの方法を、HWB、Google、Yahoo、外務省、首相官邸のウェブサイトに適用し、不規則構造の発見に成功している。ここで発見される不規則構造は第5章の意味のものであるが、第1章の意味の不規則構造との対応については、ウェブサイトの更新履歴の分析や、人工的なデータでの検討などを行っており、一定の説得力が認められる。第6章では結論として、構造の特徴や共通性の抽出への応用可能性に言及している。

本研究は、ウェブの構造の分析に集合論を適用するという独創的なアイデアにより、あらかじめ目標とする構造を設定することなく、不規則構造を発見できることを示した。その実現においては、非有基的集合論の適切な選択、高階ランクの数学的定式化と性質の分析、ウェブの性質を考慮に入れた分析方法の開発、ウェブサイトのデータ収集と分析方法の適用、分析結果の評価など、緻密な検証作業が行われており、信頼できる結果が得られている。本研究は、非有基的集合論の、構造の分析への適用の可能性を拓いたものとも云え、その寄与は大きいものと判断される。よって、本審査委員会は本研究が博士(学術)の学位を授与するにふさわしいものと認定する。