代数的接続性

グラフGの代数的連結性（ミロスラフ・フィードラーにちなんでフィードラー値またはフィードラー固有値とも呼ばれる）は、 Gのラプラシアン行列の2番目に小さい固有値（複数の固有値を個別に数える）である。^{[1]この固有値は、} G が連結グラフである場合に限り、0より大きくなる。これは、ラプラシアンにおいて固有値として0が現れる回数がグラフ内の連結成分の数であるという事実の帰結である。この値の大きさは、グラフ全体の連結度を反映している。これは、ネットワークの堅牢性と同期可能性の分析に使用されている。

非負の重みを持つ無向グラフの代数的連結性。不等式が厳密となるのは、G が連結されている場合のみ。しかし、一般の有向グラフでは、G が連結グラフであっても、代数的連結性が負になることがあります。^[2]さらに、代数的連結性の値は、グラフが完全でない限り、グラフの従来の（頂点）連結性によって上方に制限されます（完全グラフK _nの代数的連結性はその位数nです）。^[3] 非負の辺の重みを持つ無向連結グラフの頂点数がnで、直径がDの場合、代数的連結性は によって下方に制限されることも知られています。 ^{[4]また、実際（} Brendan McKayによる結果では） によっても制限されます。^[5]上記の6つのノードを持つグラフ（n=6、D=3）の場合、これらの境界値は、4/18 = 0.222 ≤ 代数的接続性 0.722 ≤ 接続性 1 となります。 ${\displaystyle a(G)\geq 0}$${\displaystyle {\text{代数的連結性}}\leq {\text{連結性}}}$ ${\displaystyle {\text{代数的連結性}}\geq {\frac {1}{nD}}}$${\displaystyle {\frac {4}{nD}}}$

グラフの接続性が局所的な構成によって定義され、その構成を削除するとグラフが切断される従来のグラフ接続性とは異なり、代数的接続性は頂点のグローバルな数と頂点の接続方法に依存します。ランダムグラフでは、代数的接続性は頂点の数とともに減少し、平均次数とともに増加します。^[6]

代数的連結性の正確な定義は、使用されるラプラシアンの種類によって異なります。Fan Chungは、頂点の数への依存を排除​​したラプラシアンの再スケール版を使用した広範な理論を開発しました。そのため、境界は多少異なります。^[7]

倉本モデルのようなネットワーク上の同期モデルでは、ラプラシアン行列が自然に生じるため、代数的連結性はネットワークがどれだけ容易に同期するかの指標となる。^[8] 平均距離（特徴的な経路長）などの他の尺度も使用可能であり、^[9]実際、代数的連結性は平均距離（の逆数）と密接に関連している。^[5]

代数的連結性は、等周数などの他の連結性属性にも関連しており、等周数は代数的連結性の半分以下に制限されます。^[10]

代数的連結性に関する最初の理論は、ミロスラフ・フィードラーによって提唱されました。^{[11] [12]}彼に敬意を表して、代数的連結性に関連する固有ベクトルはフィードラーベクトルと名付けられました。フィードラーベクトルはグラフを 分割するために使用できます。

導入部のグラフ例では、フィードラー ベクトルは です。負の値は、接続が不十分な頂点 6 と、隣接する連結点、頂点 4 に関連付けられ、正の値はその他の頂点に関連付けられます。したがって、フィードラー ベクトルの値の符号を使用して、このグラフを 2 つの要素に分割できます。または、値 0.069 (ゼロに近い) を独自のクラスに配置して、グラフを 3 つの要素に分割するか、図に示すように、他の分割 に移動することもできます。フィードラー ベクトルの要素の 2 乗値は、ベクトルが正規化されているため合計が 1 になりますが、これは、対応するデータ ポイントが符号ベースの分割に割り当てられる確率として解釈できます。 ${\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}$${\textstyle \{1,2,3,5\},\{4,6\}}$${\textstyle \{1,2,5\},\{3\},\{4,6\}}$${\textstyle \{1,2,5\},\{3,4,6\}}$

• 連結性（グラフ理論）
• グラフプロパティ