Tampere University of Technology

TUTCRIS Research Portal

The orbit-polynomial: A novel measure of symmetry in networks

Research output: Contribution to journalArticleScientificpeer-review

Standard

The orbit-polynomial : A novel measure of symmetry in networks. / Dehmer, Matthias; Chen, Zengqiang; Emmert-Streib, Frank; Mowshowitz, Abbe; Varmuza, Kurt; Feng, Lihua; Jodlbauer, Herbert; Shi, Yongtang; Tao, Jin.

In: IEEE Access, Vol. 8, 2020, p. 36100-36112.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Dehmer, M, Chen, Z, Emmert-Streib, F, Mowshowitz, A, Varmuza, K, Feng, L, Jodlbauer, H, Shi, Y & Tao, J 2020, 'The orbit-polynomial: A novel measure of symmetry in networks', IEEE Access, vol. 8, pp. 36100-36112. https://doi.org/10.1109/ACCESS.2020.2970059

APA

Dehmer, M., Chen, Z., Emmert-Streib, F., Mowshowitz, A., Varmuza, K., Feng, L., ... Tao, J. (2020). The orbit-polynomial: A novel measure of symmetry in networks. IEEE Access, 8, 36100-36112. https://doi.org/10.1109/ACCESS.2020.2970059

Vancouver

Dehmer M, Chen Z, Emmert-Streib F, Mowshowitz A, Varmuza K, Feng L et al. The orbit-polynomial: A novel measure of symmetry in networks. IEEE Access. 2020;8:36100-36112. https://doi.org/10.1109/ACCESS.2020.2970059

Author

Dehmer, Matthias ; Chen, Zengqiang ; Emmert-Streib, Frank ; Mowshowitz, Abbe ; Varmuza, Kurt ; Feng, Lihua ; Jodlbauer, Herbert ; Shi, Yongtang ; Tao, Jin. / The orbit-polynomial : A novel measure of symmetry in networks. In: IEEE Access. 2020 ; Vol. 8. pp. 36100-36112.

Bibtex - Download

@article{c65a4dbb32c840a882c8bc19c48e021f,
title = "The orbit-polynomial: A novel measure of symmetry in networks",
abstract = "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.",
keywords = "data science, graph measures, graphs, networks, Quantitative graph theory, symmetry",
author = "Matthias Dehmer and Zengqiang Chen and Frank Emmert-Streib and Abbe Mowshowitz and Kurt Varmuza and Lihua Feng and Herbert Jodlbauer and Yongtang Shi and Jin Tao",
year = "2020",
doi = "10.1109/ACCESS.2020.2970059",
language = "English",
volume = "8",
pages = "36100--36112",
journal = "IEEE Access",
issn = "2169-3536",
publisher = "Institute of Electrical and Electronics Engineers",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - The orbit-polynomial

T2 - A novel measure of symmetry in networks

AU - Dehmer, Matthias

AU - Chen, Zengqiang

AU - Emmert-Streib, Frank

AU - Mowshowitz, Abbe

AU - Varmuza, Kurt

AU - Feng, Lihua

AU - Jodlbauer, Herbert

AU - Shi, Yongtang

AU - Tao, Jin

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - data science

KW - graph measures

KW - graphs

KW - networks

KW - Quantitative graph theory

KW - symmetry

U2 - 10.1109/ACCESS.2020.2970059

DO - 10.1109/ACCESS.2020.2970059

M3 - Article

VL - 8

SP - 36100

EP - 36112

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

ER -