ビジネス的に重要度が高いのがこの辺の話題ではないかな？ということで、今回は中心性(centrality)の話題を取り上げてみようと思います。参考文献はいつも通りこちら。
- 作者: 鈴木努,金明哲
- 出版社/メーカー: 共立出版
- 発売日: 2009/09/25
- メディア: 単行本
- 購入: 5人 クリック: 62回
- この商品を含むブログ (9件) を見る
データセットはこれまで通り前々回適当に生成したグラフのものと、C elegansと、さらに以前使った『レ・ミゼラブル』の人物相関図を対比のために併用しようと思います。
そもそも中心性とは
『ネットワーク分析』p.41にはこんなことが書いてあります。
中心性は、ネットワークにおける各頂点の重要性を評価したり、比較したりするための指標である。例えば、交通ネットワークでは、ある地点から他の地点へ移動するための道のりや時間の面から、その地点の中心性を評価できるだろう。社会ネットワークでは、友人がどれくらいいるか、あるいはそのうち何人から信頼されているかが、個人の中心性の指標となり得る。ウェブページなら他のサイトからどれくらいリンクされているかでそのサイトの重要性が評価できるだろう。
これでほぼ言い尽くしている気もしますが、要はネットワークにおける「個々のノードの重要性を示すもの」だと言って良いかと思います。そしてその後に続く説明にもあるように、これはあくまでもネットワークの構造「のみ」に依存します。
それらに共通しているのは、中心性があくまでもネットワークの構造によって決まるのであり、他の何らかの属性によって決まるのではないということである。例えば、社会ネットワークにおいて個人の性格や肩書は中心性と直接関係しないし、ウェブページの中心性はそのページの内容的な面白さや有益さとは直接関係がない。もちろん、個人の性格の良さがより多くの友人をもつことを可能にしたり、逆に友人の多さが個人の出世を助け社会的に認められる肩書を可能にすることはあるだろう。ウェブページの内容が良いからこそ、より多くのリンクを得られるのだと考えれば、リンクの多さからウェブページの内容の良さを推定することは可能かもしれない。しかし、それらはネットワークにおける頂点の中心性と、その頂点の何らかのパフォーマンスの関係を仮定して論じているのであって、中心性の評価そのものとは別の話である。
実はかつて僕が手掛けた仕事にもまさにこれに当てはまるようなものがあって、（ゴニョゴニョゴニョ）*1ということでなかなか面白い成果が挙がったのを思い出します。ともあれ、ネットワーク構造に純粋に依拠する中心性という考え方が、もちろんそのデータの質や量にも依存するものの、これまでにない重要な意味をもたらし得るということは個人的には確信を持って言い切れると思っています。
データセットの準備
冒頭にも書いたように、このシリーズでは一貫して3つのデータセットを使います。1つ目は前々回生成した適当なグラフ。
> d [,1] [,2] [1,] 1 8 [2,] 3 1 [3,] 1 2 [4,] 6 2 [5,] 3 8 [6,] 5 3 [7,] 6 3 [8,] 8 3 [9,] 3 4 [10,] 8 4 [11,] 2 5 [12,] 4 5 [13,] 8 5 [14,] 1 6 [15,] 2 6 [16,] 4 6 [17,] 5 6 [18,] 4 7 [19,] 6 7 > library(igraph) > g0<-graph.edgelist(as.matrix(d),directed=T)
残り2つはC elegansの神経細胞ネットワークと『レ・ミゼラブル』の人物相関グラフです。Network dataからcelegansnural, lesmisの2つのデータセットをDLしてきてgmlファイルを以下のようにインポートしてください。
> g1<-read.graph("celegansneural.gml",format="GML") > g2<-read.graph("lesmis.gml",format="GML")
以下、個々の指標の説明はg0で行い、最後にまとめてg1とg2で主要な中心性のみを算出して可視化した結果を示します。
離心中心性・近接中心性
この2つはある要件を満たすグラフの最短経路長に基づくもので、『ネットワーク分析』では「円や球の『中心』のイメージに近い」ものとして紹介されています。まず「離心中心性」(eccentricity centrality)は、グラフ全体を最短経路長を長さの単位とする円（球）*2とみなした上で、その「中心」からの距離*3の逆数を取ったものです。端的に言えば、グラフのど真ん中に近ければ近いほど大きくなります。
一方、ある要件を満たすグラフの最短経路長の「合計」に着目したものもあります。あるノードから他のノードへの最短経路長の合計*4の逆数を取ったものを「近接中心性」(closeness centrality)と呼びます。
その定義上、前者は「とにかくあるノードから他のノードへの距離の最大値を最小化したい」時に目安となり、後者は「とにかく距離の総和や平均距離を小さくしたい」時に目安になります。いずれにせよ両者とも全ノードで最短経路長が非ゼロでないと色々不都合の多い指標なので、どちらかというと無向グラフか強連結の有向グラフでないと使いづらい指標だと言えます。
近接中心性は、{igraph}ではcloseness関数で算出できます。試しにg0で算出し、可視化してみるとこうなります。
> g0.cls<-closeness(g0,mode = 'out') > plot(g0,vertex.size=g0.cls*200)
ノード6が最大で、自分から出て行くエッジを持たないノード7が最小となるのが分かります。ちなみに離心中心性と近接中心性どちらが良いか？というのが気になる人もいるかと思いますが、『ネットワーク分析』の書きぶりにせよ自分の印象からも近接中心性の方が良いかなと。何故かというと、以下のようなグラフでは
「中心」がノード4になり「メディアン」がノード5になるのですが、どちらがよりグラフの「中心」として妥当か？ということを考えれば何となくピンと来るのではないでしょうか。
次数中心性
今度は次数(degree)に注目した手法を取り上げます。次数とは各ノードに接続しているエッジの数のことで、「次数中心性」(degree centrality)とはより多くのエッジ（＝他ノードとの関係性）を持つノードを高く評価する指標です。{igraph}ではdegree関数で計算できて、有向グラフの場合はmode引数で入次数（流入数）・出次数（流出数）を選ぶことができます（デフォルトは両方の和）。
> g0.deg<-degree(g0) > set.seed(11) > plot(g0,vertex.size=g0.deg*5,main='both',edge.arrow.size=0.5) > g0.deg.in<-degree(g0,mode='in') > set.seed(11) > plot(g0,vertex.size=g0.deg.in*5,main='in',edge.arrow.size=0.5) > g0.deg.out<-degree(g0,mode='out') > set.seed(11) > plot(g0,vertex.size=g0.deg.out*5,main='out',edge.arrow.size=0.5)
set.seed関数で同じ配置になるようにプロットしてみましたが、入出次数を分けるとその値が異なることが描画されたノードの大きさから分かるかと思います。
固有ベクトル中心性
先に挙げた次数中心性は「そのノード自体のエッジの多さ（他者との関係性の多さ）」を評価する指標だったわけですが、『ネットワーク分析』p.48でも暗喩として語られている通り人脈を広げるという観点から言えば「交友関係の広い友人を何人も持っている」ような人、つまり他の次数中心性の高いノード「とつながっている」ノードを評価するような指標というのもあって良いのではないか？ということがいえるわけです。
それを適切に線形代数を用いて演算すると、『ネットワーク分析』pp.48-49に挙げられている通り隣接行列の固有ベクトルを用いて、隣接するノードの中心性を反映させた中心性を得られることが分かります。そのうち特に絶対値最大の固有値に対応する第1固有ベクトルを中心性指標としたものを、「固有ベクトル中心性」(eigenvector centrality)と呼びます。{igraph}ではevcent関数で最大値1に正規化された固有ベクトル中心性を得ることができます。
> par(mfrow=c(1,3)) > set.seed(12) > plot(g0,main='none') > set.seed(12) > plot(g0,vertex.size=g0.deg*5,main='degree') > g0.evcent<-evcent(g0,directed = T) > set.seed(12) > plot(g0,vertex.size=g0.evcent$vector*20,main='evcent')
注目したいのはノード6と7。ノード6はこれまでのどの中心性でも高い値を示していた（多くのエッジを持つ）一方でノード7は流入エッジを2個しか持たず零細扱いだったんですが、固有ベクトル中心性で見るとノード7はその「人気者」ノード6とつながっていることで、例えばノード1よりも高い値を示しています。
PageRank
固有ベクトル中心性はなかなか便利な指標ですが、これをさらに踏み込んでwebサイト間の重要性を算出するために「リンク（流入）」を重視するようにした上で、さらに分離グラフや強連結でない有向グラフにも適用できるようにしたのが、あのSergey BrinとLawrence "Larry" Pageの2人が考案してGoogle検索の基になったPageRankです。
やってることは系列データ分析を知っている人から見ると多分簡単で、要はまず遷移確率行列を作り、さらにグラフ全体を強連結にするために遷移確率行列上で成分0になるところに強制的に何か小さな値を加え、その上で列和が1に正規化されるように非ゼロの成分からは少し確率を割り引いて調整するということをやっています（『ネットワーク分析』pp.52-53）。
{igraph}ではpage.rank関数で計算できます。
> par(mfrow=c(1,3)) > set.seed(12) > plot(g0,vertex.size=g0.deg*5,main='degree') > g0.evcent<-evcent(g0,directed = T) > set.seed(12) > plot(g0,vertex.size=g0.evcent$vector*30,main='evcent') > g0.pr<-page.rank(g0,directed=T) > set.seed(12) > plot(g0,vertex.size=g0.pr$vector*200,main='pagerank')
左から次数中心性、固有ベクトル中心性、PageRankでノードの大きさを描画した結果を並べていますが、ノード1と7の扱いに注目してもらえればその違いが分かるかと。
ボナチッチのパワー中心性
固有ベクトル中心性やPageRankでは「中心性の高いノードとつながるノードの中心性も高くなる」ように設計されていました。でもその逆、つまり「中心性の高いノードとつながるノードの中心性が低くなる」というような指標はあり得ないのでしょうか？ ここで『ネットワーク分析』p.53に面白い喩えが出てきます。
例えば、商取引のネットワークを考えてみよう。頂点は企業や個人など取引の主体であり、辺（ここではとりあえず無向辺とする）は取引関係を表す。ここで次数の高い頂点は、数多くの取引先を持つ主体である。取引先を他より多くもつ主体は、取引において有利な立場に立ち得る。なぜなら、自分は他にも取引相手の選択肢があるということを、交渉において相手への圧力として使えるからである（「安くしてくれないなら他から買う」など）。つまり、関係ある相手の力が強いほど、自分の力は弱くなるということである。
まるで下請けいじめみたいな構図ですが（苦笑）、こういう状況を扱えるように拡張されたのがBonacichが考案したパワー中心性(power centrality)です。その原理の説明はやや面倒なので同書pp.54-55に譲るとして、{igraph}ではbonpow関数で算出できます。
> par(mfrow=c(1,3)) > set.seed(12) > plot(g0,vertex.size=g0.deg*5,main='degree') > g0.evcent<-evcent(g0,directed = T) > g0.pr<-page.rank(g0,directed=T) > set.seed(12) > plot(g0,vertex.size=g0.pr$vector*200,main='pagerank') > g0.bp<-bonpow(g0,exponent=0.2) > set.seed(12) > plot(g0,vertex.size=g0.bp*25,main='power')
左から次数中心性、PageRank、パワー中心性でノードの大きさを描画した結果を示していますが、ここでもやはりノード1と7の結果が興味深いですね。ノード7が流入エッジしかなく他者の動向に無関心な一方で、ノード1が他のノードからの影響を大きく受ける様子が見て取れます。
媒介中心性
これまで挙げてきた中心性はどれも最短経路長や次数に基づいてきましたが、ここではネットワークにおける「媒介」や「伝達」に注目してみます。同書の図4.1に出てくるグラフを再現するとこうなります。
このグラフからノード3を削除すると、グラフ全体が2つに分離してしまうことが分かるかと思います。このような「そのノードを取り除くとそれまで連結であったネットワーク（もしくはその一部分）がバラバラに分離してしまう」ようなノードのことを切断点(cutpoint)と呼び、また上のグラフのノード3と8の間にあるエッジのように「そのエッジを取り除くと連結されていたネットワークが切断されてしまう」ようなエッジのことをブリッジ(bridge)と呼びます。それらは1つとは限らないので、それらを集めて切断集合(cutset)とも呼ぶようです。
というように切断点やブリッジの概念はネットワークにおける「要衝」、即ちある社会ネットワークにおいて異なる集団同士をつなぐ顔の広いキーパーソンだったり、はたまたズバリ交通網で言えばそこがボトルネックになるような重要な地点かもしれない、という捉え方ができるわけですが、これをそのまま用いようとすると要件が厳し過ぎて評価しにくいんですね。そこで、あるノードが他のノード間の最短経路上に位置する「程度」を中心性指標としたものが媒介中心性(betweeness centrality)です。
アルゴリズムに関する実例を含めた丁寧な説明は『ネットワーク分析』pp.57-60に詳説されているので、ここでは割愛します。{igraph}ではbetweeness関数で算出することが可能です。
> par(mfrow=c(1,3)) > set.seed(12) > plot(g0,vertex.size=g0.deg*5,main='degree') > set.seed(12) > plot(g0,vertex.size=g0.pr$vector*200,main='pagerank') > g0.bw<-betweenness(g0,directed = T) > set.seed(12) > plot(g0,vertex.size=g0.bw*4,main='betweeness')
左から次数中心性、PageRank、媒介中心性の順にノードの大きさを描画したものを並べていますが、ノード3が媒介中心性で見ると最も重要なノードになる（それまでの2種類の中心性ではノード6が一番重要だった）ことが分かるかと思います。
情報中心性
最後に、グラフやネットワークを伝ってやってくる「情報」に着目した中心性について。これは伝言ゲームみたいな状況を想像してもらえれば分かるかと思いますが、社会ネットワークの内部で伝わってくる情報というのは必ずしも最短経路を通らず、色々迂回しながらやってくることもあるわけです。そうなると当然ですが情報の精度の低下みたいなことも起きるわけで、これを逆手にとって精度の高い情報を受け取れる人（ノード）の評価を高くするような中心性の定義の仕方も出来ることになります。そのような指標を情報中心性(information centrality)と呼びます。
アルゴリズムの詳説は『ネットワーク分析』pp.60-64をお読みいただくとして、{igraph}にはこれを算出する関数がなく、なおかつその性質上有向グラフでは計算できません。ということでこれまでの結果との比較は難しいのですが、以下のようにして算出することが可能です。以下g0を同じ元のデータフレームから読み込んで無向グラフにし、simplify関数で重複エッジを削除したものをg0uとして計算した結果です。
> g0u IGRAPH U--- 8 17 -- + edges: [1] 1--2 1--3 1--6 1--8 2--5 2--6 3--4 3--5 3--6 3--8 4--5 4--6 4--7 4--8 5--6 5--8 6--7 > A<-get.adjacency(g0u) > A 8 x 8 sparse Matrix of class "dgCMatrix" [1,] . 1 1 . . 1 . 1 [2,] 1 . . . 1 1 . . [3,] 1 . . 1 1 1 . 1 [4,] . . 1 . 1 1 1 1 [5,] . 1 1 1 . 1 . 1 [6,] 1 1 1 1 1 . 1 . [7,] . . . 1 . 1 . . [8,] 1 . 1 1 1 . . . > B<-1-A > B 8 x 8 Matrix of class "dgeMatrix" [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [1,] 1 0 0 1 1 0 1 0 [2,] 0 1 1 1 0 0 1 1 [3,] 0 1 1 0 0 0 1 0 [4,] 1 1 0 1 0 0 0 0 [5,] 1 0 0 0 1 0 1 0 [6,] 0 0 0 0 0 1 0 1 [7,] 1 1 1 0 1 0 1 1 [8,] 0 1 0 0 0 1 1 1 > diag(B)<-rowSums(A)+1 > C<-solve(B) > T<-diag(C) > R<-sum(C[,1]) > 1/(T+(sum(T)-2*R)/nrow(A)) [1] 2.277833 1.943090 2.553084 2.553084 2.566038 2.807285 1.501717 2.275271 > g0u.ic<-1/(T+(sum(T)-2*R)/nrow(A)) > par(mfrow=c(1,3)) > set.seed(12) > plot(g0,vertex.size=g0.pr$vector*200,main='pagerank') > set.seed(12) > plot(g0,vertex.size=g0.bw*5,main='betweeness') > set.seed(12) > plot(g0,vertex.size=4^(g0u.ic),main='information')
左からPageRank、媒介中心性、情報中心性の順にノードの大きさを描き分けた結果です。ノード4・5の重要性が他の指標より高く評価されていることが見て取れると思います。同書によれば、情報中心性は一般に次数が大きく他のノードとの距離が近いノードほど高い値を取るということで、次数中心性と近接中心性の両方とそれぞれ似た側面を持っているとのことです。
C elegans / 『レ・ミゼラブル』のデータの場合
以上のように幾つか中心性の定義について見てきたわけですが、実際のデータセットに対して適用してみるとどうなるか見てみましょう。ということでようやくC elegans神経回路網と『レ・ミゼラブル』人物相関図のデータセットでやってみることにします。まずC elegans。
> g1 IGRAPH D--- 297 2359 -- + attr: id (v/n), label (v/c), value (e/n) + edges: [1] 1-> 2 1-> 3 1-> 4 1-> 5 1-> 6 1-> 7 1-> 8 1-> 9 1-> 10 2-> 11 2->116 2-> 13 2-> 85 2->130 2-> 8 2->131 2->132 [18] 2-> 73 2-> 75 3-> 68 3->152 3->153 3->154 3->155 3->156 3->157 3->158 3->159 3-> 13 3-> 87 3->119 3-> 5 3->160 3->161 [35] 3->162 3->163 3->164 3->165 3->166 3->167 3->168 3->169 3->170 3->185 3->186 3->126 3-> 9 3->174 3->187 3->176 3->177 [52] 3->178 3->179 3->180 3->181 3->182 3->183 3->184 4->152 4->155 4->156 4-> 13 4->118 4->160 4->161 4->162 4->163 4->169 [69] 4->196 4->126 4->174 4->187 4->197 4->179 4->180 4->181 4->183 4->198 4->190 5->152 5->155 5->156 5-> 3 5->119 5->160 [86] 5->161 5->162 5->163 5->169 5->196 5->173 5->174 5->175 5->197 5->179 5->180 5->181 5->183 5->198 5->190 6-> 11 6-> 12 [103] 6-> 13 6-> 4 6-> 14 6-> 15 6-> 9 7-> 28 7-> 51 7-> 35 7-> 24 7-> 36 7-> 48 7-> 49 7-> 44 7-> 47 7-> 73 7-> 89 7-> 95 [120] 7-> 26 7-> 74 7-> 75 7-> 78 7-> 76 8-> 2 8-> 3 8-> 4 8-> 7 8-> 60 8-> 74 9->103 9->109 9->236 9-> 4 9-> 5 9->214 + ... omitted several edges > g1.pr<-page.rank(g1,directed = T,weights = E(g1)$value) > g1.bw<-betweenness(g1,directed = T,weights = E(g1)$value)
C elegansの神経回路網のノードの大きさをPageRank・媒介中心性で描き分けてみたところ、全く見映えの異なるグラフになりました。これは面白いですね。僕自身は脳研究業界出身のくせにC elegansの神経系の知識が全くないので何もコメントできないんですが（おい）、それでもノード305が中心性の種類を変えただけで立ち位置が大幅に変わること、そして媒介中心性で見ると重要なノードが途端に激増することが容易に見て取れます。
次に『レ・ミゼラブル』の人物相関図。
> g2 IGRAPH U--- 77 254 -- + attr: id (v/n), label (v/c), value (e/n) + edges: [1] 1-- 2 1-- 3 1-- 4 3-- 4 1-- 5 1-- 6 1-- 7 1-- 8 1-- 9 1--10 11--12 4--12 3--12 1--12 12--13 12--14 12--15 [18] 12--16 17--18 17--19 18--19 17--20 18--20 19--20 17--21 18--21 19--21 20--21 17--22 18--22 19--22 20--22 21--22 17--23 [35] 18--23 19--23 20--23 21--23 22--23 17--24 18--24 19--24 20--24 21--24 22--24 23--24 13--24 12--24 24--25 12--25 25--26 [52] 24--26 12--26 25--27 12--27 17--27 26--27 12--28 24--28 26--28 25--28 27--28 12--29 28--29 24--30 28--30 12--30 24--31 [69] 31--32 12--32 24--32 28--32 12--33 12--34 28--34 12--35 30--35 12--36 35--36 30--36 35--37 36--37 12--37 30--37 35--38 [86] 36--38 37--38 12--38 30--38 35--39 36--39 37--39 38--39 12--39 30--39 26--40 26--41 25--42 26--42 42--43 26--43 25--43 [103] 12--44 27--44 28--44 29--45 12--45 29--46 47--48 48--49 26--49 28--49 12--49 27--50 12--50 50--51 25--51 50--52 27--52 [120] 12--52 52--53 40--53 52--54 52--55 50--55 27--55 52--56 50--56 40--56 55--56 27--56 12--56 17--56 26--56 42--56 49--56 + ... omitted several edges > g2.pr<-page.rank(g2,directed=F,weights=E(g2)$value) > g2.bw<-betweenness(g2,directed = F,weights = E(g2)$value) > par(mfrow=c(1,2)) > set.seed(25) > plot(g2,layout=layout.fruchterman.reingold,vertex.size=g2.pr$vector*300,main='pagerank') > set.seed(25) > plot(g2,layout=layout.fruchterman.reingold,vertex.size=g2.bw/30,main='betweeness')
『レ・ミゼラブル』の人物相関図でノードの大きさをPageRank・媒介中心性とで描き分けると、非常に面白い知見が見えてきます。最も顕著なのが浮浪児のガヴローシュ。PageRankではそこまで高くない（コゼットやマリウスはたまたクールフェラックよりも低い）のに、媒介中心性で見るとジャン・ヴァルジャンに次いで高いことが分かります。いかに彼が作中の多くの人物同士を結び付けていたか、そして多くの伏線を伴っていたか*5が分析結果だけからでも見て取れますね。同様の傾向がマブーフ老人にも言えます。
一方、ファンティーヌを弄んだトロミエスとその一団がPageRankだとそこそこ高い値をつけているものの、媒介中心性になると揃ってほぼゼロに近いぐらい低くなるのも面白いですね。これも同じことがABCの友の一団についても言えます。あくまでも主役級のバイプレイヤーとしての立場にある、と読み取れそうです。
そんな中、PageRankでも媒介中心性でも似たような位置につけているのが、テナルディエ。主役のジャン・ヴァルジャンとも、第2の主役のマリユスとも、裏の主役のジャヴェールとも、はたまたヒロインのコゼットとも、第2巻以降のほぼ全てで絡んでいるというのがその位置付けに影響しているのではないでしょうか。
