Title Trokuti, klinovi i klasteriranje u usmjerenim grafovima Author Marko Markežić Mentor Zlatko Drmač (mentor)Committee member Marko Vrdoljak (predsjednik povjerenstva)Committee member Maja Starčević (član povjerenstva)Committee member Zlatko Drmač (član povjerenstva)Committee member Josip Tambača (član povjerenstva)Granter University of Zagreb Defense date and country 2017-09-28, Croatia Scientific / art field, NATURAL SCIENCES Abstract 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.
Abstract (english) 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.
Keywords
klin
trokut
neusmjerene mreže
usmjerene mreže
homofilnost
tranzitivnost
algoritam klin uzorkovanja
Block Two-Level Erdos-Renyi
BTER
Keywords (english)
wedges
triangles
undirected graphs
directed graphs
homophily
transitivity
wedge sampling algorithm
Block Two-Level Erdos-Renyi
BTER
Language croatian URN:NBN urn:nbn:hr:217:847644 Study programme Title: Mathematical Statistics Type of resource Text File origin Born digital Access conditions Open access Terms of use Created on 2018-02-28 11:11:13
