Approximative symmetries of complex networks

• Thesis title in Czech: Aproximativní symmetrie komplexních sítí
• Thesis title in English: Approximative symmetries of complex networks
• Key words: komplexní sítě|symmetrie|automorfismus|approximace|graph matching
• English key words: complex network|symmetry|automorphism|approximace|graph matching
• Academic year of topic announcement: 2021/2022
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D.
• Author: Bc. Matej Straka - assigned and confirmed by the Study Dept.
• Date of registration: 22.04.2022
• Date of assignment: 25.04.2022
• Confirmed by Study dept. on: 02.05.2022
• Date and time of defence: 23.06.2022 09:00
• Date of electronic submission: 11.05.2022
• Date of submission of printed version: 11.05.2022
• Date of proceeded defence: 23.06.2022
• Opponents: RNDr. Martin Černý

Guidelines

Komplexní sítě jsou zajímavými modely reálných systémů, které mohou leccos napovědět o jeho chování studiem specifického charakteru propojení jeho částí. Sítě tohoto charakteru jsou často realitivně neuniformní z hlediska mnohých charakteristik, například rozdělení stupňů vrcholů. Přesto v nedávné době se začalo se studiem symetrie těchto sítí a existence různých druhů symetrie byla ukázána pro mnohé sítě zastupující reálné systémy. Většina symetrií tohoto typu byla založena na studiu struktury automorfní grupy odpovídající sítě. Jelikož konektivita sítě je dána měřením dat či popisem charakteru reálné situace, může být zatížena různými nejistotami. Proto se nabízí využití definice symetrie, která s nejistotou počítá. Cílem práce je prozkoumat algoritmy stanovení aproximativní symetrie v komplexních sítích.

References

Barabási, A.-L. and Pósfai, M.. Network science. Cambridge University Press, Cambridge, 2016.
MacArthur, B. D., Sánchez-Garcı́a, R. J., and Anderson, J. W.. Symmetry in complex networks. Discrete Applied Mathematics, 156(18):3525–3531, Nov 2008.
Sánchez-Garcı́a, R. J.. Exploiting symmetry in network analysis. Communications Physics, 3(1), May 2020
Conte, D., Foggia, P., Sansone, C., & Vento, M.. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18(03), 265-298, 2004.