Pythonで作る二部グラフ – 完全ガイド

2023.01.18 2022.08.31

本日のチュートリアルでは、2分割グラフとは何か、そしてそれをpythonプログラミング言語でnetworkxライブラリを使って実装する方法について理解します。

二部グラフ入門

ここで，”a “はAに属し，”b “はBに属している．

一方の集合のノードは互いに接続できず、他方の集合のノードにのみ接続できる。

import networkx as nx

from networkx.algorithms import bipartite

二部グラフは、例えば、顧客の購買のモデル化に有用です。

この場合、ノードは顧客のパーティションと商品のパーティションの2つのグループに分けられる。

エッジは、消費者がある製品を購入したことを示す。

このシナリオでは、アイテムは互いにリンクできないのが道理です。

結局、製品は他の製品を購入できないのだから。

プログラムの最初のステップは、モジュールやライブラリをコードにインポートすることです。

ここでは、基本的なnetworkxと、networkxからbipartiteをインポートする必要があります。

G = nx.Graph()

次に、空のグラフを作成して、後の節でノードとエッジを追加します。

G.add_nodes_from(['A1','A2','A3','A4'], bipartite=0)

G.add_nodes_from(['B1','B2','B3'],bipartite=1)

次にノード属性 “bipartite “を持つノードを追加します。

ここで、bipartite属性の値は、ノードのクラスを決定します。

その値が0であれば第1クラスに属し、1であれば第2クラスに属します。

G.add_edges_from([('A1', "B3"),('A4', "B1"),('A2', "B2"),('A2', "B3"),('A3', "B1")])

次に、対向するクラスのノード間のみにエッジを追加します。

エッジはいくつでも追加できますが、ここではいくつかのエッジを追加しました。

bipartite.is_bipartite(G)

また、グラフが二部構成かどうかは、以下の簡単なコードで確認することができます。

nx.draw_networkx(G, pos = nx.drawing.layout.bipartite_layout(G, ['A1','A2','A3','A4']), width = 2)

さて、以下のコードでグラフを簡単に可視化できます。

Networkx を使って二部グラフを作成する方法を学びました。

このチュートリアルはいかがでしたか？いずれにせよ、以下のチュートリアルをご覧になることをお勧めします。

お時間を割いていただきありがとうございました! 何か新しいことを学べたでしょうか!