图的符号特征值与符号图谱 我们首先从 符号图 的基本定义开始。符号图 \( G^\sigma = (V, E, \sigma) \) 是在一个普通无向图 \( G=(V,E) \) 的基础上，为每条边赋予一个符号（+1 或 -1）的函数 \( \sigma: E \to \{+1, -1\} \)。正边通常表示友好、支持、吸引的关系，负边则表示敌对、反对、排斥的关系。这个概念在社会网络分析、物理自旋系统、生物化学网络等领域有广泛应用。 接下来，我们需要一个代数工具来描述符号图。 符号邻接矩阵 \( A_ \sigma \) 是最常用的表示，其定义与普通邻接矩阵类似： \[ (A_ \sigma)_ {ij} = \begin{cases} \sigma(ij), & \text{如果 } ij \in E, \\ 0, & \text{否则}. \end{cases} \] 这是一个实对称矩阵，因此它的所有特征值都是实数。这些特征值按非增顺序排列 \( \lambda_ 1 \ge \lambda_ 2 \ge \dots \ge \lambda_ n \)，就构成了符号图 \( G^\sigma \) 的 谱 。这个谱与底层图 \( G \) 的谱（即 \( A \) 的特征值）在数值和性质上通常有显著差异，因为边的符号信息被编码了进来。 符号图谱理论的一个核心关注点是 符号特征值 的极值与图的结构性质之间的关系。例如，符号图的最大特征值 \( \lambda_ 1(A_ \sigma) \) 满足柯西交错定理，并且其上界与底层图的最大度有关，但符号的引入使得极值情况更为复杂。一个有趣的结构是 平衡性 ：如果一个符号图的所有圈中，负边的数量都是偶数，则该图是平衡的。平衡的符号图在结构上等价于其所有负边可以通过顶点集的二部划分“切换”为正边，这对应着谱的性质：一个符号图是平衡的，当且仅当其谱与某个普通图（即将所有边视为正）的谱完全相同。因此，不平衡符号图的谱才携带了独特的“符号”信息。 更深一层，我们可以研究 最小特征值 \( \lambda_ n(A_ \sigma) \) 的性质。在普通图中，最小特征值与图的二部性质紧密相关（连通图是二部图当且仅当谱关于原点对称）。在符号图中，最小特征值与符号的“摩擦”或“挫败”程度有关。一个重要的概念是 最小特征值的下界 问题。通过选择适当的符号函数 \( \sigma \)，可以最大化或最小化 \( \lambda_ n \)。寻找使得 \( \lambda_ n \) 最大（即最靠近0）的符号赋值，与图的结构平衡性和“最小挫败”问题相关；而寻找使得 \( \lambda_ n \) 最小（即最负）的符号赋值，则与图的 二部性 和某些极值组合问题相联系。这个最小可能的最小特征值，被称为图的 最小可能特征值 ，是图本身的一个组合不变量。 最后，我们探讨符号图谱理论的一个前沿方向： 符号拉普拉斯矩阵 。与普通图类似，符号拉普拉斯矩阵定义为 \( L_ \sigma = D - A_ \sigma \)，其中 \( D \) 是度对角矩阵。由于其半正定性（即使有负边，\( L_ \sigma \) 仍然是半正定矩阵，这是符号图的一个优美性质），它在符号图聚类和社区发现中非常有用。符号拉普拉斯矩阵的谱（特别是其最小非零特征值，即代数连通性）衡量了符号图的“连通强度”，同时考虑了正边的连接作用和负边的分离作用，为分析具有对抗关系的网络提供了强大的数学工具。