Graph theory in Python

Introduction

Today, I write the networkx module for graph theory in Python.
I write about basis of Gragh theory.
Please look at this page.
This post is not written Graph theory, but I want to share module in Python for Graph theory.

Networkx

Python3 have Networkx module.
If you have python2, you should install by pip

pip install networkx

Make Graph by Networkx

first, import networkx module and make instance.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

next, add node and edge

G.add_node(1)
# add Multiple nodes
G.add_nodes_from([2,3,4])

G.add_edge(1,2)
# add Multiple edges
G.add_edges_from([(3,4),(1,2),(4,6)])

next, plot G

nx.draw(G)
plt.show()

networkx have many function.
I will write new learning about networkx in this post.

Reference
https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f
http://akiniwa.hatenablog.jp/entry/2013/05/12/012459

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編の記事を見ていただけるとよいのではないかと思います。カーネルK-meansの実装編も併せてご覧ください。概要 K-meansの弱点カーネルトリックカーネルK-means アルゴリズム K-meansの弱点例えば、次のようなデータを用意します。このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。カーネルK-meansはK-meansの弱点を補います。カーネルトリック初めに、カーネルトリックを説明します。線形分離できないようなデータ

$X$ を例えば次のように線形分離できるように

$\phi(x)$ に送る写像

$\phi$ を考えます。カーネルは次のように定義されます。

$K(x,y) = \phi(x)^T \phi(y)$

$\phi$ を具体的に計算することは難しいですが、

$K(x,y)$ を計算することなら簡単です。この手法をカーネルトリックと呼ばれます。カーネルK means K-meansの目的関数を復習しておきます。

$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$ ここで、プロトタイプは

$\mu_i ~\forall k \in K$ としま...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。このスライドはダイクストラ法を説明したスライドです。 Overview アルゴリズム実装アルゴリズムこのアルゴリズムはスタート始点のノードを決める。そして、それをAと名付ける。各ノードに

$d=\infty$ を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。 For adj in adj_list: If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除くグラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。となっています。このアルゴリズムを図を用いて説明します。このグラフを使って説明します。初めに、スタート地点を決めます。そして、各ノードに

$d=\infty$ を割り当てます。 Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。次にAを取り除きます。次はBから始まります。Aと同じことをやります。このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。実装このアルゴリズムでは

$O(log(|V|^2))$ という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

Kullback-Leibler divergence

Introduction sorry, this page is Japanese only. 今日がダイバージェンスについて書いていきます。ちなみにエントロピーの知識を使うのでエントロピーの記事も見てあげてください。エントロピーの記事はこちら Kullback-Leibler Divergence 二つの確率分布の平均エントロピーの差を表す値をKLダイバージェンスといいます。式では次のように定義されます。

$KL(P||Q) = \int_{-\infty}^{\infty} P(X) log \frac{P(X)}{Q(X)}$ 離散の場合は

$KL(P||Q) = \sum_{i} P(X_i) log \frac{P(X_i)}{Q(X)}$ なぜ二つの分布間の距離をこのように定義できるのでしょうか。式の解釈真の分布P(X)が存在するとします。しかし、有限のデータから真の分布P(X)を求めるのは難しいです。そこで、有限のデータから推定して得られた確率分布をQ(X）とします。では真の分布P(X）と推定した分布Q(X)はどれだけ違っているのでしょうか。ここで登場するのがエントロピーです。エントロピーはその分布の不確実性を示す値でした。エントロピーが高いほど不確かなことが起こるとゆうことです。 P(X)のエントロピーとは

$-\int_{-\infty}^{\infty} logP(X)$ でした。では推定した確率分布Q(X）は確率分布P(X)に対してどれだけ不確実性を持っているのでしょうか。エントロピーとは情報量の期待値でした。確率分布Q(X）が持つ情報量は

$-logQ(X)$ です。この情報量を確率P(X)で期待値をとります。式は以下のようになります。

$-\int_{-\infty}^{\infty} P(X) logQ(X)$ この値と真の分布のエントロピーとの差を二つの分布間の差として定義します。式では以下のようになります。

$-\int_{-\infty}^{\infty} P(X) logQ(X) - (--\int_{-\infty}^{\infty} P(X) logP(X)))$ これを式変形すると $$-\int_{-\infty}^...

journey of Froakie (ケロマツの旅路)

このブログを検索

Graph theory in Python

Introduction

Networkx

Make Graph by Networkx

ラベル

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

ダイクストラ法

Kullback-Leibler divergence