Využití relaxace pro výpočet approximativní symetrie grafů
| Thesis title in Czech: | Využití relaxace pro výpočet approximativní symetrie grafů |
|---|---|
| Thesis title in English: | Using relaxation to compute approximate symmetry of graphs |
| Key words: | komplexní sítě|symmetrie|aproximativní symetrie|spojitá optimalizace|relaxace |
| English key words: | complex networks|symmetry|approximate symmetry|continuous optimization|relaxation |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | doc. Ing. et Ing. David Hartman, Ph.D. et Ph.D. |
| Author: | Bc. Dávid Kubek - assigned and confirmed by the Study Dept. |
| Date of registration: | 10.12.2024 |
| Date of assignment: | 15.01.2025 |
| Confirmed by Study dept. on: | 15.01.2025 |
| Date of electronic submission: | 16.07.2025 |
| Guidelines |
| V oblasti komplexních sítí (Barabasi 2016) se v nedávné době začala studovat symmetrie různých typů reálných sítí založená na automorfismech (MacArthur et al. 2007). Jelikož jsou komplexní sítě často zatíženy chybou, tak přesná definice automorfismu může být někdy zavádějící. Proto se nedávno objevil pojem aproximativní symetrie umožňující zobrazením být blízko automorfismům, viz (Lui 2020). Kromě definice problému byl v citovaném zdroji navržen i postup založený na lokálních kombinatorických přístupech, nicmě se objevili i základní přístupy i na bázi relaxace viz (Pidnebesna et al. 2023), který vedl k mírnému zlepšení. Cílem práce je prozkoumat širší možnosti využití metod relaxace pro představený problém. |
| References |
| Barabasi, A.-L. (2016) Network Science. Cambridge University Press.
B. D. MacArthur, R. J. Sanchez-Garcia, and J. W. Anderson. Symmetry in complex networks. Discrete Applied Mathematics, 156(18):3525–3531, 2007. Liu, Y. (2020). Approximate network symmetry. arXiv preprint arXiv:2012.05129. Pidnebesna, A., Hartman, D., Pokorná, A., Straka, M., & Hlinka, J. (2023). Computing approximate symmetries of complex networks. arXiv preprint arXiv:2312.08042. |