代数连通度
图的代数连通度（algebraic connectivity）是的拉普拉斯矩阵的第二小的特征值（重特征值要重复计算）。[1]这个特征值大于0当且仅当是连通图。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。
性质
[编辑]图的代数连通度大于0当且仅当是连通图。而且，图的代数连通度的值不大于（顶点）连通度。[2]设一个连通图有个顶点且直径为，则代数连通度的一个下界是，[3]而且根据Brendan McKay的一个结果这个下界可以改进为。[4]对于上图中的例子，。
不像传统的连通度，代数连通度除了与顶点的连接方式有关以外，还与顶点的个数有关。对随机图，代数连通度随顶点数增大而减小，随平均度的增大而增大。[5]
代数连通度的具体定义依赖于所使用的拉普拉斯矩阵的类型。金芳蓉使用一种重新标度的拉普拉斯矩阵，消除了对顶点数的依赖，所以上下界有所不同。[6]
拉普拉斯矩阵自然地出现在网络上的同步模型中，例如藏本模型，因而代数连通度标志了网络达到同步的容易程度。[7]也可以使用其他度量，例如平均距离（特征路径长度），[8]实际上代数连通度与平均距离（的倒数）密切相关。[4]
Fiedler向量
[编辑]代数连通度的相关理论最早由Miroslav Fiedler提出。[9][10]为了纪念他，与代数连通度对应的特征向量命名为Fiedler向量。Fieldler向量可用于图的划分。
用Fiedler向量对图进行划分
[编辑]以首段中的图为例，Fiedler向量为(0.415, 0.309, 0.069, -0.221, 0.221, -0.794)。负值对应连通程度很差的点6，及其相邻的节点4；而正值对应其他顶点。因此可以根据Fiedler向量中的符号把图分成两部分：{1, 2, 3, 5}与{4, 6}。另外，值0.069非常接近0，可以单独成为一类，这样就把图分成三部分：{1, 2, 5}, {3}, {4, 6}。
另见
[编辑]参考资料
[编辑]- ^ Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.
- ^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 314.
- ^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 571.
- ^ 4.0 4.1 Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.
- ^ Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.
- ^ F. Chung. Spectral Graph Theory, Providence, RI: Amer. Math. Soc., 1997.[1]
- ^ Tiago Pereira, Stability of Synchronized Motion in Complex Networks, arXiv:1112.2297v1, 2011.
- ^ D. Watts, Six Degrees: The Science of a Connected Age, Vintage, 2003.
- ^ M. Fiedler. "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98) (1973), 298–305.
- ^ M. Fiedler. "Laplacian of graphs and algebraic connectivity", Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publications 25(1) (1989), 57–70.