グラフを使用したネットワークの分析

ソーシャルネットワーク分析は、ネットワーク理論を使用してさまざまなシステムを探索するプロセスです。膨大な数の既存のネットワーク（社会的、経済的、生物学的）が普遍的な特性を持っていることが明らかになったとき、それは正確に広く使用され始めました。1つのタイプを研究すると、他のネットワークの構造を理解し、それらから予測を行う方法を学ぶことができます。



すべてのネットワークは、個々の参加者（ネットワーク内の人または物）とそれらの間の関係で構成されます。ネットワークは、グラフ（これらのポイント間の接続を表す多くのポイントとラインで構成される構造）を使用して視覚化されることがよくあります。参加者はネットワークのノードとして表され、参加者の関係はそれらを結ぶ線として表されます。このような視覚化は、ネットワークの定性的および定量的評価を取得するのに役立ちます。





図： 1.外国為替市場を形成する銀行間の資金回転率を示す方向グラフ（1）。 EUの銀行は赤で、北米は青で、その他の国は緑でマークされています。





図： 2. 2010〜2014年のデンマークの監査パートナーの協力を示すグラフ（2）



ソーシャルネットワークの分析を使用して、資料と情報の両方のリソースのさまざまな相互作用と交換プロセスを分析することができます。たとえば、銀行のクライアント間のトランザクションのネットワーク（ノードが銀行のクライアントであり、エッジがそれらの間の転送である場合）を分析することにより、不正なトランザクションに関与する人の輪を特定したり、銀行の従業員による内部規制の違反を特定したりすることができます。



また、（従業員間のさまざまなタイプのコミュニケーションの例を使用して）作業関係のネットワークを構築することもできます。これは、組織の社会構造とこの構造における各従業員の位置を理解するのに役立ちます。各従業員のコミュニケーションの種類に関するデータがあれば、リーダーシップ、メンタリング、協力などの特性が彼のキャリアにどのように影響するかを分析し、得られた知識に基づいてキャリア目標を決定し、それらを達成するためのトレーニングプログラムを提案することもできます。



さらに、ネットワークの例を使用してイベントを予測できます。たとえば、ソフトウェア障害の可能性を推定するモデルがあり、その中には人を予測のソースと見なすものもあります。結局のところ、リリース前に製品を開発してテストするのは人です。それらの相互作用はネットワークを形成します。開発者をノードと見なすことができ、開発者が同じリリースの同じファイルで、ネットワークのエッジとして一緒に作業したかどうかを考えることができます。相互作用と以前の障害に関する情報を理解すると、最終製品の信頼性について多くのことがわかり、障害が発生する可能性が最も高いファイルが指摘されます。



それでは、ソーシャルネットワークの分析を実際に適用してみましょう。これを行うには、Pythonプログラミング言語、つまりグラフを操作するためのnetworkxライブラリ、視覚化のためのmatplotlibライブラリ、およびネットワーク内のコミュニティを強調表示するためのコミュニティライブラリを使用します。それらをインポートしましょう：

1.	import community
2.	import networkx as nx
3.	import matplotlib.cm as cm
4.	import matplotlib.pyplot as plt

1.データをインポートしてグラフに変換する

データセットとして、研究機関のメンバー間のすべての送受信メールに関する匿名情報が含まれている、ヨーロッパの大規模な大学からのメール通信を取り上げましょう（リンク）。データセットには、各行に相互に関連するノードのペアがリストされているtxtファイルが含まれています。

1.	G = nx.read_edgelist('email-Eu-core.txt', create_using=nx.DiGraph())
2.	print(' : {}'.format(G.number_of_nodes()))
3.	print(' : {}'.format(G. number_of_edges()))
4.	print('       : {}'.format(round(G.number_of_edges() / float(G.number_of_nodes()), 4)))

 : 1005
 : 25571
      : 25.4438

上記のコードでは、データセットがインポートされ、グラフに変換されています。次に、グラフの主なパラメータであるノードの数、エッジ、およびグラフ内のノードの隣接ノードの平均数を順次推定しました。最後のパラメーターは、ノードが互いにどれだけ密接に接続されているかを反映します。

2.グラフの主な特徴

特定の各グラフをどのように操作できるかを理解するには、まずグラフがどのように機能するかを理解する必要があります。グラフの構造を理解するための特徴を簡単に見てみましょう。



まず、接続性と方向性の概念を検討します。グラフ内のノードの各ペアが相互接続されている場合、グラフは接続されていると呼ばれます。どのノードからでも、他のノードにアクセスできます。グラフが切断されている場合は、最大に接続されたサブグラフ（コンポーネントと呼ばれる）に分割できます。また、グラフは有向および無向にすることができます。これは、2人の参加者間のリンクの方向性の存在によって決定されます。有向ネットワークの一例は、銀行の顧客間のトランザクションであり、各顧客は入金と出金の両方を受け取ることができます。



一般的な場合、有向グラフでは、接続は相互的ではありません。したがって、有向グラフでは、接続の概念ではなく、弱い接続と強い接続のコンポーネントの概念が区別されます。方向を無視するとグラフが接続される場合、コンポーネントは接続が弱いと見なされます。強力な接続のコンポーネントは、そのすべての頂点が相互に到達可能である場合にそのようなものになる可能性があります。メールデータセットのグラフの構造を見てみましょう。

1.	if nx.is_directed(G):
2.	        if nx.is_weakly_connected(G):
3.	                print('         .')
4.	        else:
5.	                print('       .')
6.	else:
7.	        if nx.is_connected(G):
8.	                print('    .')
9.	        else:
10.	                print('       .')

グラフは方向性があり、いくつかのコンポーネントで構成されています。



ここでは、グラフの方向性と接続性を確認し、データセットのグラフが方向付けられており、いくつかの切断されたコンポーネントが含まれていることを確認しました。強い接続と弱い接続の最大のコンポーネントを詳しく見てみましょう。

1.	G_weak = G.subgraph(max(nx.weakly_connected_components(G), key=len))
2.	print(' : {}'.format(G_weak.number_of_nodes()))
3.	print(' : {}'.format(G_weak.number_of_edges()))
4.	print('      : {}'.format(round(G_weak.number_of_edges() / float(G_weak.number_of_nodes()), 4)))
5.	
6.	G_strong = G.subgraph(max(nx.strongly_connected_components(G), key=len))
7.	print(' : {}'.format(G_strong.number_of_nodes()))
8.	print(' : {}'.format(G_strong.number_of_edges()))
9.	print('      : {}'.format(round(G_strong.number_of_edges() / float(G_strong.number_of_nodes()), 4)))


 : 986
 : 25552
      : 25.9148

 : 803
 : 24729
      : 30.7958

そこで、弱く接続されたコンポーネントとそれに含まれる強く接続されたコンポーネントの主な特性を取得しました。この段階でどのような結論を導き出すことができるか見てみましょう。 1005人の参加者のうち、986人が相互に通信し、そのうち183人が一方的に他の人にメールを送信し、803人だけが双方向の通信を維持していることがわかります。 823件のケースで、電子メールを介した通信の確立に失敗しました。また、最もアクティブな参加者（強力な接続コンポーネントに含まれる）が平均30人と通信していることもわかります。



グラフの構造を定義するグラフの他の重要な特性を見てみましょう。ノード間の関係が接続の存在そのものを反映しているだけでなく、この接続の強さを反映して特定の重みも反映している場合、グラフは重み付けされていると見なされます。電子メールメッセージを含むデータセットは、通信の事実のみを考慮し、送信された文字の数は考慮しないため、重み付けされていません。



さらに、ノードとリンクは、単子葉、二子葉、またはマルチレベルのさまざまなタイプのネットワークを作成できます。単子葉ネットワークは、1つのタイプの参加者とそれらの間の接続で構成されます。二者間ネットワークは、2つの異なるタイプの参加者で構成され、一方のタイプのノードはもう一方のタイプにのみ関連付けられます。マルチレベルネットワークにも2種類の参加者が含まれますが、リンクは、異なる種類の参加者と同じ種類の参加者の両方を接続できます（たとえば、マネージャー間の関係やプロジェクト間の関係）。私たちが研究のために取ったデータセットは、1つのタイプの参加者とそれらの間の接続のみで構成されているため、単子葉のネットワークです。

3.グラフの視覚化

次に、取得したデータセットを視覚化してみましょう。このためには、すでに上でインポートしたmatplotlibライブラリが必要です。

1.	plt.figure(figsize=(15, 15))
2.	plt.title('E-mails')
3.	nx.draw(G, node_size=5)
4.	plt.show()

最初の行は、将来の画像のサイズを設定し、特定の名前が割り当てられます。描画関数の3行目はグラフを通過し、ノードのサイズを指定します。その後、グラフが画面に表示されます。それを見てみましょう：





図。 3.研究機関のメンバー間のすべての受信および送信電子メールに関する情報とのユーザーインタラクションのグラフ。



結果のグラフでは、他の通信参加者と接続されていないポイントがいくつかあることがわかります。これらの人々は、他の参加者とは関係がなく、自分たちだけに手紙を送ったので、グラフに載りました。また、周辺には、いくつかの着信接続によってグラフの残りの部分に接続されているポイントがいくつかあることに気付くでしょう。これらは、グラフの弱く接続されたコンポーネントに分類されたが、強く接続されたコンポーネントには分類されなかった参加者です。



強いつながりの要素、つまり研究機関の他のメンバーと双方向のコミュニケーションをとっている人々を示すグラフも見てみましょう





。4.研究機関のメンバー間のすべての送受信メールに関する情報との強力な接続のコンポーネント..。

4.結び目の程度と結び目の程度の分布

グラフの構造がわかり、視覚化できるようになったので、さらに詳細な分析に移りましょう。グラフの各ノードには次数（そのノードの最も近い隣接ノードの数）があります。有向ネットワークでは、入口の程度（ノードへの着信接続の数）と出口の程度（ノードからの発信接続の数）の両方を区別できます。グラフの各ノードの次数を計算すると、ノードの次数の分布を決定できます。メールグラフを見てみましょう。

1.	degree = dict(G.degree())
2.	degree_values = sorted(set(degree.values()))
3.	hist = [list(degree.values()).count(x) for x in degree_values]
4.	plt.figure(figsize=(10, 10))
5.	plt.plot(degree_values, hist, 'ro-')
6.	plt.legend(['Degree'])
7.	plt.xlabel('Degree')
8.	plt.ylabel('Number of nodes')
9.	plt.show()

図：5.研究機関のメンバー間のすべての送受信電子メールに関する情報を含むグラフ内の度数の分布



結果のグラフには、ノードの度数の分布が表示されます。多数のノードは隣接ノードとの接続がほとんどありませんが、他のノードとの接続が多数ある大きなノードは少数です。参加者は膨大です。この傾向は配電の電力法則と呼ばれ、大規模なネットワークでは非常に一般的です。この法律は、さまざまな都市の人口の分布、インターネット上のサイトのランキング、さらには人々の間の富の分布を説明することができます。

5.グラフのパス、直径、平均距離

次に、グラフのメンバーがどの程度接続されているかを確認しましょう。まず、さまざまなタイプのノード間隔について説明します。



ノードを接続するエッジのシーケンスは、パスと呼ばれます。ほとんどの場合、研究では単純なパス、つまりサイクルと繰り返しノードのないパスが考慮されます。 2つのノード間の最短パスは、測地距離と呼ばれます。グラフの最長の最短パスは直径と呼ばれますが、偏差に非常に敏感です（数百万ドルのグラフの1つのチェーンが直径を変更する可能性があります）。有向グラフでは、直径の概念は、強力な接続のコンポーネントにのみ使用できます。直径を計算するには、ノードのペアごとにノード間にパスが存在する必要があるためです。無向グラフでは、検討中のコンポーネントが接続されていれば十分です。



もう1つの非常に有益な特性は、ノード間の平均距離です。これは、グラフ内のすべての最短パスの平均値を取得することで取得できます。平均距離はグラフの構造によって決まります。グラフがチェーンの形で作成されている場合、グラフは大きくなりますが、ノードが接続されているほど、平均距離は小さくなります。平均距離は、強く接続されたコンポーネントと弱く接続されたコンポーネントの両方について計算できます。

1.	print (': ', nx.diameter(G_strong))
2.	print ('     : ', nx.average_shortest_path_length(G_strong))
3.	print ('     : ', nx.average_shortest_path_length(G_weak))

: 6
     :  2.5474824768713336
     :  2.164486568301397

結果を見てみましょう。この場合の直径は、2人の見知らぬ人の間の最大距離を示しています。ここでは、6回のハンドシェイクのよく知られた理論のように、この距離は6です。コンポーネントの平均距離も小さく、平均して2回の「ハンドシェイク」で2人の見知らぬ人に十分です。ここでも興味深い現象が見られます。強く接続されたコンポーネントの平均距離は、弱く接続されたコンポーネントよりもわずかに短くなっています。これは、結合の方向が弱く接続されたコンポーネントに対して考慮されていないという事実によって説明できます（その存在の事実のみ）。このため、弱いコンポーネントの接続は、強いコンポーネントには存在しなかった場所に表示されます。

6.コミュニティのクラスタリングと割り当て

参加者間の距離を把握したら、グラフの参加者が互いにどのように接続されているかを反映する他の現象、つまりクラスタリングとコミュニティに移りましょう。



クラスター係数は、3番目の要素を介して接続されているグラフの2つの要素が、高い確率で相互に接続されていることを示しています。リンクされていない場合でも、将来リンクされる可能性は、ランダムに取得された他の2つのノードよりもはるかに高くなります。クラスタリングまたはトランジティビティと呼ばれるこの現象は、ソーシャルグラフでは非常に一般的です。



高度なクラスタリングを備えたグラフは、多数の接続されたトリプレット（3つのノードが相互に接続されている）の存在を特徴としています。それらは、そのような三角形の数が非常に多い多くのソーシャルネットワークの構成要素です。多くの場合、三角形は発生しませんが、コミュニティと呼ばれるクラスター形成全体が発生します。これらは、グラフの他の部分よりも相互に密接に関連しています。



弱く接続されたコンポーネントのクラスタリングとクラスター係数を見てみましょう。

1.	print (': ', nx.transitivity(G_strong))
2.	print (' : ', nx.average_clustering(G_strong))


:  0.2201493109315837
 :  0.37270757578876434

強力な接続のコンポーネントの場合、同じ特性を取得でき、中央ノード（残りのノードに最も密接に接続されているノード）の数とグラフの周辺にあるノードの数も決定できます。

1.	print (': ', nx.transitivity(G_strong))
2.	print (' : ', nx.average_clustering(G_strong))
3.	print ('  : ', len(nx.center(G_strong)))
4.	print ('   : ', len(nx.periphery(G_strong)))


:  0.2328022090200813
 :  0.3905903756516427
  : 46
   : 3

2番目のケースでは、強力に接続されたコンポーネントに接続されたトリプレットの数が多いことを反映して、クラスタリングとクラスター係数が増加しました。緩く結合されたコンポーネントで主要なコミュニティを定義するために一緒に試してみましょう。

1.	G_undirected = G_weak.to_undirected()
2.	partition = community.best_partition(G_undirected)
3.	communities = set(partition.values())
4.	communities_dict = {c: [k for k, v in partition.items() if v == c] for c in communities}
5.	highest_degree = {k: sorted(v, key=lambda x: G.degree(x))[-5:] for k, v in communities_dict.items()}
6.	print(' : ', len(highest_degree))
7.	print('    :', ', '.join([str(len(highest_degree[key])) for key in highest_degree]))


 : 8
    : 113, 114, 125, 131, 169, 188, 54, 92

したがって、電子通信のある列では、8つのコミュニティを区別できます。これらのコミュニティは、列の他の部分よりも相互に密接に関連しています。最小のコミュニティには54人のメンバーがいて、最大のコミュニティには188人のメンバーがいます。重複またはネストされたコミュニティを含むネットワークの場合、最適なパーティショニングを決定するのがより困難になる可能性があります。したがって、コードを実行するたびに、コミュニティの構成が異なる場合があります。取得した分割の視覚化を見てみましょう。

1.	pos = nx.spring_layout(G)
2.	plt.figure(figsize=(15, 15))
3.	cmap = cm.get_cmap('gist_rainbow', max(partition.values()) + 1)
4.	nx.draw_networkx_nodes(G, pos, partition.keys(), node_size=20, cmap=cmap, node_color=list(partition.values()))
5.	nx.draw_networkx_edges(G, pos, alpha=0.5)
6.	plt.show()

図：6.研究機関のメンバー間のすべての送受信電子メールに関する情報を含む、ゆるく結合されたコンポーネントでのさまざまなコミュニティの表示。



上のグラフでは、コミュニティごとの参加者の分布を示しています。ノードの色は特定のコミュニティに属していることを示しています。

7.関係の互恵性

すでに説明したプロパティに加えて、有向ネットワークの相互関係などもあります。この特性は、発信リンクの何パーセントがフィードバック、着信リンクを持っているかを表します。調べるために、networkxライブラリの特別な関数overall_reciprocityを使用して、グラフとそのコンポーネントの相反性のレベルを調べます。

1.	print ('  : ', nx.overall_reciprocity(G))
2.	print ('    : ', nx.overall_reciprocity(G_weak))
3.	print ('    : ', nx.overall_reciprocity(G_strong))

  :  0.6933635759258535
    :  0.6938791484032562
    :  0.7169719762222492

ケースの71％で、ユーザーは強力な接続コンポーネントでメッセージへの返信を受け取りました。弱く接続されたコンポーネントとグラフ全体の場合、レベルは予想どおりに低くなります。

8.ネットワークの普遍的な特性

要約すると、複雑なネットワークは一般に特定の特性を持ち、いくつかは多くのネットワークの特徴です。電子メールデータセットの分析は、これらの傾向を十分にサポートしています。

1. . , , . : web-, , , (Wikipedia, Microsoft). , .
2. . , , « ». : , .
3. , , : 80% , . – , , . , , .
4. , . , .

電子メールに対応するデータセットについて、上記のすべての傾向を分析および確認しました。グラフには、すべてのノードの80％以上を含む、接続された大きなコンポーネントが見つかりました。このコンポーネント内では、ほとんどのノードが少数であることが特徴でしたが、多数のネイバーを持つ参加者の割合はわずかでした。また、グラフの参加者間の直径と平均距離が小さいこともわかりました。986人の参加者を含む弱く接続されたコンポーネントの平均距離はわずか2.1でした。つまり、ほとんどの参加者は2回の「ハンドシェイク」で互いに接続されています。さらに、グラフは高度な相互関係を特徴としています。すべての参加者の69％が相互に双方向の接触を維持しています。

ノート

研究の全文は、Nikolai ViktorovichUrsulによる本「TheWholeTruth About Forex」（2019）にあります。



この研究は、記事「会計と監査へのソーシャルネットワーク分析の適用」Slobodan Kacanski、Dean Lusher（2017、リンク）に記載されています。