diplomsko delo
Povzetek
Trikotniki v grafu so podgrafi, sestavljeni iz treh povezanih vozlišč. Število trikotnikov je računsko zahtevna statistika, ki se pogosto uporablja v analizi velikih omrežij in v raznih primerih uporabe, kot so recimo odkrivanje skupnosti v omrežju, zaznavanje vsiljive vsebine, odkrivanje skritih tematskih struktur.
Cilj diplomskega dela je pregled in primerjava algoritmov za štetje trikotnikov. Na začetku predstavimo problem, definicije in nekaj primerov uporabe štetja trikotnikov. Nato predstavimo algoritme za točno štetje trikotnikov, zatem pa še algoritme za približno štetje. Na koncu sledi še primerjava hitrosti in kratek zaključek.
Ključne besede
algoritem;graf;trikotniki;štetje;računalništvo;računalništvo in informatika;univerzitetni študij;diplomske naloge;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2021 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UL FRI - Fakulteta za računalništvo in informatiko |
Založnik: |
[J. Adamič] |
UDK: |
004:519.17(043.2) |
COBISS: |
54953219
|
Št. ogledov: |
321 |
Št. prenosov: |
84 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Algorithms for counting triangles in a graph |
Sekundarni povzetek: |
Triangles in a graph are subgraphs composed of three connected nodes. The number of triangles is a computationally intensive statistic that is often used in the analysis of large networks and in various use cases, such as discovering communities in a network, detecting spam, discovering hidden thematic structures.
The aim of the thesis is to review and compare algorithms for counting triangles. At the beginning we present the problem, definitions and some examples of the use of counting triangles. Then we present algorithms for exact counting of triangles, and then algorithms for approximate counting. Finally, there is a comparison of speed and a short conclusion. |
Sekundarne ključne besede: |
algorithm;graph;triangle;counting;computer science;computer and information science;diploma; |
Vrsta dela (COBISS): |
Diplomsko delo/naloga |
Študijski program: |
1000468 |
Komentar na gradivo: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Strani: |
45 str. |
ID: |
12639640 |