KIT | KIT-Bibliothek | Impressum
Open Access Logo
§
Verlagsausgabe
DOI: 10.5445/IR/1000080151

How Symmetric Are Real-World Graphs? A Large-Scale Study

Ball, Fabian; Geyer-Schulz, Andreas

Abstract:
The analysis of symmetry is a main principle in natural sciences, especially physics. For network sciences, for example, in social sciences, computer science and data science, only a few small-scale studies of the symmetry of complex real-world graphs exist. Graph symmetry is a topic rooted in mathematics and is not yet well-received and applied in practice. This article underlines the importance of analyzing symmetry by showing the existence of symmetry in real-world graphs. An analysis of over 1500 graph datasets from the meta-repository networkrepository.com is carried out and a normalized version of the “network redundancy” measure is presented. It quantifies graph symmetry in terms of the number of orbits of the symmetry group from zero (no symmetries) to one (completely symmetric), and improves the recognition of asymmetric graphs. Over 70% of the analyzed graphs contain symmetries (i.e., graph automorphisms), independent of size and modularity. Therefore, we conclude that real-world graphs are likely to contain symmetries. This contribution is the first larger-scale study of symmetry in graphs and it shows the necessity of ha ... mehr


Zugehörige Institution(en) am KIT Institut für Informationswirtschaft und Marketing (IISM)
Publikationstyp Zeitschriftenaufsatz
Jahr 2018
Sprache Englisch
Identifikator ISSN: 2073-8994
URN: urn:nbn:de:swb:90-801519
KITopen ID: 1000080151
Erschienen in Symmetry
Band 10
Heft 1
Seiten 29
Bemerkung zur Veröffentlichung Gefördert durch den KIT-Publikationsfonds
Schlagworte graph symmetry; graph automorphism groups; symmetry analysis; real-world networks
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page