複雑ネットワークからの情報抽出

この分野のキーワード

複雑ネットワーク, マイニング技術, WWW, 自然言語, 検索手法, ウェブ技術, 集合知

複雑ネットワーク

現実世界のもつネットワークは，その性質としてスモールワールド構造やスケールフリー性，クラスタ性などを持つことが知られています． このような性質を持つネットワークは総称して複雑ネットワークと呼ばれています．

複雑ネットワークは，現実世界の多くのネットワーク構造に見られます． 近年になって，WWWや人間関係，神経細胞網など様々な現実社会のネットワークにこのような性質が見られることが分かってきており，盛んに研究が行なわれています．

スモールワールド

複雑ネットワーク研究の源流は社会学にあります．
1960年代，社会学者のS.ミルグラムはある地域の無作為に選ばれた住人に対して，地域的に離れたある特定の人物へ手紙を送付する実験を行ないました． この実験は，送付先の人物を知っていれば直接送り，知らなければその人物を知っていそうな自分の知人に送付し，受け取った人も同様に繰り返すというものでした． この結果，送付先の人物まで届いた手紙の仲介人数は平均約６人という少ない仲介数となりました．
このことは，意外と世界は狭いという意味からスモールワールド，６人を経由するということから劇作家J.グエアにより名付けられた六次の隔たりとして知られています．

SNS（ソーシャルネットワークサービス）は，このことを利用したサービスとも言え，研究対象としてネットワークの解析も行なわれています．

数理モデル

近年になって複雑ネットワーク研究が始まりましたが，そのきっかけとなったのが数理モデルの登場でした．
当時，博士課程の大学院生だったD.ワッツはホタルの点滅などの自然界に見られる同調現象から，スモールワールドの数学モデルを考案しました．

このスモールワールドモデルは規則正しいネットワークとランダムなネットワークの中間に位置しています． 規則正しいネットワークのリンクをランダムにほんの数％張り替えるだけで，効率の良いネットワークが生成されます．

このモデルは映画俳優の共演関係のネットワークやインターネット，食物連鎖など多くのネットワークが同様の性質を有することが判明したことによって，複雑ネットワークとして注目されることになりました．

情報抽出

大沢研究室では，現実世界の多くのネットワークが複雑ネットワークの特徴を有する点に注目し，複雑ネットワークからの情報抽出技術の研究を行っています．
特に，WWWネットワークは大規模でしかも日々変化しており，かつ手軽にアクセスできるということから重要な研究対象の一つです．
また，自然言語の文法構造は複雑ネットワークである事が知られています． これを踏まえ，複数言語による概念情報のネットワークからの情報抽出にも取り組んでいます．

ウェブマイニング

WWWからの情報抽出では，ハイパーリンク構造の解析を主に行ないます． 一般に，ウェブ検索などの情報抽出は，文書情報を解析することで得られていると考えられているでしょう． しかし，文書の中身を解析せずとも情報抽出を行なう事は可能で，様々な手法が存在します．

例えば，HITSアルゴリズムは，特徴的な２種類のウェブページを抽出します． ２種類のページとは，ハブとオーソリティです． ハブは自身のページ内に多くのリンクを含むページで，他の情報へのアクセスを提供している点で有用といえます． また，オーソリティは多くのページからリンクされているようなページのことで，多くのページから参照されている点で有用だろうと推測できます． このような有用な２種類のページで結合されたネットワークを抽出するアルゴリズムがHITSアルゴリズムです．

また，初期のウェブページのランキングに使用されていたPageRankアルゴリズムは，各ページ内にあるリンク先のすべてのページに，自分のページのスコアを分配するということを再帰的に繰り返す事で実現しています． これを繰り返すと，最終的にはページに付加されるスコアは他のページからの評価ということになります． このとき，他のページからの評価は，その原理から相手ページが有名であればあるほど高い評価が得られることになります．
すなわち，ありふれたページから多くリンクされるよりも，オーソリティからリンクされているページの方が評価が高くなります．

これらの例からも分かる通り，情報の有用性や関連情報の抽出は，文書の中身を吟味しなくても評価する事が可能なのです．

研究紹介

弱い紐帯の概念を利用したWWW上からの情報抽出手法の提案

社会学の概念に「弱い紐帯の強み」というものがあります． これは有益な情報を提供するのは，友人や親族など強い繋がりの人よりも，むしろ友人の友人といった関係の薄い人の方だというものです．

人間社会は複雑ネットワークであり，WWWもまた複雑ネットワークです． では，WWWにも弱い紐帯というものが存在するはずです． そして，弱い紐帯が分かれば有益な情報を得やすくなるのではないでしょうか．

そこで，本研究では上図のような構造を弱い紐帯として定義し，WWWからの情報抽出を行ないました．

結果として，従来の検索エンジンでは上位にランクインされないにも関わらず，有用性を認められるような関連ページを抽出することが確認されました．

現在は実験段階ですが，今後はより高速なアルゴリズムを考案し，リアルタイムでブラウジングが可能なシステムの実装を目指しています．

Wikipediaからの構造情報抽出

Wikipediaは多くのユーザによって執筆，編集された集合知によるウェブ百科事典です． Wikipediaの特徴は不特定多数の執筆者が存在することで，その執筆に明確な基準が存在しません． ですから，大変有用ではありますが，利用する際に不便さを感じる事もあります．

その解消のため，Wikipediaを対象としたナビゲーションシステムの開発を行なっています． ナビゲーション情報の生成にはウェブコミュニティと呼ばれる，ページの固まりを抽出することで実現します．

図に示す例は，「ガソリン」というページに対して関連性の深いページのリストを生成した例です． このような，ナビゲーションをブラウジング時に付加することで，より効率的なページ閲覧ができるようになります．

入門書

この分野に関係のある入門的な書籍の中で，本学ライブラリに所蔵されているものをリストアップしてみました．興味のある方は是非ご一読を．