The Orbit-Polynomial: A Novel Measure of Symmetry in Networks

IEEE Access

Yongtang Shi¹  Zengqiang Chen²  Abbe Mowshowitz³  Jin Tao⁴  Frank Emmert-Streib⁵  Kurt Varmuza⁶  Lihua Feng⁷  Herbert Jodlbauer⁸  Matthias Dehmer⁸ 

[1] Center for Combinatorics and LPMC, Nankai University, Tianjin, China;College of Artificial Intelligence, Nankai University, Tianjin, China;Department of Computer Science, The City College of New York (CUNY), New York, NY, USA;Department of Electrical Engineering and Automation, Aalto University, Espoo, Finland;Department of Signal Processing, Predictive Medicine and Data Analytics Lab, Tampere University of Technology, Tampere, Finland;Institute of Statistics and Mathematical Methods in Economics, Vienna University of Technology, Vienna, Austria;School of Mathematics and Statistics, Central South University, Changsha, China;Steyr School of Management, University of Applied Sciences Upper Austria, Steyr, Austria;

关键词: Quantitative graph theory;    networks;    symmetry;    graphs;    graph measures;    data science;   

DOI  :  10.1109/ACCESS.2020.2970059

来源: DOAJ

【 摘 要 】

Research on the structural complexity of networks has produced many useful results in graph theory and applied disciplines such as engineering and data analysis. This paper is intended as a further contribution to this area of research. Here we focus on measures designed to compare graphs with respect to symmetry. We do this by means of a novel characteristic of a graph G, namely an “orbit polynomial.”A typical term of this univariate polynomial is of the form czn, where c is the number of orbits of size n of the automorphism group of G. Subtracting the orbit polynomial from 1 results in another polynomial that has a unique positive root, which can serve as a relative measure of the symmetry of a graph. The magnitude of this root is indicative of symmetry and can thus be used to compare graphs with respect to that property. In what follows, we will prove several inequalities on the unique positive roots of orbit polynomials corresponding to different graphs, thus showing differences in symmetry. In addition, we present numerical results relating to several classes of graphs for the purpose of comparing the new symmetry measure with existing ones. Finally, it is applied to a set of isomers of the chemical compound adamantane C10H16. We believe that the measure can be quite useful for tackling applications in chemistry, bioinformatics, and structure-oriented drug design.

【 授权许可】

Unknown