Webダイナミクス-膨大で動的なWeb情報の知的処理に向けて-：3.Webコミュニティ
6
0
0
全文
(2) 3. Webコミュニティ. ��������������. �������� �� ������� �����. �������������� �� �� ������� �����. ��� �� ������� �����. ��� �� ������� �����. ���������������. �����. 図 -2 二部グラフを構成する Web コミュニティ （文献 3）より） ������������ ����������. 図 -1 Web の蝶ネクタイ構造（文献 1）より）. われているページもある．そのため，Web ページ上に出 現するキーワードに基づいたランキングでは，ユーザに のようなページに対してハイパーリンクを張るページの. とって好ましくない結果となる可能性がある．. 両方からなる二部グラフを構成する場合が多い．たとえ. ハイパーリンクの多くは，その参照先のページ内容に. ば図 -2 は，右側の Boeing や Airbus などの航空機製造会. 対する支持を表すものであると考えられる．ハイパーリ. 社の各ページに対して，左側の航空機ファンのページが. ンクのグラフ構造に基づいた Web ページのランキング. ハイパーリンクを張っている．このような構造を持つ. においては，あるページの重要度を，そのページとハイ. Web ページ集合は興味を共有する Web コミュニティで. パーリンクで結合している周囲のページの重要度を使っ. あると見なすことができる．Kumar らは Web のスナッ. て決定する．したがって，上述のような操作の影響を受. プショットデータから二部グラフを探索する実験を行. けにくく，サーチエンジンにおける妥当なランキングを. い，多くの Web コミュニティを見出している．これに. 実現する上で好ましいものである．そのようなランキン. ついては後述する．. グの代表的な例として，特定のトピックのページに関す. これらの結果は，ハイパーリンクによって形成される. るランキングアルゴリズムである HITS と，トピック. 特有のグラフ構造が Web 上に数多く存在していること. に依存しないランキングアルゴリズムである. を示唆している．このようなハイパーリンクのグラフ構. PageRank. 造に注目して知識発見を行う Web 構造マイニングの主. HITS においては Web ページの有用性を表す評価基準. な目標としては，（1）重要ページのランキングや（2）. として，特定のトピックに関する情報の豊富さを表す. Web コミュニティの発見などが挙げられる．以下では，. authority と，authority へのリンクの豊富さを表す hub. それぞれについて代表的な研究を紹介する．. を導入している．authority として価値の高いページへ. 3）. ☆1. について説明する．. リンクを張っているページは hub としての価値が高く，. ハイパーリンクのグラフ構造に基づく ランキング. また hub として価値の高いページからリンクを張られて いるページは authority としての価値が高いといえるた め，両者は相互再帰的に定義することができる．ハイパ. Web から情報を得ようとしてサーチエンジンでキーワ. ーリンクによるページ間の結合関係は隣接行列によって. ード検索をするユーザにとっては，キーワードに関連し. 表される．隣接行列とは，ページ i からページ j へのハ. た内容のページが検索結果の上位にランキングされるこ. イパーリンクが存在する場合に（i, j）の成分が 1 で，そ. とが望ましい．一方，Web ページ作成者の多くは自分の. れ以外は 0 であるような n × n の正方行列である．個々. ページが検索結果の上位にくることを望んでおり，見え. のページの authority 値と hub 値の計算は，隣接行列と. ない色で単語の羅列を表示するなどの恣意的な操作が行. その転置行列の積の主固有ベクトルを求める計算に帰着. ☆1. 参考資料として以下の online manuscript がある：Page, L., Brin, S., Motwani, R. and Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web, http://www-db.stanford.edu/~backrub/pageranksub.ps (1998).. IPSJ Magazine Vol.44 No.7 July 2003. −2−. 703.
(3) 特集. Webダイナミクス ����� �����. �����������. ����� �����. �＝3 �＝4. �����. �＝5 �＝6. �����. �＝7. ����� ����� � �. �. �. �. �. ��. ��. ��. ��. ��. �. 図 -3 PageRank アルゴリズム. 図 -4 Web コミュニティ数の分布. する．. のスナップショットデータからそのグラフ構造を探索す. 一方，PageRank は「多くの良質なページからリンク. ることによって Web コミュニティの発見を行うことが. されているページはやはり良質なページである」という. できる．そのようなアプローチの代表的な例として，上. 考えに基づいた，トピックに依存しないランキングアル. 述の Kumar らによる trawling の研究がある．この研究. ゴリズムである．この PageRank は，サーチエンジン. においては，2 つの頂点集合 F と C から構成され，F の. Google（http://www.google.com/）におけるランキングの. 各頂点 u から C の各頂点 v への有向辺が存在するような. 一部として利用されている．図 -3 は，PageRank アルゴ. 完全二部グラフを，興味を共有するページからなる Web. リズムの概念図である．あるページの PageRank 値は，. コミュニティであるとしている．Kumar らは約 2 億ペ. そこにハイパーリンクを張っている他のページの. ージの大規模スナップショットデータから，Fi, Cj. PageRank 値によって決まる．PageRank 値の高い有用な. となるサイズ (i , j) の完全二部グラフを高速に探索する. ページからハイパーリンクを張られていたり，多くのペ. ための枝刈りの手法を提案し，個数の分布を実験結果に. ージからハイパーリンクを張られていたりすると，その. よって示している．データ中に含まれていると推定され. ページの PageRank 値が高くなる．各ページの PageRank. る Web コミュニティ数の分布を大きさ別に表したグラ. 値はランダムにハイパーリンクをたどる閲覧者がページ. フを図 -4 に示す．この図において，縦軸は Web コミュ. を訪れる確率に対応している．. ニティの個数，横軸はサイズ (i, j) の j を表し，5 種類の. 4）. 線は i の値がそれぞれ 3 から 7 の場合の分布を表してい る．i1i2 のとき，サイズ (i2, j) の完全二部グラフの部. Webコミュニティの発見. 分集合 (i1, j) も完全二部グラフであることから，数え上 げにはアプリオリアルゴリズムを用いることができる．. Web コミュニティという単語はさまざまな文脈におい. j を固定してまず (1, j) を見出し，その結果を利用して順. て用いられるが，本稿ではハイパーリンクによって密に. に (2, j)，(3, j)，…を見出すことで数え上げを行っている．. 結合した関連 Web ページ集合という意味で用いること. また Kumar らは得られた Web コミュニティの質を評. にする．Web コミュニティを発見する手法としては，固. 価するために，ランダムに選択した 400 個の完全二部. 定したグラフ構造を探索する手法と，密な部分グラフ構. グラフを人手で調べた結果，関連性のない Web ページ. 造を抽出する手法の 2 つに大まかに分けることができ. 集合によって偶然に形成されたものが 4％あり，データ. る．それぞれについて以下で説明する．. 収集から 18 カ月後の Web 上においてはすでに存在しな いものが約 30 ％あったが，それ以外のものは実際に関 連性のある Web ページ集合であった．. 固定したグラフ構造の探索 ハイパーリンクが特定のグラフ構造を構成するような Web ページ集合が意味的なまとまりを持つならば，Web. 704. 44 巻 7 号 情報処理 2003 年 7 月. −3−.
(4) 3. Webコミュニティ. �. (a). (b). (c). (d). �. 図 -6 edge betweenness を利用した コミュニティ発見. (e). 図 -5 最大流最小カット定理による Web コミュニティ発見. 密な部分グラフ構造の抽出. 密な部分グラフ構造を見出す他のアプローチとして，. 上述のアプローチとは別に，与えられた Web データ. Girvan. のグラフ構造を分割するなどして，密な部分グラフであ. を分析するにあたり，辺が頂点間の経路となっている度. る Web コ ミ ュ ニ テ ィ を 見 出 す ア プ ロ ー チ も あ る．. 合いとして edge betweenness を導入している．ある辺. 2）. ☆2. らはグラフ構造で表された社会ネットワーク. Flake らは，全頂点集合 V の部分集合 C において，C の. の edge betweenness は，その辺を通るような 2 頂点間. 各要素 v が VC の頂点よりも C の頂点とより多くリンク. の最短パスの本数で定義される．密な部分グラフ間を結. していることを Web コミュニティの定義としている．. ぶ細い経路となる辺においてはその edge betweenness. このような Web コミュニティを見出すことは一般には. が大きくなるため，edge betweenness が大きい辺を取り. NP 完全のグラフ分割問題であることから，ネットワー. 除く処理を繰り返すことによって密な部分グラフを見出. ク理論における最大流問題の枠組みでこの問題を捉え直. している．図 -6 に示す例では，頂点 A と B とを結ぶ辺. す．種となる頂点集合を想定し，それを含むような Web. の edge betweenness が大きいために取り除かれ，2 つの. コミュニティを効率的に見出す問題を考える．. コミュニティに分割される．. グラフにおける辺を水，頂点を接合点と見なし，各辺 s(source) と t(sink) が与えられたとき，最大流問題は各辺. サーチエンジンからのデータ獲得に基づくWeb コミュニティ発見・視覚化. の容量を越えることなく s から t への最大流を求める問. 主要なサーチエンジンには大量の Web ページが収録. 題であり，これは s と t を分離する最小容量カット問題. されており，巨大で動的な Web を扱う上で重要な資源. と同値であることが知られている．図 -5 は Flake らのア. である．筆者は，サーチエンジンを Web データ獲得の. プローチの概念図である．（a）は仮想的な source,（e）は. ための道具と見なし，必要に応じて検索を行うことで. 仮想的な sink を表している．発見したい Web コミュニ. Web コミュニティの視覚化や発見を行う手法を提案し実. ティの種となる頂点集合（b）が与えられたとき，それと. 験を行っている．一般に，2 つのページ間の関係が密接. リンクで結合している頂点を（c），それ以外の頂点を. であるほど，両ページへのハイパーリンクが共起してい. （d）とする．仮想的な source（a）から（b）のすべての頂. るような Web ページが数多く存在すると考えられる．. 点へ容量無限大の辺を付け加え，また（a）,（b）,（e）以. 筆者が構築した，Web ページ間の関連性を視覚化するシ. 外のすべての頂点から（e）へ容量 1 の辺を付け加える．. ステムにおいては，2 つのページの関連性の強さを判定. 元のグラフの辺の容量は k とし，（a）から（e）への最大. する際，サーチエンジン AltaVista において 2 つの URL. 流アルゴリズムを適用し，最小カットの結果の（a）側の. をキーワードとして検索して得られるページ数を，片方. 頂点集合を Web コミュニティとする．. の URL をキーワードとして検索して得られるページ数. に は 正 の 容 量 が 付 与 さ れ て い る と す る． 頂 点 集 合. ☆2. 参考資料として以下の online manuscript がある：Girvan, M. and Newman, M. E. J.: Community Structure in Social and Biological Networks, http://arxiv.org/ abs/cond-mat/0112110/ (2001).. IPSJ Magazine Vol.44 No.7 July 2003. −4−. 705.
(5) 特集. Webダイナミクス. 図 -7 Jaccard 係数に基づく Web コミュニティの視覚化. の和で割った値（Jaccard 係数）を求め，その値が大きい. ニングにおけるその他の話題として Web ページ生成モ. ほど URL 間を結ぶ辺の長さが短くなるようなグラフを. デルがある．1 つの Web ページから出る（入る）ハイパ. 表示している．この視覚化システムは Web 上に公開し ており（http://research.nii.ac.jp/ ~ tmurata/） ，実行例を. ーリンクの本数と，そのようなページの数との関係は指. 図 -7 に示す．サーチエンジンの検索件数を用いたこの. ばれている．そのような関数に従うような Web ページ. ような手法は，対象間の関連性を見出す便宜的な手法と. 集合を作り出すプロセスのモデル化とシミュレーション. して有効である．. による検証が進められている．. また，サーチエンジンの検索結果を用いて Web コミ. Web コミュニティについては，Web という巨大で動的. ュニティを発見する手法として，入力された Web ペー. なメディアをとらえていく新たな概念として重要であ. ジ数個を含んでいるような完全二部グラフを見出すシス. り，得られる知見は工学的な意味で重要であるだけでな. テ ム の 構 築 も 行 っ て い る． 与 え ら れ た Web ペ ー ジ. く，社会学的にも興味深いものであると考えられる．. （centers）すべてにリンクを張っているようなページ集. Web コミュニティの性質の分析，発見手法の比較，発見. 数関数で表せることが指摘されており，Power law と呼. 合（fans）をサーチエンジンのバックリンク検索で求め，. された Web コミュニティの評価手法など，さまざまな. その fans から出ているハイパーリンクの中で出現回数が. 課題が残されており，今後の研究が期待される．. 多いものの参照先ページを centers に追加する処理を繰 り返すことで Web コミュニティの発見を行っている． 詳細については文献 6）を参照されたい． Web コミュニティの動的な変化を見出す試みとして は，豊田らの研究. 5）. がある．これは，1999 年から毎年. 収集された Web アーカイブデータを利用して Web コミ ュニティの発見を行い，その結果を比較することによっ て Web コミュニティの動的な変化を見出している．. Webコミュニティ発見の今後 本稿では，Web 構造マイニングについて紹介し，その 中の重要なトピックである Web コミュニティ発見につ いて説明した．本稿では扱わなかったが，Web 構造マイ. 706. 44 巻 7 号 情報処理 2003 年 7 月. −5−. 参考文献 1）Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. and Wiener, J.: Graph Structure in the Web: Experiments and Models, Proc. of the 9th WWW Conference, pp.309-320 (2000). 2 ）Flake, G. W., Lawrence, S., Giles, C. L. and Coetzee, G. M.: SelfOrganization and Identification of Web Communities, IEEE Computer, Vol.35, No.3, pp.66-71 (2002). 3）Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S. and Tomkins, A.: The Web as a Graph: Measurements, Models, and Methods, Proc. of COCOON'99, LNCS 1627, pp.1-17 (1999). 4）Kumar, R., Raghavan, P., Rajagopalan, S. and Tomkins, A.: Trawling the Web for Emerging Cyber-Communities, Proc. of the 8 th WWW Conference, pp.403-416 (1999). 5 ）Toyoda, M. and Kitsuregawa, M.: Observing Evolution of Web Communities, Proc. of the 11th WWW Conference, CD-ROM (2002). 6）村田剛志 : 参照の共起性に基づく Web コミュニティの発見，人工知能 学会論文誌，Vol.16, No.3, pp.316-323 (2001). （平成 15 年 4 月 1 日受付）.
(6) −6−.
(7)
関連したドキュメント
ROKU KYOTO Autumn Parfait ~ Shine muscat & Jasmine tea ~ ROKU KYOTO
(3) We present a JavaScript library 2 , that contains all the al- gorithms described in this paper, and a Web platform, AGORA 3 (Automatic Graph Overlap Removal Algorithms), in
（4） 現地参加者からの質問は、従来通り講演会場内設置のマイクを使用した音声による質問となり ます。WEB 参加者からの質問は、Zoom
※ログイン後最初に表示 される申込メニュー画面 の「ユーザ情報変更」ボタ ンより事前にメールアド レスをご登録いただきま
Webカメラ とスピーカー 、若しくはイヤホン
特に LUNA 、教学 Web
[r]
Digital media has had a profound impact on human behavior.. Nevertheless, articles about digital media have focused on the power of the technology rather than the impact it has had on
