データサイエンス設計マニュアル

4.5 私の体験談から：Clyde の逆襲 101

差によって頂点をソートすれば、比較的整合性の取れた順列が得られる。プラスであれマイナスであれ、最

も差

の大きい頂点 v から順に論理的位置に挿入し、v に入ってくる辺を削除して、次の頂点を挿入する前に

調整すればなおよい。

4.4.4 PageRank

ネットワーク内の頂点を重要なものから順に並べる方法として、もっと有名なものがある。それは、

Google の検索エンジンを支えている PageRank アルゴリズムだ。

ウェブはウェブページから構成されており、ほとんどのページには、他のページへのリンクが含まれてい

る。あなたのウェブページに私のページへのリンクがあるとすると、それはあなたが私のページを高く評価

しているということを暗黙のうちに示している。それを「あなたは自分のページよりも私のページを優れて

いると考えている」という意味の投票として解釈して、リンクのネットワークを構築し、それを前節で取り

上げた最大非巡回部分グラフ問題として扱うことができる。

しかし、リンク/被リンクは、ウェブ上のリンクの正しい解釈ではない。PageRank は、最も被リンクの多

い頂点を高く評価する。すべての道がローマに通じているなら、ローマはきっと重要な場所に違いない。さ

らに、PageRank は、ソースが重要かどうかによって被リンクに重みを付けている。重要なページからのリ

ンクは、スパムサイトからのリンクよりも重視される。

ここで説明したことは興味深いが、さらに深い説 ...