graph-toolチートシート（グラフ構築、統計量編）

この記事ではグラフ解析ライブラリ[graph-tool](https://graph-tool.skewed.de/)で行う典型的な処理をまとめた。
特にグラフの構築と、次数分布などのグラフの基本的な統計量を計算する方法をまとめる。

動作確認環境は以下の通り

- python 3.9.0
- graph-tool 2.35
- numpy, matplotlib

以後のサンプルコードでは、前提条件として以下のモジュールをimportしている。

```py3
import graph_tool.all as gt
import numpy as np
import matplotlib.pyplot as plt
```

# 基本操作

## グラフの構築

### グラフオブジェクトの作成

```py
g = gt.Graph()
# => <Graph object, directed, with 0 vertices and 0 edges, at 0x7fbf8897c100>
```

デフォルトで有向グラフになる。undirected graphを構築するには`directed=False`を引数で指定する

```py3
ug = gt.Graph(directed=False)
```

### ノード追加

```py3
v = g.add_vertex()         # => <Vertex object with index '0' at 0x7fbfd8c718d0>
vlist = g.add_vertex(3)   # 複数のノードの追加
# => [<Vertex object with index '1' at 0x7fbfd8c71690>,  <Vertex object with index '2' at 0x7fbfd8c71b10>,   <Vertex object with index '3' at 0x7fbfd8c71bd0>]

# get the number of vertices
g.num_vertices()   # => 4

# get vertex object by index
v2 = g.vertex(2)   # => <Vertex object with index '2' at 0x7fbfd8c71b10>
```

この例でみたようにNodeをindexから取得するときには `g.vertex(idx)` とすれば取得することができる。
逆にvertex `v` があるときにそこからindexを取得する際には `int(v)` と整数に変換すれば取得できる。

### エッジ追加

```py3
e = g.add_edge(g.vertex(0), g.vertex(2))                 # => 0,2 の間にエッジを作る
( e.source(), e.target() )                # => vertex0, vertex2 をそれぞれ取得

# 短縮してintegerを引数に渡すこともできる
e1 = g.add_edge(3, 1)
e2 = g.add_edge(1, 2)
```

試しにこの状態で可視化してみると以下のようになる。

```py3
gt.graph_draw(g, vertex_text = g.vertex_index)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/11204725-9b85-3916-40bf-0b71d767999d.png)

同じノードペアに対して複数のエッジ(multiedge)を作成したり、始点と終点が同一な self-loopを作ることも同様の手順でできる。

## イテレーション

エッジおよびノードに対してイテレーションする処理は以下のように書ける

```py3
# iterations over vertices
for v in g.vertices():
    for e in v.out_edges():
        print(e.source(), e.target())

# iterations over edges
for e in g.edges():
    print(e.source(), e.target())
```

エッジ数、ノード数の取得

```py3
g.num_vertices()   # => 4
g.num_edges()     # => 3
```

## 属性の追加

- reference : https://graph-tool.skewed.de/static/doc/quickstart.html#property-maps

ノードおよびエッジに属性を指定することができ、それぞれ`VertexProperty`, `EdgeProperty`と呼ばれる。（グラフ全体に対しても属性 GraphProperty を付与することができるが、主に使うのはVertexとEdgeだけだろう）

例えば、重み付きのグラフのエッジの重みは`double`型のEdgePropertyとして指定することができる。
`int`, `double`といった数値的な型だけではなく、`bool`, `string`, `vector<int>`, `vector<double>`, `object` といった様々な型の属性を付与することができる。
たとえばノードの名前を`string`型のVertexPropertyとして保持したり、マルチレイヤーネットワークのリンクのレイヤーの情報を`int`型のEdgePropertyとして持つことができる。

たとえば重み付きグラフを構築する手順は以下の通りになる。

```py3
g = gt.Graph()
g.ep["weight"] = g.new_edge_property("double")                            # `ep` (edge property)の"weight" という名前でdouble型のedge propertyを作成
g.list_properties()
#  =>     weight         (edge)    (type: double)
```

以後、`g.ep.weight` でアクセスでき、さらに`g.ep.weight.a` で内部のnumpy.arrayが取得できる

```py3
g.ep.weight                      # => <EdgePropertyMap object with value type 'double', for Graph 0x7fbf8897c100, at 0x7fbfcb2e3ee0>
g.ep.weight.a                 # PropertyArray([0., 0., 0.])
```

要素にアクセスするには`[]` に edge (vertex) を渡す。
EdgePropertyおよびVertexPropertyはedge(vertex)を引数にして要素アクセスできる配列のようなものだと考えておけば良い。

```py3
e1 = g.edge( g.vertex(0), g.vertex(2) )    # node-(0,2) の間のedgeを取得
g.ep.weight[e]          # => weight of edge e
```

# 基本統計量の計算

以後、以下のサンプルデータを用いて説明する。このサンプルデータには`g.ep.value` に重みが格納されている。

```py3
g = gt.collection.data["celegansneural"]
```

## degree distribution

`vertex_hist` メソッドで取得する。in-degree, out-degree, total-degreeの場合、第２引数に"in", "out", "total" という文字列をそれぞれ渡す。
参考 : https://graph-tool.skewed.de/static/doc/stats.html#graph_tool.stats.vertex_hist

```py3
pk,k = gt.vertex_hist(g, "out")

plt.xlabel("degree")
plt.ylabel("frequency")
plt.plot(k[:-1], pk)               # `k`の最後の１要素は除く
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/f0c780ca-3251-a7e8-d7d5-230803174bc8.png)


`pk`, `k` ともにnumpy.arrayで返るが、`pk`の方がサイズが一つ大きい。
これは`k`の方に、それぞれのbinの最大値、最小値が入るため。プロットするときには`k`の最後の要素を取り除く必要がある。

第二引数に文字列ではなくVertexPropertyを渡すことで、次数以外の任意のVertexPropertyの分布を計算することもできる。

## average_degree

```py3
avg,sdv = gt.vertex_average(g, "out")          # => (7.942760942760943, 0.39915717608995005)
```

第二引数に "in", "out", "total" の文字列を指定すると、それぞれin-degree, out-degree, total-degree の平均値が計算され、平均と標準偏差が返り値として得られる。

また、次数以外にもVertexのPropertyの平均値も同様に計算することができる。

## edge weight distribution

参考: https://graph-tool.skewed.de/static/doc/stats.html#graph_tool.stats.edge_hist

```py3
pw,w = gt.edge_hist(g, g.ep.value)
# =>
(array([0.000e+00, 1.023e+03, 4.250e+02, 2.200e+02, 1.820e+02, 1.070e+02,
        7.000e+01, 6.000e+01, 3.800e+01, 3.800e+01, 3.700e+01, 1.500e+01,
        1.600e+01, 7.000e+00, 1.000e+01, 2.000e+01, 1.100e+01, 2.000e+00,
        1.100e+01, 2.000e+00, 0.000e+00, 1.000e+00, 1.700e+01, 1.000e+01,
        0.000e+00, 9.000e+00, 0.000e+00, 2.000e+00, 4.000e+00, 1.400e+01,
        1.000e+00, 1.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 0.000e+00, 2.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 2.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00,
        0.000e+00, 0.000e+00, 0.000e+00, 0.000e+00, 2.000e+00]),
 array([ 0.,  1.,  2.,  3.,  4.,  5.,  6.,  7.,  8.,  9., 10., 11., 12.,
        13., 14., 15., 16., 17., 18., 19., 20., 21., 22., 23., 24., 25.,
        26., 27., 28., 29., 30., 31., 32., 33., 34., 35., 36., 37., 38.,
        39., 40., 41., 42., 43., 44., 45., 46., 47., 48., 49., 50., 51.,
        52., 53., 54., 55., 56., 57., 58., 59., 60., 61., 62., 63., 64.,
        65., 66., 67., 68., 69., 70., 71.]))
```

`vertex_hist`のedgeバージョン。任意のEdgePropertyの分布を計算することができる。

また、complementary cumulative distribution function は以下のようにプロットできる

```py3
# complementary cumulative distribution function
weights = np.sort(g.ep.value.a)
ccdf = np.linspace(1.0, 0.0, num=g.num_edges(), endpoint=False)
plt.xlabel("weight")
plt.ylabel(r"$P_{>}(w)$")
plt.xscale("log")
plt.yscale("log")
plt.plot(weights, ccdf)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/8539536d-2c5e-63ec-a445-21dec6222c39.png)

## average edge weight

`vertex_average`のedgeバージョン。

```py3
gt.edge_average(g, g.ep.value)
```

参考 : https://graph-tool.skewed.de/static/doc/stats.html#graph_tool.stats.edge_average

## node strength

node strengthは自分でイテレートして計算する必要がある。
"double"のvertex_propertyを作成して、その中にnode strengthを格納する。

```py3
out_strength = g.new_vertex_property("double")
for v in g.vertices():
    weights = [g.ep.value[e] for e in v.out_edges()]
    out_strength[v] = np.sum(weights)

ps,s = gt.vertex_hist(g, out_strength)

# plot of complementary cumulative distribution function
s = np.sort(out_strength.a)
ccdf = np.linspace(1.0, 0.0, num=g.num_vertices(), endpoint=False)
plt.xlabel("s")
plt.ylabel(r"$P_{>}(s)$")
plt.xscale("log")
plt.yscale("log")
plt.plot(s, ccdf)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/ee78d40e-e5cd-c4b4-6794-63714ba699c7.png)

## clustering coefficient

参考 : https://graph-tool.skewed.de/static/doc/clustering.html#graph_tool.clustering.global_clustering

```py3
gt.global_clustering(g)              # => (0.19795997218143885, 0.027169317947021772)
```

## clustering spectrum c(k)

nodeにおける属性間の相関をみるには`avg_combined_corr`を使う。
degreeとlocal clustering coefficientだけでなく、任意のVertexProperty間の相関を計算できる。
参考 : https://graph-tool.skewed.de/static/doc/correlations.html#graph_tool.correlations.avg_combined_corr

```py3
# correlation between k and local clusteirng
gt.local_clustering(g)                 # => double type の VertexProperty

h = gt.avg_combined_corr(g, "total", gt.local_clustering(g))
plt.errorbar( h[2][:-1], h[0], yerr=h[1], fmt="o")
```

`h` は (bin, average, stddev) のタプル

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/e0338158-5b68-ec4b-22df-fb9c691cc767.png)


## degree correlation

参考 : https://graph-tool.skewed.de/static/doc/correlations.html#graph_tool.correlations.avg_neighbor_corr

隣接ノード間のVertexPropertyの相関を計算することができる。文字列"in", "out", "total" を引数に渡すと次数相関を計算できる。

```py3
# average degree correlation
knn = gt.avg_neighbor_corr(g, "total", "total")
plt.xlabel("k")
plt.ylabel("average neighbor degree")
plt.errorbar( knn[2][:-1], knn[0], yerr=knn[1], fmt="o")
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/35e5ae9f-c3e9-370d-0068-219644a706fe.png)

## centrality

参考 : https://graph-tool.skewed.de/static/doc/centrality.html

さまざまなcentralityの指標を計算できるが、ここではpagerankを計算してみよう。
`gt.pagerank`でpagerankを計算してVertexPropertyとして取得できる。その値に応じて色をつけて描画してみる。

```py3
prc = gt.pagerank(g, weight = g.ep.value)
gt.graph_draw(g, vertex_fill_color = prc, pos = g.vp.pos)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28792/9dd1b25f-7cf2-e36d-d17d-160dba89ea11.png)

pagerankの他にもbetweeness centrality, Katz centrality, eigen-vector centrality など一通り揃っている。