
298 10 章 ネットワーク分析と距離
さま
ざまな比較ができるようになるなど、さまざまな形で役に立つ。例えば、1 個の属性(例えば性
別)だけが異なり他の属性は同じ頂点同士をすべて取り上げて比較すると、その変数が特定の結果変
数(例えば収入や寿命)にどのような影響を与えているかに注目できる。マッチングは、ネットワー
クのサイズ縮小の手段にもなる。マッチした対を取り除き、両者の重心を表す頂点を追加すると、頂
点数は半分だが全体を表現するグラフを作ることができる。
• トポロジカルソート:ランキング問題(第 4 章参照)は、何らかの基準に基づいて集合に上下関係を
追加する。トポロジカルソートは有向非巡回グラフ(DAC)の頂点にランクを付与し、辺 (i, j) があ
るということは i の方が j よりも序列が上だという意味を与えることである。「i は j よりも上にラ
ンキングされなければならない」という形式の観測された制約を持つ集合があるとき、トポロジカル
ソートは、その観測と矛盾しない順序を定義する。
10.4 PageRank
グラフ内の頂点の相対的な重要性をカテゴリ化できると便利であることが多い。おそらく最も単純な順位
は、頂点の次数だろう。次数とは、頂点 v をグラフのその他の頂点と結ぶ辺の数のことである。接続されて
いる頂点が多ければ多いほど、その頂点はおそらく重要だ。
頂点 v の次数は、v に対応する要素を表現する優れた特徴になる。しかし、次数よりももっと優れている
のが PageRank、すなわ ...