数年前、私は 本を夢中で読んでいたのですが、頭の中で登場人物全員を追跡するのが大変だということに気づきました。(これは驚くことではありません。このシリーズには 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 を使用すると、元のデータセットを エンティティに変換し、それを隣接行列に変換できます。次に、 の graph.adjacency を使用して、この隣接行列から「グラフ オブジェクト」を作成し、それをプロットやその他の分析に使用できます。 **{src, dest, weight}** R の igraph パッケージ ネットワークプロットの視覚化 graph_obj は 関数を使用して視覚化できます。この関数には選択できるカスタム レイアウトが多数あるため、まずは「star」レイアウトを使用して同じグラフをレンダリングします。 plot.igraph 結果は技術的にはネットワーク プロットです。しかし、さらに優れたものを作ることは可能でしょうか。上の図は、すべての頂点と辺が同等の重要性を持っていることを示しているように見えますが、これはソーシャル ネットワークを視覚化するという全体的な目的を損ないます。確かに、一部のキャラクターはより「重要」であり、一部の話者は他の話者よりも強い関係を持っています。 このグラフはそれをどのように反映しているのでしょうか? ここで、 と が関係してきます。まず、 関数のパラメータを操作して、 (つまり、プロット内のエッジの太さ) を重みに相対的に、 (つまり、頂点のフォント サイズ) を次数に相対的に設定してみます。 エッジの重み 頂点の 次数 plot.igraph edge.width vertex.label.cex ずっと良くなりました! 度数の高いキャラクターは視覚的に大きく表示され、強い関係と弱い関係の区別も線の濃さから明らかです。この繰り返しははるかに直感的で、視聴者はキャラクター間の関係をすぐに把握できます。また、キング ジョージの歌は常に (非常に面白い) 独白であることを考えると、キング ジョージが孤独なノードであることも適切です。 R の ライブラリを使用して、 ネットワーク グラフを作成することもできます。このライブラリを使用すると、グラフの複数の部分を拡大/縮小することができ (特に大きなグラフの場合に便利です)、Shiny もサポートされています。 visNetwork インタラクティブな 中心性測定 、ノードの重要性を識別するためのグラフ理論の重要な概念です。 中心性は : これは各ノードに接続されているエッジの数の尺度です。 次数中心性 : これは、ネットワークを通じてノードがどの程度「適切に接続されているか」、接続がいくつのリンクを共有しているかなどを示す尺度を表します。これは、ネットワークに直接接続されているノードだけでなく、ネットワーク全体に影響を及ぼすノードを識別します。 固有中心性 これは文字通り、特定のノードが他のノード どれだけ存在し、さまざまなネットワーク クラスター間の「橋渡し」として機能するかを示します。これは、各頂点がネットワークの残りの部分に及ぼす「影響」の尺度です。 媒介中心性: の間に 生成されたグラフの中心性を取得するには、igraph の degree()、betweenness()、eigen_centrality() 関数を使用できます。 このグラフでは、アーロン・バーが最も高い (「ブリッジ」)を持ち、ハミルトンが最も高い (「インフルエンサー」)を持っているように見えます。これをどう解釈するかはあなた次第です。 媒介中心性 固有ベクトル中心性 結論 ネットワーク グラフのビジネス アプリケーションは数多くあります。 ソーシャル ネットワーキング サイトは、ネットワーク グラフを利用して類似したユーザーのコミュニティを作成し、ターゲットを絞った推奨を提供します。「おすすめの友達」機能の背後にあるアルゴリズムの基本的な実装は、次のようになります。「アリスの直接の友達 10 人のうち 9 人はボブの友達でもある -> ボブをアリスの潜在的な友達として推奨する。」 場所 X から場所 Y までの最短距離をマップするアプリケーション (地図、ライドシェア サービス、配送トラックのサプライ チェーンとロジスティクスなど) では、コンピューター サイエンスで としてよく知られている「最短経路」アルゴリズムのバリエーションが使用される可能性があります。 巡回セールスマン問題 ネットワーク理論は、自然言語処理 (NLP) における語彙および意味処理の重要な要素であり、Alexa、Cortana、Siri、さらには単純な言葉遊びのゲーム などのチャットボットや仮想アシスタントにも使用されています。 Jeopardy! で優勝した IBM の Watson のような名前を出すパーティーゲームでは、ネットワーク グラフが使用されます。 「Six Degrees of Kevin Bacon」 疫学では、中心性指標はパンデミックや「スーパースプレッダー」イベントの起源を特定するために使用されることがあります。 よく考えてみると、インターネットはさまざまな Web サイトが集まった巨大なネットワークにすぎません。検索エンジンは の尺度を利用して、特定の検索クエリに最も関連性の高いページを返します。 ナレッジ グラフ ネットワーク グラフは楽しいものですが、実稼働環境で使用する際に欠点がないわけではないことに注意することが重要です。たとえば、リソースを大量に消費することがあります。マトリックス操作の場合と同様に、スケーラビリティとパフォーマンスが損なわれることがあります。また、「コールド スタート」の問題もあります。データセットがまばらすぎる場合や、エンティティ間の関係があまり多くない場合、ネットワーク グラフは効果的なソリューションではありません。ただし、正しく適切なコンテキストで使用すれば、ビジネスにとって価値のあるものになります。 • コード: https://github.com/iswaryam/hamilton/ データセットのクレジット: https://www.kaggle.com/lbalter/hamilton-lyrics# ポッターヘッドなら、私の GitHub をチェックしてください。私も同様の方法で のキャラクターをグラフ化しました。 ハリー・ポッター