NetworkX : Tutorials (翻訳/解説)

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

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

• https://networkx.github.io/documentation/stable/tutorial.html

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

 

NetworkX : Tutorials

グラフを作成する

ノードもエッジもない空のグラフを作成します。

import networkx as nx
G = nx.Graph()

定義により、グラフは (エッジ、リンク, etc. と呼称される) 識別されるノードのペアを伴うノード (頂点) のコレクションです。NetworkX では、ノードは任意の hashable オブジェクトであり得ます、e.g. テキスト文字列、画像、XML オブジェクト、もう一つのグラフ、カスタマイズされたノード・オブジェクト, etc.

Note: Python の None オブジェクトはノードとして使用されるべきではありません、何故ならばそれは多くの関数でオプションの function 引数が割り当てられるかどうかを決定するからです。

 

ノード

グラフ G は幾つかの方法で増大できます。NetworkX は多くのグラフ generator 関数と多くの形式でグラフを読み書きするためのファシリティを含みます。けれどもスタートするために単純な操作を見ます。一度に一つのノードを追加できます、

G.add_node(1)

ノードのリストを追加します、

G.add_nodes_from([2, 3])

あるいはノードの任意の iterable なコンテナを追加します。コンテナが 2-タプル (node、node_attribute_dict) を yield する場合ノード属性を持つノードを追加することもできます。ノード属性は下で更に議論されます。

H = nx.path_graph(10)
G.add_nodes_from(H)

G は今では H のノードを G のノードして含むことに注意してください。対照的に、グラフ H を G 内のノードとして使用することもできます。

G.add_node(H)

グラフ G では今では H をノードとして含みます。この柔軟性は非常にパワフルです、何故ならばそれはグラフのグラフ、ファイルのグラフ、関数のグラフそしてそれ以上を可能にするからです。ノードが有用な実在 (= entities) となるように貴方のアプリケーションをどのように構造化するかについて考えることは価値があります。もちろん貴方が好むのであれば G 内の一意の識別子を常に使用して識別子をキーとするノード情報への個々の辞書を持つことができます。

Note: ハッシュがその内容に依拠する場合ノードオブジェクトを変更するべきではありません。

 

エッジ

G はまた一度に一つのエッジを追加することにより増大できます、

G.add_edge(1, 2)
e = (2, 3)
G.add_edge(*e)  # unpack edge tuple*

エッジのリストを追加することにより、

G.add_edges_from([(1, 2), (1, 3)])

あるいはエッジの任意の ebunch を追加することにより。ebunch はエッジ-タプルの任意の iterable コンテナです。エッジ-タプルはノードの 2-タプルか、エッジ属性辞書が続く 2 ノードを持つ 3-タプルであり得ます、e.g., (2, 3, {‘weight’: 3.1415})。エッジ属性は下で更に議論されます

G.add_edges_from(H.edges)

既存のノードやエッジを追加するとき不平はありません。例えば、総てのノードとエッジを削除した後、

G.clear()

新しいノード/エッジを追加します、そして NetworkX は既に存在している任意のものを静かに無視します。

G.add_edges_from([(1, 2), (1, 3)])
G.add_node(1)
G.add_edge(1, 2)
G.add_node("spam")        # adds node "spam"
G.add_nodes_from("spam")  # adds 4 nodes: 's', 'p', 'a', 'm'
G.add_edge(3, 'm')

この段階でグラフ G は 8 ノードと 3 エッジから成ります、次により見られるように :

G.number_of_nodes()
G.number_of_edges()

8
3

ノードとエッジを調査できます。4 つの基本的なグラフ・プロパティが報告を容易にします: G.nodes, G.edges, G.adj と G.degree です。これらはグラフのノード、エッジ、近傍 (隣接)、そしてノードの次数のセット的な view です。それらは継続的に更新される read-only ビューをグラフ構造へ供給します。それらはまた辞書的でそこでは view を通してノードとエッジ・データ属性を検索できて メソッド.items(), .data(‘span’) を使用してデータ属性で iterate できます。view の代わりに特定のコンテナ型を望むのであれば、それを指定できます。ここではリストを使用しますが、他のコンテキストでは集合、辞書と他のコンテナがより良いかもしれません。

list(G.nodes)
list(G.edges)
list(G.adj[1])  # or list(G.neighbors(1))
G.degree[1]  # the number of edges incident to 1

[1, 2, 3, 'spam', 's', 'p', 'a', 'm']
[(1, 2), (1, 3), (3, 'm')]
[2, 3]
2

nbunch を使用して総てのノードのサブセットからエッジと次数を報告することを指定できます。nbunch は次のいずれかです: (総てのノードを意味する) None、ノード、あるいはそれ自体はグラフのノードではないノードの iterable コンテナ。

G.edges([2, 'm'])
G.degree([2, 3])

EdgeDataView([(2, 1), ('m', 3)])
DegreeView({2: 1, 3: 2})

追加と同様の流儀でグラフからノードとエッジを除去できます。
メソッド Graph.remove_node(), Graph.remove_nodes_from(), Graph.remove_edge() と Graph.remove_edges_from() を使用します、e.g.

>>> G.remove_node(2)
>>> G.remove_nodes_from("spam")
>>> list(G.nodes)
[1, 3, 'spam']
>>> G.remove_edge(1, 3)

graph クラスの一つをインスタンス化することによりグラフ構造を作成するとき、幾つかの形式でデータを指定できます。

>>> G.add_edge(1, 2)
>>> H = nx.DiGraph(G)   # create a DiGraph using the connections from G
>>> list(H.edges())
[(1, 2), (2, 1)]
>>> edgelist = [(0, 1), (1, 2), (2, 3)]
>>> H = nx.Graph(edgelist)

 

ノードとエッジとして何を使用するか

ノードとエッジは NetworkX オブジェクトとして指定されていないことに気がつくかもしれません。これはノードとエッジとして意味があるアイテムを使用することを貴方に自由のままにします。最も一般的な選択は数字か文字列ですが、ノードは (None 以外の) どのような hashable オブジェクトでもかまいません、そしてエッジは G.add_edge(n1, n2, object=x) を使用してどのようなオブジェクト x とも関連付けられます。例として、RCSB 蛋白質構造データバンクからの n1 と n2 は蛋白質オブジェクトであり得ます、そして x はそれらの相互作用の実験的観測を詳述した文献の XML レコードを参照できるでしょう。

私達はこのパワーが非常に有用であることを見出しましたが、その乱用は Python に精通していない限りは予期せぬ驚きに繋がるかもしれません。疑わしい場合には、整数ラベルを持つより伝統的なグラフを得るために convert_node_labels_to_integers() を使用することを考えてください。

 

エッジと近傍にアクセスする

view Graph.edges() と Graph.adj() に加えて、添字記法を使用してエッジと近傍へのアクセスが可能です。

>>> G[1]  # same as G.adj[1]
AtlasView({2: {}})
>>> G[1][2]
{}
>>> G.edges[1, 2]
{}

エッジが既に存在していれば添字記法を使用してエッジの属性を get/set できます。

>>> G.add_edge(1, 3)
>>> G[1][3]['color'] = "blue"
>>> G.edges[1, 2]['color'] = "red"

総ての (node, adjacency) ペアの高速な調査は G.adjacency() か G.adj.items() を使用して成されます。無向グラフについては、adjacency iteration は各エッジを 2 度見ることに注意してください。

>>> FG = nx.Graph()
>>> FG.add_weighted_edges_from([(1, 2, 0.125), (1, 3, 0.75), (2, 4, 1.2), (3, 4, 0.375)])
>>> for n, nbrs in FG.adj.items():
...    for nbr, eattr in nbrs.items():
...        wt = eattr['weight']
...        if wt < 0.5: print('(%d, %d, %.3f)' % (n, nbr, wt))
(1, 2, 0.125)
(2, 1, 0.125)
(3, 4, 0.375)
(4, 3, 0.375)

総てのエッジへの便利なアクセスは edges プロパティで成されます。

>>> for (u, v, wt) in FG.edges.data('weight'):
...     if wt < 0.5: print('(%d, %d, %.3f)' % (u, v, wt))
(1, 2, 0.125)
(3, 4, 0.375)

 

グラフ、ノードとエッジへ属性を追加する

重み、ラベル、色、あるいは貴方の好む任意の Python オブジェクトのような属性はグラフ、ノードやエッジにアタッチできます。

各グラフ、ノードとエッジは関連付けられた属性辞書でキー/バリュー属性を保持できます (キーは hashale でなければなりません)。デフォルトではこれらは空ですが、属性は add_edge, add_node かグラフ G のための G.graph, G.nodes と G.edges と命名された属性辞書の直接操作により追加や変更できます。

 

グラフ属性

新しいグラフを作成するときグラフ属性を割り当てます

>>> G = nx.Graph(day="Friday")
>>> G.graph
{'day': 'Friday'}

あるいは後で属性を変更できます

>>> G.graph['day'] = "Monday"
>>> G.graph
{'day': 'Monday'}

 

ノード属性

add_node(), add_nodes_from() か G.nodes を使用してノード属性を追加します

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.nodes[1]
{'time': '5pm'}
>>> G.nodes[1]['room'] = 714
>>> G.nodes.data()
NodeDataView({1: {'time': '5pm', 'room': 714}, 3: {'time': '2pm'}})

G.nodes へのノードの追加はそれをグラフに追加しているのではないことに注意してください、新しいノードを追加するには G.add_node() を使用します。エッジについても同様です。

 

エッジ属性

add_edge(), add_edges_from() か添字記法を使用してエッジ属性を追加/変更します。

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edges[3, 4]['weight'] = 4.2

特別な属性 weight は数値であるべきです、何故ならばそれは重み付けられたエッジを必要とするアルゴリズムにより使用されるからです。

 

有向グラフ

DiGraph クラスは有向エッジに特有の追加プロパティを提供します、e.g., DiGraph.out_edges(), DiGraph.in_degree(), DiGraph.predecessors(), DiGraph.successors() etc. アルゴリズムに両者のクラスで容易に動作することを可能にするためには、neighbors() の有向バージョンは successors() に等値でその一方で degree は in_degree と out_degree の総計を報告します、それは時に矛盾を感じるかもしれませんが。

>>> DG = nx.DiGraph()
>>> DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
>>> DG.out_degree(1, weight='weight')
0.5
>>> DG.degree(1, weight='weight')
1.25
>>> list(DG.successors(1))
[2]
>>> list(DG.neighbors(1))
[2]

幾つかのアルゴリズムは有向グラフのためだけに動作して他は有向グラフのために上手く定義されていません。実際に有向と無向グラフを一緒に扱う傾向は危険です。ある計測のために有向グラフを無向として扱うことを望む場合、多分それを Graph.to_undirected() を使用するか次により変換するべきです

>>> H = nx.Graph(G)  # convert G to undirected graph

 

多重グラフ

NetworkX はノードの任意のペアの間の多重エッジを許容するグラフのためのクラスを提供します。MultiGraph と MultiDiGraph クラスは多分異なるエッジデータを伴う、同じエッジを二度追加することを可能にします、これは幾つかのアプリケーションに対してパワフルであり得ますが、多くのアルゴリズムはそのようなグラフ上では上手く定義されません。結果が上手く定義されるところでは、e.g., MultiGraph.degree() 、関数を提供します。そうでなければ測定が上手く定義されるような方法で標準的なグラフに変換するべきです。

>>> MG = nx.MultiGraph()
>>> MG.add_weighted_edges_from([(1, 2, 0.5), (1, 2, 0.75), (2, 3, 0.5)])
>>> dict(MG.degree(weight='weight'))
{1: 1.25, 2: 1.75, 3: 0.5}
>>> GG = nx.Graph()
>>> for n, nbrs in MG.adjacency():
...    for nbr, edict in nbrs.items():
...        minvalue = min([d['weight'] for d in edict.values()])
...        GG.add_edge(n, nbr, weight = minvalue)
...
>>> nx.shortest_path(GG, 1, 3)
[1, 2, 3]

 

グラフ generator とグラフ演算

グラフをノード毎やエッジ毎に構築することに加えて、それらはまた次によっても生成できます

1. 次のような古典的なグラフ演算を適用します :

   subgraph(G, nbunch)      - nbunch 内のノード上の G の誘導部分グラフ view
   union(G1,G2)             - グラフの和
   disjoint_union(G1,G2)    - 総てのノードが異なると仮定するグラフの和
   cartesian_product(G1,G2) - 直積 (Cartesian product) グラフを返す
   compose(G1,G2)           - 両者の共通のノードを識別してグラフを結合する
   complement(G)            - 補グラフ
   create_empty_copy(G)     - 同じグラフクラスの空のコピーを返す
   to_undirected(G) - G の無向表現を返す
   to_directed(G)   - G の有向表現を返す
   

2. 古典的な小さいグラフの一つへの呼び出しを使用する、e.g.,

   >>> petersen = nx.petersen_graph()
   >>> tutte = nx.tutte_graph()
   >>> maze = nx.sedgewick_maze_graph()
   >>> tet = nx.tetrahedral_graph()
   

3. 古典的なグラフのための (構成的な) generator を使用する、e.g,

   >>> K_5 = nx.complete_graph(5)
   >>> K_3_5 = nx.complete_bipartite_graph(3, 5)
   >>> barbell = nx.barbell_graph(10, 10)
   >>> lollipop = nx.lollipop_graph(10, 20)
   

4. 確率論的なグラフ generator を使用する、e.g.

   >>> er = nx.erdos_renyi_graph(100, 0.15)
   >>> ws = nx.watts_strogatz_graph(30, 3, 0.1)
   >>> ba = nx.barabasi_albert_graph(100, 5)
   >>> red = nx.random_lobster(100, 0.9, 0.9)
   

5. エッジリスト, 隣接リスト, GML, GraphML, pickle, LEDA 等のような一般的なグラフ形式を使用するファイル内にストアされたグラフを読む読む

   >>> nx.write_gml(red, "path.to.file")
   >>> mygraph = nx.read_gml("path.to.file")
   

グラフ形式の詳細については Reading and writing graphs をそしてグラフ generator 関数については Graph generators を見てください。

 

グラフを解析する

G の構造は次のような様々なグラフ理論関数を使用して解析できます :

>>> G = nx.Graph()
>>> G.add_edges_from([(1, 2), (1, 3)])
>>> G.add_node("spam")       # adds node "spam"
>>> list(nx.connected_components(G))
[{1, 2, 3}, {'spam'}]
>>> sorted(d for n, d in G.degree())
[0, 1, 1, 2]
>>> nx.clustering(G)
{1: 0, 2: 0, 3: 0, 'spam': 0}

巨大な output を持つ幾つかの関数は (node, value) 2-タプルに渡り iterate します。これらは望むのであれば辞書構造で容易にストアされます。

>>> sp = dict(nx.all_pairs_shortest_path(G))
>>> sp[3]
{3: [3], 1: [3, 1], 2: [3, 1, 2]}

サポートされるグラフアルゴリズム上の詳細については Algorithms を見てください。

 

グラフを描く

NetworkX は主としてはグラフ描画パッケージではありませんが、Matplotlib による基本的な描画とオープンソース Graphviz ソフトウェアを使用するためのインターフェイスは含まれています。これらは networkx.drawing モジュールの一部で可能な場合にはインポートされます。

最初に Matplotlib の plot インターフェイスをインポートします (pylab もまた動作します)

>>> import matplotlib.pyplot as plt

ipython -pylab を使用してコードを対話的にテストすることは有用であると見い出すかもしれません、これは ipython と matplotlib のパワーを結合して便利な対話モードを提供します。

networkx.drawing のインポートが成功したかを試すためには次の一つを使用して G を描画します、

>>> G = nx.petersen_graph()
>>> plt.subplot(121)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw(G, with_labels=True, font_weight='bold')
>>> plt.subplot(122)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold')

対話ディスプレイに描画するとき。Matplotlib を呼び出す必要があるかもしれないことに注意してください。

>>> plt.show()

matplotlib を対話モードで使用していない場合のコマンドです (Matplotlib FAQ 参照)。

>>> options = {
...     'node_color': 'black',
...     'node_size': 100,
...     'width': 3,
... }
>>> plt.subplot(221)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw_random(G, **options)
>>> plt.subplot(222)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw_circular(G, **options)
>>> plt.subplot(223)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw_spectral(G, **options)
>>> plt.subplot(224)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw_shell(G, nlist=[range(5,10), range(5)], **options)

draw_networkx() を通した追加の options と layout を通した layoutsを見つけられます。draw_shell() でマルチ shells を使用できます。

>>> G = nx.dodecahedral_graph()
>>> shells = [[2, 3, 4, 5, 6], [8, 1, 0, 19, 18, 17, 16, 15, 14, 7], [9, 10, 11, 12, 13]]
>>> nx.draw_shell(G, nlist=shells, **options)

描画をファイルにセーブするためには、例えば次を使用します

>>> nx.draw(G)
>>> plt.savefig("path.png")

はローカルディレクトリのファイル path.png に書きます。Graphviz と PyGraphviz または pydot が貴方のシステムで利用可能であれば、ノード位置を得るためや、更なる処理のためにdot 形式でグラフを書くために nx_agraph.graphviz_layout(G) か nx_pydot.graphviz_layout(G) もまた使用できます。

>>> from networkx.drawing.nx_pydot import write_dot
>>> pos = nx.nx_agraph.graphviz_layout(G)
>>> nx.draw(G, pos=pos)
>>> write_dot(G, 'file.dot')

追加の詳細のためには Drawing を見てください。

以上