
4.5 私の体験談から:Clyde の逆襲 101
差によって頂点をソートすれば、比較的整合性の取れた順列が得られる。プラスであれマイナスであれ、最
も差
の大きい頂点 v から順に論理的位置に挿入し、v に入ってくる辺を削除して、次の頂点を挿入する前に
調整すればなおよい。
4.4.4 PageRank
ネットワーク内の頂点を重要なものから順に並べる方法として、もっと有名なものがある。それは、
Google の検索エンジンを支えている PageRank アルゴリズムだ。
ウェブはウェブページから構成されており、ほとんどのページには、他のページへのリンクが含まれてい
る。あなたのウェブページに私のページへのリンクがあるとすると、それはあなたが私のページを高く評価
しているということを暗黙のうちに示している。それを「あなたは自分のページよりも私のページを優れて
いると考えている」という意味の投票として解釈して、リンクのネットワークを構築し、それを前節で取り
上げた最大非巡回部分グラフ問題として扱うことができる。
しかし、リンク/被リンクは、ウェブ上のリンクの正しい解釈ではない。PageRank は、最も被リンクの多
い頂点を高く評価する。すべての道がローマに通じているなら、ローマはきっと重要な場所に違いない。さ
らに、PageRank は、ソースが重要かどうかによって被リンクに重みを付けている。重要なページからのリ
ンクは、スパムサイトからのリンクよりも重視される。
ここで説明したことは興味深いが、さらに深い説 ...