ウェブグラフ

ウェブグラフは、ワールドワイドウェブのページ間の有向リンクの集合です。グラフは一般に、いくつかの頂点と、辺で接続されたいくつかのペアで構成されます。有向グラフでは、辺は有向線または弧です。ウェブグラフは有向グラフであり、その頂点はWWWのページに対応し、ページXにページYを参照するハイパーリンクが存在する場合、有向辺がページXとページYを接続します。 ^{[ 1 ]}

物件

ウェブグラフの次数分布は、古典的なランダムグラフモデルであるエルデシュ・レニーモデルの次数分布とは大きく異なります。^{[ 2 ]}エルデシュ・レニーモデルでは、ウェブグラフの次数分布に比べて、次数が大きいノードは非常に少ないです。正確な分布は不明ですが、^{[ 3 ]}対数正規分布や、べき乗則のバラバシ・アルバートモデルによって比較的よく説明されます。^[⁴^]^[⁵^]
ウェブグラフはスケールフリーネットワークの一例である。

アプリケーション

ウェブグラフは以下の目的で使用されます。

ワールドワイドウェブのページのページランク^{[ 6 ]}を計算する。
パーソナライズされた PageRank を計算する; ^{[ 7 ]}
共引用などのグラフ理論的特性のみを使用して類似トピックのウェブページを検出する。^{[ 8 ]}
そして、 HITSアルゴリズムのためのウェブ上のハブと権威を特定する。

参考文献

↑マニング、クリストファー D.、ラガヴァン、プラバカール、シュッツェ、ヒンリッヒ (2008)。「ウェブグラフ」。情報検索入門。ケンブリッジ大学出版局。
↑エルデシュ、ポール；レーニ、アルフレッド（1960）。「ランダムグラフの進化について」（PDF）。ハンガリー科学アカデミー数学研究所出版物。5 ：17–61。
↑ Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). "The Graph Structure in the Web - Analyzed on Different Aggregation Levels" (PDF) . Journal of Web Science . 1 (1): 33– 47. doi : 10.1561/106.00000003 . hdl : 2434/372411 .
↑ Clauset, A.; Shalizi, CR; Newman, MEJ (2009). "経験的データにおけるべき乗則分布". SIAM Rev. 51 ( 4): 661–703 . arXiv : 0706.1062 . Bibcode : 2009SIAMR..51..661C . doi : 10.1137/070710111 . S2CID 9155618 .
↑バラバシ、アルバート＝ラスロー。アルバート、レカ（1999 年 10 月）。「ランダムネットワークにおけるスケーリングの出現」(PDF)。科学。286 ( 5439 ): 509–512。arXiv : cond-mat/ 9910332 。Bibcode : 1999Sci...286..509B。土井: 10.1126/science.286.5439.509。PMID 10521342。S2CID 524106。。
↑ Brin, Sergey ; Page, Lawrence (1998-04-01). "大規模ハイパーテキストWeb検索エンジンの構造" . Computer Networks and ISDN Systems . Proceedings of the Seventh International World Wide Web Conference. 30 (1): 107– 117. doi : 10.1016/S0169-7552(98)00110-X . ISSN 0169-7552 .
↑ Glen Jeh および Jennifer Widom. 2003. パーソナライズされたウェブ検索のスケーリング。第 12 回国際ワールドワイドウェブ会議 (WWW '03) 議事録。ACM、ニューヨーク州ニューヨーク、米国、271–279。doi : 10.1145/775152.775191
↑ Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). "Trawling the Web for emerging cyber-communities". Computer Networks . 31 ( 11–16 ): 1481–1493 . CiteSeerX 10.1.1.89.4025 . doi : 10.1016/S1389-1286(99)00040-7 . S2CID 7069190 .

外部リンク

Yahoo Sandbox 内の Webgraphs
ミラノ大学のウェブグラフ研究室 – ウェブアルゴリズム研究所
スタンフォード大学のウェブグラフ – SNAP
Erdős Webgraph サーバーの Webgraph
ウェブデータコモンズ - ハイパーリンクグラフ

[1] マニング、クリストファー D.、ラガヴァン、プラバカール、シュッツェ、ヒンリッヒ (2008)。「ウェブグラフ」。情報検索入門。ケンブリッジ大学出版局。

[2] エルデシュ、ポール；レーニ、アルフレッド（1960）。「ランダムグラフの進化について」（PDF）。ハンガリー科学アカデミー数学研究所出版物。5 ：17–61。

[3] Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). "The Graph Structure in the Web - Analyzed on Different Aggregation Levels" (PDF) . Journal of Web Science . 1 (1): 33– 47. doi : 10.1561/106.00000003 . hdl : 2434/372411 .

[4] Clauset, A.; Shalizi, CR; Newman, MEJ (2009). "経験的データにおけるべき乗則分布". SIAM Rev. 51 ( 4): 661–703 . arXiv : 0706.1062 . Bibcode : 2009SIAMR..51..661C . doi : 10.1137/070710111 . S2CID 9155618 .

[5] バラバシ、アルバート＝ラスロー。アルバート、レカ（1999 年 10 月）。「ランダムネットワークにおけるスケーリングの出現」(PDF)。科学。286 ( 5439 ): 509–512。arXiv : cond-mat/ 9910332 。Bibcode : 1999Sci...286..509B。土井: 10.1126/science.286.5439.509。PMID 10521342。S2CID 524106。。

[6] Brin, Sergey ; Page, Lawrence (1998-04-01). "大規模ハイパーテキストWeb検索エンジンの構造" . Computer Networks and ISDN Systems . Proceedings of the Seventh International World Wide Web Conference. 30 (1): 107– 117. doi : 10.1016/S0169-7552(98)00110-X . ISSN 0169-7552 .

[7] Glen Jeh および Jennifer Widom. 2003. パーソナライズされたウェブ検索のスケーリング。第 12 回国際ワールドワイドウェブ会議 (WWW '03) 議事録。ACM、ニューヨーク州ニューヨーク、米国、271–279。doi : 10.1145/775152.775191

[8] Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). "Trawling the Web for emerging cyber-communities". Computer Networks . 31 ( 11–16 ): 1481–1493 . CiteSeerX 10.1.1.89.4025 . doi : 10.1016/S1389-1286(99)00040-7 . S2CID 7069190 .

[ 1 ]

[ 2 ]

[ 3 ]

[

[

[ 6 ]

[ 7 ]

[ 8 ]

物件

アプリケーション

参考文献

外部リンク

関連するトピック

ワールドワイドウェブ

グラフは

有向グラフ

ハイパーリンクが