共通の知人数でエッジを重み付けする

はじめに：構造的埋め込みについて

構造的埋め込み(structural embeddedness) とは、「ある紐帯がどれほど社会構造の中に埋め込まれているか」を表す概念です。これは「両者の間で共通の知人がどれだけいるか」によって測定されます。

愛着や相互作用の数など、直接的にノードペアの関係性の深さを観測できない時、構造的埋め込みの度合いが紐帯の強度として使用されることがあります。ネットワークの構造的特徴が、エッジの重みとして畳み込まれるわけです。

これを扱った研究としては、古典的には以下のような論文があります。こちらの論文では、共通の知人の数が、好き嫌いや過ごす時間よりも時間安定的であることが明らかにされています。

www.sciencedirect.com

この概念はグラノヴェッターの社会的埋め込み(social embeddedness)概念に由来しています。社会的埋め込みは「家族関係」「婚姻関係」などの紐帯の性質や社会的状況までカバーする概念ですが、構造的埋め込みは、社会的埋め込み概念のなかでも、特にその構造的側面に着目したものと言えます。

問題は、共通の知人数をどう計算するかです。 愚直に二重ループを回してもいいのですが、隣接行列の性質をうまく利用すると、行列計算に持ち込めるため、たいへん高速に計算することが可能です。

それは、隣接行列をn乗した行列の各成分はi-j間のn-pathの数に等しいという性質です(ループなしの無向グラフの場合)。ことn=2の時、n-pathの数はノードiとノードjが共通してつながっているノードの数と同じです。

実際にやってみる

ライブラリ読み込み

library(igraph)
library(ggnetwork)
library(tidyverse)

ランダムグラフ生成して可視化

set.seed(111)
network <- erdos.renyi.game(15,0.3)

original_layout <- layout.fruchterman.reingold(network)

gnet <- ggnetwork(network,layout = original_layout)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodes(size=3)
g <- g + geom_nodelabel(aes(label = vertex.names))
g <- g + theme_blank()
g <- g + ggtitle("ORIGINAL NETWORK")
g

もともとの隣接行列

adjmat <- as_adjacency_matrix(network)
adjmat

15 x 15 sparse Matrix of class "dgCMatrix"
                                   
 [1,] . . 1 . . . . . . 1 1 1 . . .
 [2,] . . . . . . . . . . . . 1 1 1
 [3,] 1 . . 1 1 . . . . 1 . 1 1 1 1
 [4,] . . 1 . . . . . . . . . . 1 .
 [5,] . . 1 . . . 1 . . . 1 . 1 . .
 [6,] . . . . . . . 1 1 . . 1 1 . .
 [7,] . . . . 1 . . 1 . . . . . . .
 [8,] . . . . . 1 1 . 1 . . . . . .
 [9,] . . . . . 1 . 1 . . 1 1 . 1 1
[10,] 1 . 1 . . . . . . . 1 . . 1 .
[11,] 1 . . . 1 . . . 1 1 . . . . 1
[12,] 1 . 1 . . 1 . . 1 . . . . . .
[13,] . 1 1 . 1 1 . . . . . . . . .
[14,] . 1 1 1 . . . . 1 1 . . . . .
[15,] . 1 1 . . . . . 1 . 1 . . . .

続いてこれを自乗します。Rで行列積を計算する時は %*% 演算子を使います。

squared_adjmat <- adjmat %*% adjmat
squared_adjmat

15 x 15 sparse Matrix of class "dgCMatrix"
                                   
 [1,] 4 . 2 1 2 1 . . 2 2 1 1 1 2 2
 [2,] . 3 3 1 1 1 . . 2 1 1 . . . .
 [3,] 2 3 8 1 1 2 1 . 3 2 4 1 1 2 .
 [4,] 1 1 1 2 1 . . . 1 2 . 1 1 1 1
 [5,] 2 1 1 1 4 1 . 1 1 2 . 1 1 1 2
 [6,] 1 1 2 . 1 4 1 1 2 . 1 1 . 1 1
 [7,] . . 1 . . 1 2 . 1 . 1 . 1 . .
 [8,] . . . . 1 1 . 3 1 . 1 2 1 1 1
 [9,] 2 2 3 1 1 2 1 1 6 2 1 1 1 . 1
[10,] 2 1 2 2 2 . . . 2 4 1 2 1 1 2
[11,] 1 1 4 . . 1 1 1 1 1 5 2 1 2 1
[12,] 1 . 1 1 1 1 . 2 1 2 2 4 2 2 2
[13,] 1 . 1 1 1 . 1 1 1 1 1 2 4 2 2
[14,] 2 . 2 1 1 1 . 1 . 1 2 2 2 5 3
[15,] 2 . . 1 2 1 . 1 1 2 1 2 2 3 4

こうしてできた行列は、各成分がi-j間の相異なる2-pathの数になっています。当然ですが、対角成分は、各ノードの次数と等しくなります。

最後に、もともとエッジがあったところにだけ重み付けするため、隣接行列との要素積を計算し、最後に隣接行列との要素和を計算します。

weighted_adjmat <- squared_adjmat * adjmat + adjmat
weighted_adjmat

> weighted_adjmat
15 x 15 sparse Matrix of class "dgCMatrix"
                                   
 [1,] . . 3 . . . . . . 3 2 2 . . .
 [2,] . . . . . . . . . . . . 1 1 1
 [3,] 3 . . 2 2 . . . . 3 . 2 2 3 1
 [4,] . . 2 . . . . . . . . . . 2 .
 [5,] . . 2 . . . 1 . . . 1 . 2 . .
 [6,] . . . . . . . 2 3 . . 2 1 . .
 [7,] . . . . 1 . . 1 . . . . . . .
 [8,] . . . . . 2 1 . 2 . . . . . .
 [9,] . . . . . 3 . 2 . . 2 2 . 1 2
[10,] 3 . 3 . . . . . . . 2 . . 2 .
[11,] 2 . . . 1 . . . 2 2 . . . . 2
[12,] 2 . 2 . . 2 . . 2 . . . . . .
[13,] . 1 2 . 2 1 . . . . . . . . .
[14,] . 1 3 2 . . . . 1 2 . . . . .
[15,] . 1 1 . . . . . 2 . 2 . . . .

こうして作成した重み付き隣接行列を実際に可視化してみます。igraphでネットワークオブジェクトを作成した後に、重みから1を引きます。共通の知人がいないエッジは重みが0と表示されるようになります。

weighted_network <- graph.adjacency(weighted_adjmat,
                                    mode = "undirected",
                                    diag = FALSE,
                                    weighted = TRUE)
E(weighted_network)$weight <- E(weighted_network)$weight - 1

gnet <- ggnetwork(weighted_network,layout = original_layout)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodelabel(aes(label=vertex.names))
g <- g + geom_edgelabel(aes(label=weight))
g <- g + theme_blank()
g <- g + ggtitle("WEIGHTED NETWORK")
g

タコのレモン和え

昨日の宅飲みに持っていったもの。

晩冬ですが、春を飛び級して夏を感じさせる一品です。 簡単に作れる割に見た目が鮮やかなので、宅飲みにはとても重宝します。 香りのキーとなる生のイタリアンパセリは手に入らない場合も多いと思いますが、その時はドライタイプのものを死ぬほど入れることで代用できます（もちろん風味は落ちます）。

元ネタはこちらのレシピですが、より手軽に作れるようにアレンジしています。 abebeeno.blogspot.com

必要なもの

• ジップロック（あるいはそれに準ずる袋）
• タコ（生食用、茹でてあるもの）300gくらい？
  • 一口大に切っておく
• イタリアンパセリ（生）5,6枝
  • 葉っぱの部分だけをちぎり、ざっくりと刻んでおく
• レモン 1個
  • 皮ごと使うので、表面はよく洗っておく
  • 縦に4等分する
    • 1/4個は薄くいちょう切りにしておく
    • 2/4個は漬ける用の絞り汁に使う
    • 1/4個は食べる直前の絞り汁用
• にんにく 1片
  • 細かくみじん切りにしておく
• オリーブオイル
• 塩・こしょう

工程

• ジップロックににんにく、イタリアンパセリ、タコ、いちょう切りにしたレモンを入れる
• オリーブオイルと、レモン半個分の絞り汁を入れる
• 塩・こしょうを入れる
• ジップロックの中で揉み込んで、空気を抜いたら冷暗所で1,2時間ほど寝かせ、味を染み込ませる。
  • 味が染み込むのは温度ではなく時間オーダーの現象(参考： 冷めるときに味が染み込む理由 | エンジニアのメソッド)なので、冷やす必要はないですが、よく冷やしたほうがお酒に合います。
  • 寝かせている間、適当なタイミングで1個つまんで味見して、塩気が足りなかったら塩を足す
• 皿に盛り付けて、最後に1/4個分のレモン果汁を回しかけて完成。

タコはもちろんのこと、オイルソースにバゲットをつけて食べると最高です。

Generate Random Graphs with Fixed Degree Distribution (R igraph)

※This article is translated version of 次数分布を固定してランダムグラフを生成する - SNAGeek

Introduction

There are situations when you want to evaluate statistically the whole network statistics, such as global clustering coefficient, average path length.

In such a case, you can use a method of comparing network statistics with that generated from a null model to find out how it statistically deviates . What is commonly used is to compare it with a random graph having an degree distribution same as the original graph.

In this article, we introduce a method to generate random graph by fixing the degree distribution, using R igraph package.

Loading graphs

For this case, we use karate club network data attached to igraph by default.

library(igraph)
library(tidyverse)
library(ggnetwork)

net <- graph("Zachary")

Visualization

Let's visualize the graph with ggnetwork. We will visualize the random graph later, but we must first acquire the coordinates of the node in the original graph so that we can use it again later.

hruchterman_reingold = layout.fruchterman.reingold(net)
gnet <- ggnetwork(net, layout = hruchterman_reingold)
g <- ggplot(gnet, aes(x = x, y = y, xend = xend, yend = yend))
g <- g + geom_edges(size = 0.5)
g <- g + geom_nodes(size = 3, col = "blue")
g <- g + geom_nodelabel_repel(aes(label = vertex.names))
g <- g + ggtitle("original karate club network")
g <- g + theme_blank()
g

Here is the image. Somehow, it seems that the clustering coefficient is high and the average path length is large, at first glance.

Zachary Karate Club Network

When actually calculating it

> cc_original <- transitivity(net) # global clustering factor
> pl_original <- mean_distance(net) # average path length
>
> cc_original
[1] 0.2556818
> pl_original
[1] 2.4082

Well, how far is these values ​​characteristic?

Random graph generation

In igraph it can be generated with sample_degseq(in.deg). in.deg is a vector of degree of each node. In the case of an undirected graph, only in.deg., In case of directed graph, in.deg the distribution of in-degree, out.deg specifying the distribution of out-degree.

Acquire the degree distribution of the original network.

degree_dist <- igraph::degree(net)
g <- ggplot(data = tibble(degree = degree_dist), aes(x = degree))
g <- g + geom_histogram()
g <- g + ggtitle("degree distribution of karate club network")
g

Degree distribution of original network

The method of generating the graph is specified by the optional argument. There are three kinds of igraph, simple(default),simple.no.multiple, vl.

simple

A method of generating n edges appropriately from the node and combining them. Although it is a simple method, multiple edges and self loops occur. This is because the possibility of duplication of the edge partners of the two nodes to be joined together is not excluded.

degree_dist <- igraph::degree(net)
simple_random_net <- sample_degseq(degree_dist)

In the graph obtained in this way, it can be confirmed that if the simplify() `and multiple edges and self-loops are eliminated, the number of edges is slightly reduced.

> simple_random_net
IGRAPH 3c731f6 U --- 34 78 - Degree sequence random graph
+ attr: name(g / c), method(g / c)
+ edges from 3c731f6:
 [1] 2 - 6 1- 1-4 3--17 - - 28 1- - 34 19 - - 28 12 - 33 7 - - 18 9 - - 29 21 - 33 5 - 34 1 - 14 3--33 1 - 28 8 - 8 22 - - 27 25 - 31
[18] 7 - 32 9 - 33 1 - 22 19 19 - 20 11 - 34 1 - 20 2- - 7 4- - 34 1 - 30 18 - 34 4 - 32 2- 5 10 - 34 1 - 1 - 6 - 1 14 1 - 3 9 - 17
[35] 6 - 33 8 - - 24 5 - 34 16 - 30 4 - 2 3 1 - 31 33 - 34 3 - 24 4 25 - 27 33 - 34 2 - 26 1- 3 3-33 33 28 - 34 26 - 33 1 - 3 23 - 34
[52] 4--29 14 - 32 10 - 34 2 - 29 9 - 32 11 - 20 34 - 34 3 - 2 4 11 - 25 5 - 1 5 3 - 1 15 1- 14 2- 1-31 1 - 1 6 7 - - 24 2- - 34 3 - 13
[69] 21 - 32 6 - 32 24 - 30 1 - 2 - 2 - 34 13 - 33 8 - 30 33 - 33 9 - 34 26 - 31
> simplify(simple_random_net, remove.multiple = TRUE, remove.loops = TRUE)
IGRAPH 40 d 3 c 01 U --- 34 65 - Degree sequence random graph
+ attr: name(g / c), method(g / c)
+ edges from 40 d 3 c 01:
 [1] 1 - 2 - 1 - - 3 1 - 4 - 1 - 1 14 1 - 1 6 1 - 20 - 1 - 22 22 1 - 28 1- 1-30 1-31 1-34 2- 5 2-- 6 2-- 7 2--26 2--29 2--31
[18] 2 - 34 - 3 - 3 - 3 - 3 - 3 - 3 - 3 - 2 - 3 - 33 4 - 1 5 4 - 2 3 4 - 2 9 4 - 32 4- - 34 5 - 34 6 - - 14 6 - 32 6 - 33 7 - - 18 7 - 24
[35] 7 - 32 8 - - 24 8 - 30 9 - - 17 9 - 29 9 - 32 9 - 33 9 - 34 10 - 34 11 - 20 11 - 25 11 - 34 12 - 33 13 - 33 14 - 32 16 - 30 17 - 28
[52] 18 - 34 19 - 20 19 - 28 21 - 32 21 - 33 22 - 27 23 - 34 24 - 30 25 - 27 25 - 31 26 - 31 26 - 33 28 - 34 33 - 34

simple.no.multiple

The generation logic is the same as simple, but when multiple edges and self loops occur, the graph is discarded and generation continues until a graph without multiple graphs or loops is generated. Therefore, the larger the average degree is , the more calculation time is required, and it is not uniform sampling from the possible graph set.

Visualize the random graph generated by this method.

gnet <- ggnetwork(simple_no_multiple_random_net, layout = hruchterman_reingold)
g <- ggplot(gnet, aes(x = x, y = y, xend = xend, yend = yend))
g <- g + geom_edges(size = 0.5)
g <- g + geom_nodes(size = 3, col = "blue")
g <- g + geom_nodelabel_repel(aes(label = vertex.names))
g <- g + ggtitle("sampled karate club network(method: simple.no.multiple)")
g <- g + theme_blank()
g

Generated random graph

Compared to the original network, the clustering coefficient is small and the mean distance between nodes seems to be close.

Unlike the graph generated by simple, the number of edges does not change before and aftersimplify().

> ecount(simple_no_multiple_random_net)
[1] 78
> ecount(igraph::simplify(simple_no_multiple_random_net, remove.multiple = TRUE, remove.loop = TRUE))
[1] 78

vl

• Because it is difficult, explanation is omitted.
• It seems to be uniform sampling here
• Official document of igraph says

  The "vl" method is a more sophisticated generator. This generator is generated unidentified, connected simple graphs, it is an error to pass the in.deg argument to it. Then some rewiring is done to make the graph connected. Finally a Monte-Carlo algorithm is used to randomize The graph. The "vl" samples from the undirected, connected simple graphs unformly. See http://www-rp.lip6.fr/~latapy/FV/generation.html for details.

Significance Test

In fact, we evaluate the clustering coefficient and the average path length by the deviation from the null model. We generate 1,000 random graphs by the vl method and examine where the value of the original network are located in the distribution of values calculated from them.

sample_cc <- c()
sample_pl <- c()
for(i in 1: 1000) {
  vl_random_net <- sample_degseq(degree_dist, method = "vl")
  sample_cc <- c(sample_cc, transitivity(vl_random_net))
  sample_pl <- c(sample_pl, mean_distance(vl_random_net))
}

The distribution of each indicator is as follows.

# cc hist
g <- ggplot(data = tibble(cc = sample_cc), aes(x = cc))
g <- g + geom_histogram(binwidth =. 01)
g <- g + geom_vline(xintercept = cc_original, col = "red")
g

# pl hist
g <- ggplot(data = tibble(pl = sample_pl), aes(x = pl))
g <- g + geom_histogram(binwidth =. 01)
g <- g + geom_vline(xintercept = pl_original, col = "red")
g

Distribution of clustering coefficients Red line is original value)

Distribution of average path length(red line is original value)

We assume that these distributions follow a normal distribution(though it is distorted to the right with respect to the average path length...), calculate the mean, standard deviation, and z value, and calculate the p value.

cc_mean = mean(sample_cc)
pl_mean = mean(sample_pl)
cc_sd = sd(sample_cc)
pl_sd = sd(sample_pl)
cc_zscore <-(cc_original - cc_mean) / cc_sd
pl_zscore <-(pl_original - pl_mean) / pl_sd

> 1-pnorm(cc_zscore)
[1] 0.1035129
> 1-pnorm(pl_zscore)
[1] 0.0003767265

Compared with the distribution of indices obtained from the random graph, it can be seen that the original network is a statistically deviated value for both network statistics.

Finally

It may be better to keep the series of methods introduced here to the extent that it is used for searching what kind of point is characteristic in a certain graph.

Because according to the paper Comparing Brain Networks of Different Size and Connectivity Density Using Graph Theory which examined the comparison method between graphs with different clustering coefficients and average path length Since these indices are greatly influenced by the node size N and the average degree k, it is difficult to compare graphs of different sizes and densities by raw numerical values ​​based on the original size(this bias is N-independent or k- independent, etc.).

It seems that the null model-based metrics introduced here are more influenced by N and k, if you use it, please be careful.

春菊とサラミのパスタ

オイルソースのパスタの具として緑色の野菜が欲しい時は大体ほうれん草を使っていたのですが、以下のまとめを見てから、春菊にリプレースしました。

togetter.com

個人的には、春菊を使うメリットは以下の通りかと思っています。

• 下茹での必要がなく、生のままでも食べられる。
• 芳香成分であるα-ピネンとペリルアルデヒドは脂溶性のため、オイルソースとの相性が良い。
• ほうれん草と比べてシュウ酸の含有量が少ないため、歯のざらつきが少ない。

普段はベーコンと春菊を炒めてアーリオ・オーリオを作るのですが、今回はフエ・カセーロという、表面に白カビのついたサラミを使いました。 先日、ヨーロッパ留学から帰ってきた友人からもらったもので、チーズのような風味がたまらない一品です。

フエ・カセーロ・カタルーニャ・サラミ/エルポソブランド

レシピ

必要なもの

• 春菊
  • 包丁を使うのはダルいので手でちぎってしまいます。
  • 炒めると思いのほか小さくなるので、多めに使うくらいがちょうどよいです。
  • トッピング用に葉の部分を取っておくのもよいですね。
  • 根っこの部分を食べるかどうかは自由ですが、茎は食感のアクセントになるので捨てることなきよう。
• サラミ
  • 食べやすいように輪切りにしておきます。
  • こちらもトッピング用に2,3切れほど炒めずに取っておいてもよいですね。
• にんにく
• 鷹の爪(optional)
• 白ワイン
• 塩・コショウ
• スパゲッティ
  • 今回は1.9mmを使っています。

分量はすべて適当です。適当にやっても美味しくできるのがパスタのいいところです。 強いて言うならば、サラミの塩気があるので、塩は少なめで構いません。

工程

1. フライパンにオリーブオイル、刻みニンニク、種を取った鷹の爪を入れてから、弱火で熱します。
   • このタイミングでパスタも茹で始めてしまいましょう。
2. にんにくの香りが立ってきたら、輪切りにしたサラミを炒めます。ちょっとカリカリになるくらいがちょうどいいですね。
3. 中火にして、春菊を投入してサッと炒めたら、火を強めて白ワインを振ります。アルコールが飛ぶまでフライパンを適当に揺らしましょう。
4. パスタの茹で汁を少し加え、かき混ぜて乳化させます。パスタが茹で上がるのを待ちます。
5. パスタが茹で上がったら、ソースと絡めます。
6. 皿に盛り付けたら、春菊の葉やサラミを乗せて完成です。

あとはビールをプシュッとして、いただきましょう。

次数分布を固定してランダムグラフを生成する

はじめに

グローバルクラスタリング係数や平均パス長、度数中心性など、ホールネットワークに関する統計量について、客観的に見てその数値がどれほど大きなものなのかを知りたい時がある。

このような場合、ヌルモデルと比較し、グラフの特徴量が統計的にどれほど逸脱しているのかを調べるという方法がある。よく使われるのは、オリジナルのグラフと同様の次数分布を持つランダムグラフと比べるというものである。

この記事では、Rのigraphパッケージを使って、次数分布を固定してランダムグラフを生成する方法について紹介する。

グラフ読み込み

今回はigraphに付属している空手クラブネットワークデータを用いる。

library(igraph)
library(tidyverse)
library(ggnetwork)

net <- graph("Zachary")

とりあえず可視化

ggnetworkでグラフを可視化する。後ほど、ランダムグラフも可視化するが、オリジナルのグラフでのノードの座標を最初に取得しておき、使い回せるようにしておく。

hruchterman_reingold = layout.fruchterman.reingold(net)
gnet <- ggnetwork(net,layout=hruchterman_reingold)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodes(size=3,col="blue")
g <- g + geom_nodelabel_repel(aes(label=vertex.names))
g <- g + ggtitle("original karate club network") 
g <- g + theme_blank()
g

画像がこちら。なんとなく、クラスタリング係数が高く、平均パス長は大きい、ような気がする。

Zachary Karate Clubのネットワーク

実際に計算してみると

> cc_original <- transitivity(net) #グローバルクラスタリング係数 
> pl_original <- mean_distance(net) #平均パス長
> 
> cc_original
[1] 0.2556818
> pl_original
[1] 2.4082

さて、これらの値はどこまで特徴的なのだろうか？

ランダムグラフ生成

igraphでは、sample_degseq(in.deg) で生成できる。in.deg はそれぞれのノードの次数のベクトル。無向グラフの場合はin.degのみ、有効グラフの場合はin.degで入次数の分布、out.degで出次数の分布を指定する。

オリジナルのネットワークの次数分布を取得しておく。

degree_dist <- igraph::degree(net)
g <- ggplot(data=tibble(degree=degree_dist),aes(x=degree))
g <- g + geom_histogram()
g <- g + ggtitle("degree distribution of karate club network ")
g

オリジナルネットワークの次数分布

グラフの生成方法はオプション引数のmethodで指定する。igraphにはsimple (デフォルト), simple.no.multiple,vl の3種類が用意されている。

simple

ノードから適当にn本のエッジを生やして、それを結合するという方法。シンプルな方法だが、多重エッジやセルフループが発生する。つなげ合わせる2つのノードの持つエッジの相手が重複する可能性を排除していないためである。

degree_dist <- igraph::degree(net)
simple_random_net <- sample_degseq(degree_dist)

こうして得られたグラフだが、simplify() して多重エッジとセルフループを取り除くと、エッジ数が少し減ることが確認できる。

> simple_random_net
IGRAPH 3c731f6 U--- 34 78 -- Degree sequence random graph
+ attr: name (g/c), method (g/c)
+ edges from 3c731f6:
 [1]  2-- 6  1-- 4  3--14 17--28  1--34 19--28 12--33  7--18  9--29 21--33  5--34  1--14  3--33  1--28  8-- 8 22--27 25--31
[18]  7--32  9--33  1--22 19--20 11--34  1--20  2-- 7  4--34  1--30 18--34  4--32  2-- 5 10--34  1-- 1  6--14  1-- 3  9--17
[35]  6--33  8--24  5--34 16--30  4--23  1--31 33--34  3--24 25--27 33--34  2--26  1-- 3  3--33 28--34 26--33  1-- 3 23--34
[52]  4--29 14--32 10--34  2--29  9--32 11--20 34--34  3--24 11--25  4--15  3--15  1--14  2--31  1--16  7--24  2--34  3--13
[69] 21--32  6--32 24--30  1-- 2  2--34 13--33  8--30 33--33  9--34 26--31
> simplify(simple_random_net,remove.multiple = TRUE,remove.loops = TRUE)
IGRAPH 40d3c01 U--- 34 65 -- Degree sequence random graph
+ attr: name (g/c), method (g/c)
+ edges from 40d3c01:
 [1]  1-- 2  1-- 3  1-- 4  1--14  1--16  1--20  1--22  1--28  1--30  1--31  1--34  2-- 5  2-- 6  2-- 7  2--26  2--29  2--31
[18]  2--34  3--13  3--14  3--15  3--24  3--33  4--15  4--23  4--29  4--32  4--34  5--34  6--14  6--32  6--33  7--18  7--24
[35]  7--32  8--24  8--30  9--17  9--29  9--32  9--33  9--34 10--34 11--20 11--25 11--34 12--33 13--33 14--32 16--30 17--28
[52] 18--34 19--20 19--28 21--32 21--33 22--27 23--34 24--30 25--27 25--31 26--31 26--33 28--34 33--34

simple.no.multiple

生成ロジックは simple と同じだが、こちらは多重エッジやセルフループが発生したらそのグラフは破棄し、多重グラフやループのないグラフが生成されるまで生成を続ける。したがって平均次数が多い場合は計算時間がかかり、また、可能なグラフ集合からの均一なサンプリングではない。

この方法で生成したランダムグラフを可視化する。

gnet <- ggnetwork(simple_no_multiple_random_net,layout=hruchterman_reingold)
g <- ggplot(gnet,aes(x=x,y=y,xend=xend,yend=yend))
g <- g + geom_edges(size=0.5)
g <- g + geom_nodes(size=3,col="blue")
g <- g + geom_nodelabel_repel(aes(label=vertex.names))
g <- g + ggtitle("sampled karate club network (method: simple.no.multiple)") 
g <- g + theme_blank()
g

生成されたランダムグラフ

オリジナルのネットワークに比べると、クラスタ化の度合いが小さく、ノード間の距離は近いように思われる。

先ほどの simple によって発生させたグラフと異なり、simplify() の前後でエッジ数は変化しない。

> ecount(simple_no_multiple_random_net)
[1] 78
> ecount(igraph::simplify(simple_no_multiple_random_net,remove.multiple = TRUE,remove.loop = TRUE))
[1] 78

vl

• 難しいので説明は省略。

• こちらについても不均一サンプリングになるらしい

• igraphの公式ドキュメント曰く

  The “vl” method is a more sophisticated generator. The algorithm and the implementation was done by Fabien Viger and Matthieu Latapy. This generator always generates undirected, connected simple graphs, it is an error to pass the in.deg argument to it. The algorithm relies on first creating an initial (possibly unconnected) simple undirected graph with the given degree sequence (if this is possible at all). Then some rewiring is done to make the graph connected. Finally a Monte-Carlo algorithm is used to randomize the graph. The “vl” samples from the undirected, connected simple graphs unformly. See http://www-rp.lip6.fr/~latapy/FV/generation.html for details.

有意性判定

実際に先程のクラスタリング係数と平均パス長をヌルモデルからの乖離によって評価してみる。vlメソッドによってランダムグラフを1000個発生させ、そこから計算した指標の分布の中でオリジナルネットワークの指標がどのあたりに位置するのかを検討する。

sample_cc <- c()
sample_pl <- c()
for(i in 1:1000){
  vl_random_net <- sample_degseq(degree_dist,method = "vl")
  sample_cc <- c(sample_cc,transitivity(vl_random_net))
  sample_pl <- c(sample_pl,mean_distance(vl_random_net))
}

各指標の分布は以下のようになる。

#cc hist
g <- ggplot(data = tibble(cc = sample_cc),aes(x = cc))
g <- g + geom_histogram(binwidth = .01)
g <- g + geom_vline(xintercept = cc_original,col = "red")
g

#pl hist
g <- ggplot(data = tibble(pl = sample_pl),aes(x = pl))
g <- g + geom_histogram(binwidth = .01)
g <- g + geom_vline(xintercept = pl_original,col = "red")
g

クラスタリング係数の分布（赤線はオリジナルの値）

平均パス長の分布（赤線はオリジナルの値）

これらの分布が正規分布に従っていると仮定（平均パス長に関してはずいぶん右に歪んでいるが…）して、平均と標準偏差とz値を計算し、p値を算出する。

cc_mean = mean(sample_cc)
pl_mean = mean(sample_pl)
cc_sd = sd(sample_cc)
pl_sd = sd(sample_pl)
cc_zscore <- (cc_original - cc_mean) / cc_sd
pl_zscore <- (pl_original - pl_mean) / pl_sd

> 1-pnorm(cc_zscore)
[1] 0.1035129
> 1-pnorm(pl_zscore)
[1] 0.0003767265

ランダムグラフから得られた指標の分布と比較すると、オリジナルのネットワークは両指標とも統計的に逸脱した値であることが分かる。

さいごに

ここで紹介した一連の方法は、あるグラフの中でどのような構造が特徴的なのかを探索する際に使う程度に留めておいたほうがよいかもしれない。つまり、他のグラフと比較する際に上の統計的な逸脱度を比べる、ということはしないほうが良いかもしれない。

というのも、クラスタリング係数や平均パス長の異なるグラフ間の比較方法について検討した論文Comparing Brain Networks of Different Size and Connectivity Density Using Graph Theoryによれば、これらの指標はノードサイズNや平均次数kの影響を大きく受けるため、元に異なるサイズや密度のグラフを生の数値によって比較することは困難である（こうしたバイアスはN-independentやk-independent等と呼ばれている）。

今回紹介したようなヌルモデルベースのメトリックのほうがむしろNやkの影響を受けてしまうようで、安易な使用には注意が必要である。

オランダでパスポートを盗まれるの巻

　1月9日から10連休を取得してオランダとマルタ共和国を旅行した。オランダはアムステルダム、ユトレヒトを観光した後にマルタ島に飛び、4日滞在してから再びオランダに戻り、ロッテルダム、デン・ハーグを回った。

　中学生の頃からティエストやフェリー・コーステンに代表される所謂ダッチトランスが好きだったので、かねてより行きたいと思っていた。いや、だからといって、言うまでもないが、変な草は吸っていない（断じて）。

www.youtube.com

ロッテルダム中央駅のイケてる建築

　ちなみに、社会ネットワークオタク的な観点で言うと、オランダは社会ネットワーク分析が非常に盛んな地域である。SIENAやマルチレベル分析で知られるTom Snijdersはオランダの出身で現在はグローニンゲン大学に身を置いており、ユトレヒト大学にはゲーム理論を用いたネットワークシミュレーションで有名なVincent Buskensがいる。

　オランダで具体的にどんなアクティビティに興じたかと言うと、『真珠の耳飾りの少女』で有名なマウリッツハイス美術館など各地の美術館を巡ったり、ハーリング（ニシンの酢漬け）っといった現地のB級グルメを食べたり、ハーグから徒歩でスヘフェニンゲン（「スケベニンゲン」と聞こえると有名な地域）の海岸まで行って黄昏れたり等々。

　旅行自体は最高のエクスペリエンスだったのだが、旅行の最終日、帰国直前に事件が発生する。空港に向かう途中駅でパスポートを盗まれたのである。以下、事の顛末を簡単に記述する。

カバンを盗まれるまで

　最終日はロッテルダムに滞在していた。ロッテルダムからアムステルダムのスキポール空港までは通常であれば急行が走っているのだが、ちょうど線路がメンテナンス中（そんなことあるんですね）ということで、ロッテルダムからライデンまでは電車、ライデンからスキポールまではバスで移動する必要があった。ちなみにオランダには9292という乗換案内アプリがあり、旅行前にインストールしておくと何かと重宝する。

　たまたま乗った列車は各駅停車だった。車中、10日間の旅行でどれくらいの距離を歩いたのかを確認して悦に浸っていた。ふだんはカバンを前に抱えるのだが、この時は隣の席に置いていた。この点に関しては帰国直前ということもあり、油断があったと言わざるを得ない。

　ある駅に停車した時、窓の方から音がする。そちらを見ると、なにやら男が切符を見せながら窓を執拗にノックしてくる。「切符を売りたいのか？それともこの切符がどこに行くのか教えてほしいのか？なんでそんなことを日本人観光客に聞くんだ？」といった様々な疑念が去来する。その間、視界の端でなんとなく「カバンが落ちた」ような気がした。刹那、男はやれやれ、といった感じでどこかに消えていく。「いったい今のはなんだったんだ？」という思いで、ふと隣席に目をやると、カバンがないことに気づく。と同時に、電車のドアの閉まる音がする。全てに気付く。ノックする男とは別の人間が見事のチームワークでカバンを持ち去っていったのである。

カバンを盗まれてから

　キャリーケースを持って一目散に出口に向かい、乗務員に「カバンを盗まれたから降ろしてくれ！」と懇願する。すぐに電車から降りることはできたが、男たちの姿はなくなっていた。その駅はハーグ中央駅からやや北のDen Haag laan van NOI駅という無人駅で、監視カメラすらなかった。カバンの中にはパスポートや私物のPC・タブレット等様々なものが入っていた。

　ホームの階段を半狂乱になりながら降りて、助けてくれそうな人を探す。キオスクの店員に声を掛ける。とりあえずハーグ中央駅に行けとのこと。乗るべきトラムを教えてもらう。トラムの中でも焦りが隠しきれず、それを見かねたのか若いカップルに助けられる。事情を説明すると、ハーグ中央駅まで同行して、鉄道警察に話をつけてくれるという。駅について借りてきた猫のようにカップルと警察が会話しているのを眺めていると、警察曰く、とりあえず空港に行けとのこと。

　スマホと財布を盗まれないように常にポケットに手をあてながら、一路スキポール空港へ。だが、空港の警察に相談するも、何もできないそうだ。ハーグの警察署で盗難届を発行してもらうように、とのこと。ちなみに、この時奇跡的なタイミングで友人がアムステルダムに旅行に来ており、現金を借りることができた（ありがとう…）。

　再びハーグに戻り、駅員に警察署がどこかを聞く。駅から約2kmほどの場所に交番があり、事情を説明し、然るべき書類に事件の詳細を書き、1時間ほどで盗難届を発行してもらうことができた。

　さて、帰国のための手続きをしようにも、盗まれた日は土曜日で、月曜日までは大使館が開かない。オランダ→成田行きの便は現地時間14時なので、月曜日だとリスキーだろうということで、KLM航空のスタッフの判断で、火曜日の便を予約してもらった。

　というわけで急に3泊する場所を確保しなければならなくなった。宿泊場所については、オランダに留学中の友人から、おすすめのドミトリーを教えてもらう。警察署内で予約を済ませる。こういう時は他人と喋らないと寂しさで精神が荒廃してしまうと考え、ホテルよりも多くの人がいるドミトリーのほうが良いと即判断した。

　滞在したのはthe Golden Storkというハーグ中央駅近くのドミトリー。スタッフにパスポートを盗まれたと説明すると、非常に親身に相談に乗ってくれた。「色々あったと思うけど、ここは安全な場所だから」と。カナダ出身のリンゴ農家と同室になったのだが、彼も親切に話を聞いてくれた。カナダはパスポート紛失に対してかなり厳しく、再発行が認められないケースがあるという話も聞いた。取り留めのない世間話ですら心に染みる。

　こういった事件に遭遇すると、周りの人間が全員敵なのではないかという疑心暗鬼に陥りがちであるが、人々と会話すると、性善説への信仰心が戻ってくる。

帰国のためにやったこと

　パスポートを盗まれた場合、帰国するためには(1)パスポートの再発行と(2)帰国のための渡航書の発行という2つの選択肢がある。しかし、(1)の場合は1週間以上の時間がかかる。(2)の渡航書というのは一回限りしか使用できない帰国のためだけの緊急パスポートである。今回発行してもらったのは後者である。 　

渡航書発行のために必要だったもの

• 盗難届
• 戸籍謄（or 抄）本
  • 日本の親族に大使館宛にFAXで送ってもらうとよい。今回は.pdfを添付する形でも受理してもらえた。
  • マイナンバーカードや免許証でも構わないらしい。
• 顔写真
  • 現地の写真屋で撮ってもらう。どこで撮ればいいかわからない場合はホテルのスタッフ等に聞くとよい。
• 帰りの飛行機の予約証明
  • 予約の変更時にメールで予約証明書を送ってもらうように念押ししたほうがいい。
• 手数料現金20ユーロ
  • 金額は国によって異なるかもしれない

やるべきだったこと

以下は今回の旅行での反省点である。

• パスポートや免許証のコピーは持っておくべき
• 電車関連
  • 監視カメラつきの車両に乗る
  • そもそもカバンを隣席に置かない
  • 真ん中のほうの席に座る
  • 各駅停車の電車にはできるだけ乗らない
• 渡航先の国外務省の情報を事前にチェックして、よくある手口を頭に叩き込んでおく
  • 今回遭った手口も、調べると外務省のページで注意喚起があった。

さいごに

散々な最後になってしまったが、一ヶ月経って思い返すと非常に良い経験だった……と素直には言えない。 今は新しいPCやバッグを買い直した際の楽天カード請求額と、欠勤による減給に打ち震えている……。 （なお楽天カード付帯の旅行保険は現在審査中）

帰国寸前に除雪で足止めされたシーン

社会学の院生がITベンチャーの研究開発職に就くまで、そしてこれから

今年の2月にSansan株式会社に研究開発職として入社してから、そろそろ1年が経とうとしている。

社会学の修士卒→ITベンチャーのR&Dというキャリアはかなり特殊ということもあり、「どうしてそうなったのか」を色々な人から尋ねられる機会も増えてきた。

というわけで、2018年の振り返りも兼ねて、大学・大学院時代にやっていたこと、入社までの経緯、そして現在何をやっているのか等をまとめることにする。

学部1~2年

自分が入学した東京大学教養学部文科3類は、他の科類に比べても文系色が強く、世にいう「文学部」をイメージしてもらえば大枠としては外さないはずだ。学部1,2年は教養課程で、3年生から専門の学部へと進学する仕組みになっている。

この頃はドイツ語やイタリア語などの外国語を中心に哲学、社会学などをつまみ食い的に勉強していた。大学に入る前から大学院にはなんとなく進学するつもりではいたが、おおまかには文献研究になるだろうと踏んでいた。

この時期は基本的に人文・社会系の勉強が多かったが、たまたま履修した行動生態学の授業が面白く、それ関連の本を読み漁ることもあった。

遺伝マインド　--遺伝子が織り成す行動と文化 (有斐閣Insight)

では、現在の仕事に直接つながるような勉強をしていたかというと、決してそうではなかった気がする。

準必修でたまたま履修した自然言語処理の授業でRを触ったことはあったが、成績はそこまで芳しくなく、スクリプトを書いていても全く楽しさを感じなかったので、将来的にこれが商売道具になろうとは当時は思いもしなかった。

加えて、もともとプログラミングや情報技術自体には興味があり、趣味で基本情報技術者試験を受けたりしていたものの、実務でコードを書くといった経験はほとんどなかった。

学部3~4年

社会学専攻に進学してからは、先輩や同学年の人たちに恵まれた。近年のコーホートの中では、最も「社会学を勉強するんだ」という気骨のある人たちが集まる世代だったのではないかと思う。

理論・メソッドを問わず、非常に盛んに勉強会や研究会が開かれた。自分もほぼ毎週のように何かしらの勉強会の準備に追われていた。学部生室には常に誰かがいて、何かしらの議論が行われていた。

具体的にどのような文献を読んでいたかというと、理論だったらColemanやGiddens、メソッドだったらWooldridgeの計量経済学の教科書やAgrestiのカテゴリカルデータ分析の本などを輪読していた。とにかく興味のある本があれば、周りを巻き込んで何でも読んだ。

コールマン 社会理論の基礎〈上〉 (社会学の思想)

An Introduction to Categorical Data Analysis (Wiley Series in Probability and Statistics)

計量分析を始めたのは、専門課程に入ってからのゼミの影響が大きかったと思う。学部に入った当初は興味が思想方面にあったのだが、優秀な人たちが計量寄りのゼミに入っていたこともあり、気付けばそちらの道に進んでいた。

統計学やRの使い方を本格的に勉強し始めたのはこの頃だった。当時はRの解説本はまだ市場にそれほど出回っておらず、『Rによるやさしい統計学』を繰り返し読んでスクリプトを書いていたと思う。

Rによるやさしい統計学

社会ネットワーク分析(以下SNA)と出会ったのもこの頃で、きっかけはたまたま乱読していた本の中で出会った安田雪先生の『パーソナルネットワーク』だったような記憶がある。

もともと自分はずっと「社会的分断」のようなテーマに興味があり、そのような現象に対するフォーマルな記述手法を提供するSNAに感銘を受けた。

パーソナルネットワーク―人のつながりがもたらすもの (ワードマップ)

SNAに興味を持ち始めてからは、GUIベースのPajekというソフトウェアを使って、サンプルデータを用いながら遊び半分で分析を回していた。

学部3年で書くゼミ論では、高校の学級にフィールドワークに行き、そこで実際にネットワークデータを収集して、Pajekで分析・可視化などを行った。修論もこのテーマをそのまま引き継いだものだ。

（ちなみに現在ネットワークを分析する時はigraphかNetworkXを使っている）

Exploratory Social Network Analysis with Pajek (Structural Analysis in the Social Sciences)

ちなみに東京大学には「情報学環教育部」というユニークな組織があり、こちらにも所属していた。メディア論やジャーナリズム論を学べる学内のダブルスクールのような組織で、情報法について学ぶ授業や、レッシグの『CODE』を読む授業などを聴講していた。

東京大学大学院 情報学環・学際情報学府 – 情報学環教育部 (実はヘッダー画像に僕が写っている)

ここでは、自主的にネット炎上や監視社会に関するゼミも開いていた。学部では定量的な分析がメインだったが、こちらではどちらかというと歴史や理論的なアプローチで、しかもかなり自由な形式で発表などを行っていた。

CODE VERSION 2.0

この組織にはフルタイムで働いている人や、普段出会わないような理工系の学生も在籍しており、何気ない会話の中で異なる領域の知識や視点を知ることができた。

自分の中での見える世界の幅が広がったのは教育部のおかげだと思う。例えば現在仕事でやっているような「社会学の知識を活用して何かプロダクトが作れるんじゃないか」みたいなアイデアが、教育部に在籍した経験なくして出てくるものなのかは自信がない。本当に良い教育機関だと思う。

大学院修士課程

修士1年のときには学会発表共著で査読付きの書評論文を書いたり、学会発表にも精力的に参加し、年度の終わりにはINSNAというSNAの国際会議にも出席した。Scott FeldやBarry WellmanといったSNA界のレジェンドを間近で見られて感無量だった記憶がある。

修士生活はかなり順調だったと思う。ここまでは。

Networked: The New Social Operating System (The MIT Press)

SNAを勉強していると誰もが思うことかもしれないが、SNAの本流は主にアメリカ合衆国、オランダ、オーストラリアの3カ国にあり、日本の社会学のプレゼンスはまだまだ高いとは言えない。

当然そうなると海外にPh.D留学したいという気持ちが湧いてくる。INSNAに参加してこのあたりの思いは決定的なものになったと思う。

ただ、あまりにも遅かった。M2の4月から急いで準備を始めて、TOEFLなどを受験するも、一向にスコアが伸びなかった。2万円弱ほどの受験料が発生する試験で、金銭的な負担はそのまま精神的な不安として大きくのしかかった。

フルブライトや伊藤国際などの奨学金プログラムにも応募したが、おそらくTOEFLの点数が低すぎて軒並み不合格となった。

この間、概日リズムは完全に狂ってしまい、朝の5時に寝て午後4時に起き、その後は一切頭が働かずにボーっとしただけで一日が終わる、ということも珍しくなかった。

結局、留学は挫折することとなった。この決断の後、推薦状を書いていただくなど尽力していただいた指導教員にもその旨を伝えた。そこで励ましの言葉をいただいたのだが、先生の部屋から出てすぐに法文1号館のトイレ個室でどうしようもなく大泣きしてしまったことを今でも鮮烈に思い出す。

さて、そこからは概日リズムを調整する薬を服用しつつ、修士論文をやっとの思いで書き上げた。その後、口頭試問で激烈な批判を浴びせられながらも、なんとか修士の学位を手に入れ、博士課程に進んだ。

博士課程に進むことに特別な「覚悟」があったわけではなく、さしあたりそうする以外に選択肢がなかった、というだけだった。

大学院博士課程

こうして博士課程に進学するも、修士時代は留学準備に精一杯で学振特別研究員(DC1)にも応募しておらず、露頭に迷っていたところ、修士時代に1年間アルバイトしていた情報学環教育部の先輩方の経営する会社に拾っていただいた。

正社員として雇用していただきながら、ダッシュボードの作成、レポート作成、効果検証やPythonでのスクレイピング、アンケート調査の集計システムの開発などを行った。

ある程度裁量を与えられながら、VMやgitなどの技術にも触れつつ、データ分析およびシステム開発の実務に携われたのは非常に貴重な経験だったと思う。気が向いた時にはkaggleでKernelを書いたりしていた（最近はサボっている）。

Clustering Top Players | Kaggle

こうして週4日ほど勤務しながら、かなりスローペースながらも、修士論文の投稿論文化を中心に研究活動は続けていた。査読論文こそ出していないものの、SNAに依拠しつつ、学会やシンポジウムでの発表や、研究プロジェクトの報告書などを書いていた。

ある日

日々の生活には一切の不満もなかったのだが、ある日、Twitterで一件の求人募集を目にする。

どうやらSansan株式会社というところで、「社会科学分野のデータサイエンティスト」を募集しているらしい。いやいや「社会科学」というのは経済学や金融工学のことだろうと思いながらも詳細を見ると、

「計量経済学、社会心理学、ネットワーク分析、Computational Social Scienceなど」の研究経験がある人を募集しているという。しかも、実務経験があり、かつRやPythonが使えることが募集要件の中に入っている。

胸が高鳴った。「これは自分のことではないのか？」という気持ちが捨てきれなかった。この募集要項を見た晩はロクに眠れず、仕事中ももっぱら悶々としていた。いてもたってもいられずに、会社の人たちに相談したところ「とりあえず面接に行ってみたら？」と言われた。

学部・院時代には就活をした経験がなかったため、様々なことが分からなかった。それでも慣れない手つきで履歴書と職務経歴を書き上げて、送った。書類審査に通過したという知らせを受けて、面接に向かうと、オフィスはあまりにもオシャレでキラキラしていた。とても緊張した。

だが、面接官（後に同じチームの人になる）とネットワーク研究について喋るうちに、「ここにもいたんだ」という感覚を覚えた。自分のやってきたことは、もしかしたらここで実を結ぶのではないかと。

幸運にも、自分の「やってきたこと・これからやりたいこと」と、先方が「やってほしいこと」がマッチングし、無事に採用が決まった。今から思えば、会社からするとかなりの思い切った判断だったのかもしれない。

現在

現在は、大学院を休学してフルタイムで働いている。機械学習のプロフェッショナルや一流のエンジニアの中で揉まれつつも、なんとか自分なりのやり方で新規サービスを作ったり、社内システムを作ったり、その傍らで社会ネットワーク研究オタクとしてSNAに関するコラムやブログなどを書いている。

bnl.media

部署のslackには15000個のemojiがあり、毎日愉快に仕事できている。また、みなそれぞれ専門領域があり、お互いがリスペクトし合える雰囲気があって、環境としてはとても良いと思う。

qiita.com

自分のバックグラウンドは工学・情報学にないが、かといって全く歯が立たなかったり、自分の作ったものが全然評価されないというわけでもない。むしろ社会(科)学では当たり前の発想が、真新しいアイデアとして驚かれることもある。

これは希望的観測だが、社会科学出身者の雇用先として、今後データサイエンティストやエンジニアといった選択肢は増えていくはずだ。だが、自分が失敗してしまったら、自分以外の人の未来の可能性まで潰してしまうような予感もあり、そのあたりの緊張感は持って日々仕事をしている。

さいごに

こうして改めて振り返ってみると、良い人との出会いの中で自分の方向性が水路づけられていったに過ぎないと感じる。

本当に、人と人との出会いというものはそれ自体奇跡だと思う。

一方、科学的な立場からは、やはり奇跡で終わらせることはせずに、そのメカニズムと対峙する必要があるとも考える。

ネットワーク研究者として、その狭間で揺れながら、それなりに気合を入れて2019年はやっていこうと思う。

まだまだ未熟者ですが、来年もよろしくお願いします。