渋谷駅前で働くデータサイエンティストのブログ

元祖「六本木で働くデータサイエンティスト」です / 道玄坂→銀座→東京→六本木→渋谷駅前

グラフ・ネットワーク分析で遊ぶ(5):何となくNIPS2015の共著者グラフを描いてみた

先日閉幕したNIPS2015ですが*1、そう言えばサイト上に全論文のタイトル&著者一覧があるなと思い出したのでした。



ということで、これまでの4回のグラフ・ネットワーク分析特集で学んだことをこの著者一覧に応用してみようかと思います。やったことはごくごく単純、共著者関係だけを抽出してそれをグラフにしてみるというだけのもの。ぶっちゃけ何の奇もてらわずただ可視化しただけなので、程度が低いのはご容赦くださいということで。


ちなみにこの業界にやってきて3年半になりますが、未だに僕はこの業界の研究者の有名人のお歴々のことを殆ど何も知りません*2。事前知識なしで適当にやっている結果だということをご承知あれ。


とりあえず可視化してみる


個々の論文内で全ての共著者の「フルネーム+所属名」同士の組み合わせから成る無向グラフになるようなエッジリストをPythonで前処理しながら作ります*3。単著の人は削除します。そうすると1740行のエッジリストが出来上がるはずなので、これを{igraph}で可視化してみます。

> g<-graph.edgelist(as.matrix(d1),directed=F)
# d1は1740行のエッジリストを格納したデータフレーム
> plot(g,vertex.label='',vertex.size=0.5,edge.width=3)

f:id:TJO:20151215141549p:plain


今回に限ってはFruchterman - Reingoldでやるととんでもないことになる*4ので一旦こちらで。もう見た瞬間に殆ど連結してないグラフ構造なのが分かります。まぁ、共著者って意味ではそこまで皆さんつながりませんわな。


非連結のまま中心性を見る


第3回の記事で見たように、非連結の場合でもある程度色々内部的に工夫することで中心性を算出することができて、実際{igraph}ではそうしていることが多いです。試しに非連結のままPageRankと媒介中心性のトップ20だけ見てみましょう。

> g.pr<-page.rank(g,directed=F)
> g.bw<-betweenness(g,directed=F)
> head(sort(g.pr$vector,decreasing = T),n=20)
Pradeep Ravikumar, University of Texas at Austin                    Han Liu, Princeton University 
                                     0.003631965                                      0.003212943 
        Le Song, Georgia Institute of Technology                  Lawrence Carin, Duke University 
                                     0.003085846                                      0.002893141 
 Inderjit Dhillon, University of Texas at Austin                       Yoshua Bengio, U. Montreal 
                                     0.002679262                                      0.002649978 
      Zoubin Ghahramani, University of Cambridge                              Josh Tenenbaum, MIT 
                                     0.002629387                                      0.002598333 
                        Honglak Lee, U. Michigan                              Ryan Adams, Harvard 
                                     0.002544551                                      0.002471264 
                     Michael Jordan, UC Berkeley               Zhaoran Wang, Princeton University 
                                     0.002392069                                      0.002136090 
                           Shie Mannor, Technion     Parag Singla, Indian Institute of Technology 
                                     0.001941880                                      0.001908881 
                               Zoltan Szabo, UCL      Ruslan Salakhutdinov, University of Toronto 
                                     0.001898561                                      0.001884744 
                           Oriol Vinyals, Google                  Yann LeCun, New York University 
                                     0.001881835                                      0.001868760 
                           Antonio Torralba, MIT                  David Blei, Columbia University 
                                     0.001854594                                      0.001834747 
> head(sort(g.bw,decreasing = T),n=20)
               Haipeng Luo, Princeton University                 Elad Hazan, Princeton University 
                                        364.0000                                         347.0000 
Pradeep Ravikumar, University of Texas at Austin                  Daniel Hsu, Columbia University 
                                        339.3333                                         319.0000 
                       Csaba Szepesvari, Alberta                   Nagarajan Natarajan, UT Austin 
                                        293.0000                                         276.0000 
      John Langford, Microsoft Research New York         Anna Choromanska, Courant Institute, NYU 
                                        231.0000                                         204.0000 
               Alekh Agarwal, Microsoft Research              Robert Schapire, MIcrosoft Research 
                                        189.0000                                         189.0000 
                           Shie Mannor, Technion             Ambuj Tewari, University of Michigan 
                                        179.3333                                         174.0000 
                 Yann LeCun, New York University                 Branislav Kveton, Adobe Research 
                                        148.0000                                         144.0000 
                             Josh Tenenbaum, MIT                 Prateek Jain, Microsoft Research 
                                        125.0000                                         124.0000 
         Jacob Abernethy, University of Michigan  Inderjit Dhillon, University of Texas at Austin 
                                        124.0000                                         116.6667 
                 Lawrence Carin, Duke University      Ruslan Salakhutdinov, University of Toronto 
                                        115.4333                                         104.0000


ビッグネームがちらほら見えますね。こんな感じで、非連結のままでもそれなりの情報を得ることは出来ます。と言っても既に元のグラフの可視化を見た通りで、この状況ではあまり大きな意味のある分析ではありませんが。。。


グラフを連結部分のみに切断する


なので、これ以上突っ込んだ分析をするには連結グラフになるまでばらす必要があります。これは{igraph}のdecompose.graph関数でいけます。

> g1<-decompose.graph(g)
> length(g1)
[1] 224


パラメータ次第ですが、224の連結サブグラフに切断できるはずです。そこで、その中でもそこそこノード数の大きいものを選んでこようかと思います。

> idx<-cbind(rep(0,length(g1)),rep(0,length(g1)))
> for (i in 1:length(g1)){
+     idx[i,1]<-i
+     idx[i,2]<-length(V(g1[[i]])$name)
+ }
> summary(idx[,2])
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  2.000   2.000   3.000   4.719   5.000  41.000 
> hist(idx[,2])
# プロット省略:20以上が特に少ないことが見て取れる
> idx[idx[,2]>20,]
     [,1] [,2]
[1,]    6   41
[2,]   20   23
[3,]   54   36


20以上のノードを含むサブグラフが3個あることが分かりました。とりあえず大きい方から見ていきましょう。


サブグラフについて掘り下げてみる

一番大きかった6番目のサブグラフ

> set.seed(2015)
> plot(g1[[6]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2)

f:id:TJO:20151215142523p:plain


LeCun先生が見えますね。これをスピングラス法によるコミュニティ検出でコミュニティを分けるとこうなります。

> g1_6.com<-spinglass.community(g1[[6]],spins=15)
> set.seed(2015)
> plot(g1[[6]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2,vertex.color=g1_6.com$membership)

f:id:TJO:20151215142642p:plain


最後に、ページランクと媒介中心性でノードの大きさを変えてみます。

> g1_6.pr<-page.rank(g1[[6]],directed=F)
> g1_6.bw<-betweenness(g1[[6]],directed=F)
> par(mfrow=c(1,2))
> set.seed(2015)
> plot(g1[[6]],layout=layout.fruchterman.reingold,margin=0.2,vertex.color=g1_6.com$membership,vertex.size=g1_6.pr$vector*300,main='pagerank')
> set.seed(2015)
> plot(g1[[6]],layout=layout.fruchterman.reingold,margin=0.2,vertex.color=g1_6.com$membership,vertex.size=g1_6.bw*0.05,main='betweeness')

f:id:TJO:20151215143038p:plain


可視化しただけでも直感的に分かりやすいグラフなんですが、こうして中心性指標をノードの大きさとして強調してみるとさらに分かりやすくなった感がありますね。


次に大きかった54番目のサブグラフ

> par(mfrow=c(1,1))
> set.seed(2015)
> plot(g1[[54]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2)

f:id:TJO:20151215143331p:plain


台湾大の人たちが見えますね。これもスピングラス法でコミュニティ検出してみましょう。

> g1_54.com<-spinglass.community(g1[[54]],spins = 15)
> set.seed(2015)
> plot(g1[[54]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2,vertex.color=g1_54.com$membership)

f:id:TJO:20151215143552p:plain


最後に、ページランクと媒介中心性でノードの大きさを変えてみます。

> g1_54.pr<-page.rank(g1[[54]],directed=F)
> g1_54.bw<-betweenness(g1[[54]],directed=F)
> par(mfrow=c(1,2))
> set.seed(2015)
> plot(g1[[54]],layout=layout.fruchterman.reingold,margin=0.3,vertex.color=g1_54.com$membership,vertex.size=g1_54.pr$vector*200,main='pagerank')
> set.seed(2015)
> plot(g1[[54]],layout=layout.fruchterman.reingold,margin=0.3,vertex.color=g1_54.com$membership,vertex.size=g1_54.bw*0.1,main='betweeness')

f:id:TJO:20151215143830p:plain


そう言えばこの中に結構偉い先生いらっしゃるなー、とここまで気付いた業界知識ゼロの僕でした(汗)


3番目に大きかった20番目のサブグラフ

> par(mfrow=c(1,1))
> set.seed(25)
> plot(g1[[20]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2)

f:id:TJO:20151215144020p:plain


トロント大とMITの人たちが多いですね。これもスピングラス法でコミュニティ検出してみます。

> g1_20.com<-spinglass.community(g1[[20]],spins = 15)
> set.seed(25)
> plot(g1[[20]],vertex.size=5,layout=layout.fruchterman.reingold,margin=-0.2,vertex.color=g1_20.com$membership)

f:id:TJO:20151215144218p:plain


最後に、ページランクと媒介中心性でノードの大きさを変えてみます。

> g1_20.pr<-page.rank(g1[[20]],directed=F)
> g1_20.bw<-betweenness(g1[[20]],directed=F)
> par(mfrow=c(1,2))
> set.seed(2015)
> plot(g1[[20]],layout=layout.fruchterman.reingold,margin=0.2,vertex.color=g1_20.com$membership,vertex.size=g1_20.pr$vector*300,main='pagerank')
> set.seed(2015)
> plot(g1[[20]],layout=layout.fruchterman.reingold,margin=0.2,vertex.color=g1_20.com$membership,vertex.size=g1_20.bw*0.3,main='betweeness')

f:id:TJO:20151215144446p:plain


これもまぁ見たまんまのグラフなんですが、それぞれの中心性でノードの大きさを変えて強調してやるとより個々の著者の立ち位置が分かりやすくなります。


雑感など


これをやれば少しは業界地図が分かるようになるかと思ったんですが、非連結グラフが多過ぎてこれでは無理だということが分かりましたorz

*1:僕は参加してません

*2:Vapnik御大、Hinton先生、Bengio先生、LeCun先生、Ng氏、Platt、Smolaまでは分かるとかいうかなりの低レベル

*3:僕の汚いPythonコードを出すのは気が引ける&大して難しくないので皆さんご自身でどうぞ

*4:L字に並んでしまって訳分からん