igraphとは

igraph は R のパッケージの一つで，グラフの可視化や，中心性解析，コミュニティ検出といったネットワーク分析を簡単に行うことができるため非常に便利です．

igraphのインストールと読み込みは以下を実行します．

install.packages("igraph")
library(igraph)

本記事では，(1)グラフの構築，(2)グラフの可視化，(3)中心性解析，(4)コミュニティ検出について簡単に説明したいと思います．

(1)グラフの構築

まずはigraphを用いてグラフを構築します．構築方法は(a)ファイルから読み込む，(b)igraphの関数を用いた生成の2通りが存在します．

(a)ファイルから読み込む

igraphでは，network data や SNAP といったデータセットから直接グラフを構築することができます．

ファイルから読み込む場合は，データのフォーマットに応じてグラフの構築方法が異なります．
ファイル拡張子が
“edgelist”, “pajek”, “ncol”, “lgl”, “graphml”, “dimacs”, “graphdb”, “gml”, “dl”
の場合は直接グラフを構築し，それ以外の場合は一度データフレームに変換し，データフレームをグラフに変換します．

（例）gmlフォーマット
gmlは Graph Modeling Language の略であり，グラフを記述するためのフォーマットです．

network data の American College footballというデータセットを用いて例を示します．

read.graph() 関数を用いて直接グラフを構築します．

fb_graph <- read.graph("./football.gml", format="gml")

引数の format にデータフォーマットを記述します．
ここでは gml フォーマットを扱っていますが，データに応じて "edgelist"，"pajek"などに書き換えて使用します．

（例） txtファイル
SNAP の wiki-Vote というデータセットを用いて例を示します．

wiki-Vote.txt はエッジのソースノードとターゲットノードがタブで区切られており，データフレームとして読み込むことができます．

wiki-Vote.txt

# Directed graph (each unordered pair of nodes is saved once): Wiki-Vote.txt 
# Wikipedia voting on promotion to administratorship (till January 2008). Directed edge A->B means user A voted on B becoming Wikipedia administrator.
# Nodes: 7115 Edges: 103689
# FromNodeId	ToNodeId
30	1412
30	3352
30	5254
30	5543
30	7478
：
8150	8276
8274	8275

このようなデータの読み込みは，標準の read.table() 関数を用います．

> vote <- read.table("wiki-Vote.txt", skip=4, header=FALSE)
> head(vote, 5)
  V1   V2
1 30 1412
2 30 3352
3 30 5254
4 30 5543
5 30 7478

wiki-Vote.txt は最初の4行にコメントが記載されているため，skip=4を指定してコメントを読み飛ばします．

また，ソースノードとターゲットノードの属性が書いていないため、header=FALSE を指定します．

次に，データフレームをグラフに変換します．
igraph の graph.data.frame() 関数を実行します．

vote_graph <- graph.data.frame(vote, directed=TRUE)

引数にデータフレームと，有向グラフかどうかを示す directed を指定します．
（directed が TRUE のとき有向グラフ， FALSE のとき無向グラフとなります．）

(b)関数で生成する

データセットを用意することなく，igraph の関数を用いることによってグラフを生成することができます．

生成したいグラフのモデルに応じて様々な関数が用意されています．

（例）ランダムグラフ
ランダムグラフは任意の頂点間にエッジが存在する確率が一定であるグラフです．

生成には random.graph.game() 関数を用います．

random_graph <- random.graph.game(n=100, p=0.2)

nはノード数，pは任意の頂点間にエッジが存在する確率です．

（例）バラバシ・アルバートモデル
バラバシ・アルバートモデルは，一部のノードが大きな次数を持っている一方で，大半のノードの次数が小さいようなグラフのモデルです．
グラフ理論の言葉で言うと，「スケールフリー性」を持つグラフです．

Webグラフといった現実世界に現れる多くのグラフがこの性質を持っているため，このモデルのグラフを解析することは良い練習になると思います．

生成には barabasi.game() 関数を用います．

ba_graph <- barabasi.game(n=100)

nはノード数です．

(2)グラフの可視化

plot()関数を用いることで，構築したグラフを出力することができます．

ここでは，(1)で構築した American College football のグラフ fb_graph と，バラバシ・アルバートモデルの ba_graph を出力したいと思います．

plot(fb_graph, vertex.label=NA, vertex.size=4, edge.arrow.size=0.2, layout=layout.fruchterman.reingold)

plot(ba_graph, vertex.label=NA, vertex.size=4, edge.arrow.size=0.2, vertex.color="lightblue", layout=layout.fruchterman.reingold)

上のグラフが fg_graph，下のグラフが ba_graph です．

plot() 関数は引数を与えることで，グラフの出力の調整を行うことができます．
（とても細かいので，詳しくはマニュアルを参照してください．）

上の例では，ノードのラベル（vertex.label)，ノードのサイズ(vertex.size)，エッジのサイズ（edge.arrow.size），ノードの色(vertex.color），グラフレイアウト（layout）を指定しました．

グラフレイアウトはノードの配置を指定するものです．
（例えば、layout.circle と指定すると全てのノードが円状に配置されます．）

(3)中心性解析

中心性とはグラフにおけるノードの重要性を議論するための指標です．
ソーシャルネットワークを例に考えてみますと，多くの人からフォローされ，発言力の高い人物は重要な人物であると言えることができると思います．

すなわち，中心性解析はグラフの中で重要なノードを発見するための手法とも言うことができます．

中心性には次数中心性などいくつか種類がありますが，本記事では PageRank の例を用いて考えます．

PageRank はグラフの各ノードの重要度を測ることができ，Googleの検索エンジンで用いられていることでも有名なアルゴリズムです．

igraph では，page.rank() 関数で簡単に PageRank を求めることができます．

バラバシ・アルバートモデルの ba_graph に対して PageRank を計算した例を以下に示します．

ba_graph.pr <- page.rank(ba_graph, directed=TRUE)

各ノードの PageRank 値は ba_graph.pr$vector に格納されます．

igraph では，得られた PageRank 値に応じてノードのサイズを変えてグラフを出力することもできます．

plot(ba_graph, vertex.label=NA, vertex.size=ba_graph.pr$vector*50, edge.arrow.size=0.2, vertex.color="lightblue", layout=layout.fruchterman.reingold)

引数 vertex.size に ba_graph.pr$vector*50 を指定していますが，こうすることで PageRank 値が高いノードほど大きく表示されるようになります．

(4)コミュニティ検出

コミュニティ検出とは，ノードの関連性に基づき，グラフをいくつかのグループに分ける手法です．
（クラスタリングと言った方がわかりやすいかと思います．）

コミュニティ検出の方法もいくつか種類が存在しますが，ここでは固有ベクトルに基づいた手法を紹介します．
（マニュアルはこちら）

igraph では leading.eigenvector.community() 関数で簡単に計算することができます．

fb_graph.com <- leading.eigenvector.community(fb_graph);

ここでは American College football のグラフ fb_graph に対して計算した例を示します．

plot(fb_graph, vertex.label=NA, vertex.size=4, edge.arrow.size=0.2, vertex.color=fb_graph.com$membership, layout=layout.fruchterman.reingold)

引数 vertex.color に fb_graph.com$membership を指定することで，得られたコミュニティごとに異なる色で表示されます．

まとめ

igraphを用いて，グラフの可視化や中心性解析，コミュニティ検出といったネットワーク分析を行うことができました．

また，実行速度の問題で大規模グラフの可視化が難しそうなので，今後はigraph以外のライブラリも探してみたいと思いました．
何かオススメがあったら教えていただければと思います．

参考

次のページを参考に記事を作成いたしました．
とてもわかりやすいので，是非こちらも参照ください．

・グラフ・ネットワーク分析で遊ぶ(3)：中心性(PageRank, betweeness, closeness, etc.)
http://tjo.hatenablog.com/entry/2015/12/09/190000

・グラフ・ネットワーク分析で遊ぶ(4)：コミュニティ検出（クラスタリング）
http://tjo.hatenablog.com/entry/2015/12/14/190000

・ネットワーク分析をもうちょっと勉強
http://deta.hateblo.jp/entry/2013/05/01/053426

・R+igraph
https://sites.google.com/site/kztakemoto/r-seminar-on-igraph---supplementary-information

・複雑ネットワーク
https://ja.wikipedia.org/wiki/%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF