Web コミュニティにおける構造モデル A Structure Model for Web

知 能 と 複 雑 系 124−6
（２００１． ５．１７）
Web コミュニティにおける構造モデル
村田剛志
国立情報学研究所
〒101-8430
東京都千代田区一ツ橋 2-1-2
[email protected]
あらまし：特定トピックに関する代表的な Web ページを見出して推薦するシステムを実現す
ることは、ユーザの Web からの情報獲得を支援する上で重要である。本稿ではハイパーリン
クによって構成されるグラフ構造に基づいてそのようなページを発見する手法について述べ
る。トピックに関する情報を持つ centers と、それらに対するリンクを持つ fans によって構
成される完全 2 部グラフは、興味を共有するコミュニティとみなすことができる。fans の多
くはそのトピックに関する代表的なページへのリンクを持っているという仮定に基づき、本
稿の手法ではコミュニティのメンバの多数決によって fans と centers の両方を反復的に更新
する。この手法に基づいて実験を行なった結果、いくつかのトピックについて、数個の入力
URL から代表的なページを見出すことに成功している。
キーワード： WWW、ハイパーリンク、グラフ構造、コミュニティ
A Structure Model for Web Communities
Tsuyoshi Murata
National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
[email protected]
Abstract: Recommendation of representative Web pages of specific topic is important for
assisting users’ information retrieval from the Web. This paper describes a method for
discovering such pages using connectivity information of hyperlinks. A complete
bipartite of Web graph, which is composed of centers (containing useful information
regarding a topic) and fans (containin g hyperlinks to centers), can be regarded as a
community sharing a common interest. The method is based on the assumption that most
of the fans contain hyperlinks pointing to representative pages regarding the topic. In
the method, both fans and centers are renewed iteratively by the result of the majority
vote of the members of previous community. Experimental results show that our method
has abilities of finding representative pages for some topics only from a few input URLs.
Keywords: WWW, hyperlink, graph structure, community
−41−
1
1. はじめに
のあるトピックについて、既に知っているページ
Webの情報から有用な知識を見出すWeb Mining
のアプローチの中で、ハイパーリンクの構造に基
づいた Web structure mining[Kosala 00]が新た
なアプローチとして注目されてきている。Web に
よりも質が高く人気のあるページを新たに見つけ
たいという要求は多くのユーザがもっており、ユ
ーザにページを推薦するシステムを実現する上で
重要であると考えられる。
おけるハイパーリンクによって構成されるグラフ
構造を解明することの利点として、Broder らは以
下の 5 つをあげている[Broder 00]。
• ロボットが Web ページを収集する際の戦略
決定
• Web コンテンツ生成における社会学の理解
• リンク情報を用いる Web アルゴリズムの振
舞いの分析
• Web 構造の発展の予測とそれを発見するア
ルゴリズムの開発
• Web グラフでの重要な新現象の出現の予測
膨大な Web ページの中からの情報獲得を支援す
るための試みとして、著者はハイパーリンクによ
るグラフ構造に基づいて Web ページの関連性を
見出す研究を行なっている。ハイパーリンクによ
本稿で述べる手法は、トピックについての代表的
なページを見出すにあたり、ハイパーリンクのグ
ラフ構造を利用する。具体的な手法として、先に
る co-citation を基に Web ページ間の関連性を見
出し、関連するページが近接するようなグラフを
生成する視覚化システム[Murata 99]や、Web の
グラフ構造中の完全 2 部グラフをコミュニティと
みなし、サーチエンジンから得られる backlink
情報を基に Web コミュニティを発見するシステ
ム[村田 01]を構築している。
ハイパーリンクによるグラフ構造を利用した
query dependent ranking の代表的な研究として
HITS アルゴリズム[Kleinberg 98]がある。これは
入力したトピックに関する Web ページ集合をサ
ーチエンジンの検索結果とその近傍から求めた後
に、トピックに関して関連性の高いページを見出
すためのアルゴリズムである。このアルゴリズム
において、入力トピックを一般化した内容のペー
ジや、全く関連性のないページが出力結果として
得られる場合があることが報告されている。この
ような現象のメカニズムを考察することは、リン
クベースのアルゴリズムの振舞いを解明する上で
重要である。
本稿では、HITS におけるこのようなトピックの
変化について検討するとともに、Web コミュニテ
ィを洗練し、興味を共有するトピックにおける代
表的なページを見出す手法について述べる。興味
提案した Web コミュニティ発見手法[村田 01]を
発展させた手法を提案する。完全 2 部グラフを構
成する頂点集合である fans と centers に属する
Web ページを、互いの参照度の高いものへ更新す
る作業を反復的に行なうことによってコミュニテ
ィの洗練を行なう。特定のトピックに関するリン
ク集においては、そのトピックについての代表的
なページへのリンクが含まれている可能性が高い。
リンク集の参照先の多数決を行なうことによって
そのトピックにおける代表的なページ集合が得ら
れ、さらにそのようなページを参照するリンク集
をサーチエンジンでの backlink 検索によって得
ることによって、リンク集の質を高めることが期
待できる。この手法に基づいてシステムを実装し
実験を行なった結果、いくつかのトピックについ
て代表的な Web ページ集合を発見することに成
功している。また、時として意外性のある URL
がトピックの代表として出力されることが確認で
き、
そのような実験結果についても考察を行なう。
2. 関連研究
ハイパーリンクのグラフ構造に基づいて Web ペ
ージ間の関連性を見出したりランキングを行なっ
たりする Web structure mining の研究としては、
HITS[Kleinberg 98]、PageRank[Page 98]、Web
Trawling[Kumar 99]などがあげられる。HITS は、
特定トピックに関する有用なページ集合を出力す
る代表的なアルゴリズムである。このアルゴリズ
ムにおいては、Web ページの有用性の評価基準と
して、特定トピックに関する情報の豊富さを表す
authority と、authority へのリンクの豊富さを表
す hub を導入している。authority として価値の
高いページへリンクを張っているページは hub
としての価値が高く、また hub として価値の高い
ページからリンクを張られているページは
2
−42−
authority と し て の 価 値 が 高 い と 言 え る 。
う topic drift[Henzinger 01]と呼ばれる現象があ
authority と hub の具体的な計算方法は以下の通
りである。
1. 特定トピックに関する有用なページを含
んでいる Web ページ集合を取得する。ま
ず通常のサーチエンジンでのキーワード
検索によって 200 ページ程度を取得し(こ
れを root set とする)、その root set のペー
ジからのリンク先のページや、root set の
ページへリンクを張っているページを追
加する(これを base set とする)。このよう
にして得られるおよそ 1000 ページから
3000 ページの base set の中に、特定トピ
ックに関する authority や hub が含まれて
いると考えられる。
2. 次に、このbase set に含まれている各ペー
ジ p の authority weight(x p) と hub
weight(y p)を計算する。相互再帰的な関係
から、両者は以下のように定義できる。
x p = Σ{q such that q→p} yq
y p = Σ{q such that p→q} xq
3. 個々のページの x p と y p を計算する方法と
して、base set に含まれている n 個のペー
ジの隣接行列を用いる。隣接行列 A はペー
ジ i からページ j へのハイパーリンクが存
在する場合に(i,j)の成分が 1 で、それ以外
は0 であるようなn×n の正方行列である。
base set の n 個のページの authority と
hub をベクトル x、y で表現するとそれぞ
れ x=ATy, y=Ax となる。x と y を正規化す
ることにすると、両者はそれぞれ ATA、
AAT の主固有ベクトルとして求めること
ができる。
HITS は、最初の root set の取得以外はハイパー
リンク情報のみに基づくシンプルなアルゴリズム
る。また、同一サイト内の同じフォーマットのペ
ージが base setのかなりの部分を占めている場合
に、その影響で全く異なるトピックのページの
authority の値が大きくなる inadvertent topic
であり、その振舞いの特徴についての研究も数多
くなされている。HITS において入力として特殊
なトピックが与えられた場合、それを一般化した
内容の authority と hub が得られる傾向(topic
generalization)があり[Gibson 98]、それを利用し
た topic distillation の 研 究 [Bharat
98][Chakrabarti 98]が行なわれている。
また HITS アルゴリズムを適用した結果、最終的
に得られる hub や authority が入力トピックと関
係のないページとなってしまう現象が指摘されて
いる。具体的な例として、hub の値が大きいペー
ジが複数のトピックについてのリンク集である場
合に、その影響で異なるトピックのページである
にも関わらず authority の値が大きくなってしま
hijacking[Chakrabarti 99]と呼ばれる現象があ
る。
HITS におけるこれらの問題を解決するための工
夫として、
リンク周辺のテキスト情報を用いたり、
リンクに対する重みを導入するなどして HITS の
性能を改善するための研究[Chakrabarti 98] や、
base set の中から関連性のないページをpruning
する研究もなされている[Bharat 98]。しかし
HITS におけるこれらの問題は、hub や authority
の計算の基になるbase setの作り方に起因するも
のであると考えられる。HITS においては、入力
されたトピックをサーチエンジンで検索し、得ら
れた Web ページ集合の近傍をとることによって
base set を作っている。これは入力トピックに内
容的に関連性のあるページが、検索結果とその近
傍にあるページに数多く含まれているという前提
に基づいているが、これは必ずしも正しいとは言
えない。また、base set となる Web ページ集合を
固定してその中でランキングを行なうため、base
set の質が出力結果に大きな影響を与えてしまう。
著者が提案した Web コミュニティ発見手法[村田
01]においては、ハイパーリンクによるグラフ構造
から完全 2 部グラフを見出すにあたり、fans(リ
ンク集のページ)が最も参照しているページを
centers(情報のあるページ)に追加し、それに対応
した fans をサーチエンジンから求める処理を繰
り返すことによって発見を行なっている。これは
発見のためのデータを必要に応じて獲得するため
に上述の問題点を回避できる可能性がある。その
一方で、この手法では centers が増加するにつれ
て fansが単調に減少していき、トピックについて
の有用なリンク集がどの段階で得られるかを判断
するのが困難であった。また、fans の個数がごく
少数になると、入力ページのトピックと関係のな
いページが centers に追加されてしまう場合があ
る。
本稿ではこの手法に改良を加えることで、fansと
−43−
3
centers の両方を洗練していく手法を提案する。
このような処理をすることによって、以下のよう
この手法においては 2 部グラフを探索する際の条
件を緩和し、完全でない2 部グラフを許容するこ
とによって fans の偏りを防ぐとともに、fans の
参照先のページを centers のページと部分的に交
な効果が期待できる。
• トピックが異なっている URL が centers
に混入している場合においても、ほぼ全ての
centersを参照しているfansを獲得すること
によって適切なリンク集を得ることができ、
fansの質の劣化を回避できる。
換することによって centers の質を高めている。
•
fansの多数が参照している URL はそのト
3. コミュニティ洗練による代表ページの
ピックに関する代表的な URL である可能性
発見
が高く、centers の URL をその URL と交換
することによって centers の質を高めること
提案手法のベースとなる Web コミュニティ発見
が期待できる。また、交換する URL の個数
手法について説明した後に、本稿での手法につい
を高々半分に制限することによって、
て述べる。Web コミュニティ発見手法においては、
centers が全く異なるトピックのページ集合
と完全に入れ代わってしまうことを回避し
ハイパーリンクによる Web のネットワークから
ている。
完全 2 部グラフを見出すにあたり、入力 URL を
4. 実験
centers とし、その全ての URL に対してハイパー
上述の手法に基づき、Web コミュニティを洗練す
リンクを張っているような Web ページ集合をサ
るシステムを実装した。システムに対する入力と
ーチエンジンの backlink 探索によって獲得して
しては、100hot.com においてランキングがなさ
fansとする。次に、そのページからのリンク先を
れている各トピックの最下位 5 個の URL とし、
すべて抽出し、最も多くの fans が参照している
その入力 URL を centers の初期集合として実験
URL を centers に追加し、その centers を用いて
を行なった。各トピックにおけるランキングの平
上述の処理を繰り返すというものである。
均順位の変化を表 1 に示す。
topic
Museum
Book
Event
Music
Election
Finance
Job
Loan
College
Kid
Adult
Gambling
Movie
Game
PS2
Family
Food
Gardening
図 1:Web コミュニティ発見手法
本稿で提案するコミュニティ洗練においては、以
下のようにして fansと centers を更新する。
• centers を参照している fansを獲得する際
に、全ての centers を参照しているページが
少数の場合は、centers 中の一つを除去して
再度 backlink の検索を行ない、予め定めた
個数以上の fans を獲得するようにする。
• fansを基に centers を更新する際、fansの
参照している URL を出現頻度順にソートし、
上位の URL を centers の URL と交換する
ことで新たな centers を作る。ただし、一度
に交換する URL 数は、centers の総数の半
分以下とする。
前 後 topic
前 後 topic
66 98 Holiday
25 23 Flowers
76 49 Pet
59 59 Luxury
39 39 Beauty
42 42 Shop
98 42 Car
98 98 Toy
40 18 Chat
80 73 Developer
98 67 Dating
80 80 Hardware
98 55 Spirit
34 30 Internet
31 31 Travel
98 54 Mac
98 101 Magazine
98 101 Uniｘ
98 98 Newspaper
98 98 Wireless
98 98 Health
98 101 Windows
87 87 Sport
98 91
98 98 Winter
68 55 平均
98 98 Athletic
45 45
36 36 Auction
38 37
74 74 Clothing
48 48
98 98 Electronics
48 48
98 98 Entertainment 48 23
前 後
41 26
33 33
98 101
41 41
98 101
98 98
98 42
37
7
43 43
80 80
98 98
72.3 65.1
表 1: 実験結果
この表を見ると、いくつかのトピックにおいて順
位が上がっており、centers の質が向上している
ことがわかる。また、順位としては上がっていな
いが興味深い出力結果が得られるトピックもあっ
た。例えば、Magazine における入力 URL と出
力 URL は以下の通りである。
• 入力: chemweek.com, mysterynet.com,
cosmomag.com, playbill.com, si.edu
4
−44−
•
出力: washingtonpost.com, nytimes.com,
usatoday.com, latimes.com, wsj.com
この結果は、コミュニティのトピックが
Magazine から Newspaper へと変化しているこ
とを示しており、両トピック間の内容的な近さを
表しているものであると考えられる。またトピッ
ク Travel においては、以下のような結果になった。
• 入力: smarterliving.com, sheraton.com,
ebookers.com, qixo.com, hotel.com
• 出 力 :
hilton.com, hyatt.com,
sheraton.com,
marriott.com,
holiday-inn.com
一般に多くのサブトピックを含んでいるような広い
内容のトピックにおいては、代表的なページが数多
く存在し得る。このトピックでは、ホテルに関する
URL が入力に多く含まれていることから、洗練の過
程でホテルに関するコミュニティに変化しているこ
とがわかる。
“Experiments in Topic Distillation”, Proc. of
ACM SIGIR workshop on Hypertext
Information Retrieval on the Web, 1998.
[Chakrabarti 99] S. Chakrabarti, et.
al.:
“Mining the Web’s Link Structure”, IEEE
Computer, Vol.32, No.8, pp.60-67, 1999.
[Gibson 98] D. Gibson, J. Kleinberg, P.
Raghavan: “Inferring Web Communities from
Link Topology”, Proc. of the 9th Conf. on
Hypertext and Hypermedia, 1998.
[Henzinger 01] M. Henzinger: “Hyperlink
Analysis for the Web”, IEEE Internet
Computing, Vol.5, No.1, pp.45-50, 2001.
[Kleinberg 98] J. Kleinberg et. al.: “The Web
as a Graph: Measurements, Models, and
Methods”, Proc. of COCOON ’99, LNCS 1627,
pp.1-17, Springer, 1999.
[Kosala 00] R. Kosala, H. Blockeel, “Web
ラフ構造を基に処理を行なっている。本稿の手法
Mining Research: A Survey”, ACM SIGKDD
では Web 上のデータを随時獲得してコミュニテ
ィのメンバを反復的に更新していくことによって、 Explorations, Vol.2, No.1, pp.1-15, 2000.
[Kumar 99] R. Kumar et. al.: "Trawling the
初期のコミュニティにおける少数のノイズによる
Web for Emerging Cyber-Communities", Proc.
影響を回避することができると考えられる。この
of the 8th WWW conference, 1999.
ような効果を十分に示すための実験の方法論も含
HITS も本稿の手法も、Web における局所的なグ
めて、
今後もさらに検討を進めていく予定である。
5. おわりに
本稿においては、トピックにおける代表的なWeb
ページ集合を発見する手法の提案を行ない、その
手法に基づいて実装したシステムの実験結果を示
した。このシステムはリンク情報だけに基づくも
のであるが、代表的なページ集合を見出すことに
ある程度成功している。今後この手法を発展させ
る方向性として、複数のコミュニティ間の関連性
を見出すことなどが考えられる。
参考文献
[Bharat 98] K. Bharat, M. Henzinger:
“Improved Algorithms for Topic Distillation in a
[Murata 99] T. Murata: “Machine Discovery
Based on the Co-occurrence of References in a
Search Engine”, Proc. of DS99, LNAI 1721,
pp.220-229, Springer, 1999．
[Page 98] L. Page et. al.: "The PageRank
Citation Ranking: Bringing Order to the Web",
Online manuscript, http://www-db.stanford.edu
/~backrub/pageranksub.ps, 1998.
[村田 01] 村田剛志: “参照の共起性に基づく
Web コミュニティの発見”，人工知能学会誌，
Vol.16, No.3, pp.316-323, 2001．
Hyperlinked Environment”, Proc. of the 21st
Int’l ACM SIGIR Conf. pp.104-111, 1998.
[Broder 00] A. Broder et. al.: “Graph structure
in the Web”, Proc. of WWW9 conference, 2000.
[Chakrabarti 98] S. Chakrabarti et. al.:
−45−
5