人工知能の話題

Web構造マイニング

Web構造マイニング（Web Structure Mining）(注1)の，Webとは，説明するまでもなく，今，あなたが見ているものです．また，マイニングの元の意味は「（鉱山から鉱石を）掘り起こす」ということですが，ここでは本当の鉱山を掘るのではありません．Webを，情報が埋もれている「鉱山」だと思って，情報や知識を見つけ出すことをマイニングと呼んでいます．すなわち，Web構造マイニングとは，「Webの構造から情報や知識を見つけ出す」ことです．

では，Webの構造とはいったい何でしょうか？ここでは，リンクに注目します．リンクとは，みなさんがWebを見ているときに，ページの中をクリックして，別のページに移動しているでしょう．このクリックすると，別のページへ移る仕掛けのことをリンクといいます．

右の図を見てください．一番左に「グルメガイド」というページがあります．このページには「ケーキ」や「寿司」といった項目があります．ここで，ケーキの項目をクリックすると，リンクによって「ケーキ店」のページに移ることができます．このことを図では「グルメガイド」のページから，「ケーキ店」への矢印で書いてあります．同様に「グルメガイド」のどこかをクリックすれば移ることができる他のページ（図の「寿司屋」など）にも矢印を書きます．逆に，どこをクリックしても，一回のクリックでは移ることができないページには矢印を書かないことにします．

リンクをたどって見つかるありとあらゆるページについて，このように矢印で結んでいくと右の図のようなものができます．これは，入り組んだ「クモの巣」のように見えるので，World Wide Web（ワールド・ワイド・ウェブ）「世界中に広がったクモの巣」と呼ばれています．Web構造マイニングとは，このクモの巣を解きほぐして，その構造から情報を取り出す研究です．

Web構造マイニングもいろいろなものがありますが，Webの中の「サイバー社会」についての研究をとりあげます．まず，あるWebページから出ているリンクは，そのページの作者がリンクの先のページに興味があったから作られたと考えます．この考えにもとづき，「どんな話題にみんなは興味があるのか？」とか「ページの作者の人間関係はどうなっているのか？」ということを調べた研究を紹介します．

まず，Web全体のおおまかな様子を捉えることに 挑戦したA.Broderらの研究(注2)を紹介します． Broderらは，1999年10月に2億以上のページを収集し，そのリンクを調べて，Web全体には下の図のようなチョウネクタイ型の構造を見いだしました．

図のSCC(注3)はWebの中で中心的な役割を果たす部分です．この部分に含まれるページは，うまくリンクをたどっていくと，元のページに帰ってくることができます．ポータルサイトなど，Webを利用する誰もが興味をもつようなサイトが集まっています．

INは，この中のページからリンクをたどってSCCにたどり着けるが，SCCからはたどり着けないページの集まりです．比較的新しく，まだあまり知られていないページが多く含まれています．OUTは，INとは逆で，SCCからはたどり着けるが，OUTの中のページからSCCへはたどり着けないページの集まりです．この中には，競合企業にはリンクをしない企業などのページが多く含まれます．その他に，SCCにたどり着くことも，SCCからたどり着くこともできないが，INやOUTの中のページとは繋がっているというTENDRIL(巻きひげ)やTUBE(管)といった構造もあります．

このチョウネクタイ型の部分に含まれるページは，リンクで繋がっている一番大きなかたまりで，一番全体の91%ほどを占めています．また，リンクをたどってたどり着ける場合，平均して16回ほどリンクをたどればたどり着けてしまいます．2億を超えるページがあるにもかかわらず，16回ほどでたどり着けてしまう(注4)というのは，思ったより少ないのではないでしょうか？

A.Broderらの研究はWeb全体の様子について調べました．それとは逆に，同じ事柄に興味をもつ小さなコミュニティについて調べた，R.Kumarらの研究(注5)を紹介しましょう．

R.Kumarらは，Webのコミュニティには右の図のような構造がその中核にあると考えました．「センター」はそのコミュニティの興味の対象を表すページであり，「ファン」は同じ興味をもつコミュニティの中心的メンバーが運営するページです．例えば，野球チーム「ブレインズ」に興味があるコミュニティの場合．興味の対象となるセンターにはブレインズの公式ページや球場のページが含まれるでしょう．また，中心的なブレインズファンのページがファンに含まれます．そして，ファンに含まれるどのページからも，センターのどのページへもリンクがあるとき(注6)，これらのファンやセンターのページはWebコミュニティの中核となると，Kumarらは考えました(注7)． 1997年に収集したデータを調査し，このようなコミュニティが10数万あると述べています．

Web構造マイニングは，このようなサイバー社会の調査の他に，検索サイトの結果の表示順序を決めるとか，効率よくWebページを巡回する手法などの研究があります．

注1：Web構造マイニングは，データマイニングの一分野であるWebマイニングの，そのまた一部と位置づけられています．Webマイニングには，他にも，Webに書かれている内容から情報を抽出するWeb内容マイニング（Web Content Mining）や，Webを閲覧した記録を扱うWeb利用マイニング（Web Usage Mining）があります．

注2：A.Broder, R.Kumar, F.Maghoul, P.Raghavan, S.Rajagopalan, R.Stata, A.Tomkins and J.Wiener "Graph Structure in The Web" The 9th International World Wiede Web Conference (2000)

注3：SCCとは，グラフ理論の用語で Strongly Connected Component （強連結成分）のことです．

注4：厳密にいうと，二つのページをランダムに選ぶと75%は繋がっていませんが，残り25%の繋がっているページについては平均して16回リンクをたどるとたどりつけます．

注5：R.Kumar, P.Raghavan, S.Rajagopalan and A.Tomkins "Trawling the Web for Emerging Cyber-Communities" The 8th International World Wide Web Conference (1999)

注6：グラフ理論の用語で完全2部グラフ(Complete bipartite graph)といいます．

注7：このような構造をもつWebページを探したあと，いくつかのページを実際に調査すると，その多くは確かに同じ話題についてのコミュニティだったそうです．