Název:
Aproximativní symmetrie komplexních sítí
Překlad názvu:
Approximative symmetries of complex networks
Autoři:
Straka, Matej ; Hartman, David (vedoucí práce) ; Černý, Martin (oponent) Typ dokumentu: Bakalářské práce
Rok:
2022
Jazyk:
eng
Abstrakt: [eng][cze] The aim of this thesis is to investigate the problem of an approximate symmetry of complex networks. First, we analyze how to measure such symmetry. Then we explore two algorithms by which we can measure levels of symmetry of networks and also find permutations representing those symmetries. First method uses a simulated annealing algorithm which is very slow if implemented naively. We exploit properties of an objective function to make this approach much faster, making it usable for large networks. In second approach we modify an existing method for inexact graph matching, making it applicable for measuring symmetry. We then provide a comparison of these two approaches. We then apply these algorithms to explore levels of symmetry produced by artificial networks, which are used to generate networks with properties possessed by real sys- tems. We explore how does our measure of an approximate symmetry correlate with other network measures, such as clustering coefficient or modularity. Finally, we measure symmetry of real brain networks and look where their symmetry comes from. 1Cieľom tejto práce je preskúmať problém aproximativných symetrií komplexných sietí. Najprv analyzujeme ako sa takáto symetria dá merať. Potom preskúmame dva algoritmy, ktorými môžeme merať aproximativné symetrie sietí a hľadať permutácie reprezentu- júce tieto symetrie. Základom prvej metódy je využitie algoritmu simulovaného žíha- nia, ktorý je veľmi pomalý pri naivnej implementácii. Využijeme vlastnosti funkcie na meranie symetrií na to, aby sme simulované žíhanie výrazne zrýchlili, čoho dôsledkom je využiteľnosť tejto metódy na väčších sieťach. V druhom prístupe modifikujeme už existujúcu metódu využívanú v hľadaní podobností grafov tak, aby bola využiteľná na meranie symetrie. Následne tieto dva algoritmy porovnáme. Tieto dve metódy zároveň aplikujeme na modely generujúce náhodné siete, ktoré re- flektujú vlasnosti reálnych sietí. Preskúmame ako naša funkcia na meranie aproximatívnej symetrie koreluje s inými mierami grafov, ako napríklad modularita či klastrovací koe- ficient. Na záver použijeme tieto algoritmy na hľadanie symetrie na reálnych mozgov- ých dátach a preskúmame, ako veľmi symetrické tieto mozgy sú a odkiaľ ich symetria pochádza. 1
Klíčová slova:
komplexní sítě|symmetrie|automorfismus|approximace|graph matching; complex network|symmetry|automorphism|approximace|graph matching