ネットワーク グラフの分析: ハミルトンの登場人物をソーシャル ネットワークとして視覚化する

数年前、私はゲーム オブ スローンズの本を夢中で読んでいたのですが、頭の中で登場人物全員を追跡するのが大変だということに気づきました。(これは驚くことではありません。このシリーズには 150 人以上の名前付きキャラクターがいます!) 章間を行ったり来たりしたり、ストーリーラインを思い出すために絶えず「氷と炎の歌」のウィキを調べたりしていました。頭の中の地図が必要でした。これらのキャラクターを視覚化するもっと良い方法はないでしょうか?

基礎

ここに示すのは、Wikipedia のネットワーク グラフのサンプルで、さまざまな言語に対する Wikipedia 編集者の貢献を示しています。この例を使用して、グラフ理論の概念の基本 (または、すでに理解している場合は簡単な復習) をいくつか示します。

• 記事が書かれた言語を表す円は、グラフの「頂点」（または「ノード」）です。

• 「エッジ」とは、各頂点のペアを接続する線です。グラフ内の各エッジは、頂点のペアをエッジにマッピングするインシデンス関数によって決定されます。

  
  

この例では、各辺は（線の太さ、つまり厚さで）線が接続する両方の言語に貢献した編集者の数を表します。これは、無向単純グラフと呼ばれるものです。「無向」とは、{en--> fr} と {fr --> en} が同一であることを意味し、「単純」とは、各頂点のペアを接続する辺が 1 つだけであることを意味します。このグラフは「重み付け」もされており、辺の太さは頂点間の関係の強さに比例します。この例では、重み付けされた接続関数は次のようになります。

このようにグラフを視覚的に表現することは、関係をすばやく表示して理解しやすくするための直感的なアプローチですが、データセットをグラフ オブジェクトとして表現することで、さらに豊富な洞察を得ることができます。

ハミルトンデータセットのデータの取得

「データサイエンスでは、80%の時間がデータの準備に費やされ、20%の時間はデータの準備の必要性について不満を言うことに費やされます。」

データ サイエンティストは、すべての点で意見が一致するわけではありませんが、どのプロジェクトでも最も難しいのはデータの取得であるという点では一致しています。幸いなことに、この記事ではその部分はすでに終わっています。Kaggle には、ダウンロードしてグラフ化を開始できる、ハミルトンの歌詞のきれいなデータセットが用意されています。

探索的分析

ハミルトンデータセットは次のようになります。

キャラクター/曲/歌詞の行ごとに 1 行のレコードがあります。

• タイトル- 曲の名前を指します。
• 話者- 特定のセリフを歌っているキャラクターを指します。
• 歌詞- 歌の中の特定の歌詞の行を指します。

隣接行列の構築

すべてのハミルトン話者のネットワーク グラフを構築するには、以下を定義する必要があります。

• ノード（スピーカーのリスト）

• エッジ（各スピーカーのペアを接続するため）

• 各頂点のペアをエッジにマッピングするインシデンス関数（オプションの重み付き）

  
  

私が選択した発生関数は、各話者のペアが一緒に登場した曲の数です。2 人のキャラクターが一緒に登場した曲が多いほど、彼らの関係が強くなると想定しています。

Weight {speaker,x, speaker,y} = #songs that feature both speaker,x and speaker,y

R の dplyr を使用すると、元のデータセットを**{src, dest, weight}**エンティティに変換し、それを隣接行列に変換できます。次に、 R の igraph パッケージの graph.adjacency を使用して、この隣接行列から「グラフ オブジェクト」を作成し、それをプロットやその他の分析に使用できます。

ネットワークプロットの視覚化

graph_obj はplot.igraph関数を使用して視覚化できます。この関数には選択できるカスタム レイアウトが多数あるため、まずは「star」レイアウトを使用して同じグラフをレンダリングします。

結果は技術的にはネットワーク プロットです。しかし、さらに優れたものを作ることは可能でしょうか。上の図は、すべての頂点と辺が同等の重要性を持っていることを示しているように見えますが、これはソーシャル ネットワークを視覚化するという全体的な目的を損ないます。確かに、一部のキャラクターはより「重要」であり、一部の話者は他の話者よりも強い関係を持っています。

このグラフはそれをどのように反映しているのでしょうか?

ここで、エッジの重みと頂点の次数が関係してきます。まず、 plot.igraph関数のパラメータを操作して、 edge.width (つまり、プロット内のエッジの太さ) を重みに相対的に、 vertex.label.cex (つまり、頂点のフォント サイズ) を次数に相対的に設定してみます。

ずっと良くなりました! 度数の高いキャラクターは視覚的に大きく表示され、強い関係と弱い関係の区別も線の濃さから明らかです。この繰り返しははるかに直感的で、視聴者はキャラクター間の関係をすぐに把握できます。また、キング ジョージの歌は常に (非常に面白い) 独白であることを考えると、キング ジョージが孤独なノードであることも適切です。

R のvisNetworkライブラリを使用して、インタラクティブなネットワーク グラフを作成することもできます。このライブラリを使用すると、グラフの複数の部分を拡大/縮小することができ (特に大きなグラフの場合に便利です)、Shiny もサポートされています。

中心性測定

中心性は、ノードの重要性を識別するためのグラフ理論の重要な概念です。

• 次数中心性: これは各ノードに接続されているエッジの数の尺度です。

• 固有中心性: これは、ネットワークを通じてノードがどの程度「適切に接続されているか」、接続がいくつのリンクを共有しているかなどを示す尺度を表します。これは、ネットワークに直接接続されているノードだけでなく、ネットワーク全体に影響を及ぼすノードを識別します。

• 媒介中心性:これは文字通り、特定のノードが他のノードの間にどれだけ存在し、さまざまなネットワーク クラスター間の「橋渡し」として機能するかを示します。これは、各頂点がネットワークの残りの部分に及ぼす「影響」の尺度です。

  
  

生成されたグラフの中心性を取得するには、igraph の degree()、betweenness()、eigen_centrality() 関数を使用できます。

このグラフでは、アーロン・バーが最も高い媒介中心性（「ブリッジ」）を持ち、ハミルトンが最も高い固有ベクトル中心性（「インフルエンサー」）を持っているように見えます。これをどう解釈するかはあなた次第です。

結論

ネットワーク グラフのビジネス アプリケーションは数多くあります。

• ソーシャル ネットワーキング サイトは、ネットワーク グラフを利用して類似したユーザーのコミュニティを作成し、ターゲットを絞った推奨を提供します。「おすすめの友達」機能の背後にあるアルゴリズムの基本的な実装は、次のようになります。「アリスの直接の友達 10 人のうち 9 人はボブの友達でもある -> ボブをアリスの潜在的な友達として推奨する。」

  
  

• 場所 X から場所 Y までの最短距離をマップするアプリケーション (地図、ライドシェア サービス、配送トラックのサプライ チェーンとロジスティクスなど) では、コンピューター サイエンスで巡回セールスマン問題としてよく知られている「最短経路」アルゴリズムのバリエーションが使用される可能性があります。

  
  

• ネットワーク理論は、自然言語処理 (NLP) における語彙および意味処理の重要な要素であり、Alexa、Cortana、Siri、さらには単純な言葉遊びのゲームJeopardy! で優勝した IBM の Watsonなどのチャットボットや仮想アシスタントにも使用されています。

  
  

• 「Six Degrees of Kevin Bacon」のような名前を出すパーティーゲームでは、ネットワーク グラフが使用されます。

  
  

• 疫学では、中心性指標はパンデミックや「スーパースプレッダー」イベントの起源を特定するために使用されることがあります。

  
  

• よく考えてみると、インターネットはさまざまな Web サイトが集まった巨大なネットワークにすぎません。検索エンジンはナレッジ グラフの尺度を利用して、特定の検索クエリに最も関連性の高いページを返します。

  
  

ネットワーク グラフは楽しいものですが、実稼働環境で使用する際に欠点がないわけではないことに注意することが重要です。たとえば、リソースを大量に消費することがあります。マトリックス操作の場合と同様に、スケーラビリティとパフォーマンスが損なわれることがあります。また、「コールド スタート」の問題もあります。データセットがまばらすぎる場合や、エンティティ間の関係があまり多くない場合、ネットワーク グラフは効果的なソリューションではありません。ただし、正しく適切なコンテキストで使用すれば、ビジネスにとって価値のあるものになります。