library(igraph)
library(ggplot2)
library(showtext)第8章：ネットワークの結束とコミュニティ
このチュートリアルの内容は、下記からWebページとしてアクセスできます！！
https://yuki-takahashi342.github.io/network-analysis-with-R-ch08/
このチュートリアルでは、Rにおける結束性（cohesion）とコミュニティ（ないしグループ）に関する詳細な例を解説します。まず、ネットワークが断片化に対してどれほど頑健であるかを捉える結束性について検証します。次に、どの行為者（actor）の集合がグループを形成しているか（相互作用の割合が高い、ネットワーク内で距離が近いなど）を捉えるコミュニティ構造について説明します。
このチュートリアルは、以前の章、特に基本的なネットワーク測定に関するチュートリアルで扱った内容を基にしています。分析には2つのサンプルネットワークを利用します。最初の例は、Daniel McFarlandがある教室で発生するさまざまな種類の相互作用について収集した思春期の集団に関するデータです。このネットワークは16人の俳優しかいない小さなものです。2番目の例では、20万以上のノードを持つEメールネットワークという、はるかに大きなネットワークの分析問題を取り上げます。この2番目の例は、「ビッグ」データを扱う際のさらなる複雑さの一部を示すとともに、そのようなネットワークを分析する際のベストプラクティスに関する提案を提供するために含まれています。
教室の例は、主に2つの実質的な問いに動機づけられています。第一に、教室のネットワークは結束性が高いのか、それともコミュニティ間の結びつきがほとんどなく、局所的なコミュニティ（またはグループ）に強く分裂しているのか？これは、例えば、教室における規範の維持に関心がある場合に重要な問いです。物事について合意しそうにない2つの分裂したコミュニティが見つかるのでしょうか？それとも、コミュニティ間のつながりを考慮すると、全体的な合意の可能性があるのでしょうか？
第二の問いは、コミュニティ自体の構成に焦点を当て、特に人種的アイデンティティに注目します。人種的アイデンティティに対応する別個のコミュニティ（「白人」グループと「黒人」グループ）が見つかるのか、それとももっと複雑なのでしょうか？これらの問いをまとめると、私たちは教室における合意と連帯の可能性について何かを知りたいのであり、合意への脅威が人種的な分断に関連しているかどうかを知りたいのです。
8.1 最初のサンプルネットワーク
このセッションでは、主にigraphパッケージを使用します。また、ggplot2もロードします。
まず、教室のネットワークデータを（URLから）読み込み、最初の6行を見てみましょう。
url1 <- "https://github.com/JeffreyAlanSmith/Integrated_Network_Science/raw/master/data/class182_networkdata.csv"
class182_networkdata <- read.csv(file = url1)
head(class182_networkdata) ego alter friend_tie social_tie task_tie
1 1 1 0 0.0 0.0
2 1 2 0 0.0 0.0
3 1 3 0 0.0 0.0
4 1 4 0 0.0 0.0
5 1 5 0 1.2 0.3
6 1 6 0 0.0 0.0このデータフレームには、教室内の各ダイアド（二者関係）に関する情報が格納されており、友情、社会的相互作用、タスク相互作用の3つの関係に関する情報が示されています。最初の列はエゴ（ego）、2番目の列はオルター（alter）、3、4、5番目の列は0以上の値で、2つのノード間の関連の強さを示しています。友情は、2 = 親友、1 = 友人、0 = 友人ではない、として測定されます。社会的相互作用は、1時間あたりの社会的相互作用の回数として測定されます。タスク相互作用は、1時間あたりのタスク相互作用の回数として測定されます。ここでは、友情データを利用します。属性ファイルも読み込んでみましょう。
url2 <- "https://github.com/JeffreyAlanSmith/Integrated_Network_Science/raw/master/data/class182_attributedata.csv"
class182_attributes <- read.csv(file = url2)
class182_attributes ids race grade gender
1 1 white 10 male
2 2 black 10 female
3 3 white 10 female
4 4 white 11 female
5 5 white 10 male
6 6 white 10 female
7 7 black 10 female
8 8 black 10 female
9 9 white 10 female
10 10 black 11 male
11 11 white 10 male
12 12 black 11 female
13 13 white 10 female
14 14 black 10 female
15 15 black 10 female
16 16 black 13 male教室内の各生徒について、人種、学年、性別の情報があります。友情関係に基づいてエッジリストを作成しましょう。ここでは、友情の値が0より大きい場合をエッジとして定義します。
edge_value <- class182_networkdata$friend_tie
edgelist_friendship <- class182_networkdata[edge_value > 0,
c("ego", "alter", "friend_tie")]
head(edgelist_friendship) ego alter friend_tie
17 2 1 1
23 2 7 1
24 2 8 1
29 2 13 2
30 2 14 1
37 3 5 1そして、エッジリストと属性のデータフレームを使ってigraphオブジェクトを作成します。
net182_friend <- graph_from_data_frame(d = edgelist_friendship, directed = T,
vertices = class182_attributes)
net182_friendIGRAPH 0ff8519 DN-- 16 62 --
+ attr: name (v/c), race (v/c), grade (v/n), gender (v/c), friend_tie
| (e/n)
+ edges from 0ff8519 (vertex names):
[1] 2 ->1 2 ->7 2 ->8 2 ->13 2 ->14 3 ->5 3 ->6 3 ->11 3 ->14 3 ->15
[11] 5 ->1 5 ->3 5 ->6 5 ->8 5 ->10 5 ->11 6 ->1 6 ->3 6 ->5 6 ->7
[21] 6 ->10 6 ->11 6 ->12 7 ->2 7 ->8 7 ->13 7 ->14 8 ->2 8 ->5 8 ->7
[31] 8 ->13 8 ->14 8 ->15 9 ->1 9 ->3 9 ->10 9 ->12 9 ->15 10->1 10->9
[41] 10->12 10->15 11->1 11->3 11->5 11->6 11->10 12->1 12->9 12->15
[51] 13->2 13->7 13->8 13->14 14->2 14->3 14->8 14->12 15->1 15->7
[61] 15->9 15->12このネットワークは有向（directed）であり、関係の強さ（＝重み）を示すエッジ属性 friend_tie を持っていることに注意してください。
8.2 結束性（Cohesion）
まず、ネットワーク全体の結束性を見ていきます。友情ネットワークを簡単にプロットすることから始めます。これにより、ネットワーク構造の直感的な全体像を把握できます。
plot(net182_friend, vertex.label = NA, vertex.size = 10,
edge.arrow.size = .25, edge.arrow.width = 1,
edge.color = "light gray", vertex.frame.color = NA)
教室のネットワークは（2つの孤立点（isolates）を無視すれば）かなり結束性が高いことがわかりますが、大まかに2つのグループに分かれているようにも見えます。密度（density）から始めて、ネットワークのいくつかの特性をより形式的に調べてみましょう。
edge_density(net182_friend)[1] 0.2583333ここでは、全ての可能な結びつきのうち0.258がネットワーク内に存在することがわかります。観測される多くのネットワークは密度がはるかに低いため、これを結束性が高い指標と見なすかもしれません。しかし、密度は結びつきの量について何かを捉えるだけであり、結びつきのパターンについては捉えないことを覚えておくことが重要です（また、密度は通常、小さなネットワークで高くなる傾向があり、ここでは小さなネットワークを扱っていることも覚えておく価値があります）。
結びつきが多いネットワークであっても、結びつきの配置によっては、ネットワークの一部が他の部分から切断されている（あるいは非常に緩やかにしか接続されていない）という意味で、依然として脆弱である可能性があります。したがって、結束性をより直接的に捉える他の指標を検討することが有用です。
例えば、コンポーネントサイズ（component size）を調べてみましょう。主コンポーネントは、すべてのijペアが互いに（何かしらの経路で）到達できるようなノードの最大の集合です。これは、iがjに到達できると言っているだけで、iとjが実際にどれだけ相互接続されているか（例えば、iとjが複数の短い経路で接続されているか、一つの長い経路で接続されているか）については何も言及していないため、それ自体は比較的ハードルが低い結束性の基準です。
ここでの関数は components() です。主な引数は graph（対象のネットワーク、igraphオブジェクトとして）と mode です。mode = "strong" オプションは、iがjに到達でき、かつjがiに到達できる集合としてコンポーネントを定義します。mode = "weak" オプションは、iがjに到達できるか、またはjがiに到達できれば、iとjが同じコンポーネントにあるという別のバージョンを与えます。（←有向グラフなので2つは別になる）
ここでは、weakオプションを使用します。無向ネットワークの場合、mode引数は無視されることに注意してください。
components_friendship <- components(graph = net182_friend, mode = "weak")
components_friendship$membership
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 3
$csize
[1] 14 1 1
$no
[1] 3出力は3つの要素を持つリストです：membership（各ノードが属するコンポーネント）、csize（各コンポーネントのサイズ）、no（コンポーネントの数）。
各コンポーネントのノードの割合を計算してみましょう。
components_friendship$csize / sum(components_friendship$csize)[1] 0.8750 0.0625 0.0625ノードの87.5%が最大のコンポーネントに含まれていることがわかります。2つの孤立点はそれぞれ独自のコンポーネントにあり、他のすべての（結びつきを持つ）ノードは1つの大きなコンポーネントにあります。これは実質的に、ほとんどの生徒が、より局所的な仲間グループに属しているかもしれない一方で、教室レベルで定義される、少なくとも最小限に接続されたより大きな社会集団の一部であることを示唆しています。
過去の研究では、社会的結束性を測定するためにバイコンポーネントサイズ（bicomponent size）もしばしば使用されてきました（Moody and White 2003）。バイコンポーネントサイズはコンポーネントサイズの拡張であり、少なくとも2つの独立した経路で接続されているノードの集合を示し、単一のノードを削除しても集合全体が接続されたままであることを示します。バイコンポーネントサイズは、ネットワークが主要なノードの喪失（または除去）に耐えられるかどうかを捉えるため、結束性の理想的な指標です。したがって、結束性の高いネットワークは、特定のノードの存在を超えてより大きな単位として存在し、切断に対して頑健（ロバスト）です。
バイコンポーネントサイズを計算する関数は biconnected_components() です。この関数は自動的にネットワークを無向として扱い、これは上記のコンポーネントサイズの ‘weak’ オプションに相当することに注意してください。（←なぜ？strongだと条件がキツすぎる？）
bicomponents_friendship <- biconnected_components(graph = net182_friend)出力はリストです。関心の主要な項目は、各バイコンポーネントに含まれるノードです。これはリストの components 部分にあります。
bicomponents_friendship$components[[1]]
+ 14/16 vertices, named, from 0ff8519:
[1] 10 15 11 9 12 14 13 8 5 3 6 7 2 1 この場合、16ノード中14ノードが単一のバイコンポーネントにあり、少なくとも2つの独立した経路で接続されています。繰り返しになりますが、この主バイコンポーネントに含まれていないのは、2つの孤立点だけです。これは、ネットワークが高い結束性を持っていることを示唆しており、すべてのノード（2つの孤立点を除く）が複数の方法で互いに接続されているためです。
出力の中身
ちなみにbicomponents_friendshipの中身は
bicomponents_friendship$no
[1] 1
$tree_edges
$tree_edges[[1]]
+ 13/62 edges from 0ff8519 (vertex names):
[1] 10->15 11->10 9 ->10 12->9 14->12 13->14 8 ->13 5 ->8 3 ->5 6 ->3
[11] 6 ->7 2 ->7 2 ->1
$component_edges
$component_edges[[1]]
+ 62/62 edges from 0ff8519 (vertex names):
[1] 10->1 5 ->10 6 ->10 10->9 9 ->10 15->1 3 ->15 15->7 8 ->15 15->9
[11] 9 ->15 10->15 15->12 12->15 11->1 11->3 3 ->11 11->5 5 ->11 11->6
[21] 6 ->11 11->10 9 ->1 9 ->3 12->1 6 ->12 12->9 9 ->12 10->12 14->2
[31] 2 ->14 14->3 3 ->14 7 ->14 14->8 8 ->14 14->12 13->14 13->2 2 ->13
[41] 13->7 7 ->13 13->8 8 ->13 8 ->2 2 ->8 8 ->5 5 ->8 8 ->7 7 ->8
[51] 5 ->1 5 ->3 3 ->5 6 ->1 6 ->3 3 ->6 6 ->5 5 ->6 7 ->2 2 ->7
[61] 6 ->7 2 ->1
$components
$components[[1]]
+ 14/16 vertices, named, from 0ff8519:
[1] 10 15 11 9 12 14 13 8 5 3 6 7 2 1
$articulation_points
+ 0/16 vertices, named, from 0ff8519:となっており、noがバイコンポーネントの数（孤立点はバイコンポーネントになり得ないので、数に入らない）、tree_edgesがコンポーネント自体（？）を表す。スパニングツリー（最小限の辺で全てのノードをつなぐ）になっている。component_edgesがコンポーネント内の全てのエッジ、articulation_pointsが除いた場合にコンポーネント数を増やすことになるノードを示す（ここではそのようなノードは存在しない）。
バイコンポーネントサイズとコンポーネントサイズの考え方に基づき、ネットワーク内の特定のノードペアの連結性、つまり頂点連結度（vertex connectivity）を調べることもできます。ここでは、vertex_disjoint_paths() 関数を利用します。引数は graph、source（開始ノード）、target（終了ノード）です。出力は、iからjへの直接の結びつきを除き、iがjに到達できなくなるために削除する必要があるノードの数です。
上記のコンポーネントとバイコンポーネントの計算と一貫性を持たせるために、頂点連結度を調べるための無向ネットワークを作成しましょう。mode を “collapse” オプションに設定します。これは ‘weak’ ルールを使用するため、iがjに結びついているか、jがiに結びついている場合、iとjの間に結びつきが存在することになります。
net182_friend_und <- as.undirected(net182_friend, mode = "collapse")
net182_friend_undIGRAPH eec8473 UN-- 16 42 --
+ attr: name (v/c), race (v/c), grade (v/n), gender (v/c)
+ edges from eec8473 (vertex names):
[1] 1 --2 1 --5 3 --5 1 --6 3 --6 5 --6 2 --7 6 --7 2 --8 5 --8
[11] 7 --8 1 --9 3 --9 1 --10 5 --10 6 --10 9 --10 1 --11 3 --11 5 --11
[21] 6 --11 10--11 1 --12 6 --12 9 --12 10--12 2 --13 7 --13 8 --13 2 --14
[31] 3 --14 7 --14 8 --14 12--14 13--14 1 --15 3 --15 7 --15 8 --15 9 --15
[41] 10--15 12--15ここでは、2つのサンプルノード、1と9の頂点連結度を計算します。
vertex_disjoint_paths(graph = net182_friend_und, source = 1, target = 9)[1] 5友情ネットワークでノード1とノード9を切断するには、他の5つのノードを削除する必要があることが分かります。これは非常に高い数です。したがって、ノード1とノード9は高度に相互接続されており、同じ社会集団の一部である可能性が高いです。この種の計算をすべてのダイアドに拡張し、頂点連結度の分布を要約することで、バイコンポーネントサイズを補完しつつ拡張する結束性の要約指標を作成できます。
バイコンポーネントサイズは、最小閾値である2つの独立した経路で接続されていることしか捉えません。ノードを接続する実際の経路の数は教えてくれません。ただし、すべてのダイアドにわたって頂点連結度を計算することは（時間的に）コストがかかる可能性があり、計算に使用するダイアドをサンプリングすることが有用/必要になる場合があることに注意してください。
また、vertex_connectivity() 関数を使用して、ネットワーク全体の連結度、つまりネットワークを切断するために削除する必要がある最小ノード数（すべてのiがすべてのjに到達できなくなるように）を取得することもできます。
vertex_connectivity(graph = net182_friend_und)[1] 0ここでは、頂点連結度が0であることがわかります。これは、ネットワークに2つの孤立点があるためです。ネットワークを切断するためにノードを削除する必要はありません。
2つの孤立点をネットワークから削除して、頂点連結度を再計算してみましょう。まず、孤立点を特定します。次に、孤立点のない新しいネットワークを作成し、頂点連結度を再計算します。
isolates <- which(degree(net182_friend_und) == 0)
net182_noisolates <- delete_vertices(net182_friend_und, isolates)
vertex_connectivity(graph = net182_noisolates)[1] 4孤立点を無視すると、ネットワークを切断するためには4つのノードを削除する必要があります。全体として、この教室の設定は、2つの孤立点を除いて、高いレベルの結束性を持っていることがわかります。すべての非孤立点は、少なくとも2つの独立した経路で接続された1つの大きなバイコンポーネントの一部です。さらに進むと、すべての非孤立点は、実際には最小4つの独立した経路で接続されており、切断に対して非常に頑健です。
8.3 コミュニティ（またはグループ）検出
これまでのところ、この教室の友情ネットワークは結束性が高いことを確立しました。次に、より大きな結束性のある集合内のコミュニティ（またはグループ）について問い、詳細に見ていきます。目標は、内部密度が高く、外部メンバーへの結びつきが少ないノードの集合を特定することです。したがって、結束性の高いネットワークであっても、より大きなネットワーク内には重要なコミュニティ（または密な領域）が存在する可能性があります。
私たちには3つの主要な問いがあります。第一の問いは、ネットワークに存在するコミュニティについてです。ネットワークは多数の小さなコミュニティに分割されるのでしょうか？ それとも、ネットワークは基本的に1つの強い分割線で半分に分かれるのでしょうか？ 第二の問いは、これらのコミュニティの構成についてです。人種は、見つかったコミュニティに強く対応しているのでしょうか？ 第三の問いは、コミュニティ間の接触のレベルについてです。コミュニティ（およびその間の結びつき）は、ネットワーク全体の結束性にどのように貢献する、または損となるのでしょうか？
これらの問いに対処するために、コミュニティ検出を利用します。コミュニティを検出するにはさまざまな方法があります。このチュートリアルでは、ウォークトラップ（walktrap）、エッジ媒介性（edge-betweenness）、階層的クラスタリング（hierarchical clustering）、結束ブロッキング（cohesive blocking）の4つを使用します。これらを見ていく中で、それらがコミュニティをどのように描写するかを検討し、どれが社会世界を結束的に組織されたものとして賢明な見方を提供するかを考えることが重要です。igraphはグループではなくコミュニティという言葉を使用していますが、これらは交換可能です。一貫性と単純さのために、分析では無向ネットワークを使用します。
8.3.1 ウォークトラップ（Walktrap）
このアルゴリズムは、一連の短いランダムウォークを通じてコミュニティを検出します。その考え方は、任意のランダムウォークで遭遇するノードは、コミュニティ外であるよりもコミュニティ内である可能性が高いというものです。アルゴリズムは最初にすべてのノードをそれ自身のコミュニティとして扱い、次にそれらをより大きなコミュニティに統合し、さらにそれらをより大きなコミュニティに統合していきます。ウォークトラップアルゴリズムは、ユーザーにランダムウォークの長さを指定するよう求めます。過去の研究では、長さ4または5のウォークを使用することが示唆されていますが、これが「最良」の分割、例えばモジュラリティを最大化するものを生み出す保証はありません（Pons and Latapy 2005）。モジュラリティ（本文、第8章で詳述）は、分割の質を測定し、（与えられた分割に基づいて）コミュニティ内で引かれるエッジの数を、帰無モデルの下で期待される数と比較します。
関数は cluster_walktrap() です。主な引数は graph（対象のネットワーク、igraphオブジェクトとして）、steps（ランダムウォークのステップ数）、membership（T/F、メンバーシップは最高のモジュラリティスコアに基づいて計算されるべきか？デフォルトはT）です。まず、4ステップ進むことから始めましょう。
friend_comm_wt4 <- cluster_walktrap(graph = net182_friend_und, steps = 4,
membership = T)
friend_comm_wt4IGRAPH clustering walktrap, groups: 4, mod: 0.27
+ groups:
$`1`
[1] "2" "7" "8" "13" "14"
$`2`
[1] "1" "3" "5" "6" "9" "10" "11" "12" "15"
$`3`
[1] "4"
$`4`
+ ... omitted several groups/vertices次に、各ノードのメンバーシップと、4ステップの解に基づくモジュラリティスコアを取得しましょう。
mems_wt_4step <- membership(friend_comm_wt4)
mems_wt_4step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 1 2 3 2 2 1 1 2 2 2 2 1 1 2 4 mod_wt_4step <- modularity(friend_comm_wt4)
mod_wt_4step[1] 0.2695578もし3ステップを使ったらどうなるでしょうか？
friend_comm_wt3 <- cluster_walktrap(graph = net182_friend_und,
steps = 3, membership = T)
mems_wt_3step <- membership(friend_comm_wt3)
mems_wt_3step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 1 3 4 3 3 1 1 2 2 3 2 1 1 2 5 mod_wt_3step <- modularity(friend_comm_wt3)
mod_wt_3step[1] 0.27976193ステップを使用するとモジュラリティがわずかに高くなることがわかります。table 関数を使って2つの分割を比較できます。
table(mems_wt_4step, mems_wt_3step) mems_wt_3step
mems_wt_4step 1 2 3 4 5
1 5 0 0 0 0
2 0 5 4 0 0
3 0 0 0 1 0
4 0 0 0 0 1大きな違いは、3ステップを使用すると、（4ステップに基づいた）コミュニティの1つが2つに分割されるように見えることです（4ステップのコミュニティ2が3ステップのコミュニティ2と3に分割）。
見つかったコミュニティに基づいてネットワークをプロットし、2つの分割を比較してみましょう。以前と同じようにネットワークをプロットしますが、ウォークトラップアルゴリズムを使用して見つかったコミュニティに基づいてノードを色分けします。まず、両方のプロットで使用するレイアウトを定義します。これにより、ネットワークが同じように配置および回転され、分割の比較が容易になります。
par(mfrow = c(1, 2))
layout <- layout.fruchterman.reingold(net182_friend)
plot(net182_friend_und, layout = layout, #note the use of layout
vertex.color = mems_wt_4step, edge.color = "light gray",
vertex.size = 20, main = "Walktrap: 4 Steps")
plot(net182_friend_und, layout = layout, #note the use of layout
vertex.color = mems_wt_3step, edge.color = "light gray",
vertex.size = 20, main = "Walktrap: 3 Steps")
これまでの結果は、（孤立点を無視すれば）2つの基本的なコミュニティ（2, 7, 8, 13, 14 と 1, 3, 5, 6, 9, 10, 11, 12, 15）があり、そのうちの1つのコミュニティが内部で分割されていることを示唆しています。3ステップの解では、より大きなコミュニティが2つに分割されていることがわかります：(3, 5, 6, 11) と (1, 9, 10, 12, 15)。より大きな値がより強い結びつきに対応するように、エッジに weights 引数を含めることが可能であることに注意してください（デフォルトではigraphオブジェクトのエッジウェイトが使用されます）。
8.3.2 エッジ媒介性（Edge Betweenness）
エッジ媒介性アルゴリズムの考え方は、別々のコミュニティをつなぐエッジは、あるコミュニティから別のコミュニティへのすべての最短経路がそれらを通過しなければならないため、高いエッジ媒介性を持つ可能性が高いというものです。したがって、エッジ媒介性スコアが最も高いエッジを繰り返し削除していくと、グラフ内のコミュニティの階層的なマップが得られます。詳細については Newman and Girvan (2004) を参照してください。関数は cluster_edge_betweenness() です。
friend_comm_eb <- cluster_edge_betweenness(graph = net182_friend_und)
friend_comm_ebIGRAPH clustering edge betweenness, groups: 5, mod: 0.28
+ groups:
$`1`
[1] "1" "9" "10" "12" "15"
$`2`
[1] "2" "7" "8" "13" "14"
$`3`
[1] "3" "5" "6" "11"
$`4`
+ ... omitted several groups/verticesデフォルトでは、モジュラリティを最大化するコミュニティが選択されます。メンバーシップを取得し、上記の3ステップのウォークトラップの解と比較してみましょう。
mems_eb <- membership(friend_comm_eb)
table(mems_wt_3step, mems_eb) mems_eb
mems_wt_3step 1 2 3 4 5
1 0 5 0 0 0
2 5 0 0 0 0
3 0 0 4 0 0
4 0 0 0 1 0
5 0 0 0 0 1この場合、見つかったコミュニティはアルゴリズム間で同じです（コミュニティのラベリングは異なる場合がありますが）。デフォルトでは最高のモジュラリティ値に基づいてメンバーシップを選択しますが、ノードのコミュニティへの完全な階層的分割を調べることも可能です。
plot(as.dendrogram(friend_comm_eb))
これはエッジ媒介性の結果のデンドログラムプロットです。y軸はコミュニティが分割される順序を捉えており、値が高いほどノード（別々の枝にある）がエッジ除去プロセスの早い段階で分割されること（したがって、コミュニティに配置される可能性が低いこと）を示します。
デンドログラムは階層的であり、異なる非集計レベルでのコミュニティの構成を示しています。例えば、4と16が最初に分割され、次に(11, 6, 5, 3, 15, 12, 10, 9, 1)と(14, 13, 8, 7, 2)が分割されます。次のレベルでは、(11, 6, 5, 3)と(15, 12, 10, 9, 1)が分割されます。デンドログラムを使用して、異なる非集計レベルでのコミュニティを視覚的に調べることができます。デンドログラムを下に進むにつれて、より多くのコミュニティを持つ、より非集約の解を見ることになります。
8.3.3 スクリープロット（Scree Plots）
私たちはしばしば、視覚的検査を超えて、異なる非集計レベルでのクラスタリング解をより定式的に調べたいと考えます。これは、コミュニティの数が増えるにつれて適合度がどのように変化するかを問うことに相当します。目標は、モジュラリティスコアをコミュニティの数に対してプロットした図を作成することです。これらのスクリープロットを、どの範囲の解をより詳細に調べる価値があるかを判断する手段として使用できます。このようにして、最高のモジュラリティスコアを持つ解を自動的に使用するよりも、少しうまくやることができます。これは、多くの可能な分割があり、多くの解が同様のモジュラリティスコアを提供する大規模なネットワークでは特に重要です。
まず、すべての非集計レベルにわたってコミュニティの数とモジュラリティスコアを抽出する関数を作成します。引数は communities（コミュニティオブジェクト）と graph（対象のigraphネットワーク）です。この関数は、コミュニティ検出アルゴリズムが（ウォークトラップやエッジ媒介性のように）階層構造を持つことを前提としています。
extract_modularity_data <- function(communities, graph){
# 引数:
# communities: igraphのコミュニティオブジェクト
# graph: igraphオブジェクト
mems_list <- list() # メンバーシップの情報が保存されるリスト
num_communities <- NA # コミュニティの数が保存されるベクトル
modularities <- NA # モジュラリティスコアが保存されるベクトル
# 集約の水準（すなわち段階）を
# 階層的マージデータから抽出する.
num_merges <- 0:nrow(communities$merges)
# 初めは全てのノードが自身だけのコミュニティに属していることに対応する
# 0から始める。これはマージデータフレームに行を持っていない。
# それぞれの集約のレベルを繰り返す
for (x in 1:length(num_merges)){
# 最初にcut_at関数で与えられたマージレベルのメンバーシップ情報を
# 抽出する。入力はコミュニティオブジェクトと関心のあるマージ段階。
mems_list[[x]] <- cut_at(communities, steps = num_merges[x])
# そして与えられたクラスタリング解法に紐づいたコミュニティの数を計算する:
num_communities[x] <- length(unique(mems_list[[x]]))
# 当該コミュニティ帰属に対応する値を取得できていることを確かめるために
# モジュラリティスコアも計算する:
modularities[x] <- modularity(graph, mems_list[[x]])
}
# 抽出した情報をデータフレームにまとめる
plot_data <- data.frame(modularity = modularities,
num_communities = num_communities)
# 小さいコミュニティ数から大きなコミュニティ数になるよう並び替える:
mems_list <- mems_list[order(plot_data$num_communities)]
plot_data <- plot_data[order(plot_data$num_communities), ]
rownames(plot_data) <- 1:nrow(plot_data)
# 結果をリスト形式で出力:
return(list(summary_data = plot_data,
membership_list = mems_list))
}それでは、エッジ媒介性の結果を入力として、私たちの関数 extract_modularity_data() を実行してみましょう。
modularity_data <- extract_modularity_data(communities = friend_comm_eb,
graph = net182_friend_und)出力は2つの要素を持つリストです。1つ目は要約データフレームで、コミュニティの数が増えるにつれてモジュラリティスコアがどう変わるかを示します。2つ目はリストで、各クラスタリング解（要約データフレームの各行に対応）の下でのコミュニティメンバーシップを示します。要約データフレームを抽出して見てみましょう。
summary_data <- modularity_data[[1]]
summary_data modularity num_communities
1 0.000000000 3
2 0.269557823 4
3 0.279761905 5
4 0.238945578 6
5 0.211734694 7
6 0.147675737 8
7 0.103458050 9
8 0.064909297 10
9 0.021825397 11
10 0.007936508 12
11 -0.013888889 13
12 -0.044501134 14
13 -0.061507937 15
14 -0.073412698 16最初の列は各クラスタリング解のモジュラリティスコアを示します。2番目の列は、そのモジュラリティスコアに関連するコミュニティの数です。
これで結果をプロットする準備ができました。ggplot() を使用して、x軸にコミュニティの数、y軸にモジュラリティスコアを持つスクリープロットを作成します。線グラフと棒グラフを含めます。入力データフレーム（summary_data）をサブセット化すれば、モジュラリティスコアの一部だけをプロットすることもできます。これは、プロットする値の数が非常に多くなる大規模なネットワークで役立ちます。
ggplot(summary_data, aes(num_communities, modularity)) +
geom_bar(stat = "identity", fill = "grey") +
geom_line(color = "black", linetype = "solid") +
geom_point(shape = 19, size = 1, color = "black") +
labs(title = "Modularity by Number of Communities",
x = "Number of Communities", y = "Modularity")
このようなプロットは、最適なコミュニティ数を決定するのに役立ちます。一般に、モジュラリティが高い解を求めますが、特にコミュニティを追加しても適合度がわずかにしか改善されず、より単純な解がより直感的で実質的に明確なストーリーを提供する場合は、必ずしもモジュラリティが最も高いものを選択するとは限りません。
さらに、多くの解が同様のモジュラリティスコアを提供する可能性があり、スクリープロットはどの解をより詳細に調べるべきかを判断するのに役立ちます。私たちのプロットを見ると、最も良い2つの解は4つまたは5つのコミュニティを持つものであり、その後モジュラリティスコアが減少し始めていることが明らかです。これらの2つの解をより注意深く調べる必要があります。
実際、私たちはすでに5コミュニティの解を調べています。これはモジュラリティが最も高い解であり、元のエッジ媒介性の結果に自動的に含まれています。4コミュニティの結果はそれほど簡単にはアクセスできません。まず、modularity_data（私たちの関数からの出力オブジェクト）からメンバーシップリストを抽出し、上記の要約プロットで表される各解のコミュニティメンバーシップを示す必要があります。メンバーシップリストは modularity_data の2番目の要素です。
mems_list <- modularity_data[[2]]次に、メンバーシップリストのどの部分を取得するかを決定します。4つのコミュニティに関連するメンバーシップIDが必要です。
mems_ids <- which(summary_data$num_communities == 4)次に、4コミュニティの解のメンバーシップを抽出します。
mems_eb4 <- mems_list[[mems_ids]]
mems_eb4 [1] 1 2 1 3 1 1 2 2 1 1 1 1 2 2 1 4結局のところ、これは4ステップを使用したウォークトラップアルゴリズムと同じコミュニティの集合です。
8.3.4 多重レベルクラスタリング（Multi-level Clustering）
もう一つよく使われるアプローチは、多重レベルクラスタリング、または多重レベルモジュラリティ最適化です。基本的な考え方は、各ノードをそれ自身のコミュニティから始めることです。次に、各頂点はモジュラリティを最も増加させるコミュニティに移動させられます（または、各ノードiについて、アルゴリズムはモジュラリティを最も増加させる移動を選択します）。どの移動もモジュラリティを増加させなければ、ノードは自身のコミュニティに留まります。このフェーズは、モジュラリティの局所的な最大値に達するまで続きます。その後、プロセスは新しく統合されたコミュニティに基づいて再び開始され、新しいノードは前のフェーズで見つかったコミュニティになります。Blondel et al. (2008) を参照してください。igraphの関数は cluster_louvain() です。
resolution引数を設定できます。これは、アルゴリズムがコミュニティを探す際に使用する解像度を決定します。値が高いと、より多くの小さなコミュニティが得られ、値が低いと、より少ない大きなコミュニティが得られます。ここではデフォルトの1に設定しますが、複数の値でこれを実行し、より少ない/多いコミュニティ数での結果を（上記の分析と同様に）調査することもできます。また、結果を再現しやすくするためにシードを設定します。
set.seed(100)
friend_comm_multi <- cluster_louvain(graph = net182_friend_und,
resolution = 0.8)多重レベルのコミュニティ構造を見てみましょう。
friend_comm_multi$memberships [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] 1 2 3 4 3 3 2 2 1 1 3 1 2 2
[2,] 1 2 1 3 1 1 2 2 1 1 1 1 2 2
[,15] [,16]
[1,] 1 5
[2,] 1 42つの行、つまりレベルがあることがわかります。これを、2つの異なる粒度レベルでコミュニティ/グループ構造を見ていると考えることができます。出力は、最も非集約のもの（1行目）から最も集約されたもの（2行目）へと整理されています。
ここで1行しか出てこない場合について
最初、resolution=1でやったら、ここで2行出てくるはずが1行しか出てきませんでした。これは、第1フェーズで発見されたコミュニティが最適と判断されたため、第2フェーズでのコミュニティの集約が行われなかったことから起きた現象です。
第1フェーズでは、各ノードを単位としてコミュニティを形成しますが、第2フェーズでは第1フェーズで形成したコミュニティを一つのノード（スーパーノード）とみなして同じ作業を行い、さらに大きなコミュニティに集約する作業を行なっています。ここでモジュラリティが増加する選択肢がなかった場合、第2フェーズの結果は表示されません。
解像度を下げると、より大きなコミュニティを形成しようとするため、第2フェーズが行われる可能性が上がり、2行目が出てくるかもしれません。私もresolution=0.8にしたら、2行目が現れました。ただし、ここでのレベル1のコミュニティは教科書のものとは少し異なっています。
1つ目のレベルの個人が2番目のレベルでどのようにネストされているかを確認するために、簡単なテーブルを作成してみましょう。
mems_mult_level1 <- friend_comm_multi$memberships[1, ]
mems_mult_level2 <- friend_comm_multi$memberships[2, ]
table(mems_mult_level1, mems_mult_level2) mems_mult_level2
mems_mult_level1 1 2 3 4
1 5 0 0 0
2 0 5 0 0
3 4 0 0 0
4 0 0 1 0
5 0 0 0 12番目のレベルのコミュニティ1にいる全員が、最初のレベルでは2つのコミュニティに分かれていることがわかります。各解に関連するモジュラリティも見てみましょう。
friend_comm_multi$modularity[1] 0.3476190 0.3823129そして、2つの解をプロットします。
par(mfrow = c(1, 2))
#4 communities
plot(net182_friend_und, layout = layout, vertex.color = mems_mult_level2,
edge.color = "light gray", vertex.size = 20,
main = "Level 2 Community Membership")
#5 communities
plot(net182_friend_und, layout = layout, vertex.color = mems_mult_level1,
edge.color = "light gray", vertex.size = 20,
main = "Level 1 Community Membership")
これは、異なる集計レベルでのエッジ媒介性で見たコミュニティと似ていますが、ここでの5コミュニティの解は少し異なっています（そしてやや低いモジュラリティスコアを示しています）。より一般的に言うと、エッジ媒介性と多重レベルアルゴリズムは、ネットワークの基本的な分割（4つのコミュニティがある場合）については一致しますが、（より大きなコミュニティ内を見て）ネットワークをさらにどのように分割するかについては一致しません。
高速貪欲法（fast and greedy）やラベル伝播法（label propagation）のような他のアルゴリズムも同様の結果を提供しますが、常にそうとは限りません。他のオプションについては、以下を見てください。 ?cluster_fast_greedy ?cluster_label_prop ?cluster_spinglass
その他のクラスタリング手法について
高速貪欲法では5つのクラスターに分かれる。
showtext_auto()
friend_comm_fandg <- cluster_fast_greedy(graph = net182_friend_und)
plot(net182_friend_und, layout = layout, vertex.color = friend_comm_fandg$membership,
edge.color = "light gray", vertex.size = 20,
main = "高速貪欲法でのコミュニティ分割")
ラベル伝播法では4つのクラスターに分かれる。
friend_comm_prop <- cluster_label_prop(graph = net182_friend_und)
plot(net182_friend_und, layout = layout, vertex.color = friend_comm_prop$membership,
edge.color = "light gray", vertex.size = 20,
main = "ラベル伝播法でのコミュニティ分割")
スピングラス法では孤立ノードは扱えないので、孤立ノードを削除してからクラスタリングを行い、色分けする。これまでのコミュニティとはかなり違うコミュニティ（全部で3つ）が得られることが分かる。
friend_comm_spinglass <- cluster_spinglass(graph = net182_noisolates)
plot(net182_friend_und, layout = layout, vertex.color = friend_comm_spinglass$membership,
edge.color = "light gray", vertex.size = 20,
main = "スピングラス法でのコミュニティ分割")
8.3.5 結束ブロッキング (Cohesive Blocking)
4番目の例として、MoodyとWhiteの結束ブロッキング手法を使い、友情ネットワークにおける結束グループを考察します (Moody and White 2003)。この考え方は、頂点連結度に基づいてネットワークを階層的にグループへとサブセット化するものです。あるノードの集合がk-連結であるとは、その集合の全メンバーが互いに到達できなくなるまでにk個のノードを削除する必要がある場合を指します。このアルゴリズムは、より高い連結度を持つノードの集合を連続的に見つけていくことで機能します。これは、上記（8.2）の結束性に関するセクションで探求した考え方に基づいています。例えば、先ほどの頂点連結度の計算では、孤立点以外のすべてのノードが4-連結であることがわかりました。MoodyとWhiteの結束ブロッキング手法を実行する関数はcohesive_blocks()です。
friend_comm_cohesive <- cohesive_blocks(graph = net182_friend_und)
friend_comm_cohesiveCohesive block structure:
B-1 c 0, n 16
'- B-2 c 4, n 14 ooo.oooooo ooooo. 出力は、ブロックのメンバーシップと（各ブロックの）結束性で構成されます。2つのブロックがあるようで、1つは頂点連結度0、もう1つは頂点連結度4です。結果をプロットすることもできます。
plot(friend_comm_cohesive, net182_friend_und)
このブロッキング手法が、まず孤立点をメインコンポーネントから分離していることは明らかです。メインコンポーネントにいる全員は結束レベル4で接続されており、この集合を切断するには4人の削除が必要です。これは上で見た結果を反映しています。
ここまで、友情ネットワーク内のコミュニティを特定するために、さまざまなアルゴリズムを見てきました。結果は、5つの明確に定義されたコミュニティ（2つの孤立点を含む）が存在する可能性が高いことを示唆しています。結束ブロッキング手法は、メインコンポーネントが潜在的に3つのサブグループに分割される可能性がある一方で、それ自体は依然としてかなり結束性が高い（すべてのメンバーが4つの独立した経路で接続されているため）ことを示唆するでしょう。
コミュニティ分析の結果を用いてさらに分析を進め、見つかったコミュニティの実質的な意味合いを明らかにすることができます。コミュニティ間の行動規範（例：逸脱行動）、各コミュニティにマッピングされるアイデンティティ、コミュニティ間の関係（例：あるグループのメンバーは別のグループを嫌っているか？）などについて問うことができます。ここでは、人口統計学的特性がコミュニティにどのようにマッピングされるか（またはされないか）を見ていきます。その後、コミュニティ間の関係を見ていきます。
8.4 人口統計学的特性
単純化のため、エッジ媒介性アルゴリズムに基づくコミュニティを使用し、人種的アイデンティティという単一の特性に焦点を当てます。問題は、この教室で人種がどれほど顕著な特徴かということです。人種はコミュニティに強く反映されるのでしょうか？それともコミュニティは何か別のものに基づいて組織されているのでしょうか？まずネットワークを再度プロットしますが、今回はノードを人種によって色分けします。最初に、人種に基づいてノードの色を設定します：黒人なら青、白人なら白です。
library(car)
cols <- recode(class182_attributes$race,
as.factor = F, "'black' = 'blue'; NA = NA; else = 'white'")これがうまくいったか確認しましょう。
table(class182_attributes$race, cols) cols
blue white
black 8 0
white 0 8良さそうです。では、ノードを人種で色分けし、見つかったコミュニティ（上記のエッジ媒介性による分割に基づく）の周りにポリゴンを配置したプロットを作成しましょう。
plot(friend_comm_eb, net182_friend_und,
col = cols, layout = layout,
main = "Race Mapped onto Communities")
この教室は人種の構成に基づいて、3つのコミュニティに分かれていることがわかります。主に黒人で構成されるコミュニティ、主に白人で構成されるコミュニティ、そして均等に分かれているコミュニティです。これは、社会的コミュニティが、白人/黒人のようなアプリオリな社会的カテゴリーに対応することもあれば、そうでない場合もあることを示唆しています。ネットワーク分析者としての課題は、社会的コミュニティが事前に決定されたラベルにマッピングされると仮定するのではなく、どのような社会的コミュニティが出現するかを問うことです。同様に、細分化された大きなコミュニティが、それ自体の中で人種的な線引き（白人 (3, 6, 5, 11) 対 より人種的に統合された (1, 9, 10, 12, 15)）に沿って分かれていることがわかります。
また、各コミュニティにおける白人/黒人の割合を計算し、偶然によって期待される割合と比較することもできます。各コミュニティの人種分布を計算するためのちょっとした関数を書いてみましょう。
proportion_function <- function(communities, attribute){
# 引数:
# communities: コミュニティ所属を示すベクトル
# attribute: 属性ベクトル
# ここでは、'attribute' に含まれる各カテゴリに属する割合を計算します。
# まず、カテゴリごとの度数表を作成し、次に各カテゴリの割合を求めます。
# これは、'communities' を使用して、各コミュニティに対して (tapply を使って) 実行されます。
dat <- tapply(factor(attribute), communities,
function(x) {y <- table(x); y / sum(y)})
# その後、do.call を使用して行列として出力します。
return(do.call(rbind, dat))
}私たちの関数を、エッジ媒介性のメンバーシップでコミュニティを定義し、人種のベクトルで属性を定義して使ってみましょう。
proportion_function(communities = mems_eb, attribute = class182_attributes$race) black white
1 0.6 0.4
2 0.8 0.2
3 0.0 1.0
4 0.0 1.0
5 1.0 0.0コミュニティ1では0.6が黒人、0.4が白人であることがわかります。コミュニティ2では0.8が黒人、0.2が白人、というようになります。関数を利用した上記のコードは、さまざまな方法で実現できることに注意してください。例えば、下記でも実現できます。
table_list <- list()
race_factor <- factor(class182_attributes$race)
for (i in 1:max(mems_eb)){
tab <- table(race_factor[mems_eb == i])
table_list[[i]] <- tab / sum(tab)
}
do.call(rbind, table_list) black white
[1,] 0.6 0.4
[2,] 0.8 0.2
[3,] 0.0 1.0
[4,] 0.0 1.0
[5,] 1.0 0.0また、各コミュニティの割合を、ランダムな期待値の下で期待されるものと比較することもできます（エゴネットワークのチュートリアルで見た問題と似ています）。例えば、ネットワークとコミュニティのメンバーシップを固定し、メンバーにランダムに特性を割り当て、生徒がコミュニティ間にランダムに分布した場合の人種の分布がどのようになるかを示すことができます。このケースでは、これを少し非定式的に行い、まず教室内の人種の単純な集計表から始めます。
table(class182_attributes$race)
black white
8 8 このケースでは、8人が黒人、8人が白人と自認しているため、各コミュニティの0.50が黒人、0.50が白人であると期待されます。明らかに、実際の結果はこのランダムなベースラインから逸脱しており、特にコミュニティ2と3はそれぞれ主に黒人と白人で構成されています。コミュニティ1、つまり「混合」コミュニティは、個人が人種に基づいた選別なしにランダムにコミュニティを形成した場合に期待される値とほぼ同じです。コミュニティ4と5は両方とも孤立したノードであるため、変動はありえません。もちろん、シミュレーションを用いて帰無仮説を生成することもできます。一連の抽出を通じて、個人をランダムにコミュニティに割り当て、各コミュニティの白人/黒人の割合を計算し、それらの値を観測値（実際のネットワーク上の値）と比較します。
8.5 コミュニティの重複
ここでは、コミュニティ間の接触レベルを調べます。コミュニティ内（またはコミュニティ間）にはいくつの友情関係があるのでしょうか？ これは、見つかったコミュニティ間の相互接続（またはその欠如）について教えてくれます。これは、コミュニティ検出の側面と、結束性に関するより一般的な問いを組み合わせたものです。なぜなら、コミュニティ間の接続が、ネットワーク全体の結束性を大きく構成するからです。まず、コミュニティ内外の友情の結びつき（および非結びつき）の表を作成することから始めます。これには、各ダイアドについて2つの情報が必要です。第1に、i-jが友人であるかどうか、第2に、i-jが同じコミュニティにいるかどうかです。まず、上記のダイアドのデータフレームを取得しましょう。
class182_dyads <- class182_networkdata[, c("ego", "alter")]
head(class182_dyads) ego alter
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 6次に、エゴとオルターが結びついているかどうかを示すベクトルを取得します。まず、友人関係を示す隣接行列を取得します。自分自身への結びつきは考慮したくないので、対角線上にNAを置きます。次に、行列をベクトルに展開します。転置を使って、順序が正しいこと（行から列へ：1-2、1-3…と続く）を確認します。
mat182_friend <- as_adjacency_matrix(net182_friend_und, sparse = F)
diag(mat182_friend) <- NA
friend <- c(t(mat182_friend))
head(friend)[1] NA 1 0 0 1 11はiとjが友人であることを意味し、0はiとjが友人でないことを意味します。
次に、各ダイアドが同じコミュニティにいるかどうかを示すベクトルを作成します。この例では、4つのコミュニティを持つ多重レベル解mems_mult_level2に基づくメンバーシップを使用します。
以下のコードは、多重レベル解に基づくメンバーシップを取得し、それをエゴ(class_182_dyads$ego)でサブセット化し、オルター(class_182_dyads$alter)でサブセット化し、そしてエゴとオルターが同じコミュニティにいるかどうかを問いかけます。
ego_community <- mems_mult_level2[class182_dyads$ego]
alter_community <- mems_mult_level2[class182_dyads$alter]
same_comm <- ego_community == alter_communityこれらをまとめ、コミュニティの状態（iとjは同じコミュニティにいるか？）と友情（iとjは友人か？）の表を作成する準備ができました。ijの情報はjiの情報と同じであり、二重に数える理由はないので、2で割ります。
table(same_comm, friend) / 2 friend
same_comm 0 1
FALSE 67 7
TRUE 11 35この表は、67のダイアドが友人ではなく、同じコミュニティにもいないことを示唆しています。11は友人ではないが同じコミュニティにいます。7は友人だが異なるコミュニティにいます。そして35は友人であり、同じコミュニティにいます。
このような表があれば、関心のあるさまざまな統計量を計算できます。ここではオッズ比を計算し、同じコミュニティにいる2人が友人として互いを選ぶオッズを（異なるコミュニティにいる2人が友人として互いを選ぶオッズと比較して）示します。
(35 * 67) / (7 * 11)[1] 30.45455明らかに、グループ間の結びつきよりもグループ内の結びつきの方がはるかに多いです。しかし、分析を通して見てきたように、ネットワーク全体の結束性をかなり高くするには十分なクロスグループの結びつきが存在します（ネットワークのサイズが小さいことと相まって）。同様に、人種は概してグループにマッピングされることがわかります。しかし、グループ自体が相互に接続されているため、このような人口統計の社会的グループへのマッピングは、教室全体の連帯に対して強い脅威をもたらすものでは実際にはありません。
8.6 ビッグデータの例
次に、大規模なヨーロッパの研究機関で働く個人のEメールパターンを使用した、全く異なる2番目の例に移ります。目標は、上で使用した教室データよりもはるかに大きなネットワークでコミュニティ分析を行うことです。このEメールネットワークには265,214のノードと400,000以上のエッジがあります。データは以下で無料で入手できます。
https://snap.stanford.edu/data/email-EuAll.html
まずデータを読み込み、ネットワークを構築しましょう。
url3 <- "https://github.com/JeffreyAlanSmith/Integrated_Network_Science/raw/master/data/email-EuAll.txt"
email_edges <- read.table(file = url3)
dim(email_edges)[1] 420045 2head(email_edges) V1 V2
1 0 1
2 0 4
3 0 5
4 0 8
5 0 11
6 0 20エッジは、iさんがjさんに（表ではV1さんがV2さんに）少なくとも1通のEメールを送ったかどうかを捉えています。ネットワークを作成する前に、これを少し整理する必要があります。まず、データに分かりやすい列名を付けましょう。
colnames(email_edges) <- c("ego", "alter")次に、すべてのIDに1を加える必要があります。元のファイルは0でインデックスされていましたが、1から始めたいからです。
email_edges <- email_edges + 1また、iさんがiさんにEメールを送ったケースがいくつかあるので、それらを取り除きます。
email_edges <- email_edges[email_edges[, 1] != email_edges[, 2], ]では、igraphオブジェクトを作成しましょう。ネットワーク内のすべてのノードのIDを示すvertices引数を設定することで、孤立点を確実に捉えます。
email_network <- graph_from_data_frame(d = email_edges, directed = T,
vertices = (id = as.numeric(1:265214)))ネットワークを無向として扱いましょう。
email_network <- as.undirected(email_network, mode = "collapse")ネットワークのノード数を考えると、教室のネットワークで効果的だった戦略は、このサイズのネットワークでは調整するか、あるいは放棄する必要があります。出力の解釈も多少変える必要があります。特に、一部のアルゴリズムは、非常に粗い解像度で見るとモジュラリティを最適化する可能性があるため、少数の大きなコミュニティを持つ解を生成する可能性があります。これは、いくつかの大きな分断が存在することを示すかもしれませんが、これらの大きな分断を構成するより詳細なコミュニティを知る上ではあまり役立ちません。したがって、ネットワークの異なるレベル、または異なる粒度で存在するコミュニティを見ることが重要になるかもしれません。大規模なネットワークを扱うための一つの戦略を見てみましょう。
8.6.1 多重レベルクラスタリング
過去の研究では、ネットワークサイズが大きくなるにつれて、他のアルゴリズムよりもはるかにうまくスケールするアルゴリズムがあることが示されています。特に、一部のアルゴリズムは大規模なネットワークで非常に長い実行時間を要し、大量のメモリを使用します。これは、これらのアルゴリズムを使用できないという意味ではありませんが、そのような戦略の潜在的なコストを理解することが重要です。例えば、Yang, Algesheimer, and Tessone (2016)は、エッジ媒介性やスピングラスのような他のアプローチと比較して、多重レベルクラスタリングアプローチが大規模ネットワークでうまく機能することを示しています。ここでは、20万以上のノードを持つネットワークで多重レベルアプローチを利用します。
set.seed(101)
email_comm_multi <- cluster_louvain(graph = email_network,
resolution = 1)これは他のアルゴリズムでははるかに時間がかかる可能性があります。例えば、email_comm_wt <- cluster_walktrap(graph = email_network, steps = 4, membership = T)
では、異なる集約レベルでのコミュニティ/グループ構造を見てみましょう。
email_mems <- email_comm_multi$memberships
nrow(email_mems)[1] 33つの異なるレベルがあるようです。各集約レベルでいくつのコミュニティが存在するか見てみましょう。ここでは、各コミュニティの人数を計算するための小さな関数を書きます。
length_func <- function(x) {length(unique(x))}そして、これをメンバーシップ行列の行に適用します。
num_comms <- apply(email_mems, 1, length_func)
num_comms[1] 18354 16024 15919最も非集約的な解は18351のコミュニティを持ち、最も集約的な解は15920のコミュニティを持つことがわかります。各解のモジュラリティも見てみましょう。
email_comm_multi$modularity[1] 0.6905131 0.7820247 0.7911850最も集約された解（レベル3）に焦点を当て、結果がどのようになるか見てみましょう。見つかったコミュニティを評価する第一歩として、この解に基づいたコミュニティがどれくらいの大きさかを見てみましょう。メンバーシップベクトルに対してテーブルを作成し、そのテーブルの要約を計算して、コミュニティのサイズ分布がどのようになっているかを見てみます。
mems_email <- email_comm_multi$memberships[3, ]
summary(as.numeric(table(mems_email))) Min. 1st Qu. Median Mean 3rd Qu. Max.
1.00 2.00 2.00 16.66 2.00 15942.00 見ての通り、中央値（および75パーセンタイル）はサイズ2ですが、最大値は16233（ではなくここでは15942）であり、ほとんどのグループは小さいものの、いくつかの大きなグループが存在することを示唆しています。これらの大きなコミュニティの中には、1000、さらには10000ノードを超えるものもあります。10000ノードのコミュニティは、比較的に高いグループ内密度を持つ人々の集合を構成するとしても、直接解釈するには大きすぎる可能性が高いです。
したがって、一つの戦略として、ネットワーク全体ではなく、初期のコミュニティを新たな出発点とし、各コミュニティ内でコミュニティ検出を行うことが考えられます。これにより、最初に見つかったコミュニティがさらに小さなコミュニティに分割され、コミュニティ内のコミュニティという入れ子構造が得られます。これは、初期の結果で見られた全体的な（低解像度の）像を維持しつつ、ますます高い粒度でコミュニティ構造を見ることができることを意味します。
8.6.2 初期コミュニティ内のコミュニティ構造を見る
ここでは、既に検出されたコミュニティの集合内でコミュニティ検出を実行する方法を示します。ネットワークが小さくなることで他のオプションを使用することがより現実的になるため、コミュニティ検出には異なるアルゴリズムを利用します。さらに分割したい各コミュニティについて、そのメンバーだけのネットワークを形成し、そのサブグラフでコミュニティ検出を実行する必要があります。このタスクを実行するための小さな関数を書きましょう。
create_subcommunity <- function(graph, initial_communities, community_number){
# 引数:
# graph: igraphオブジェクト
# initial_communities: 元のコミュニティのメンバーシップ
# community_number: 対象のコミュニティ番号（つまり、さらに分割したいコミュニティ）
# ここで、対象のコミュニティだけのサブグラフを作成します
in_community <- which(initial_communities == community_number)
subgraph1 <- induced_subgraph(graph = graph,
vids = in_community)
# 次に、サブグラフに対してコミュニティ検出アルゴリズム（fast and greedyを使用）を実行します
comm1 <- cluster_fast_greedy(graph = subgraph1)
# サブグラフ内の各個人のコミュニティメンバーシップを取得します
mems_subgraph1 <- membership(comm1)
# 次に、サブグラフ内のIDを取得し、元の完全なネットワークにマッピングし直せるようにします
ids_map <- as.numeric(vertex_attr(subgraph1, "name"))
mems_new <- initial_communities # 元のコミュニティを単にコピーします
# ここで、コミュニティのラベルを付け直し、元の完全なネットワーク上のコミュニティの集合に戻せるようにします。
# これらの新しいコミュニティIDが一意であることを保証したいため、元のコミュニティ番号の最大値を取得し、
# それをサブグラフのコミュニティIDに加算します。
mems_subgraph1_relabel <- mems_subgraph1 + max(initial_communities)
# ここで、新しいコミュニティを、ネットワーク全体に対応するコミュニティメンバーシップのベクトルに配置します。
mems_new[ids_map] <- mems_subgraph1_relabel
# 注意：対象のサブグラフ内のものだけを変更します。
# 必要であれば、すべてのコミュニティのラベルを付け直し、古いコミュニティ番号を削除して、小さい順に並べ替えることができます：
num_comms_new <- length(unique(mems_new))
mems_updated <- as.numeric(as.character(factor(mems_new,
labels = 1:num_comms_new)))
# ここで、サブグラフ、メンバーシップ、そして更新されたコミュニティメンバーシップのベクトルを出力します：
return(list(subgraph = subgraph1,
mems_subgraph = mems_subgraph1,
membership_updated = mems_updated))
}では、例として3000以上のノードを持つコミュニティ番号33で実行してみましょう。入力は、Eメールネットワーク（graph引数で設定）、元のコミュニティの集合（initial_communitiesで設定）、そして内部を調べる対象のコミュニティ（community_numberで設定）です。
subcommunity_dat <- create_subcommunity(graph = email_network,
initial_communities = mems_email,
community_number = 33)サブグラフ、そのサブグラフ内のメンバーシップ、そしてグラフ全体で更新されたメンバーシップベクトルを取得しましょう。
subnet <- subcommunity_dat$subgraph
mems_subnet <- subcommunity_dat$mems_subgraph
mems_updated <- subcommunity_dat$membership_updatedでは、このより非集約的な分析に基づいて、ノードをコミュニティメンバーシップで色分けしたサブグラフをプロットしましょう。
layout_email <- layout.fruchterman.reingold(subnet)
plot(subnet, vertex.label = NA, vertex.size = .6,
layout = layout_email, edge.color = "light gray",
edge.curved = .2, vertex.frame.color = NA,
vertex.color = mems_subnet)
コミュニティ33内に、当初は見逃されていた（元の分析ではこのプロットの全員が同じコミュニティに配置されていた）サブコミュニティの集合が出現することがわかります。
新しいコミュニティベクトル（mems_updated）における対象コミュニティのメンバーシップを確認することも有用です。ここでは、mems_updatedに対して、元々コミュニティ33にいたノード（mems_emailで定義）のみを見てテーブルを作成します。
table(mems_updated[mems_email == 33])
15919 15920 15921
242 285 2 以前コミュニティ33にいた全員が、今では18のコミュニティに分かれていることがわかります（ここでは3つだが……）。これらのコミュニティのラベルも、コミュニティ全体のベクトル内で一意の値に設定されています。この新しいコミュニティメンバーシップの集合でモジュラリティスコアも確認できます。
modularity(email_network, mems_updated)[1] 0.7902892コミュニティ33を細分化しても、実際にはモジュラリティスコアは高くならなかったことに注意してください。それにもかかわらず、ネットワーク全体で（より大きなグループ内の）サブコミュニティがどのように見えるかを見ることは、依然として実質的な関心事であるかもしれません。
私たちの関数を使えば、この種の分析を関心のあるどのコミュニティにも拡張できます。ループ（またはlapply()）を使って、任意のコミュニティの集合に対してこれを行うことができます。例えば、特定のサイズ閾値より大きいすべてのコミュニティをさらに細分化することができます。これにより、異なる解像度レベルで分析されたコミュニティの集合が得られます。
例えば、ここでは最大のコミュニティであるコミュニティ2を見てみましょう。
subcommunity_dat <- create_subcommunity(graph = email_network,
initial_communities = mems_updated,
community_number = 2)注意すべき点が2つあります。第一に、initial_communitiesの入力は、そのベクトルを更新するたびに新しいメンバーシップリストで更新する必要があることを覚えておく必要があります（ここではmems_updatedを使用しました）。mems_updatedはmems_updated <- subcommunity_dat$membership_updatedとして定義したことを思い出してください。そして第二に、コミュニティメンバーシップベクトルを更新するにつれて、対象のコミュニティの番号が変わる可能性があり、プロセスが反復的に進むにつれてそれに応じて更新する必要があることに注意してください。
分割したコミュニティ2も可視化してみましょう。
subnet <- subcommunity_dat$subgraph
layout_email <- layout.fruchterman.reingold(subnet)
plot(subnet, vertex.label = NA, vertex.size = .6,
layout = layout_email, edge.color = "light gray",
edge.curved = .2, vertex.frame.color = NA,
vertex.color = mems_subnet)
全体として、このチュートリアルでは、結束性とコミュニティ構造に関連する多くの分析を提供しました。これらのトピックはそれ自体が重要であり、また、階層、2モードネットワーク、文化、拡散に関する研究など、他の分析の構成要素としても機能します（第9、11、12、14章を参照）。