Python/NetworkXを使用したグラフデータサイエンス

データが殺到しています。 拡大し続けるデータベースとスプレッドシートには、ビジネスに関する洞察が隠されています。 データが非常に多い場合、どうすればデータを分析して結論を​​引き出すことができますか？ グラフ（棒グラフではなくネットワーク）は、洗練されたアプローチを提供します。

情報を一般的に表すためにテーブルを使用することがよくあります。 ただし、グラフは特殊なデータ構造を使用します。テーブル行の代わりに、ノードが要素を表します。 エッジは2つのノードを接続して、それらの関係を示します。

このグラフデータ構造により、独自の角度からデータを観察することができます。そのため、分子生物学から社会科学まで、あらゆる分野でグラフデータサイエンスが使用されています。

では、開発者はグラフデータサイエンスをどのように活用できるでしょうか。 最も使用されているデータサイエンスプログラミング言語であるPythonに目を向けましょう。

Pythonの「グラフ理論」グラフ入門

Python開発者は、NetworkX、igraph、SNAP、graph-toolなど、いくつかのグラフデータライブラリを利用できます。 長所と短所は別として、Pythonグラフデータ構造を処理および処理するための非常によく似たインターフェイスがあります。

人気のあるNetworkXライブラリを使用します。 インストールと使用は簡単で、使用するコミュニティ検出アルゴリズムをサポートします。

NetworkXを使用して新しいグラフを作成するのは簡単です。

 import networkx as nx G = nx.Graph()

しかし、 Gはまだグラフではなく、ノードとエッジがありません。

グラフにノードを追加する方法

Graph()の戻り値を.add_node() （またはリスト内の複数のノードの場合は.add_nodes_from() ））で連鎖させることにより、ネットワークにノードを追加できます。 node 4とnode 5で示すように、辞書をパラメーターとして渡すことで、ノードに任意の特性または属性を追加することもできます。

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

これは出力します：

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

ただし、ノード間にエッジがない場合、ノードは分離され、データセットは単純なテーブルに勝るものはありません。

グラフにエッジを追加する方法

ノードの手法と同様に、2つのノードの名前をパラメーターとして.add_edge（ .add_edge()を使用し（またはリスト内の複数のエッジの場合は.add_edges_from() ）、オプションで属性のディクショナリを含めることができます。

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

NetworkXライブラリは、このようなグラフをサポートしており、各エッジに重みを付けることができます。 たとえば、ノードがユーザーでエッジがインタラクションであるソーシャルネットワークグラフでは、重みは、特定のユーザーのペア間で発生するインタラクションの数を示すことができます。これは、関連性の高い指標です。

NetworkXは、 G.edgesを使用するときにすべてのエッジを一覧表示しますが、それらの属性は含まれません。 エッジ属性が必要な場合は、 G[node_name]を使用してノードに接続されているすべてのものを取得するか、 G[node_name][connected_node_name]を使用して特定のエッジの属性を取得できます。

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

これは出力します：

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

しかし、最初のグラフをこのように読むことは実用的ではありません。 ありがたいことに、はるかに優れた表現があります。

グラフ（および加重グラフ）から画像を生成する方法

グラフの視覚化は不可欠です。グラフを使用すると、ノードとネットワークの構造との関係をすばやく明確に確認できます。

nx.draw(G)をすばやく呼び出すだけで、次のことが可能になります。

nx.draw()呼び出しを使用して、それに応じてより重いエッジを厚くしてみましょう。

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

結果に示すように、無重力エッジのデフォルトの厚さを提供しました。

私たちの方法とグラフアルゴリズムはより複雑になりつつあるので、次のステップはよりよく知られているデータセットを使用することです。

映画スターウォーズエピソードIVのデータを使用したグラフデータサイエンス

結果の解釈と理解を容易にするために、このデータセットを使用します。 ノードは重要なキャラクターを表し、エッジ（ここでは重み付けされていません）はシーンでの同時出現を示します。

注：データセットはGabasova、E.（2016）からのものです。 スターウォーズのソーシャルネットワーク。 DOI：https://doi.org/10.5281/zenodo.1411479。

まず、 nx.draw(G_starWars, with_labels = True)を使用してデータを視覚化します。

R2-D2とC-3POのように、通常一緒に表示されるキャラクターは、密接に関連しているように見えます。 対照的に、ダースベイダーはオーウェンとシーンを共有していないことがわかります。

PythonNetworkX視覚化レイアウト

各ノードが前のグラフのどこにあるのですか？

これは、デフォルトのspring_layoutアルゴリズムの結果です。 これは、ばねの力をシミュレートし、接続されたノードを引き付け、切断されたノードをはじきます。 これは、中央に配置される、適切に接続されたノードを強調表示するのに役立ちます。

NetworkXには、 circular_layoutのように、ノードを配置するために異なる基準を使用する他のレイアウトがあります。

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

結果：

このレイアウトは、ノードの場所がその重要性に依存しないという意味でニュートラルです。すべてのノードが等しく表されます。 （円形のレイアウトは、別々の連結成分（任意の2つのノード間にパスを持つサブグラフ）を視覚化するのにも役立ちますが、ここでは、グラフ全体が1つの大きな連結成分です。）

私たちが見た両方のレイアウトは、エッジが他のエッジと自由に交差するため、ある程度の視覚的な混乱があります。 しかし、 spring_layoutのような別の力指向アルゴリズムであるKamada-Kawaiは、システムのエネルギーを最小化するようにノードを配置します。

これにより、エッジの交差が減りますが、代償が伴います。他のレイアウトよりも低速であるため、ノードが多いグラフにはあまりお勧めしません。

これには特殊な描画機能があります。

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

代わりに、この形状が生成されます。

特別な介入なしで、アルゴリズムはメインキャラクター（ルーク、レイア、C-3POなど）を中央に配置し、目立たないキャラクター（キャミーやドドンナ将軍など）を境界線に配置します。

特定のレイアウトでグラフを視覚化すると、いくつかの興味深い定性的な結果が得られます。 それでも、定量的な結果はデー​​タサイエンス分析の重要な部分であるため、いくつかの指標を定義する必要があります。

ノード分析：度とPageRank

ネットワークを明確に視覚化できるようになったので、ノードの特性を明らかにすることは興味深いかもしれません。 ノードの特性と、この例では文字の特性を説明する複数のメトリックがあります。

ノードの基本的なメトリックの1つは、その次数です。つまり、ノードが持つエッジの数です。 スターウォーズのキャラクターのノードの程度は、シーンを共有した他のキャラクターの数を測定します。

degree()関数は、文字またはネットワーク全体の次数を計算できます。

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

両方のコマンドの出力：

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

次数に応じてノードを最高から最低に並べ替えることは、1行のコードで実行できます。

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

出力：

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

単なる合計であるため、次数は個々のエッジの詳細を考慮していません。 特定のエッジは、他の方法で分離されたノードに接続しますか、それともネットワーク全体に接続されているノードに接続しますか？ GoogleのPageRankアルゴリズムは、この情報を集約して、ノードがネットワーク内でどれほど「重要」であるかを測定します。

PageRankメトリックは、あるノードから別のノードにランダムに移動するエージェントとして解釈できます。 より適切に接続されたノードは、それらを通るより多くのパスを持っているため、エージェントはそれらをより頻繁に訪問する傾向があります。

このようなノードは、NetworkXライブラリで計算できるより高いPageRankを持ちます。

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

これは、ルークのランクとランクでソートされたキャラクターを出力します。

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

オーウェンは、最高の学位を持っていたルークを超えて、最高のPageRankを持つキャラクターです。 分析：オーウェンは他のキャラクターと最も多くのシーンを共有するキャラクターではありませんが、ルーク自身、R2-D2、C-3POなどの多くの重要なキャラクターとシーンを共有するキャラクターです。

対照的に、3番目に高い次数を持つキャラクターであるC-3POは、最も低いPageRankを持つキャラクターです。 C-3POには多くのつながりがありますが、それらの多くは重要でない文字を持っています。

要点：複数のメトリックを使用すると、グラフのノードのさまざまな特性をより深く理解できます。

コミュニティ検出アルゴリズム

ネットワークを分析するときは、コミュニティを分離することが重要な場合があります。つまり、相互に高度に接続されているが、コミュニティ外のノードとの接続は最小限であるノードのグループです。

これには複数のアルゴリズムがあります。 それらのほとんどは、以前にラベル付けされている必要なしにノードにラベルを割り当てるため、教師なし機械学習アルゴリズム内にあります。

最も有名なものの1つはラベルの伝播です。 その中で、各ノードは、1つのコミュニティ内の一意のラベルで始まります。 ノードのラベルは、隣接ノードのラベルの大部分に従って繰り返し更新されます。

すべてのノードがほとんどの隣接ノードとラベルを共有するまで、ラベルはネットワーク全体に拡散します。 互いに密接に接続されたノードのグループは、同じラベルを持つことになります。

NetworkXライブラリを使用すると、このアルゴリズムを実行するのに必要なPythonはわずか3行です。

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

出力：

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

このセットのリストでは、各セットはコミュニティを表しています。 映画に精通している読者は、アルゴリズムが「善人」と「悪人」を完全に分離し、真の（コミュニティ）ラベルやメタデータを使用せずに文字を有意義に区別していることに気付くでしょう。

Pythonでグラフデータサイエンスを使用したインテリジェントな洞察

グラフデータサイエンスツールの使用を開始するのは、思ったよりも簡単であることがわかりました。 PythonのNetworkXライブラリを使用してデータをグラフとして表すと、数行の短いコードでわかりやすくなります。 データセットを視覚化し、ノードの特性を測定および比較し、コミュニティ検出アルゴリズムを介してノードを適切にクラスター化できます。

Pythonを使用してネットワークから結論と洞察を抽出するスキルを持つことで、開発者はデータサイエンスサービスパイプラインで一般的に見られるツールと方法論と統合できます。 検索エンジンからフライトスケジューリング、電気工学まで、これらの方法は幅広いコンテキストに簡単に適用できます。

グラフデータサイエンスに関する推奨読書

コミュニティ検出アルゴリズム
趙陽、ルネ・アルゲスハイマー、クラウディオ・テッソーネ。 「人工ネットワーク上のコミュニティ検出アルゴリズムの比較分析。」 Scientific Reports、6、いいえ。 30750（2016）。

グラフディープラーニング
トーマス・キフ。 「グラフ畳み込みネットワーク」。 2016年9月30日。

グラフデータサイエンスの応用
アルバネーゼ、フェデリコ、レアンドロロンバルディ、エステバンフォイエシュタイン、パブロバレンズエラ。 「Twitterでテキストマイニングとグラフ機械学習を使用して、変化する個人を予測します。」 （2020年8月24日）：arXiv：2008.10749[cs.SI]。

コーエン、エリオール。 「PyDataテルアビブMeetup：Node2vec。」 YouTube。 2018年11月22日。ビデオ、21：09。 https://www.youtube.com/watch?v=828rZgV9t1g。