NetworkX : Reference : イントロダクション

by

NetworkX : Reference : イントロダクション (翻訳/解説)

翻訳 : (株)クラスキャット セールスインフォメーション
作成日時 : 06/13/2019 (v2.3)

* 本ページは、Network のドキュメント Tutorial を翻訳した上で適宜、補足説明したものです：

* サンプルコードの動作確認はしておりますが、必要な場合には適宜、追加改変しています。
* ご自由にリンクを張って頂いてかまいませんが、sales-info@classcat.com までご一報いただけると嬉しいです。

 

NetworkX : Reference : イントロダクション

NetworkX の構造はそのソースコードの体系により見ることができます。パッケージはグラフオブジェクト、標準的なグラフを作成するための generator、既存のデータセットを読み込むための IO ルーチン、結果としてのネットワークを解析するためのアルゴリズムそして幾つかの基本的な描画ツールのためのクラスを提供します。

殆どの NetworkX API はグラフオブジェクトを引数として取る関数により提供されます。グラフオブジェクトのメソッドは基本的な操作と報告に制限されます。これはコードとドキュメントのモジュール性を提供します。それはまた新参者にパッケージについて段階的に学習することを容易にします。各モジュールのためのソースコードは容易に読めるように意図されていてこの Python コードを読むことは実際にネットワーク・アルゴリズムについて更に学習するための良い方法ですが、ドキュメント十分に親切にすることに大変な努力をしています。

クラスは CamelCase (capital letters at the start of each word) を使用して命名されています。関数、メソッドと変数名前は lower_case_underscore です (lowercase with an underscore representing a space between words)。

 

NetworkX 基本

Python 開始後、networkx を次によりインポートします (推奨方法) :

>>> import networkx as nx

反復を削減するために、ドキュメントでは NetworkX はこのようにインポートされているものとします。

次の基本的なグラフ型が Python クラスとして提供されます :

Graph

  • このクラスは無効グラフを実装します。それは 2 つのノード間の多重エッジを無視します。それはノードとそれ自身の自己ループ・エッジを許容します。

DiGraph

  • 有向グラフ、つまり、有向エッジを持つグラフです。有向グラフに共通な演算を提供します、(グラフのサブクラス)。

MultiGraph

  • ノードのペア間の多重無向エッジを許容する柔軟なグラフクラスです。追加の柔軟性はパフォーマンスにおいて何某かの劣化に繋がります、通常は重要ではありませんが。

MultiDiGraph

  • MultiGraph の有向バージョンです。

空のグラフ-like なオブジェクトは次で作成されます :

>>> G = nx.Graph()
>>> G = nx.DiGraph()
>>> G = nx.MultiGraph()
>>> G = nx.MultiDiGraph()

総てのグラフクラスはノードとして任意の hashable オブジェクトを許容します。Hashable オブジェクトは文字列、タプル、整数、そしてそれ以上を含みます。重みやラベルのような任意のエッジ属性はエッジと関連付けられます。

グラフ内部データ構造は隣接リスト表現に基づき Python 辞書 データ構造を使用して実装されます。グラフ隣接構造は辞書 (群) の Python 辞書として実装されます ; 外側の辞書はノードにより値へとキーが割り当てられます、それらの値はそれ自身が近傍ノードにより (そのエッジに関連付けられた) エッジ属性へとキーが割り当てられる辞書です。この “dict-of-dicts” 構造は巨大なグラフ内で高速な追加、削除、そしてノードと近傍の検索を可能にします。基礎をなすデータ構造はクラス定義のメソッドにより直接アクセスされます。その一方で、総ての関数はデータ構造上に直接作用するのではなく、それらの API メソッドを通してグラフ-like なオブジェクトを単独に操作します。このデザインは ‘dicts-of-dicts’ ベースのデータ構造の (同じメソッドを実装する) 代替のデータ構造による可能な置き換えを可能にします。

 

グラフ

NetworkX を使用するとき行われるべき最初の選択はグラフオブジェクトのどのタイプを使用するかです。グラフ (ネットワーク) はノードのペアであるエッジのコレクションを一緒に伴うノードのコレクションです。属性はしばしばノード and/or エッジに関連付けられます。NetworkX グラフオブジェクトはネットワークの 2 つの主要なプロパティに依拠して異なるフレーバーで生じます :

  • 有向: エッジは有向ですか？エッジペア (u, v) の順序は重要ですか？有向グラフはクラス名, , e.g. DiGraph() の “Di” prefix により指定されます。この区別を行ないます、何故ならば多くの古典的なグラフプロパティは有向グラフのためには異なって定義されるからです。
  • 多重エッジ:ノードの各ペアで多重エッジは許容されますか？想像できるように、多重エッジは異なるデータ構造を必要とします、賢いユーザはこの機能をサポートするためにエッジデータ属性をデザインできるでしょうけれども。prefix “Multi”, e.g., MultiGraph() を使用してこのタイプのグラフのために標準的なデータ構造とインターフェイスを提供します。

基本的なグラフクラスは次のように命名されます : Graph, DiGraph, MultiGraph と MultiDiGraph

 

ノードとエッジ

グラフを指定するときに貴方が行わなければならない次の選択はどのような種類のノードとエッジを使用するかです。

ネットワークのトポロジーが貴方の関心のあることの総てであるならばノードとして整数か文字列を使用することは意味がありエッジデータについて心配する必要はありません。ノードを記述するためのデータ構造を適切に既に持つのであればそれが hashable である条件でノードとしてその構造を単に使用できます。それが hashable でない場合にはノードを表わすために一意な識別子を使用して ノード属性 としてデータを割り当てることができます。

エッジはしばしばそれらに関連付けられたデータを持ちます。任意のデータが エッジ属性 としてエッジに関連付けられます。データが数字で意図が重み付けられたグラフを表わすことであるならば属性のための ‘weight’ キーワードを使用します。ダイクストラの最短経路アルゴリズムのような、グラフアルゴリズムの幾つかは各エッジのための重みを得るためにデフォルトでこの属性名を使用します。

エッジを追加するとき属性はキーワード/バリュー・ペアを使用してエッジに割り当てることができます。貴方の属性を命名するために任意のキーワードを使用できてそして属性キーワードを使用してエッジデータを問い合わせることができます。

ノードとエッジをどのようにエンコードするか、そしてどのように多重エッジあり/なしで無向/有向グラフを持つかがひとたび決定されれば、ネットワークを構築する準備ができました。

 

グラフ作成

NetworkX グラフオブジェクトは 3 つの方法の一つで作成できます :

  • グラフ generators — ネットワーク・トポロジーを作成するための標準的なアルゴリズム。
  • pre-existing (通常はファイル) ソースからデータをインポートする。
  • エッジとノードを明示的に追加する。

ノード/エッジの明示的な追加と除去は記述するために最も容易です。各グラフオブジェクトはグラフを操作するためのメソッドを提供します。例えば、

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge(1, 2)  # default edge data=1
>>> G.add_edge(2, 3, weight=0.9)  # specify edge data

エッジ属性は任意のものであり得ます :

>>> import math
>>> G.add_edge('y', 'x', function=math.cos)
>>> G.add_node(math.cos)  # any hashable can be a node

多くのエッジを一度に追加できます :

>>> elist = [(1, 2), (2, 3), (1, 4), (4, 2)]
>>> G.add_edges_from(elist)
>>> elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
>>> G.add_weighted_edges_from(elist)

より多くのサンプルについては チュートリアル を見てください。

union (合併) と intersection (共通部分) のような幾つかの基本的なグラフ演算は 演算子モジュール ドキュメントで説明されています。

binomial_graph() と erdos_renyi_graph() のようなグラフ generator が グラフ generators サブパッケージで提供されます。

GML, GraphML, エッジリスト・テキストファイルのような形式からネットワークデータをインポートするためには、reading と writing graphs サブパッケージを見てください。

 

グラフレポート

クラス view はノード、近傍、エッジと次数の基本的なレポートを提供します。これらの view はプロパティに渡る iteration に加えてメンバーシップ問合せとデータ属性検索を提供します。view はグラフデータ構造を参照します、そしてグラフへの変更は view で反映されます。これは Python 3 の辞書ビューへの類推です。iterate する間にグラフを変更することを望む場合 e.g. for e in list(G.edges): を使用する必要があります。view は set 的な演算を提供します、e.g. union と intersection です、そして G.edges[u, v][‘color’] と for e, datadict in G.edges.items(): を使用して辞書的な検索とデータ属性の iteration を提供します。メソッド G.edges.items() と G.edges.values() は python 辞書から馴染みがあります。加えて G.edges.data() は特定の属性 iteration を提供しま、e.g. for e, e_color in G.edges.data(‘color’): 。

エッジの基本的なグラフ関係は 2 つの方法で得られます。ある人はノードの近傍を探すことができてある人はエッジを探すことができます。冗談としてノード/近傍に焦点を当てる人々をノード中心的 (= centric) としてエッジに焦点を当てる人々をエッジ中心的として言及します。NetworkX の設計者はノード中心的になりがちでエッジをノード間の関係として見がちです。これを、エッジ検索が G.edges[u, v] である一方で近傍 (隣接) を提供する G[u] のような検索記法の選択により見ることができます。スパースグラフのための殆どのデータ構造は本質的には隣接リストですからこの視点に fit します。最後に、もちろん、どの方法でグラフを調べるかは実際には重要ではありません。総てのノードに渡る近傍レポートが自然に両者の方向を報告する一方で G.edges は無向エッジの重複する表現を除去します。

エッジ、近傍と次数よりも複雑な任意のプロパティは関数により提供されます。例えば nx.triangles(G, n) はノード n を頂点として含む三角形の数を与えます。これらの関数は用語 アルゴリズム の下でコードとドキュメントでグループ分けされます。

 

アルゴリズム

多数のグラフアルゴリズムが NetworkX で提供されます。これらは最短経路、そして幅優先探索 (traversal 参照)、クラスタリングと同型写像アルゴリズム等々を含みます。私達がまだ開発していないものもまた多くあります。

サンプルとしてここには最短の重み付けられたパスを見つけるダイクストラのアルゴリズムを使用するコードがあります :

>>> G = nx.Graph()
>>> e = [('a', 'b', 0.3), ('b', 'c', 0.9), ('a', 'c', 0.5), ('c', 'd', 1.2)]
>>> G.add_weighted_edges_from(e)
>>> print(nx.dijkstra_path(G, 'a', 'd'))
['a', 'c', 'd']

 

描画

NetworkX はネットワーク描画ツールとして設計されていない一方で、描画パッケージへの単純なインターフェイスと幾つかの単純なレイアウト・アルゴリズムを提供します。dot と neato のような優れた Graphviz レイアウトツールと (提案される) pygraphviz や pydot インターフェイスにより接続します。描画は外部プログラムか Matplotlib Python パッケージを使用して成されます。対話的な GUI インターフェイスも可能です、提供はされませんが。描画ツールはモジュール drawing で提供されます。

基本的な描画関数は本質的にはノードを (辞書を通して提供する位置かレイアウト関数で計算された位置を使用して) 散布図の上に配置します。エッジはそれらのドットの間のラインです。

>>> import matplotlib.pyplot as plt
>>> G = nx.cubical_graph()
>>> plt.subplot(121)

>>> nx.draw(G)   # default spring_layout
>>> plt.subplot(122)

>>> nx.draw(G, pos=nx.circular_layout(G), nodecolor='r', edge_color='b')

より多くのアイデアについては サンプル を見てください。

 

データ構造

NetworkX は基本的なデータ構造として「辞書の辞書の辞書」を使用します。これは巨大なスパースネットワークに対して合理的なストレージを持つ高速な検索を可能にします。キーはノードですので G[u] は近傍をエッジ属性辞書へのキーとする隣接辞書を返します。隣接データ構造の view は 辞書的なオブジェクト G.adj により e.g. for node, nbrsdict in G.adj.items(): として提供されます。表現 G[u][v] はエッジ属性辞書自身を返します。リストの辞書もまた可能でしたが、高速なエッジ検出もエッジデータの便利なストレージも可能にはしませんでした。

辞書の辞書の辞書データ構造の優位点は :

  • 2 つの辞書検索でエッジを見つけてエッジを除去します。
  • スパースストレージを持つ高速検索のために「リスト」よりも好ましいです。
  • データがエッジにアタッチできるので「集合 (= set)」よりも好ましいです。
  • G[u][v] はエッジ属性辞書を返します。
  • “n in G” はノード n がグラフ G 内にあるかテストします。
  • “for n in G:” はグラフを通して iterate します。
  • “for nbr in G[n]:” は近傍を通して iterate します。

サンプルとして、ここにエッジを持つ無向グラフの表現があります。

>>> G = nx.Graph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> print(G.adj)
{'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}}

The data structure gets morphed slightly for each base graph class. For DiGraph two dict-of-dicts-of-dicts structures are provided, one for successors (G.succ) and one for predecessors (G.pred). For MultiGraph/MultiDiGraph we use a dict-of-dicts-of-dicts-of-dicts [1] where the third dictionary is keyed by an edge key identifier to the fourth dictionary which contains the edge attributes for that edge between the two nodes.

Graphs provide two interfaces to the edge data attributes: adjacency and edges. So G[u][v][‘width’] is the same as G.edges[u, v][‘width’].

>>> G = nx.Graph()
>>> G.add_edge(1, 2, color='red', weight=0.84, size=300)
>>> print(G[1][2]['size'])
300
>>> print(G.edges[1, 2]['color'])
red
 

以上