研究対象としてのWeb
筑波大学 研究談話会

大規模なウェブの構造とその変遷を探る
2007年11月13日

生産技術研究所
豊田正史

実社会の射影としてのウェブ• 膨大な文書集合– 200億を超えるテキスト・画像・動画(Yahoo!発表2005/8)– 自然言語処理、情報検索、情報抽出、テキストマイニング• 膨大なグラフ構造– 文書＝ノード、リンク＝エッジの膨大かつ疎な有向グラフ– グラフ理論(次数、直径、進化モデル)、情報検索への応用、グラフマイニング• 動的– 持続的な成長(サーバ数は2000年から年平均36％増加 米Netcraft社)
無数の著者が日々文書を生成する一方、消滅する文書も多い。
– 時系列解析(成長率、内容の変化、構造の変化)、社会学• サービス提供の場– 広告、通信販売、メール、ブログ、写真共有、企業間取引– XML、Webサービス、セキュリティ、経済学

目的：ウェブ情報の高度利用システ
ムの構築（ＷＥＢの時空間解析）

あらまし• ウェブアーカイブ基盤– アーカイブの概要と簡単なアプリケーション• ウェブ空間の構造俯瞰
– リンク解析によるウェブの地図– Yahoo!との比較• ウェブの時系列分析– ウェブ空間構造の時系列変化を可視化

1

アーカイブの簡単なアプリケーション

検索に対するヒットページ数の推移• URLを指定して、ページの編集履歴を見る• 時系列検索エンジン

サイトBとCの順位逆転– 検索ヒットページ数の推移– ランキングの時系列変化– 各時期の新規ページ提示

ポータルサイトA

検索サイトB
2000

2001

2002

2003

ポータルサイトC
2004

SARS

イラク

BSE
1999

テロ
鳥インフルエンザ

2000

2000
2002

2002
2003

あらまし

1999
2001

2001

2003

ウェブ空間の構造俯瞰～コミュニティチャート～• ウェブアーカイブ基盤– アーカイブの概要と簡単なアプリケーション• ウェブ空間の構造俯瞰
– リンク解析によるウェブの地図– Yahoo!との比較• ウェブの時系列分析– ウェブ空間構造の時系列変化を可視化リンク＆テキスト解析を用いてウェブの全空間を地図化
産業連関図に相当する地図が得られる¾注目分野のリサーチ・サーベイに有用
影響力のある製品ユーザのグループなども同時に抽出¾広告設置戦略への応用

ウェブコミュニティとは同じトピックに関心を持つ人々または組織が同じトピックに関心を持つ人々または組織が作成したウェブページの集まり

例２ PCメーカのコミュニティ

例1 千葉ロッテマリーンズファンのコミュニティ

2HubとAuthorityの例

HITS [Kleinberg ’97]

Hubs

以下の観測を基にコミュニティを発見する– ハイパーリンクはリンク先のページを推薦する• お勧めしないページはわざわざリンクしない– 同種類のハイパーリンクは一箇所にまとめられることがある• ブックマーク、お気に入り、リンク集、ポータルサイト、相互リンク、お友達リンク、etc.
ポータルサイト、相互リンク、お友達リンク、etc.

HubとAuthority

Authorities• 適当なウェブの部分グラフから良いhubと適当なウェブの部分グラフから良いhubとauthorityを抽出する
authorityを抽出する– Hub: 多くの良いauthorityを指しているリンク集
多くの良いauthorityを指しているリンク集– Authority: 多くの良いhubから指されているページ
多くの良いhubから指されているページ
HubAuthority

HubAuthority

HubAuthority

良いAuthorityとHubの集まりをコミュニティと呼ぶ
良いAuthorityとHubの集まりをコミュニティと呼ぶ

ウェブ空間の構造俯瞰
ウェブコミュニティチャート[ACM Hypertext 2001]• ある話題に関する有用なページの集合はウェブグラフ上で稠密な構造を持つ(稠密な構造を持つ(ウェブコミュニティ)ウェブコミュニティ)Relationship graphFor each page, find authorities in the neighborhood,and make edges from the page to authorities
Adobe• 全コミュニティとそれらの関係を抽出して地図化
ウェブグラフMicrosoftNEC

関連グラフ
PC周辺機器IBM

OracleSONY
Canon

ソフトウェアKonikaToshiba
電機／PC
ケーブル

Olympus

デジカメ

ウェブコミュニティチャート

3

Relationship Graph

MicrosoftNECIBM

Web Community Chart

Adobe•Build a graph of clusters•Weights of edges are # ofrelationships between clusters

OracleNEC3MicrosoftSONYCanon
Toshiba
Olympus

コミュニティチャートとYahoo!の比較[吉田 2003]
共有URL数(2002年のデータを使用)
Yahoo!の重複を取り除いたURL
ウェブコミュニティチャートのURL
共有URL

Canon

2
Konika177,000
1,000,000
81,000

比較対象とするコミュニティとディレクトリ
共有部分内においてURL数5以上のもの
4079コミュニティ(33930URL 平均8.13)
4965ディレクトリ(63757URL 平均12.84)

KonikaToshiba• 地球環境ポータル構築の試み[菊池（高知大）]– DEWS2001• ジェンダー関連ポータルサイト構築[増永,小山（お茶女）]– 重点研究「グローバル化とジェンダー規範」2000～2001• Web Community Browser [福地（東工大）]– DEWS2002, WISS2002, FIT2002• ウェブディレクトリとの比較[吉田]– DEWS2003, TOD22• 大域ウェブアクセスログ解析[大塚]– TOD20, DEXA2004

OlympusPC vendors

Digital Camera
VendorsチャートとYahoo!の類似度
Yahoo!ディレクトリ

コミュニティチャート
URL1
URL2
URL3
URL4

URL1
URL2
URL3
URL4
0～0.2
0.2～0.4
0.4～0.6
0.6～0.8
0.8～1.0

Community→Yahoo

Yahoo→Community
0%

応用研究

OracleSoftwarevendors

IBMSONY

Adobe

20%

40%

60%

80%

100%

あらまし• ウェブアーカイブ基盤– アーカイブの概要と簡単なアプリケーション• ウェブ空間の構造俯瞰
– リンク解析によるウェブの地図– Yahoo!との比較• ウェブの時系列分析– ウェブ空間構造の時系列変化を可視化• リンク解析による全文検索エンジンの精度向上[RICOH]– NTCIR3 Web

4ウェブの時系列分析

成果②ウェブの時系列分析[ACM Hypertext 03]～銀行業界の変遷～• 定期的にウェブを大規模収集• トピックの発展過程をコミュニティを通して観察 インターネット銀行の出現と世間への浸透
 合併した銀行の出現：三井住友、UFJ、みずほ、りそな

Internet

検索キーワード銀行

Crawling
Web
Archive
Extract all communities
and their relevanceCompare

T1

T2

T3

time

成果②ウェブの時系列分析

ウェブの時系列分析～社会現象による話題の爆発的発生～～社会学への応用：ジェンダー活動の成長～

同時多発テロテロ

ニュース記事

義援金募集

99年の男女共同参画社会基本法施行に呼応して全国に女性センターのホームページが作成されていった様子が見て取れる
平和運動

お茶ノ水大学ジェンダー研究センターとの共同研究

Types of Changes
データセットChanges are detected by comparing neighboring chartsaaa.jpbbb.jp• 日本中のウェブサイトからロボットを用いて収集したアーカイブ
1999～2004の7回分

データセット詳細Year
1999/8
2000/8
2001/10
2002/2
2003/2
2003/07
2004/05#Pages #seeds#comms
17M
671K
83K
17M
741K
94K
40M
1431K
158K
45M
1583K
171K
66M
4646K
554K
97M
7870K
874K
96M
8192K
849K

Emergeccc.jpddd.jpeee.jpfff.jpggg.jphhh.jpiii.jpjjj.jpkkk.jplll.jp

Dissolve
eee.jpfff.jpggg.jpSplit
hhh.jpiii.jpmmm.jpnnn.jpjjj.jpkkk.jplll.jpmmm.jpnnn.jp

tk-1

tk

Merge

time

5

Types of Changes• Structure of communities changes dynamically• How the size distribution is kept unchanged?
Transition of communities

N umber of Communities

180000Emerged and Dissolved
Communities• Both size distributions follow the power-law• Both exponents are greater than ones in size
distribution of all communities

Emerged
Dissolved
Split or mergedSingle160000140000120000100000
80000
60000
40000
20000

Feb-02O ct-01

Dec-01

Aug-01

Apr-01

Jun-01

Feb-01

O ct-00

Dec-00Aug-00

Apr-00

Jun-00

Feb-00O ct-99

Dec-99Aug-990Time

Grown and Shrunken Communities

Split and Merged Communities• # of split and merged URLs also follow thepower-law, and have clear symmetry• Growth rate have clear y-axis symmetry

Evolution Metrics
Growth rate:# c ( t k ) − # c ( t k −1 )t k − t k −1

Novelty:# appearedUR Ls
t k − t k −1
t k − t k −1

Split rate:
Merge rate:# mergedURLst k − t k −1

[ACM Hypertext 05]

空間＋時間分析：コミュニティの変遷（例：i-mode検索サイト）

時間c(tk)Disappearance rate: # disappeare dURLs# splitURLs
t k − t k −1

ウェブの時空間分析

c(tk-1)

Appeared URLs…
Merged URLs…

Shared URLs…

Shared URLs…

ベンチャー中心
大手の新規参入
ベンチャー衰退

Split URLs…

大手中心に移行

Disappeared URLs…

tk-1

tktime6定量評価基盤構築の課題
アーカイブの不完全性・全空間の完全収集は不可能
・ページの作成・消滅時間が一部不明

スパム・ミラーサイト
・意図的なテキスト・リンク操作の増加 (全サイトの9%～25%)
・22%～29%のページがミラーページの新規性推定手法 [WWW2006]
Crawled pages: W(t)W(t)
Crawled pages: W(tW(t-1)

U(t)U(t) ?

?

volume o?

O(t)
O(t)

?

200

200

200

200

200

200

200

200

200

200

200

199

66/0

1
4/0

75/0

54/0

73/0

2
3/0

2
2/1

0
1/1

8
2/0

80/0

2
2/0

8
9/0

t-1

t

「生協の白石さん」

Novelty Measure

qWWW2006:
Toyoda,Kitsuregawa

出現N(q)
N(q) ≒ 0.5

New50% Newp認知N(p)N(p) ≒ (3+0.5) / 4t-1t

人気爆発

OutlineA Large-Scale Study of Link Spam
Detection by Graph Algorithms
Ｈｉｒｏｏ Saito
Masashi Toyoda
Masaru Kitsuregawa
Kazuyuki Aihara

University of Tokyo. JST, ERATO
University of Tokyo
University of Tokyo
University of Tokyo. JST, ERATOAIRWEB’07, May 8, 2007

• Propose a link farm detection method using graph algorithms• Distribution of detected link farms in the Web graph structure
CORE

1. SCC decomposition
Around the largest SCC (CORE),
large SCCs are link farms

2. Maximal clique enumeration
Link farms in CORE can be found asmaximal cliques

3. Minimum cut
Link farms are expanded by min-cut.
How many links for cutting them out?

7Ｄistribution of SCCs in the bow tie

SCC decomposition

OUT• Bow-tie structure[Broder et al. 2000]

Size distribution of SCCs

CORE

1.E+06
Number of SCCs

• Size distribution follows
the power-law(1≦n≦100)with a long and thick tail• Large SCCs are spams(100<n)– 552 SCCs, 0.57M sites– 550 sample sites

IN1%

1.E+04

CORE
30%

OUT
60%
IN

1.E+02TENDRILS
2%

1.E+00
1.E+00

1.E+02

1.E+04Size of SCCs

1.E+06OTHERS
7%• Distribution of large SCCs
– 450 / 552 (81%) SCCs in OUT– 385 / 450 (85%) SCCs directly
connected to CORE

Sampling resultsspam
suspicious non-spam#sites527
230ratio (%)
95.8
4.20

• CORE has many spam sites
connecting to them

Minimum cut• How many spam sites around large SCCs and cliques?
• How many links for cutting off spam sites?
Apply max-flow / min-cut on the directed site graph

SCCs whose size arelarger than 1,000

今後の展開• より連続的な構造進化の解析– 収集間隔の短縮（月、週、毎日程度まで）• 自然言語処理の導入による各手法の発展
CORE

Virtualsource57,000 sites
Cliques

8,000 sites

210 white sites

Min-cut: 18,000

SCCs

Virtualsink
450,000 sites
Sampling result

number ratio (%)
spam
459
94.3
suspicious
27
5.5
non-spam1
0.2– コミュニティ抽出の精度向上– アーカイブ全文検索を用いたより詳細な話題伝
播分析・評判分析• 社会学、マーケティングへの応用– お茶の水女子大ジェンダー研との研究は継続中– 他にも色々と進行中

8