论文标题
对对称图的结构和光谱特性的进一步分析
Further analysis on structure and spectral properties of symmetric graphs
论文作者
论文摘要
图是一种用于建模网络系统和结构的抽象表示。在包括计算机视觉和模式识别以及神经科学在内的各个领域的问题中，通常会比较图形（一个过程称为\ textit {Graph {Graph Matching}）或检查是否有对称性。相关的邻接矩阵的友好特性（由其光谱属性指定）对于得出（棘手的）离散图匹配问题的凸松弛而言很重要。在这项工作中，我们通过研究其与基础图结构的关系来研究对称图的不友善性能。据揭示，对称图具有相同拓扑的两个或多个子图，并且与同一组顶点相邻。然后，我们表明，如果对称图的邻接矩阵具有不同的特征值，则存在与所有向量正交的特征向量，从而使它们不友好。重新审视了与一个受控节点协议动力学下的多代理系统的多代理系统的不控制性的关系。还为插图提供了合成图和现实图形的示例。
Graph is an abstract representation commonly used to model networked systems and structure. In problems across various fields, including computer vision and pattern recognition, and neuroscience, graphs are often brought into comparison (a process is called \textit{graph matching}) or checked for symmetry. Friendliness property of the associated adjacency matrices, specified by their spectral properties, is important in deriving a convex relaxation of the (intractable) discrete graph matching problem. In this work, we study unfriendliness properties of symmetric graphs by studying its relation to the underlying graph structure. It is revealed that a symmetric graph has two or more subgraphs of the same topology, and are adjacent to the same set of vertices. We then show that if adjacency matrices of symmetric graphs have distinct eigenvalues then there exist eigenvectors orthogonal to the vector of all ones, making them unfriendly. Relation of graph symmetry to uncontrollability of multi-agent systems under agreement dynamics with one controlled node is revisited. Examples of both synthetic and real-world graphs are also given for illustrations.
