グラフユーティリティパッケージ

グラフユーティリティパッケージには，グラフ理論の応用に便利な関数が多数含まれている．

グラフユーティリティパッケージに含まれる関数

グラフは，規則のリストあるいはその隣接行列で表すことができる．また，Combinatorica パッケージ形式のグラフもサポートされている．

AdjacencyMatrix

グラフの隣接行列を求める

グラフユーティリティパッケージでサポートされる形式のグラフが与えられると，AdjacencyMatrixはそのグラフを表す行列を返す．

グラフ g は規則のリスト，隣接行列，任意グラフの Combinatorica 表現で指定することができる．

SparseArrayオブジェクトの行と列は，VertexList[g]により返される順で頂点に対応する．

Bicomponents

二重連結成分を見付ける

Bicomponents[g]は，無向グラフ g の二重連結成分すべてのリストを返す．

頂点 v とすべての辺を削除するとグラフ g が連結でなくなる場合，頂点 v はグラフ g の切断点であるという．切断点がないグラフは二重連結である．二重連結成分とは切断点を持たない最大の部分グラフである．

ClosenessCentrality

近接中心性を見付ける

頂点 u の近接中心性は，u から他のすべての頂点への距離の総和の逆数として定義される．非連結グラフの頂点の近接中心性は，その頂点が属する成分の近接中心性に基づく．

ClosenessCentralityのオプション

ClosenessCentrality のオプション

Weighted

Weightedオプションは，距離の計算で辺の重みを考慮するかどうかを指定する．可能な値は True（デフォルト）かFalseである．Weighted->Falseでは，辺は単位重みを持つものとされる．

Normalize

Normalizeオプションは，出力が最大中心性1となるよう正規化するかどうかを指定する．可能な値はTrueかFalse（デフォルト）である．

以下で3つの頂点を持つ完全グラフの近接中心性を計算する．任意の頂点から他の頂点までの距離の総和は2なので，各頂点に対する近接性はである．

CommunityModularity，CommunityStructureAssignment，CommunityStructurePartition

コミュニティ構造を見付け，評価する関数

CommunityStructurePartitionはグラフをコミュニティに分割する．この分割では，コミュニティ間よりもコミュニティ内の辺の方が密になるよう，頂点がコミュニティにグループ分けされる． CommunityStructureAssignmentは結果を割当てとして与える．

コミュニティ構造を見付けるアルゴリズム

関係を示す情報の多くは，グラフとして表すことができる．グラフの特徴の一つは，コミュニティ構造である．これはグループ間よりもグループ内の辺の密度の方が大きくなるように頂点をグループ分けすることである．グラフのコミュニティ構造の発見と解析は多くの分野で有用である．例えば，ソフトウェア工学では，相互関係のあるルーチンが同じディレクトリに入るよう，ディレクトリ内のソースコードをグループ分けする必要がある場合がある．ソーシャルネットワークでは， 結びつきの強いコミュニティを形成する友達のグループを見付ける必要がある場合がある．また，並列計算では，関係の深いタスクが同じプロセッサ上に置かれるよう，計算タスクを分割することが望ましい．

ネットワーク内のコミュニティ構造を認識するアルゴリズムは多数存在する．そのひとつの例が[16]のアルゴリズムである．その鍵となる概念はコミュニティのモジュールと呼ばれる数量である．関心のあるグラフが であり，頂点集合 がそれぞれの部分集合が1つずつのコミュニティに属するような 個の部分集合 に分割されるとする．そのとき，この分割によるコミュニティのモジュール はと定義することができる．

ここで は両端がコミュニティ にある辺の数の百分率を， はコミュニティ から始まる辺の百分率である．換言すると，

と

ということになる．明らかに が成り立つ．通常， のランダム分割では はゼロに近く， の大きい正の値となるような の分割は大きなコミュニティ構造を示す．

従って，[16]のアルゴリズムは，それぞれの頂点をそれ自身のコミュニティに割り当てることにより開始され，2つのコミュニティを1つに統合した結果の の変化を計算する．その後 で最も大きい正の変化を与える2つのコミュニティを統合する．このプロセスは統合されたネットワークで繰り返される．最大の変化が負になったらこのプロセスは終了する．

CommunityStructurePartition，CommunityStructureAssignment，CommunityModularityのWeightedオプション

次のオプションを使うことができる．

CommunityStructurePartition，CommunityStructureAssignment，CommunityModularityのオプション

Weightedオプションは，辺の重みを考慮に入れるかどうかを指定する．このオプションに可能な値はTrueかFalse（デフォルト）である．

EdgeList

辺のリストを見付ける

ExpressionTreePlot

式の木をプロットする関数

ExpressionTreePlotは式の木をプロットする．これはTreePlotと同じオプションを持つ．

GraphCoordinatesとGraphCoordinates3D

座標を返すグラフ描画関数

GraphCoordinatesは，グラフ描画アルゴリズムで計算された頂点座標を返す．これは，グラフを描画するよりも頂点座標が必要であるような場合，または同じレイアウトを異なるスタイルで繰り返し描画する必要がある場合に便利である．

GraphCoordinatesはGraphPlotと同じオプションを取る．

GraphCoordinatesは頂点の位置だけを返すので，LayeredGraphPlotに使われた場合，多重辺や自己ループは描画するが曲線の辺は再生されない．

GraphCoordinatesとGraphCoordinates3Dのオプション

GraphCoordinatesとGraphCoordinates3DはそれぞれGraphPlot，GraphPlot3Dと同じオプションを取る．

GraphDistance，GraphPath，GraphDistanceMatrix

最短距離，最短経路，および全点対最短距離・経路を見付ける

GraphDistanceは1つの頂点から別の頂点までのグラフ距離を返す．i から j までに経路が存在しない場合は，Infinityが返される．デフォルトで，各辺の重みは1とされる．

GraphPathとGraphDistanceMatrixは，それぞれ最短経路および全点対最短経路を見付ける．

最短経路のアルゴリズム

以下では は辺 の重み， は頂点 から頂点 への最短経路の現在の推定の長さとする．

単一始点最短経路アルゴリズム

単一始点最短経路アルゴリズムは，1つの頂点 から他すべての頂点への最短経路を求める．

ダイクストラ(Dijkstra)法は，辺の重みが非負であるものと仮定する．

以下のように仮定する：

： までの最短経路がすでに見付かっている頂点の集合

： が「触れる」が に属さず，ヒープに保存される頂点の集合

この場合，アルゴリズムは次のようになる：

1. において最小の の値を持つ頂点 を選ぶ．このステップは二分ヒープあるいはフィボナッチヒープによる計算量 を伴い，すべての場合で 回繰り返される．

2. 頂点 が にない場合，頂点 を に置き， の隣接頂点 すべてを に挿入する． ならば，が設定され，ヒープが更新される．ヒープへの挿入および更新のすべては，二分ヒープによる計算量 ，フィボナッチヒープによる計算量 があり，すべてにおいて の更新操作との挿入が必要である．

全体的な計算量は，二分ヒープを持つ およびフィボナッチヒープを持つ である．

ベルマンフォード(Bellman–Ford)アルゴリズムは，辺の重みが負の場合でも使用することができる． ならば と設定され，各辺 を通してループすることにより動作する．このループは回実行されるので，ベルマンフォードアルゴリズムは計算量 であり，ダイクストラ法よりもかなり大きい．従って，これはグラフに負の重みが含まれるときだけ使用される．このアルゴリズムは負の閉路が検出できる．

全点対最短経路アルゴリズム

全点対最短経路アルゴリズムはすべての頂点対の間の最短経路を探す．

ワーシャル・フロイド(Floyd–Warshall)法では，隣接する頂点間の距離は辺の重みに設定され，それ以外のすべての距離は最初に設定される．次にすべての頂点対 にループし， ならば緩み，に設定される．これにより任意の反復 において，距離 は頂点 と の間の最短距離を表し，頂点 だけを通過するようになる．このアルゴリズムの計算量は である．これは負の重みでも使用できるが，負の重みの閉路は検出しない．

辺の重みが非負ならば，単一始点最短経路問題では，各頂点に繰り返しダイクストラ法を適用することができる．この計算量は二分ヒープを伴う ，およびフィボナッチヒープを伴う である．

辺の重みが負ならば，ダイクストラ法を直接適用することはできない．まずジョンソン法で， ならば となるように値 をすべての頂点 に関連付けることによりすべての辺の重みを正にする．辺の重みはその後 で修正される．

辺の重みを変更するためには，重み0ですべての頂点にリンクされる仮想頂点 が加えられる．すべての頂点 に対して， は から までの距離として定義される．したがって，すべての辺 に対して が成り立つ．そうでない場合は は真の最短経路の長さではない．よって である．

この修正により最短経路は変更されないので，ダイクストラ法を重みの修正されたグラフに適用することができる．その後，距離は によりもとに戻される．

辺の重みが非負の場合，ジョンソン法はダイクストラ法と同じ計算量を持つ．そうでない場合は，ベルマンフォードアルゴリズムと同じ計算量である．

GraphPath，GraphDistanceMatrix，GraphDistanceのオプション

GraphPath，GraphDistanceMatrixのオプション

GraphDistanceのオプション

Method

オプションMethodは最短経路を見付けるのに使用するアルゴリズムを指定する．デフォルトでは，MethodはAutomatic，つまりジョンソン法に設定されている．このオプションに可能な他の値には"BellmanFord"，"Dijkstra"，"FloydWarshall"，"Johnson"がある．

Weighted

オプションWeightedは，最短経路を見付ける場合に辺の重みを考慮に入れるかどうかを指定する．可能な値にはTrueとFalseがある．

GraphEdit

インタラクティブなグラフの編集

GraphEditは J/Link アプリケーションである．この関数を実行すると，Javaウィンドウが開く．これで新規グラフを生成することも既存のグラフを編集することもでき，結果のグラフを Mathematica に戻すことができる．

グラフ g は規則のリスト，隣接行列，グラフの Combinatorica 表現で指定することができる．

頂点および辺はマウスをクリックアンドドラッグして加えることができる．頂点は「Drawing mode」を「Move」に設定し，その頂点上でマウスをドラッグすると動かすことができる．また，「Drawing mode」を「Delete」に設定し，頂点をクリックすると，その頂点が削除される．

GraphEditウィンドウでCtrlキーを押したままで頂点をクリックする（マウスの主ボタンを使って）と，頂点ラベルが編集できる．

ウィンドウを閉じると，グラフの描画，規則のリストとしてのグラフの表現，座標，頂点ラベルが返される．

HamiltonianCyclesとFindHamiltonianCycle

ハミルトン閉路を見付ける

ハミルトン閉路が存在しない場合，HamiltonianCyclesおよびFindHamiltonianCycleはどちらも空リストを返す．どちらも入力グラフを無向グラフとみなす．

HamiltonianCycles[g,All]はすべてのハミルトン閉路を返す．

ハミルトン閉路を見付けるためのアルゴリズム

グラフのハミルトン閉路を見付けることはNP困難問題である．

HamiltonianCyclesでは深さ優先探索法が使われる．これは，大きいグラフのハミルトン閉路をすべて見付ける場合，かなりの時間がかかる場合がある．

FindHamiltonianCycleではハミルトン閉路を見付けるのにAngluin & Valiantのヒューリスティックスを使う．1つの始点からなる経路が構築される．このアルゴリズムは現行の経路の終点から始め，隣接頂点をランダムに加えることにより貪欲に作用する．隣接頂点がすでに経路上にある場合は，「回転」されて，経路の部分の方向が逆行し新しい経路が構築される．その後経路上のすべての辺がグラフから削除され，隣接頂点がなくなるまでこのプロセスが続行する．閉路が見付からない場合は，別の始点が使われ閉路を見付けようとする．これはすべての頂点が始点として使われるまで続く．これで1回の反復となる．

FindHamiltonianCycleのオプション

FindHamiltonianCycleのオプション

MaxIterations

オプションMaxIterationsは試行の最大反復回数を指定する．可能な値は正の機械整数である．

RandomSeed

オプションRandomSeedは選ばれたランダムな隣接頂点で使われれるランダムシードを指定する．可能な値は機械整数である．

LineScaledCoordinate

ポリライン上の点の座標を見付ける

LineScaledCoordinateはGraphPlot，GraphPlot3D，LayeredGraphPlotのオプションEdgeRenderingFunctionとともによく用いられ，グラフの辺にテキストや画像を加える．

MaximalBipartiteMatching

二部グラフの最大マッチングを見付ける

MaximalBipartiteMatchingは二部グラフの2つの頂点集合間の隣接しない辺の最大集合を与える．

m×n 行列により表される二部グラフは，行および列の頂点集合r={1,2,…,m}と c={1,2,…,n}から構成され，行列要素が g_ij≠0ならば頂点 i∈r と j∈c は連結されている．

規則のリスト{i₁->j₁,i₂->j₂,…}で表現される二部グラフは，頂点集合 r=Union[{i₁,i₂,…}]と c=Union[{j₁,j₂,…}]で構成され，規則 i->j が規則のリストに含まれているならば頂点 i∈r と j∈c は連結されている．

MaximalBipartiteMatchingは頂点ペアのリスト{{i₁,j₁},…,{i_k,j_k}}を返す．ここでペアの数 k はどちらの頂点集合よりも小さい．

応用

MaximalBipartititeMatchingは可能な限り多くの要素を疎行列の対角上で置換するために使うことができる．

MaximalBipartititeMatchingは疎行列の構造的ランクを見付けるために使うことができる．行列の構造的ランクとは，行列の二部グラフの最大マッチングにおける要素の数をいう．これは行列の数値ランクの上限である．行列は，対角にゼロ要素がないように置換できるなら，構造的完全ランクという．

MaximalIndependentEdgeSet

最大独立辺集合を見付ける

MaximalIndependentEdgeSetは g の非隣接辺のペアの近似的最大集合を与える．グラフの最大独立辺集合は最大マッチングとも呼ばれる．

MaximalIndependentEdgeSetのオプション

MaximalIndependentEdgeSet のオプション

Weighted

Weightedオプションは，最大独立辺集合を構成する場合に，重みの大きい辺を優先するかどうかを指定する．可能な値はTrue（デフォルト）かFalseである．

MaximalIndependentVertexSet

最大独立頂点集合を見付ける

MaximalIndependentVertexSetは，1辺に2つの頂点がないような頂点の近似最大集合を与える．入力は無向グラフとして扱われる．

ベクトルの長さ w は g の頂点の数と同じでなければならない．

MinCut

MinCut[g]

辺の切断をほぼ最小に抑えて，無向グラフ g を 個の部分に分割する

辺切断の最小化

MinCutは入力を無向グラフとして扱い，各部分がほぼ同数の頂点を持ち，その部分（辺のセパレータとして知られる）間の辺の数が最小となるように，頂点を 個の部分に分割する．

応用

MinCut関数の最も重要な使用法のひとつは，辺の分断数が最小となるようにグラフまたはメッシュを分割し，ほぼ同じ大きさの部分領域に分割することである．これは，各プロセッサが1つのサブドメインで動作し，プロセッサ間のオーバーヘッドが最小限に抑えられなければならい並列計算などの分野で重要である．通信オーバーヘッドは辺の分断数に比例するため，分割による辺の切断数は最小限でなければならないのである．

並列有限要素構造解析が，三次元構造で実行されるとする．構造をモデル化するために不規則なメッシュが生成される．

MinimumBandwidthOrdering

グラフと行列のバンド幅を最小化する順序を見付ける

頂点順序 のグラフ では，グラフのバンド幅は以下のように定義される．

ここで は から へのマッピングである．

行列 のバンド幅は

と定義される．行列 では，バンド幅は

と定義される．対称行列の場合，エンベロプの大きさは

と定義される．これは各行の最初の要素から対角要素の位置までの距離の和である．1行に対角要素がない，または対角の前の要素がない場合は，距離はゼロとされる．

行列のプロファイルは，単にエンベロプの大きさと行列の大きさを足したものである．

行列をグラフとしてプロットする．順序の早い頂点を青，遅いものを赤で彩色する．対称行列では，行と列の順序は同じ()である．

バンド幅とエンベロプサイズを最小にするためのアルゴリズム

グラフの最小バンド幅順序を見付ける問題はNP完全問題であることが証明されている．したがって，実践的なアルゴリズムはすべてヒューリスティックであり，近似的な最適順序を見付けることを目標とするものである．

基本的アルゴリズム

連結無向グラフの場合，RCM（逆Cuthill–McKee）法[8]はグラフの擬似直径を見付けることから開始する．次に直径の一方の端 から頂点が順序付けされ，多数のレベル集合を形成する．ここで同じレベル集合内の頂点は までの距離が等しい．同じレベル集合内では，可能な限り最低の順序の頂点に連結された頂点が優先される．一旦すべての頂点に順序が付いたら，その順序が逆にされる．順序を逆にすることがバンド幅に与える影響はほとんどないが，順序付けが疎行列の因数分解に使われる場合，順序を逆にすることで記入要素が減ることが多い[13]ということが分かっている．ここでの実装では，変形アルゴリズムのRCMD法を提供する．これは同じ最下位の頂点に接続されている頂点間のつながりを，最低次数の頂点に先に順序を付けることにより破るものである．

RCMあるいはRCMDの結果はさらに精錬してよいものにすることができる．これには[9, 12]のノード重心法と山登り法が使える．山登り法では，グラフのバンド幅と同じバンド幅を持つ重要頂点が見付けられ，その頂点の順序とそれ以外の頂点の順序とを入れ替えようとする．これは重要頂点の数もバンド幅も減少できなくなるまで続けられる．ノード重心法では，グラフのバンド幅に近いバンド幅を持つ準重要頂点が見付けられ，その順序および隣接頂点の順序の平均として新しい順序が計算される．それから頂点はソートされ並べ替えられる．ノード重心法の後には常に山登り法が実行される．山登り法による微調整，あるいはノード重心法と山登り法との組合せは，RefinementMethod->"HillClimbing"，RefinementMethod->"NodeCentroidHillClimbing"で指定することができる．

ノード重心法と山登り法は複数レベルの手順と組み合せることもできる．ここでは，もとのグラフからだんだん小さくなる一連のグラフが生成される．最小のグラフに対する最初の順序は，RCMあるいはRCMDを使って見付けることができる．もっと粗いグラフの順序は，細かいグラフへと補間され，ノード重心法と山登り法を使って微調整される．複数レベルのメソッドはRecursionMethod->"Multilevel"で選ぶことができる．

スローン(Sloan)法[10, 11]は，無向グラフの順序のエンベロプサイズを最小化することを目標とする．これはまず と のペアで形成されるグラフの擬似直径を見付ける．頂点は4つの互いに素なクラスに分類される．その4つとは，順序付き（すでに順序の付いているもの），アクティブ（1つ以上のアクティブな頂点に連結しているもの）， プリアクティブ（1つ以上のアクティブな頂点に連結しているが，順序の付いた頂点には連結していないもの），インアクティブ（順序付き，アクティブ，プリアクティブのいずれでもないもの）である．頂点は から優先順位が決まる．頂点 の優先順位は により与えられる．ここで， はもし次に の順序が付いたらアクティブになり，もし が現在プリアクティブならばプラス1になるプリアクティブおよびインアクティブの頂点数 である．また は と の間の距離，と は2つの正の重みである．このアルゴリズムは，アクティブおよびプリアクティブな頂点から優先順位の最も高い頂点を1つ選ぶことで動作する．一旦頂点が選ばれると，残りのアクティブおよびインアクティブな頂点の優先順位が更新される．最も優先順位の高い頂点を効率よく（ソートしないで）見付けるために，二分ヒープデータ構造が使われる．スローンアルゴリズムは，RCMアルゴリズムおよびその変形よりも大きいバンド幅ではあるが，小さいエンベロプサイズの順序を与える傾向がある．

非対称行列のアルゴリズム

グラフ g に対して，MinimumBandwidthOrderingは g の内在する無向グラフのバンド幅を最小化する頂点順序 を見付けようとする．しかし，[12]に従う次元 × の非対称行列 ではMinimumBandwidthOrderingは以下の対称行列

を使う．これは の行および列の二部グラフを表す． に対する順序がまず計算される．次にこれが の順序に変換される．順序 が のバンド幅を最小化するとすると， の行順序は 以下の の要素により与えられ，列順序は より大きい要素マイナス で与えられる．以下の通りである．

MinimumBandwidthOrderingのオプション

MinimumBandwidthOrdering のオプション

Method

オプションMethodはバンド幅あるいはエンベロプサイズを最小にするために使われるアルゴリズムを指定する．このオプションに可能な値はAutomatic，"RCM"，"RCMD"，"Sloan"である．デフォルトではMethodはAutomaticに設定されている．

次の例で，バンド幅減少アルゴリズムとエンベロプサイズ減少アルゴリズムとの差を示す．

RefinementMethod

RefinementMethodオプションは上記のメソッドのいずれか1つを適用した後に，バンド幅をさらに適切なものにするために使用する微調整メソッドを指定する．このオプションに可能な値は，Automatic（デフォルト），None，"HillClimbing"，"NodeCentroidHillClimbing"である．

RecursionMethod

RecursionMethodオプションは複数レベルのプロセスを適用するかどうかを指定する．このオプションに可能な値はNone（デフォルト）と"Multilevel"である．

適用

最小バンド幅順序付けは，数値計算のキャッシュパフォーマンスを最適化する場合にも適用される．例えば，疎行列とベクトルを掛け合せる場合，バンド幅を最小にするようあらかじめ行列に順序が付いていると，ベクトルの要素はランダムにアクセスされないため，キャッシュパフォーマンスが向上する．順序付けそのものに時間がかかるため，このキャッシュパフォーマンスの向上は，行列・ベクトル積の操作を何度も繰り返すときだけに有益である．

NeighborhoodSubgraph

近隣の部分グラフを見付ける

NeighborhoodVertices

近隣の頂点を見付ける

PageRanks，PageRankVector，LinkRanks，LinkRankMatrix

PageRanks関数とPageRankVector関数

PageRanksアルゴリズム

大雑把に言うと有向グラフの場合， から までの辺があるならば頂点 は頂点 とリンクしているインターネットを表すと仮定すると，頂点のページランクは，ランダムなインターネットサーファーがその頂点を訪れる確率である．

ランダムなサーファーが時間刻み でページ を訪れるとする．次のステップで，サーファーは同じ確率で の外近傍 の1つからノード をランダムに選ぶ．

ここでサーファーがシンク（出リンクのないノード）に捕まらないようグラフに修正を加える必要がある．出次数がゼロのノード と，それ自身を含むすべてのノードとをリンクするのである．この修正により以下が定義できる．

ページ のページランクは，サーファーが時間刻み でページ にいる確率として定義される．

行列 が，すべてのに対して項目値 を持ちが の出次数であるグラフと同じ構造であると定義する．ここでとすると， 番目の行の和は1である．ならば， を頂点の数としてその行のすべての項目を と設定することにより，行 を修正することができる．修正された行列 は

であり， である．ここで はのときに となる以外，すべての1の 次元の列ベクトル， は0の列ベクトルである．したがって はならば項目値 の行 を持ち，その他の行には項目値0である行列となる．

もう1つ修正が必要である． により与えられる有向グラフが強連結でないならば，サーファーは有向グラフの要素に捕らえられる．すべてのページが訪れられるようにするために，サーファーがページ を訪れるときに他のページをランダムに訪れるわずかな確率（転送確率）があるものと仮定する．要約すると，ノード からは，その 近傍を訪れる確率が ，それ自身を含むあらゆるノードを訪れる確率が である．ノード からはあらゆるノードを訪れる確率は となる．行列で言うと，ページランクベクトル は

を満足しなければならず，このとき

である． と表記するとページランク計算のタスクは， の固定点を見付けることである．

固定点計算は1のベクトルから開始して，反復的に実行される．ページランクの平均的な変更が許容誤差より小さいならば，プロセスは収束したと考えられる．最終結果は総和が となるようスケールされた，サーファーの確率の近似値である．

シンクを扱う別のモデルに，それをすべてのノードにそれぞれとリンクして削除するのではなく，それ自身にリンクするというものがある．このモデルでは，シンクから抜け出す唯一の方法は転送によるものとなる．サーファーがこのノードにとどまる確率は であり，ノードを訪れる確率は である．このモデルはオプションRemoveSinks->Falseで利用することができる．

PageRanksとPageRankVectorのオプション

以下のオプションを取ることができる．

PageRanksとPageRankVectorのオプション

Tolerance

Toleranceオプションはページランク計算のための反復アルゴリズムの収束許容度を指定する．平均の変更が許容誤差よりも小さいならば，反復プロセスは終了する．このオプションに可能な値はAutomaticまたは正の機械サイズの数である．

TeleportProbability

TeleportProbablityオプションは，インターネットサーファーが頂点の出リンクに従わず，ランダムにノードを訪れる確率を指定する．

このオプションに可能な値は，1より小さい正の機械サイズ数であり，デフォルト値は0.15である．これより小さい値であると，ページランクは，通常のインターネットサーファーの動作をより正確に反映したものとなる．しかし，ページランクを計算する反復プロセスの収束は遅くなる．

RemoveSinks

RemoveSinksオプションはシンク（出リンクがないノード）をすべてのノードとリンクして，シンクを削除するかどうかを指定する．可能な値はTrueとFalseであり，デフォルトはTrueである．

結果を理解するために，（PageRanksを使って）ノード のサーファーの確率が で，転送確率が であると仮定する．そのときRemoveSinksTrueでは，サーファーはノード1を訪れるが，シンクを削除した後にノード2から各ノードにリンクが加えられているためにノード2から（の確率）か，転送によりノード1自身から（の確率）か，転送によりノード2から（の確率）かのいずれかが考えられる．ここで が成り立つ．同様に，サーファーがノード2を訪れるとき，転送によりノード1から（の確率）か，リンクに従ってノード1から（の確率），シンクを削除した後に加わったリンクに従ってノード2から（の確率），転送によりノード2から（の確率）のいずれかがあり得る．したがって確率は以下の方程式を満足し，に正規化される．

のとき， に代入する．

PseudoDiameter

無向グラフの擬似直径を見付ける

グラフ測地線はグラフの2頂点間の最短経路である．グラフ直径は，グラフの測地線すべての中で最も長いものである． PseudoDiameterは近似グラフ直径を見付ける．

使用されるアルゴリズムは，頂点 u から始まり，u から最も遠い頂点 v を見付ける．このプロセスは v を新しい開始頂点として扱うことにより繰り返され，グラフ距離がそれ以上増加しなくなったら終了する．最後のレベル集合で，最小次数の頂点が最後の開始頂点 u として選ばれ，グラフ距離が増加できるかどうかを調べるために走査が行われる．このグラフ距離が擬似直径とされる．

グラフが非連結の場合，各連結成分に対する直径と頂点が返される．

PseudoDiameterのAggressiveオプション

PseudoDiameterのオプション

オプションAggressiveは最適グラフ直径を見付けるのに追加の試みが必要かどうかを指定する．可能な値はTrueかFalse（デフォルト）である．設定Aggressive->Trueでは，最後のレベル集合の各頂点からの走査が実行される．これにより大きい擬似直径が与えられることもある．

StrongComponentsとWeakComponents

強連結成分を求める

有向グラフにおける強連結成分とは，任意の2ノード間に経路が存在する頂点集合のことである．

StrongComponents[g]は，有向グラフ g の全強連結成分のリストを返す．

有向グラフの弱連結成分とは，頂点の各ペアでその頂点間に経路があるような頂点集合のことである．グラフ g は無向グラフと考えられる．

WeakComponents[g]は無向グラフ g の弱連結成分すべてのリストを返す．

応用

無向グラフの連結成分の数を求める

StrongComponentsを使って無向グラフ中に連結成分がいくつあるかを調べることができる．

規則のリストとして指定されたグラフは，まず対称化し，次にStrongComponentsを使ってその連結された成分を求めることができる．

行列をブロック三角形にする

StrongComponentsからの出力は，行列をブロック三角形に再編成するのに使うことができる．

ToCombinatoricaGraph

Combinatorica グラフオブジェクトへの変換

ToCombinatoricaGraphはグラフユーティリティパッケージで取ることのできるすべての形式のグラフを Combinatorica グラフオブジェクトに変換する．

ToCombinatoricaGraphのMethodオプション

ToCombinatoricaGraphのオプション

オプションMethodは，グラフをレイアウトするために使うメソッドを指定する．このため計算される座標は結果の Combinatorica グラフオブジェクトに埋め込まれる．可能な値はGraphPlotのMethodオプションの値と同じである．デフォルトはAutomaticで，GraphPlotのデフォルトメソッドを使う．しかし，入力が Combinatorica オブジェクトの場合は，オブジェクトの座標は変更されない．

VertexList

全頂点のリストを得る

VertexListはグラフ g の頂点のリストを返す．

規則のリストを使って指定されたグラフでは，頂点は最初に現れる順序で返される．

GraphCoordinates，PageRankVector等の関数はVertexListで与えられる順序で頂点に関する情報を返す．

参考文献

[1] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Englewood Cliffs, NJ: Prentice-Hall, 1999.

[2] T. M. J. Fruchterman and E. M. Reingold, "Graph Drawing by Force-Directed Placement," Software—Practice and Experience, 21(11), 1991 pp. 1129–1164.

[3] P. Eades, "A Heuristic for Graph Drawing," Congressus Numerantium, 42, 1984 pp. 149–160.

[4] N. Quinn and M. Breuer, "A Force-Directed Component Placement Procedure for Printed Circuit Boards," IEEE Transactions on Circuits and Systems, CAS-26(6), 1979 pp. 377–388.

[5] T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs," Information Processing Letters, 31(1), 1989 pp. 7–15.

[6] D. Harel and Y. Koren, "Graph Drawing by High-Dimensional Embedding," in Proceedings of 10 ^th Int. Symp. Graph Drawing (GD'02); Lecture Notes in Computer Science, Vol. 2528, London: Springer Verlag, 2002 pp. 207–219.

[7] C. Walshaw, "A Multilevel Algorithm for Force-Directed Graph-Drawing," Journal of Graph Algorithms and Applications, 7(3), 2003 pp. 253–285.

[8] E. Cuthill and J. McKee, "Reducing the Bandwidth of Sparse Symmetric Matrices," in Proceedings of the 24 ^th National Conference of ACM, New York: ACM Publications, 1969 pp. 157–172.

[9] A. Lim, B. Rodrigues, and F. Xiao, "A Centroid-Based Approach to Solve the Bandwidth Minimization Problem," in Proceedings of the 37 ^th Annual Hawaii International Conference on System Sciences (HICSS'04), Track 3, Vol. 3, Washington D.C.: IEEE Computer Society, 2004 p. 30075.1.

[10] S. T. Barnard, A. Pothen, and H. D. Simon, "A Spectral Algorithm for Envelope Reduction of Sparse Matrices," Journal of Numerical Linear Algebra with Applications, 2(4), 1995 pp. 311–334.

[11] S. Sloan, "A Fortran Program for Profile and Wavefront Reduction," International Journal for Numerical Methods in Engineering, 28(11), 1989 pp. 2651–2679.

[12] J. K. Reid and J. A. Scott, "Ordering Symmetric Sparse Matrices for Small Profile and Wavefront," International Journal for Numerical Methods in Engineering, 45(), 1999 pp. 1737–1755.

[13] J. A. George, "Computer Implementation of the Finite-Element Method," Report STAN CS-71-208, Ph.D. thesis, Department of Computer Science, Stanford University, Stanford, California, 1971.

[14] K. Sugiyama, S. Tagawa, and M. Toda, "Methods for Visual Understanding of Hierarchical Systems," IEEE Transactions on Systems, Man, and Cybernetics, 11(2), 1981 pp. 109–125.

[15] E. R. Gansner, E. Koutsofios, S. C. North and K.-P. Vo, "A Technique for Drawing Directed Graphs," Software Engineering, 19(3), 1993, 214–230.

[16] A. Clauset, "Finding Local Community Structure in Networks," Physical Review E, 72, 026132, 2005.

[17] Y. F. Hu, "Efficient, High-Quality Force-Directed Graph Drawing," The Mathematica Journal, 10(1), 2005 pp. 37–71.