magistrsko delo
Povzetek
V magistrski nalogi smo raziskovali stiskanje usmerjenih grafov, ki se uporabljajo za modeliranje omrežij, kot so socialna omrežja, biološka omrežja, itd. Z naraščajočo velikostjo grafov se pojavljajo težave pri shranjevanju in njihovi obdelavi. Implementirali smo dve metodi, ki stiskata grafe z uporabo simetrij, ki smo jih izračunali z avtomorfizmom grafov. Metodi smo nato združili z metodami brezizgubnega stiskanja in ju primerjali z obstoječimi metodam stiskanja usmerjenih grafov. Kakovost stiskanja smo ocenili s številom bitov na povezavo. Kakovost pristopov smo ocenili na množici grafov iz različnih domen. Metodi, ki uporabljata simetrije, nista bili uspešnejši kot obstoječe, vendar smo predlagali več možnih izboljšav.
Ključne besede
stiskanje grafov;simetrije v grafih;avtomorfizem grafov;računalništvo in informatika;magisteriji;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2023 |
Tipologija: |
2.09 - Magistrsko delo |
Organizacija: |
UL FRI - Fakulteta za računalništvo in informatiko |
Založnik: |
[Y. Kuhar] |
UDK: |
004.627:519.17(043.2) |
COBISS: |
168264195
|
Št. ogledov: |
51 |
Št. prenosov: |
8 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Methods for graph compression |
Sekundarni povzetek: |
In this thesis, we investigated the compression of directed graphs, which are used to model different types of networks such as social networks, biological networks, etc. As graphs grow in size, problems arise in their storage and processing. We implemented two methods that compress directed graphs using symmetries, which were calculated using graph automorphism. We then combined them with lossless compression methods and compared them with existing directed graph compression methods. The compression quality was evaluated by the number of bits per edge. We evaluated the performance of approaches on a dataset of graphs from various domains. The methods using symmetries were not more successful than the existing ones, but we proposed many possible improvements. |
Sekundarne ključne besede: |
data compression;graph compression;graph symetries;graph automrphism;computer science;computer and information science;master's degree;Kvantno računalništvo;Teorija grafov;Stiskanje podatkov (informatika);Računalništvo;Univerzitetna in visokošolska dela; |
Vrsta dela (COBISS): |
Magistrsko delo/naloga |
Študijski program: |
1000471 |
Konec prepovedi (OpenAIRE): |
1970-01-01 |
Komentar na gradivo: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Strani: |
65 str. |
ID: |
19933585 |