Python-data-science-python-graph-data
Python-グラフデータ
CSGraphは Compressed Sparse Graph の略で、スパース行列表現に基づく高速グラフアルゴリズムに焦点を当てています。
グラフ表現
まず、スパースグラフとは何か、グラフ表現でどのように役立つかを理解しましょう。
スパースグラフとは正確には何ですか？
グラフはノードのコレクションであり、ノード間にリンクがあります。 グラフはほとんどすべてを表すことができます-ソーシャルネットワーク接続。各ノードは人であり、知り合いに接続されています。画像。各ノードはピクセルであり、隣接するピクセルに接続されています。各ノードが最も近い隣接ノードと実際に想像できる他のものに接続されている高次元分布のポイント。
グラフデータを表す非常に効率的な方法の1つは、スパース行列です。これをGと呼びましょう。 マトリックスGのサイズはN x Nで、G [i、j]はノード「i」とノード「j」間の接続の値を示します。 スパースグラフには、ほとんどゼロが含まれています。つまり、ほとんどのノードには少数の接続しかありません。 このプロパティは、関心のあるほとんどの場合に当てはまります。
スパースグラフサブモジュールの作成は、以下を含むscikit-learnで使用されるいくつかのアルゴリズムによって動機付けられました-
- Isomap -グラフ内の最短経路を見つける必要がある多様な学習アルゴリズム。
- 階層的クラスタリング-最小スパニングツリーに基づくクラスタリングアルゴリズム。
- スペクトル分解-スパースグラフラプラシアンに基づく投影アルゴリズム。
具体的な例として、次の無向グラフを表現したいことを想像してください-
このグラフには3つのノードがあり、ノード0と1は重み2のエッジで接続され、ノード0と2は重み1のエッジで接続されています。 次の例に示すように、無向グラフは対称行列で表されることを念頭に置いて、密集したマスクされた疎な表現を構築できます。
G_dense = np.array([ [0, 2, 1],
[2, 0, 0],
[1, 0, 0] ])
G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix
G_sparse = csr_matrix(G_dense)
print G_sparse.data上記のプログラムは、次の出力を生成します。
array([2, 1, 2, 1])これは、ノード0と2が重みゼロのエッジで接続されていることを除いて、前のグラフと同じです。 この場合、上記の密な表現はあいまいさをもたらします。ゼロが意味のある値である場合、どのように非エッジを表現できますか。 この場合、あいまいさを解消するには、マスク表現またはスパース表現を使用する必要があります。
次の例を考えてみましょう。
from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
[np.inf, 2, 0 ],
[2, np.inf, np.inf],
[0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data上記のプログラムは、次の出力を生成します。
array([ 2., 0., 2., 0.])
