一般的なグラフの描画
GraphPlotおよび
GraphPlot3Dは,視覚的にアピールするグラフの2D/3Dレイアウトを計算し,プロットする.これらの関数は非常に大きいグラフで使えるよう設計されており,連結グラフも非連結グラフも扱うことができる.
GraphPlot[{vi1->vj1,vi2->vj2,…}] | 頂点 vik が頂点 vjk と接続しているグラフのプロットを生成する |
GraphPlot[{{vi1->vj1,lbl1},…}] | ラベル lblk をグラフ中の辺に関連付ける |
GraphPlot[m] | 隣接行列 m で表されるグラフのプロットを生成する |
GraphPlot3D[{vi1->vj1,vi2->vj2,…}] | 頂点 vik が頂点 vjk と接続しているグラフの3Dプロットを生成する |
GraphPlot3D[{{vi1->vj1,lbl1},…}] | ラベル lblk をグラフ中の辺に関連付ける |
GraphPlot3D[m] | 隣接行列 m で表されるグラフの3Dプロットを生成する |
次は,規則のリストで指定されたグラフをプロットする:
非連結グラフでは,個々の要素が視覚的にアピールする形に並べられている:
浮動小数点の相違のため,
GraphPlotの出力はプラットフォームによって若干異なることがある.
GraphPlotとGraphPlot3Dのオプション
DirectedEdges
オプション
DirectedEdgesは,辺を矢印として描くかどうかを指定する.このオプションが取り得る値は
Trueまたは
Falseである.このオプションのデフォルト値は
Falseである.
EdgeLabels
オプション
EdgeLabelingは,辺に与えられたラベルを表示するかどうか,また表示する場合はどのようにするかを指定する.このオプションが取り得る値は
All,
None,または
Automaticである.このオプションのデフォルト値は
Automaticで,指定された辺のラベルをグラフに表示する.
あるいは,
Tooltip[vi->vj,lbl]を使って辺のツールチップを指定する.カーソルを頂点3と頂点6の間の辺の上,および頂点3と頂点5の間の辺のラベル上に置くとツールチップが見られる:
EdgeShapeFunction
オプション
EdgeShapeFunctionはグラフの辺の視覚的表現を指定する.このオプションが取り得る値は
Automatic,
None,グラフィックスプリミティブと指示子を適切に組み合せたものを与える関数である.デフォルト設定の
Automaticでは,各辺が示される.
EdgeShapeFunction->Noneでは辺は描画されない.
EdgeShapeFunction->g のとき,各辺は関数
g で与えられるグラフィックスプリミティブとグラフィックス指示子で描画される.この関数は
g[{ri,…,rj},{vi,vj},lblij,…]という形式で3つ以上の引数を取ることができ,
ri と
rj は辺の始点と終点の座標,
vi と
vj は最初の頂点と最後の頂点,
lblij は辺に指定された任意のラベルあるいは
Noneである.
EdgeShapeFunction->g の明示的な設定値は
EdgeLabelsと
DirectedEdgesの設定値に優先する.
辺が頂点から0.1(グラフの座標系において)後退した灰色の矢印でプロットされている:
次は,頂点には球を,辺には円柱を使った3Dグラフをプロットする:
これは,辺がバネで頂点は球で描かれているグラフをプロットする:
GraphLayout
GraphPlotと
GraphPlot3Dで使えるアルゴリズムは
GraphLayoutオプションで
GraphLayout->"name"あるいは
GraphLayout->{"name",opt1->val1,…}として指定することができる.ここで
opti-> vali は,別の
セクションで記述されているようにメソッド特定のオプションである.
GraphLayout->Automaticでは,木には
"RadialDrawing"が,その他には
"SpringElectricalEmbedding"が使われる.
Automatic | 問題に適したメソッドが自動的に選ばれる |
"CircularEmbedding" | 頂点を円形に並べる |
"HighDimensionalEmbedding" | 高次埋込み法を呼び出す.この方法では,まず,頂点と k 個の中心のグラフ距離に基づいて,グラフを高次元空間でレイアウトする.次にこのレイアウトが,主成分分析の線形結合を使って二次元空間あるいは三次元空間に投影される |
"RadialDrawing" | 木または木構造のグラフに適した 放射線状描画法を呼び出す.グラフが木ではない場合,まず全域木が構成され,次に全域木の放射状描画を使ってグラフが描画される |
"RandomEmbedding" | 頂点をランダムに並べる |
"SpiralEmbedding" | 頂点をらせん状に並べる.3Dでは,球面状に頂点を等間隔で並べる |
"SpringElectricalEmbedding" | バネ電気埋込み法を呼び出す.このモデルでは,近接する頂点は,互いに両者の物理的距離に比例する引力の影響を受ける.頂点はすべて互いの物理的距離に反比例する反発的な電気力の影響を受ける.全体としてのエネルギーは最小になる |
"SpringEmbedding" | バネ埋込み法を呼び出す.このモデルでは,頂点は,まるでバネで繋がれているかの様に,他の頂点の引力あるいは反発力のどちらかの影響を受ける.理想的なバネの長さは頂点間のグラフ距離に等しい.バネの力は最小になる |
次は,デフォルトメソッドを使ってペテルセングラフを描画する:
次は,
"SpringEmbedding"アルゴリズムを使ってグラフを描画する:
次は,
"HighDimensionalEmbedding"アルゴリズムを使ってグラフを描画する:
次は
"CircularEmbedding"メソッドを使って頂点が30個のグラフを描画する:
次は,
"SpiralEmbedding"メソッドを使って30個の頂点のグラフを3Dで描画する:
次は
"RandomEmbedding"メソッドを使ってグラフを描画する:
MultiedgeStyle
オプション
MultiedgeStyleは,2つの頂点間の多重辺を描くかどうかを指定する.
MultiedgeStyleが取り得る値は
Automatic(デフォルト),
True,
False,正の実数である. デフォルト設定の
MultiedgeStyle->Automaticでは,規則のリストで指定されたグラフの多重辺が表示されるが,.
MultiedgeStyle->δ では,多重辺はスケールされた距離
δ に広がる.
デフォルトでは,グラフが規則のリストとして与えられている場合に多重辺が表示される:
しかし,多重辺が隣接行列で指定されている場合には表示されない:
PackingLayout
オプション
"PackingLayout"は非連結要素のパッキングに使用するメソッドを指定する.このオプションで取ることのできる値は
Automatic(デフォルト),
"ClosestPacking",
"ClosestPackingCenter",
"Layered",
"LayeredLeft",
"LayeredTop",
"NestedGrid"である.
"PackingLayout"->"ClosestPacking"ではポリオミノ法[6]を左上から開始し,要素ができるだけ近付くようにパックされる.
"PackingLayout"->"ClosestPackingCenter"では,要素は中央から開始してパックされる.
"PackingLayout"->"Layered"では,左上から開始し,層にパックされる.
"PackingLayout"->"LayeredLeft"あるいは
"PackingLayout"->"LayeredTop"では,要素はそれぞれ上または左から開始され,層にパックされる.
"PackingLayout"->"NestedGrid"では,要素はネストされた格子に配列される.一般の効率的なデフォルト設定は
"PackingLayout"->"Layered"であり,パッキングは最大の境界ボックス領域の要素から始まる.
次は,非連結要素を
"ClosestPackingCenter"法でパッキングする:
パッキングは
"PackingLayout"のサブオプションを使って調整することができる.サブオプション"
"Padding"は要素間に許されるスペースを指定するもので,可能な値は
Automatic(デフォルト),非負の数のどちらかである.サブオプション
"PaddingFunction"も要素間に許されるスペースを指定するものであり,
"Padding"をオーバーライドする.これは
{{w1, h1},…}という形式のリストを取る.それぞれの値は要素の境界ボックスの幅と高さであり,非負の数を返す.オプション
"PackingLayout"->"ClosestPacking"および
"PackingLayout"->"ClosestPackingCenter"でも
"PolyominoNumber"サブオプションを使うことができる.このサブオプションはそれぞれの非連結要素を近似するのに使われるポリオミノの平均の数を指定する.
"PolyominoNumber"サブオプションで取れる値は
Automatic(デフォルト.通常
"PolyominoNumber"を100に設定)か正の整数である.小さい
"PolyominoNumber"は通常小さい要素が大きい要素の間に埋め込まれることを許さないという効果がある.
5ポリオミノの平均を使って書く要素を近似するよう指定する:
PlotRangePadding
PlotStyle
PlotStyleは
GraphPlotおよび
GraphPlot3Dにより継承されるグラフィックス関数に共通のオプションである.
PlotStyleはオブジェクトを描画するスタイルを指定する.
ここでは,辺が太めの線で描かれている.辺も頂点も赤でラベル付けされている:
SelfLoopStyle
オプション
SelfLoopStyleは,自分自身とリンクしている頂点のループをどのように描くかどうか,またどのように描くかを指定する.このオプションで取れる値は,
Automatic(デフォルト),
True,
False,正の実数のいずれかである.
SelfLoopStyle->Automaticでは,グラフが隣接行列ではなく規則のリストにより指定されている場合に,自己ループが表示される.
SelfLoopStyle->δ では,直径(平均の辺の長さに対する)
δ で自己ループが描画される.
デフォルトでは,自己ループは規則のリストで指定されたグラフに対して表示される:
グラフが隣接行列で指定されると,自己ループは表示されない:
VertexCoordinates
オプション
VertexCoordinatesは頂点座標を指定する.取り得る値は,
None,座標のリスト,あるいは選択された/すべての座標を指定する規則のリストである.
次は,既知の座標を使ってペテルセン(Petersen)グラフを描画する:
"SpringEmbedding"アルゴリズムを使って,上と同じグラフの頂点座標を計算する:
座標だけ指定する:
座標を固定することで二部グラフを描画する.非連結要素を連結するために,「アンカー」を加える:
2部グラフが連結されると,左や右のアンカーで拡張しなくてもずっとよく動作する:
VertexLabels
オプション
VertexLabelsは頂点の名前をラベルとして表示するかどうかを指定する.このオプションで取れる値は,
All,
None,
Automatic(デフォルト)のいずれかである.
VertexLabels->Allではラベルが表示される.隣接行列で指定されたグラフでは,頂点ラベルは連続した整数
,
,
…,
(ここで
は行列の大きさ)を取る.規則のリストで指定されたグラフでは,ラベルは規則で使われた式である.
VertexLabels->Noneは各頂点を点として表示する.また,規則のリストの任意の場所で
Tooltip[vk,vlbl]を使うと,頂点
vk のツールチップを指定することができる.
隣接行列の指標として与えられたラベルを持つグラフを描画する:
VertexShapeFunction
オプション
VertexShapeFunctionは,グラフの辺のグラフィカルな表現を指定する.このオプションで取り得る値は,
Automatic,
None,あるいはグラフィックスプリミティブおよび指示子の適切な組合せを与える関数である.デフォルト設定の
Automaticでは,頂点は点として描かれる.
VertexShapeFunction->g では,各頂点が
g[ri,vi,…]で与えられるグラフィックスプリミティブで描画される.
ri は頂点の座標で,
vi は頂点のラベルである.
VertexShapeFunction->g の明示的な設定値は
VertexLabelsの設定値に優先する.
すべての描画メソッドで,メソッドのサブオプション
"Rotation"を使うことができる.これはデフォルト方向から正のラジアンで所望の時計回りの回転量を指定する.このオプションは任意の数値か
Falseを取る.デフォルトは0である.
GraphPlotと
GraphPlot3Dでは,デフォルトの向きは整列ステップにより導出される.ここでは主軸が見付けられ,グラフ描画は
軸で整列する.しかし,
"Rotation"->Falseが指定されると,このステップは抜かされる.
| | |
"Rotation" | 0 | 描画を時計回りにどれだけ回転させるか |
グラフのプロットを時計回りに
,
,
だけ回転させる:
"SpringEmbedding"と"SpringElectricalEmbedding"に共通のサブオプション
SpringEmbeddingメソッドと
SpringElectricalEmbeddingメソッドは両方ともいわゆるForce Directed法に属す.どちらも各頂点の力を計算し,システム全体のエネルギーが最小になるように頂点を力に沿って繰り返し動かす.アルゴリズムの詳細は
[8]を参照のこと.両者には次のような共通のオプションがいくつかある.
| | |
"EnergyControl" | Automatic | 最小化の間,エネルギー関数をどのようの制御するか |
"InferentialDistance" | Automatic | 力計算でそれより遠い頂点が無視されるカットオフの距離 |
MaxIterations | Automatic | エネルギーを最小にするために使われる最大反復回数 |
"RandomSeed" | Automatic | 最初に頂点を置く際に使うランダムシード |
"RecursionMethod" | Automatic | グラフのレイアウトにマルチレベルのアルゴリズムを使用するかどうか |
"StepControl" | Automatic | エネルギー最小化の最中にステップ長をどのように変更するか |
"StepLength" | Automatic | 頂点を動かす際の最初のステップ長 |
"Tolerance" | Automatic | エネルギーの最小化プロセスを終了するのに使われる許容率 |
"SpringEmbedding"と
"SpringElectricalEmbedding"メソッドに共通のサブオプション
"EnergyControl"
サブオプション
"EnergyControl"は,最小化の間のシステムの合計エネルギーへの制限を指定する.有効な値は
Automatic(デフォルト),
"Monotonic"あるいは
"NonMonotonic"である.値が
"Monotonic"のとき,力に沿ったステップは,エネルギーが低下する場合にのみ許容される.値が
"NonMonotonic"のときは,力に沿ったステップはエネルギーが低下しなくても許容される.
"InferentialDistance"
サブオプション
"InferentialDistance"は,頂点間のインタラクションが存在しないと仮定されるようになるカットオフ距離を指定する.可能な値は
Automatic(デフォルト),あるいは正の数値である.
"SpringEmbedding"メソッドでは,頂点
i と
j の間のグラフ距離が
"InferentialDistance"の値よりも大きい場合には,
i と
j の間のバネの反発力・引力は無視される.
"SpringElectricalEmbedding" メソッドでは,頂点
i と
j の間のユークリッド距離が
"InferentialDistance"のオプション値よりも大きければ,
i と
j の間の反発力が無視される.
以下は
"SpringElectricalEmbedding"メソッドでランダムな木を描画する:
もっと小さい(より負の)
"RepulsiveForcePower"オプション値を使う(
次のセクションを参照).これでグラフの空白がもっと埋まった:
"InferentialDistance"オプションに小さい値を使うと,同様の効果が得られる:
MaxIterations
オプション
MaxIterationsは,エネルギーを最小にするために使う再帰の最大回数を指定する.取り得る値は
Automatic(デフォルト)か正の整数である.
"RandomSeed"
オプション
"RandomSeed"は,最初に頂点を置く場所を計算する乱数ジェネレータの種を指定する.このオプションを変更すると,グラフ描画の方向に影響を与えるが,グラフのレイアウトを変更することもある.このオプションで取り得る値は
Automaticまたは整数である.
次は,Petersonグラフの描画に見られる異なる乱数シードの影響を示す:
"RecursionMethod"
オプション
"RecursionMethod"は,グラフのレイアウトを再帰的な過程で生成するかどうかを指定する.このオプションで取り得る値は
Automatic (デフォルト),
"Multilevel",あるいは
Noneである.
"Multilevel"アルゴリズムでは,グラフは徐々に頂点の少ない粗いグラフになっていく.粗いグラフは最初にレイアウトされ,細かいグラフへと補間され,さらに微調整される.
オプション
"Randomize"では,可能な値は
Automatic,
True,
Falseのいずれかである.
"MinSize"では,可能な値は
Automaticか正の数である.
"CoarseningScheme"の場合,実装されるアルゴリズムは,粗い頂点を形成する最大独立頂点集合か,マッチングとも呼ばれる最大独立辺集合のどちらかに基づく.マッチングにおいては,1辺を形成する2頂点が融合し,1つの粗いグラフの頂点を形成する.以下は
"CoarseningScheme"に可能な値である.
"MaximalIndependentVertexSet" | グラフ距離が3以下ならば最大独立集合の頂点をリンクする |
"MaximalIndependentVertexSetInjection" |
| グラフ距離が1か2ならば最大独立集合の頂点をリンクする |
"MaximalIndependentVertexSetRugeStuben" |
| 最大独立頂点集合を生成し,集合内で隣接頂点の多いものを優先し,グラフ距離が3以下ならば集合内の頂点をリンクする |
"MaximalIndependentVertexSetRugeStubenInjection" |
| グラフ距離が1か2ならば頂点をリンクし,隣接頂点の多いものを優先する |
"MaximalIndependentEdgeSet" | マッチングの際に,辺を自然順で考える |
"MaximalIndependentEdgeSetHeavyEdge" |
| マッチングの際に,辺の重みの大きい(例:もとのグラフで多数の辺を表す辺)ものを優先する |
"MaximalIndependentEdgeSetSmallestVertexWeight" |
| 頂点の重みが最小の隣接頂点とのマッチングを優先する |
"StepControl"
オプション
"StepControl"エネルギー最小化の過程でステップ長をどのように修正するかを定義する.可能な値は
Automatic (デフォルト),
"Monotonic" ステップ長を短くすることしかできない),
"NonMonotonic" (ステップ長は長くも短くもできる),
"StrictlyMonotonic" (反復の間にステップ長が厳密に縮められる)のいずれかである.
"StepLength"
オプション
"StepLength"は,頂点を動かす際の初期ステップ長を与える.可能な値は
Automatic(デフォルト)か,あるいは正の実数である.
Tolerance
オプション
Toleranceは,エネルギー最小化の過程を終了する際に使用する許容度を指定する.各頂点の座標変化の平均が許容度よりも小さい場合はエネルギー最小化が終了され,現行座標が出力として返される.取り得る値は
Automaticか正の実数である.
"SpringElectricalEmbedding"メソッドのメソッドサブオプション
| | |
"Octree" | Automatic | 反発力の計算にOCTREEデータ構造(3 Dの場合) あるいはQUADTREE構造 (2 Dの場合) を使うかどうか |
"RepulsiveForcePower " | -1 | 距離によって反発力がどれほどの速度で小さくなるか |
"SpringElectricalEmbedding"のメソッドオプション
"Octree"
"Octree"オプションは,OCTREEデータ構造(3Dで)またはQUADTREEデータ構造(2Dで)を反発力の計算に使うかどうかを指定する.可能な設定値は
Automatic(デフォルト),
True,
Falseである.OCTREEデータ構造を使うと,長距離の反発力を近似することで計算が複雑になるのを最低限に抑えることができる.然し,力の計算に近似が導入されるため,結果が思わしくない場合もある.
"RepulsiveForcePower"
可能な設定値は負の実数でデフォルトは-1である.バネ電気埋込みでは,頂点
間の反発力は,デフォルトで
である.
RepulsiveForcePowerの値が
(
)であれば,反発力は
と定義できる.ここで
は頂点間の距離,
は定数係数である.
長い距離に渡る強く長い範囲の反発力は,周辺部の頂点の間隔が中心近くのそれよりも狭まるという境界効果を及ぼすことがよくある.弱く長い範囲の反発力を指定することで,この効果を弱められることがある.このオプションは,グラフがより多くのスペースを占めるよう描画する場合に便利である(詳細は
"InferentialDistance"メソッドオプションを参照のこと).
反発力
では,境界の頂点はデフォルト値の
のときほど近付いていない:
より空間を占めるグラフを描画する
GraphPlotのデフォルト設定は一般にうまく動作するが,頂点次数に広範な値を持つグラフでは頂点が閉めるスペースを小さくできるような設定を使うことが必要になる場合がある.
しかし,
"SpringEmbedding"が,より空間を占める描画をすることもある:
反発力が距離に沿ってより速く減衰するようにデフォルト(
-1)より小さい反発力を使っても同様の効果が得られることがある:
このような木に似たグラフの場合は,木を描画するアルゴリズムが適しているだろう.木のレイアウトをうまく制御するには,
「木の描画」を参照するとよい:
非常に大きなグラフの描画をよりよくする
デフォルト設定でも非常によいパフォーマンスが得られるが,特定のタスクに対して特別なオプションの組合せを選ぶことで,さらに描画スピードを上げたり,メモリ使用量を減らしたりすることができる.例えば,スピードおよび/またはメモリ使用量は,少ない反復回数,小さい推定距離,低い許容誤差を使うと向上する.これらの設定は質を下げる傾向があるが,それでも妥協できる範囲のものである.
粗くする方法の枠組みに基づいた最大独立頂点集合は,より高速であることが多く,また,メモリ消費量も少なくレイアウトの品質もよい:
反復回数を30に減らすと,結果はより速く得られる:
推定距離を2に,反復回数を40回に指定してもデフォルトより速い:
さらに反復回数を20回に減らすと,はるかに速くなる:
"HighDimensionalEmbedding"は最速のメソッドであることが多いが,画質は劣ることが多い:
比較してみる.
"SpringEmbedding"は最も遅いメソッドであるが,直交する線を使ったメッシュが描ける唯一のメソッドである:
大腸菌転写ネットワーク
セル内の遺伝子式を制御する転写規則ネットワークのグラフ表現において,ノード(頂点)はオペロンであり,同じmRNAに転写された1つ以上の遺伝子である.グラフの辺は,転写因子をエンコードするオペロンから,それが直接支配するオペロンへと向いている[1].
データ
これは規則として記述されたネットワーク[2]である.
ネットワークの描画
ネットワークは多数の要素から構成される.マウスを頂点上に置くと,ラベルが見られる:
プロテイン:オキシドレダクターゼ
データ形式[4]を使ってオキシドレダクターゼプロテイン[3]をプロットする:
ソーシャルネットワーク
グラフの描画は,社会構造を可視化するパワフルなツールである.
語やテキストからのグラフ
次は,すべて「din」で始まる語のネットワークである.各語に2つの最も近くにある語があり,それぞれが該当語と辺で結ばれている:
単語の中のそれぞれの文字と,同じ単語のその文字の次の文字とをつないだグラフを生成する:
トーラス
[1] Milo, R., S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. "Network Motifs: Simple Building Blocks of Complex Networks." Science 298, no. 5594 (2002): 824–827.
[2] Alon, U. "Collection of Complex Networks." Uri Alon Homepage 2007.
[3] Milo, R., S. Itzkovitz, N. Kashtan, et al. "Superfamilies of Designed and Evolved Networks." Science 303, no. 5663 (2004): 1538–1542.
[4] Alon, U. "1AORInter." network Motifs 2007.
[5] National Institute of Standards and Technology. "DWA512: Square Dielectric Waveguide." Matrix Market 2007.
[6] Freivalds, K., U. Dogrusoz, and P. Kikusts, "Disconnected Graph Layout and the Polyomino Packing Approach." Lecture Notes in Computer Science: Revised Papers from the 9th International Symposium on Graph Drawing 2265 (2001): 378–391.
[7] Hu, Y. F. "Graph Drawing of Square Matrices from University of Florida Sparse Matrix Collection." (2007).
[8] Hu, Y. F. "Efficient, High-Quality Force-Directed Graph Drawing." The Mathematica Journal 10, no. 1 (2006): 37–71.