Centralities in computation of approximate symmetries

• Thesis title in Czech: Centrality ve výpočtu přibližných symetrií
• Thesis title in English: Centralities in computation of approximate symmetries
• Key words: komplexní sítě|symmetrie|automorfismus|aproximace|optimalizace|simulované žíhání|grafové centrality
• English key words: complex network|symmetry|automorphism|approximation|optimization|simulated annealing|graph centralities
• Academic year of topic announcement: 2023/2024
• 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. František Szczepanik - assigned and confirmed by the Study Dept.
• Date of registration: 17.06.2024
• Date of assignment: 09.07.2024
• Confirmed by Study dept. on: 09.07.2024
• Date and time of defence: 05.09.2024 10:00
• Date of electronic submission: 18.07.2024
• Date of submission of printed version: 18.07.2024
• Date of proceeded defence: 05.09.2024
• Opponents: Mgr. David Mikšaník

Guidelines

Komplexní sítě jsou moderní modely reálných systémů reprezentující propojený charakter jejich podsystémů. Tyto sítě mají specifickou strukturu i chování. V nedávné době se začal studovat vliv symetrií v těchto sítích, což vykazovalo výsledky v rozporu s původním očekáváním. Komplexní sítě jsou konstruovány ze systémů, jejichž měření je zatíženo neurčitostí. Z tohoto důvodu se v nedávné době začala studovat aproximativní verze těchto symetrií, což představuje těžký výpočetní problém. Ten se v literatuře prozatím primárně počítá skrze simulované žíhání či alternativní metody relaxace. Simulované žíhání sice nevykazuje příliš dobré výsledky, ale má dobrý potenciál na zlepšení z důvodu lokality výpočtu. Plánovaná práce by se měla zabývat možným vylepšením základního přístupu tohoto algoritmu pro aproximativní symetrie v nastavení známém z literatury a navrhnout cesty k vylepšení výpočtu pomocí ohodnocování vrcholů například skrze centrality.

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.
Liu, Y. Approximate Network Symmetry. 2020. Available from arXiv: 2012.05129.
Pidnebesna, B., Hartman, D., Pokorná, A., Straka, M., Hlinka, J. Computing approximate symmetries of complex networks. 2023. Available from arXiv: 2312.08042.