NetworkXによるネットワーク分析 東京海洋大学 久保 幹雄.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
図示、可視化モジュール ~ pylab と numpy を ちょっと~. pylab とは? ・数学や統計的なグラフを生成するモ ジュール ・インストール pip や easy install からのインストールを推奨 →numpy モジュールなどの前提としている。 Anaconda の場合は標準.
算法数理工学 第 7 回 定兼 邦彦 1. グラフ グラフ G = (V, E) –V: 頂点 ( 節点 ) 集合 {1,2,…,n} –E: 枝集合, E  V  V = {(u,v) | u, v  V} 無向グラフ – 枝は両方向にたどれる 有向グラフ – 枝 (u,v) は u から.
2 dimensional bit vector approach Mikio Kubo. TIGER/Line graph DC.tmp 9559 nodes and arcs Shortest Paths between all border nodes of 2 regions.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
コンピュータビジョン特論B - Graph Cuts - 永橋知行.
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
    有限幾何学        第8回.
On the Enumeration of Colored Trees
最短路問題をGurobiで解こう! 流通最適化工学 補助資料.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
An Algorithm for Enumerating Maximal Matchings of a Graph
最適化ソルバーのための Python言語入門
Bottle/Pythonによる Webアプリ入門
Real Time Graph 指定された計測のデータを実時間収集サーバ(LABCOM)から取得し、リアルタイムにグラフとして表示する。
1章前半.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
最大最小性, 双対性 min-max property duality
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
最短路問題のための LMS(Levelwise Mesh Sparsification)
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
Selfish Routing and the Price of Anarchy 第2回
Selfish routing 川原 純.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
アルゴリズムとデータ構造 2011年7月4日
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
算法数理工学 第8回 定兼 邦彦.
アルゴリズムとデータ構造 2013年7月16日
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
離散数学 08. グラフの探索 五島.
巡回セールスマン問題への招待 東京商船大学 久保 幹雄.
WWW上の効率的な ハブ探索法の提案と実装
第3回 アルゴリズムと計算量 2019/2/24.
計算量理論輪講 chap5-3 M1 高井唯史.
First Course in Combinatorial Optimization
離散数学 07. 木 五島.
算法数理工学 第8回 定兼 邦彦.
アルゴリズムとデータ構造 2011年7月8日課題の復習
第4章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題
15.cons と種々のデータ構造.
情報知能学科「アルゴリズムとデータ構造」
配送計画最適化システム WebMETROのご紹介
離散数学 06. グラフ 序論 五島.
大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
Solver for COnstraint Programming:スコープ Pythonモジュールの使い方
Selfish Routing and the Price of Anarchy
A02 計算理論的設計による知識抽出モデルに関する研究
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月8日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
ソフトウェア工学 知能情報学部 新田直也.
13.近似アルゴリズム.
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
グラフの列挙 中野 眞一    (群馬大学) 2019/9/14 列挙学校.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

NetworkXによるネットワーク分析 東京海洋大学 久保 幹雄

NetworkXとは Pythonのネットワークモジュールのデファクト BSDライセンス https://networkx.github.io/ Anacondaに含まれる

無向グラフ(undirected graph, graph) G=(V,E) 2 4 1 6 3 5 V: 点(node, vertex, point)の集合 V={1,2,3,4,5,6} E: 枝(edge, arc, link)の集合 E={(1,2),(1,3),(2,3),(2,4), (3,4),(3,5),(4,6),(5,6)}

有向グラフ (directed graph,digraph) G=(V,E) 1 2 3 4 5 6 V: 点(node, vertex, point) の集合 V={1,2,3,4,5,6} E: 枝(edge, arc, link)の集合 E={(1,2),(1,3),(2,3),(2,4), (3,4),(3,5),(4,3),(4,6),(5,6)}

ネットワーク (network) 1 2 3 4 5 6 4 21 3 始点 終点 6 7 5 13 3 有向グラフに始点,終点,枝上に重み(weight; 費用, 容量,流量,距離など)を付加

u v 接続・隣接関係 頭(head) 尾(tail) もしくは終点 もしくは始点 枝 (u,v) は点 u (または v)に接続 (incident)している 点 u と点 v は隣接(adjacent)している 点 v は点 u の後続点(successor) 点 u は点 v の先行点(predecessor)

グラフ生成 (1) NetworkXのモジュールを読み込む import networkx グラフクラス Graph のインスタンス G を生成 G= networkx.Graph() Graph( ) 無向グラフ

グラフ生成 (2) NetworkXのモジュールをnxという名前をつけて読み込む import networkx as nx グラフクラス Graph のインスタンスG を生成 G = nx.Graph() 有向グラフも同様 G = nx.DiGraph() DiGraph( ) 有向グラフ

グラフ生成 (3) NetworkXのモジュールをすべて読み込む from networkx import * G = MultiGraph() G = MultiDiGraph() MultiGraph( ) 多重無向グラフ MultiDiGraph( ) 多重有向グラフ

点の追加 点の追加 G.add_node(1) G.add_node('Tokyo') 属性付きで追加 G.add_node(5, demand=500) G.add_node(6, product=['A','F','D']) まとめて追加も可能 G.add_nodes_from( [ 1,2,3,4 ] )

枝の追加 (1) 枝の追加(点は自動的に追加される)G.add_edge(1,2) G.add_edge(1,3) 属性付きで追加 G.add_edge(2,3, weight=7, capacity=15.0) G.add_edge(1,4, cost=1000) まとめて追加も可能 G.add_edges_from([ (1,2),(1,3),(2,3),(1,4)])

枝の追加 (2) 重み(weight)の属性付きでまとめて追加 G.add_weighted_edges_from( [ (1,2,10),(1,3,5),(2,3,10),(1,4,100)] ) print (G[1][2] ) #枝 (1,2) の情報を表示 >>> {'weight': 10}

点・枝の削除 点(と点に接続する枝)の削除 G.remove_node(1) 枝の削除 G.remove_edge(2,3) まとめて削除 G.clear( )

点・枝の情報 (1) すべての点のリスト G.nodes( ) for n in G で反復 すべての枝のリスト G.edges( ) for e in G.edges_iter() で反復 隣接点のリスト G.neighbors( u ) G.add_edges_from([(1,2),(1,3)]) for n in G: print( n, G.neighbors(n) ) >>> 1 [2, 3] 2 [1] 3 [1] 2 1 3

点・枝の情報 (2) 点uに隣接する点vをキーとし,枝(u,v)に付加された情報を値とした辞書 G[u] 枝(u,v)に付加された属性の辞書 G[u][v] G.add_weighted_edges_from([(1,2,100),(1,3,200),(2,3,60)]) print( G[1] ) >>> { 2: {'weight': 100}, 3: {'weight': 200} } print( G[1][2] ) >>> {'weight': 100}

点・枝の情報 (3) 点(n)に付加された属性の辞書 G.node[n] -> {'demand': 100} 2 点(n)に付加された属性の辞書 G.node[n] -> {'demand': 100} 有向グラフに対する点uの後続点のリスト G.successors(u) 有向グラフに対する点uの先行点のリスト G.predecessors(u) 1 4 3 G.add_edges_from([(1,2),(1,3),(2,3),(1,4)]) print( G.successors(1)) -> [2,3,4] print( G.predecessors(3)) -> [1,2]

点・枝の情報 (4) >>> 4 2 2 次数(degree):点に接続している枝の本数 入次数(indegree):点に入ってくる枝の本数 出次数(outdegree):点から出ていく枝の本数 G=nx.DiGraph() G.add_edges_from([(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,3),(4,6),(5,6)]) print(G.degree(4), G.in_degree(4), G.out_degree(4)) >>> 4 2 2 1 2 3 4 5 6

グラフ描画 (1) Pylabモジュールをすべて読み込む from pylab import * 描画 nx.draw(G) 画面を表示 show()

グラフ描画 (2) Matplotlibのpyplotをpltという名前で読み込む import matplotlib.pyplot as plt nx.draw(G) 画面を表示 plt.show() ファイルに保存(規定値はPNGフォーマット) plt.savefig('sample')

ラベル,点の色・大きさ,枝の色・太さを変える nx.draw(with_labels=True, G,node_color=‘r’, node_size=1000, edge_color='g', width=10)

座標を指定 nx.draw(G,pos={1:(0,0),2:(1,5),3:(5,2),4:(5,5)}) 規定値はバネ法によって座標は自動 引数 pos (x,y座標のタプル)で点の座標を辞書で与えると,座標を指定できる. nx.draw(G,pos={1:(0,0),2:(1,5),3:(5,2),4:(5,5)})

一部の点,枝を描画 nx.draw(G, nodelist=[1,2],edgelist=[(1,2)])

座標を求めるためのレイアウト関数 円上レイアウト circular_layout(G) ランダム・レイアウト random_layout(G) 同心円レイアウト shell_layout(G, nlist) バネのレイアウト spring_layout(G) 既定値 スペクトル・レイアウト spectral_layout(G)

レイアウトの例 (1) 5×5の格子グラフの生成G=nx.grid_2d_graph(5,5) 円上レイアウトの計算 レイアウトの例 (1) 5×5の格子グラフの生成G=nx.grid_2d_graph(5,5) 円上レイアウトの計算 pos=nx.circular_layout(G) 描画 nx.draw(G,pos=pos)

レイアウトの例 (2) 10×30のランダムな2部グラフの生成G=nx.bipartite_random_graph(10,30,0.3) レイアウトの例 (2) 10×30のランダムな2部グラフの生成G=nx.bipartite_random_graph(10,30,0.3) 同心円レイアウト(最初の10点が内側) pos=nx.shell_layout( G, nlist=[ [i for i in range(10)], [i for i in range(10,40)] ] ) 描画 nx.draw(G,pos=pos)

アルゴリズム 最小費用流 リンク分析 同型判定 グラフ探索 2部グラフの判定 次数相関係数 グラフの中心性 グラフの境界 クリーク グラフの連結性やカット 閉路を持たない有向グラフ Euler閉路 マッチング 最小木問題 最短路問題 最大流と最小カット

クリークと安定集合 G.add_edges_from([ (1,3),(2,4),(3,4),(3,5),(3,6),(4,6)]) G_bar =nx.complement(G)           #補グラフを作る for c in nx.find_cliques(G_bar):        #極大クリークの列挙 print( c ) >>> [1, 5, 2, 6] [1, 5, 4] [3, 2]

連結性 G=nx.random_geometric_graph(100,0.1) c =nx.connected_components(G) 連結:任意の2点間にパスが存在 ランダムで疎な幾何学的グラフの生成 G=nx.random_geometric_graph(100,0.1) c =nx.connected_components(G) -> 連結成分(点リスト)のジェネレータ nx.draw(G, nodelist=list(c)[0]) nx.draw(G, nodelist=list(c)[1])

2連結性 G.add_edges_from([(0,1),(0,2),(1,2),(2,3),(2,4),(3,4)]) 2連結成分 2連結:1つの点を除いたときに非連結にならないグラフ 間接点:複数の2連結成分に含まれる点 G.add_edges_from([(0,1),(0,2),(1,2),(2,3),(2,4),(3,4)]) 2連結成分 print( list( nx.biconnected_components(G) ) ) >>> [{2, 3, 4}, {0, 1, 2}] 間接点 print( list( nx.articulation_points(G) ) ) >>> [ 2 ]

点カットと枝カット 点カット print( nx.minimum_node_cut(G) ) >>> { 2 } 枝カット 点カット:非連結にするための削除すべき点集合 枝カット:非連結にするための削除すべき枝集合 点カット print( nx.minimum_node_cut(G) ) >>> { 2 } 枝カット print( nx.minimum_edge_cut(G) ) >>>{(2, 3), (4, 3)}

閉路をもたないグラフ (1) トポロジカル・ソート:右から左に向かう枝がないように G=nx.DiGraph() 閉路をもたないグラフ (1) トポロジカル・ソート:右から左に向かう枝がないように G=nx.DiGraph() G.add_edges_from([('s',1),('s',2),(1,'t'),(2,1),(2,3),(3,'t'),(3,1)]) print( nx.topological_sort(G) ) >>> ['s', 2, 3, 1, 't']

閉路をもたないグラフ (2) print(nx.ancestors(G,3)) >>> {2, 's'} 閉路をもたないグラフ (2) vの先祖(ancestor):点vに至るパスが存在する点 vの子孫(descendant):点vから到達可能なパスが存在する点 print(nx.ancestors(G,3)) >>> {2, 's'} print(nx.descendants(G,3)) >>> {'t', 1}

Euler閉路 Euler閉路:すべての枝をちょうど1回ずつ通過する閉路 G.add_edges_from([ (1,2),(1,5),(2,3),(2,6),(3,4),(3,7),(4,8), (5,6),(6,7),(7,8),(2,9),(6,9),(3,10),(7,10)]) print( nx.is_eulerian(G) ) >>> True for e in nx.eulerian_circuit(G): print( e , end='') (1, 2) (2, 3) (3, 4) (4, 8) (8, 7) (7, 3) (3, 10) (10, 7) (7, 6) (6, 2) (2, 9) (9, 6) (6, 5) (5, 1)

マッチング マッチング:点の次数が1以下の部分グラフ G=nx.grid_2d_graph(3,4) print( nx.maximal_matching(G) ) print( nx.max_weight_matching(G) ) 最大(maximum)マッチング 極大(maximal)マッチング

最小木 G.add_edge ('Arigator','WhiteBear',weight= 2 ) G.add_edge ('Arigator','Bull',weight= 1 ) G.add_edge ('Bull','WhiteBear',weight= 1 ) G.add_edge ('Bull','Shark', weight= 3 ) G.add_edge ('WhiteBear','Condor',weight= 3 ) G.add_edge ('WhiteBear','Shark',weight= 5 ) G.add_edge ('Shark','Condor',weight= 4 ) T= nx.minimum_spanning_tree(G) Print( T.edges() ) >>> 結果 [('WhiteBear', 'Condor'), ('WhiteBear','Bull'), ('Arigator', 'Bull'), ('Shark', 'Bull')]

最短路 (1) G.add_weighted_edges_from([('s',1,10),('s',2,5),(1,2,2), 最短路:始点sから終点tまでのパスで費用の合計が最小のもの G.add_weighted_edges_from([('s',1,10),('s',2,5),(1,2,2), (1,'t',1),(2,1,3),(2,3,2),(3,'t',6)]) print( nx.dijkstra_path(G,'s','t') ) >>> ['s', 2, 1, 't'] 枝の費用が負の場合 bellman_ford(G,source) 全対全の最短路 floyd_warshall(G)

最短路 (2) 点sから他のすべての点への最短路の情報 print(nx.single_source_dijkstra(G,’s’)) >>> ({1: 8, 's': 0, 3: 7, 2: 5, 't': 9}, {1: ['s', 2, 1], 's': ['s'], 3: ['s', 2, 3], 2: ['s', 2], 't': ['s', 2, 1, 't']}) (各点への最小費用の辞書, 各点へのパスの辞書) 始点と終点を指定して(ちょっと)高速化(A*アルゴリズム) astar_path(G, source, target) より高速な最短路プログラム http://www.logopt.com/mikiokubo/SP/

最短路 (3) パスの列挙 all_simple_paths()はすべての単純パスのジェネレータ for p in nx.all_simple_paths(G,'s','t'): print(p) >>> ['s', 1, 't'] ['s', 1, 2, 3, 't'] ['s', 2, 1, 't'] ['s', 2, 3, 't']

最大流 容量 終点 始点 富士山から江戸までなるべくたくさんの氷を送りたい どのように運ぶ?

最大流問題(定義) 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の容量 u: E → R+ 目的: 始点sから終点tまでの最大フロー

フローとは? 以下の条件を満たす実数値関数x:E → R フロー整合条件 (江戸以外では氷は消費されない) 容量制約と非負制約 (飛脚の運べる量には限界がある)

最大流/最小カット (1) 最大流:始点sから終点tまでのフローでsから出る量が最大のもの G.add_weighted_edges_from([ ('s',1,5),('s',2,8),(2,1,2),(1,'t',8), (2,3,5),(3,'t',6)]) print( nx.maximum_flow(G,'s','t',capacity='weight') ) >>> (12, {1: {'t': 7}, 's': {1: 5, 2: 7}, 3: {'t': 5}, 2: {1: 2, 3: 5}, 't': {}}) (最大フロー値, 点から出るフローを表す辞書) 7 5 2 5 7 12 5

最大流/最小カット (2) print( nx.minimum_cut(G,'s','t',capacity='weight' ) 最小カット:始点sを含み終点tを含まない点の部分集合Sで, SとV-S間の枝の容量の合計が最小のもの print( nx.minimum_cut(G,'s','t',capacity='weight' ) >>> (12, ({'s', 2}, {'t', 1, 3})) (最小カット値, カットを表す点の部分集合 (S,V-S) )

最小費用流 容量 費用 富士山から江戸まで10単位の氷を送りたい. なるべく安く運ぶにはどうしたらよい?

最小費用流問題の特徴 流出量(需要量)を関数bで表すと b(s)=-10 b(1)=0, b(2)=0, b(3)=0 b(t)=10 枝に費用がある それぞれの点での流出(入)量が決まっている sでは-10流出 (10流入) 1では0流出 tでは10流出 流出量(需要量)を関数bで表すと b(s)=-10 b(1)=0, b(2)=0, b(3)=0 b(t)=10

最小費用流問題(グラフ理論的定義) 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の容量 u: E → R+ 枝の費用 c: E → R 流出(需要)量関数 b: V → R 目的: 費用の合計が最小となる実行可能フロー ただし,

実行可能フローとは? 以下の条件を満たす実数値関数x:E → R フロー整合条件 (各点における氷の消費・補充 が決まっている) 容量制約と非負制約 (飛脚の運べる量には限界がある) 費用の合計を最小にする実行可能フローを最適フローと呼ぶ

最小費用流 (1) 7 5 2 5 3 G.add_node(‘s’, demand = -10) # 負の流出量 = 供給量 G.add_node(‘t’, demand = 10) # 正の流出量 = 需要量 G.add_edge('s', 1, weight = 10, capacity = 5) G.add_edge('s', 2, weight = 5, capacity = 8) G.add_edge(2, 1, weight = 3, capacity = 2) G.add_edge(1, 't', weight = 1, capacity = 8) G.add_edge(2, 3, weight = 2, capacity = 5) G.add_edge(3, 't', weight = 6, capacity = 6) print( nx.network_simplex(G) ) >>> ((112, {1: {'t': 7}, 's': {1: 5, 2: 5}, 3: {'t': 3}, 2: {1: 2, 3: 3}, 't': {}}) 7 5 2 5 3

最小費用流 (2) ネットワーク単体法 network_simplex(G, demand, capacity, weight) 容量スケーリング法 capacity_scaling(G, demand, capacity, weight) 最大流+最小費用 max_flow_min_cost(G, s, t, capacity, weight)

グラフ探索 (1) 深さ優先探索(depth first search) (枝を返す場合): for e in nx.dfs_edges(G,1): print(e) >>> (1, 2) (2, 3) (1, 4)

グラフ探索 (2) 広がり優先探索(breadth first search) (直前の点を表す辞書を返す場合): print( nx.bfs_predecessors(G,1) ) >>> {2: 1, 3: 1, 4: 1}

事例 (1) 某飲料水メーカーの問題 3デポから300店舗への直送配送 (トラック台数70台) 某コンサル経由で,某大学教授に依頼 Xpress-MPで学生がモデル化 12店舗で破綻 空輸送の最小化を最小費用流問題に帰着 Euler閉路の分解で巡回路生成

原ネットワーク(輸送必要台数) F 3 1 H D 1 G E 2 C 3 4 I 4 2 A デポ 2 J B

入力-出力(次数)を計算 -3 F 3 1 H -1 D 1 +3 -3 +3 G E 2 C 3 4 I -2 4 2 A +2 +3 2 J B -2

輸送問題 (最小費用流問題の特殊形) 出力超過点 入力超過点 2 A B 2 2 流出量関数(demand) 3 D 3 F 3 E 3 3 G 3 J 3 1 H 1 2 I 2 輸送問題 (最小費用流問題の特殊形)

最短空輸送の追加->Euler閉路 F 3 3 1 H D 1 G E 3 1 2 C 3 4 I 4 2 2 A 2 J B 2

F 巡回路への分割(1) 1 1 1 H D 1 1 G E 1 C 4 4 A E 2 J A B 2

巡回路への分割(2) F 2 2 D G E 2 2 2 I 2 2 A J

事例 (2) 赤:重病者 黄:軽傷者 青:健常者 可視化ツールとしてのNetworkX 避難所 病院 災害地点 災害発生時からの経過時間

Questions, Comments, Suggestions?