Trokuti, klinovi i klasteriranje u usmjerenim grafovima

diplomski rad

• Autor: Marko Markežić
• Mentor: Zlatko Drmač (mentor)
• Član povjerenstva: Marko Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Maja Starčević (član povjerenstva)
• Član povjerenstva: Zlatko Drmač (član povjerenstva)
• Član povjerenstva: Josip Tambača (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-09-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ukratko, u ovom su se radu predstavili pojmovi klinova i trokuta u neusmjerenim i usmjerenim mrežama, koji su temelji prepoznavanja skrivenih mrežnih podstruktura koje nazivamo zajednicama. Zajednica se definira kao podstruktura mreže koja je unutar sebe gusto povezana, a trokuti su dobri indikatori povezanosti jer predstavljaju homofilnost i tranzitivnost, svojstva koja nam govore da ljudi postaju prijatelji s onima sličnima sebi, što je korisno primjerice kod istraživanja prijevara u bankovnim transakcijama. Međutim, stvarne interakcijske mreže sadrže milijune pa čak i milijarde čvorova te nije jednostavno izračunati matematičke mjere vezane uz trokute na tako velikim mrežama. Stoga je u ovom radu predstavljen i algoritam klin uzorkovanja pomoću kojega se s relativno malim uzorkom slučajno odabranih čvorova mogu dovoljno dobro izračunati ukupan broj trokuta u cijeloj mreži te mjere koje su usko povezane s trokutima i klinovima. Primjerice, da algoritam postigne točnost od 99;9% potrebno je samo 380 slučajno odabranih klinova neovisno o ukupnoj veličini mreže. Također, predstavljen je i Block Two-Level Erdos-Renyi model mreže (BTER) koji se sastoji od međusobno povezanih zajednica različitih veličina. Pokazalo se da takav model ima slična svojstva kao i stvarne interakcijske mreže kod kojih stupnjevi čvorova prate distribuciju teškog repa, odnosno veliki broj čvorova je malog stupnja, a mali je broj čvorova velikog stupnja. BTER model je u ovom radu predstavljen samo za neusmjerene grafove te bi bilo zanimljivo vidjeti kako bi se mogao primijeniti i na grafove uzimajući u obzir njihovu usmjerenost. Dodatno, iako se na primjeru vezanom za usmjerene grafove nije vidjela važnost recipročnih bridova u tvorbi trokuta, recipročnost je svojstvo koje se pokazalo bitnim kod grafova visoke tranzitivnosti tako da bi to moglo biti jedno od važnijih svojstava za buduća istraživanja primjene BTER modela na usmjerenim grafovima.

Sažetak (engleski)

In this work we presented concepts of wedges and triangles in undirected and directed graphs, which are the basis for the recognition of hidden network substructures called communities. A community is defined as a substructure of a network that is internally well connected. Triangles are good correlation indicators because they represent homophily and transitivity - indicators that tell us that people become friends with those similar to themselves, which is useful, for example, in fraud detection of banking transactions. However, actual interaction networks contain millions, even billions of nodes, and it is hard to calculate mathematical measures associated with triangles on such large networks. Therefore, we also presented the wedge sampling algorithm that can sufficiently accurately calculate total number of triangles on a relatively small sample of randomly selected nodes. For example, it only takes 380 randomly selected wedges for the algorithm to be 99; 9% correct. In addition, Block Two-Level Erdos-Renyi model network (BTER) is introduced as a model that has a community structure in the form of dense subgraphs. It has been shown that such model matches well with real-world graphs that are idealized as power laws – in other words, their degree distribution is heavy tailed. The BTER model is presented in this paper only for undirected graphs and it would be interesting to see how it can be applied for directed graphs. Additionally, the relevance of reciprocal edges in the triangle formation is noted in literature related to directed graphs. This could be one of the most important features for the future research on the BTER model for directed graphs.

• Ključne riječi: klin; trokut; neusmjerene mreže; usmjerene mreže; homofilnost; tranzitivnost; algoritam klin uzorkovanja; Block Two-Level Erdos-Renyi; BTER
• Ključne riječi (engleski): wedges; triangles; undirected graphs; directed graphs; homophily; transitivity; wedge sampling algorithm; Block Two-Level Erdos-Renyi; BTER
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:847644
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-02-28 11:11:13