グラフとネットワークアルゴリズム

有向および無向グラフ、ネットワーク解析

グラフは、ネットワークの接続をモデル化し、さまざまな物理学、生物学および情報システムに幅広く適用できます。グラフを使用して、脳内のニューロン、航空路の飛行パターン、その他多くのものをモデル化できます。グラフの構造は、「ノード」と「エッジ」で構成されています。各ノードはエンティティを表し、各エッジは 2 つのノード間の接続を表します。詳細は、有向および無向グラフを参照してください。

Example plots of undirected and directed graphs

関数

すべて展開する

構築

`graph`	無向エッジをもつグラフ
`digraph`	有向エッジをもつグラフ

ノードとエッジの変更

`addnode`	新しいノードをグラフに追加
`rmnode`	グラフからノードを削除
`addedge`	新しいエッジをグラフに追加
`rmedge`	グラフからエッジを削除
`flipedge`	エッジの方向の反転
`numnodes`	グラフのノード数
`numedges`	グラフエッジの数
`findnode`	グラフ内のノードを検出
`findedge`	グラフ内のエッジを検出
`edgecount`	2 つのノード間のエッジ数
`reordernodes`	グラフノードの並べ替え
`subgraph`	部分グラフの抽出

構造の解析

`centrality`	ノードの重要度を測定
`conncomp`	グラフの連結要素
`biconncomp`	グラフの 2 重連結要素
`condensation`	グラフの縮合
`bctree`	ブロックカット木グラフ
`toposort`	有向非循環グラフのトポロジカル順序
`isdag`	グラフが非循環かどうかの判定
`transreduction`	推移還元
`transclosure`	推移閉包
`isisomorphic`	2 つのグラフが準同型であるかどうかを判別
`isomorphism`	2 つのグラフ間の同型を計算
`ismultigraph`	グラフに複数のエッジがあるかどうかを判別
`simplify`	多重グラフを単純グラフに縮小

トラバーサル、最短経路および循環

`bfsearch`	グラフの幅優先検索
`dfsearch`	グラフの深さ優先検索
`shortestpath`	2 つの単一ノード間の最短経路
`shortestpathtree`	ノードからの最短経路木
`distances`	すべてのノードペアの最短経路の距離
`allpaths`	2 つのグラフノード間のすべての経路の検出 (R2021a 以降)
`maxflow`	グラフの最大フロー
`minspantree`	グラフの最小全域木
`hascycles`	グラフに循環があるかどうかを判別 (R2021a 以降)
`allcycles`	グラフ内のすべての循環の検出 (R2021a 以降)
`cyclebasis`	Fundamental cycle basis of graph (R2021a 以降)

行列表現

`adjacency`	グラフの隣接行列
`incidence`	グラフの接続行列
`laplacian`	グラフのラプラシアン行列

ノード情報

`degree`	グラフノードの次数
`neighbors`	グラフノードの隣接ノード
`nearest`	半径内の最近傍
`indegree`	ノードの入次数
`outdegree`	ノードの出次数
`predecessors`	先行ノード
`successors`	後続ノード
`inedges`	ノードの入方向エッジ
`outedges`	ノードからの出方向のエッジ

可視化

`plot`	グラフのノードとエッジをプロット
`labeledge`	グラフエッジにラベルを付ける
`labelnode`	グラフノードにラベルを付ける
`layout`	グラフプロットのレイアウトを変更
`highlight`	プロットしたグラフのノードおよびエッジを強調表示

オブジェクト

GraphPlot 有向グラフと無向グラフのグラフプロット

プロパティ

GraphPlot のプロパティ

グラフプロットの外観と動作

トピック

有向および無向グラフ
有向グラフおよび無向グラフの紹介。
グラフと行列
この例では、スパース行列の適用を示してグラフと行列の関係について説明します。
既存グラフのノードとエッジの変更
この例では、addedge、rmedge、addnode、rmnode、findedge、findnode および subgraph の各関数を使用して graph または digraph オブジェクト内のノードやエッジにアクセスし、それらを変更する方法を示します。
グラフのノード名、エッジの重みおよび他の属性の追加
この例では、graph と digraph を使用して作成したグラフ内のノードとエッジに属性を追加する方法を示します。
グラフのプロットおよびカスタマイズ
この例では、グラフをプロットしたうえで表示をカスタマイズし、グラフのノードとエッジにラベルや強調表示を追加する方法を示します。
グラフのノードとエッジにラベルを付ける
この例では、グラフのノードとエッジのラベルを追加およびカスタマイズする方法を示します。
グラフプロットデータヒントに対するノードプロパティの追加
この例では、GraphPlot データヒントをカスタマイズして、グラフの追加ノードプロパティを表示する方法を説明します。
幅優先探索と深さ優先探索の可視化
この例では、グラフのノードとエッジを強調表示することにより bfsearch と dfsearch の結果を可視化する関数の定義方法を示します。

注目の例

ワッツ・ストロガッツのスモールワールドグラフのモデル作成

この例では、ワッツ・ストロガッツのスモールワールドグラフを作成し、解析する方法を示します。ワッツ・ストロガッツのモデルは、クラスタリングや短い平均経路長など、スモールワールドネットワークのプロパティをもつランダムグラフです。

スクリプトを開く

PageRank アルゴリズムを使用した Web サイトのランク付け

この例では、PageRank アルゴリズムを使用して Web サイトの集まりにランクを付ける方法を示します。PageRank アルゴリズムは元々検索エンジンの結果をランク付けするよう設計されたものですが、より広範の多くの異なるタイプのグラフでノードに対して適用することもできます。PageRank のスコアは、各グラフノードが他のノードとどのように結合しているかに基づき、その相対的な重要性を示します。