[Solomonov Seminar] 156. Solomonov seminar

[Marko Grobelnik]

Vabim vas na 156. Solomonov seminar, ki bo v torek 4. januarja 2005 
ob 13:00 uri v Veliki predavalnici IJS. Posnetki preteklih seminarjev so 
na http://solomon.ijs.si/ 

Na prvem seminarju v 2005 bo predstavil svoje delo nas sodelavec 
Jure Leskovec, ki je trenutno na studiju v ZDA. V prvih mesecih studija
je zacel sodelovati z nekaj precej znanimi raziskovalca s podrocja analize 
omrezij in dataminiga - rezultate prvih skupnih raziskav na temo rasti velikih 
omrezij bo predstavil na seminarju. Omrezja (grafi) so zelo fundamentalna 
podatkovna struktura, ki jo najdemo takorekoc na vsakem koraku - 
npr. omrezje poznanstev, telekomunikacijska, spletna omrezja itd. 
Za vecino naravnih omrezij je znano, da vsa rastejo po podobnih zakonih
in da spostujejo nekaksno strukturo - Jure bo na seminarju predstavil nekaj
zanimivih in presentljivih izsledkov pri opazovanju rasti velikih naravnih omrezij.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jure Leskovec, Carnegie Mellon University:
  Casovni razvoj velikih omrezij

Kaksni zakoni in vzorci veljajo, ko se grafi in omrezja skozi cas spreminjajo in razvijajo?  
Na seminarju bom predstavil nase rezultate na podrocju casovnega razvoja grafov.  
Opazovali smo casovni razvoj mnozice omrezij iz razlicnih domen in ugotovili, da 
postajajo omrezja skozi cas vedno bolj gosta -- povprecna stopnja tocke skozi cas 
narasca.  Z drugimi besedami to pomeni, da stevilo povezav (E) raste super-linearno 
v odvisnosti od stevila tock (N) v omrezju.  Izkaze se, da lahko zgoscevanje omrezja 
zelo lepo opisemo s potencnim zakonom (power law): stevilo povezav v casu t E(t) v 
odvisnosti od stevila tock N(t) opisuje enacba E(t) = N(t)^a, kjer je koeficient 
(a) realno stevilo med 1 in 2 neodvisen od casa. Temu zakonu pravimo Growth Power Law.  
Nasa najdba predstavlja zasuk v primerjavi z dosedanjim delom na podrocju casovnega 
razvoja omrezij, saj so do sedaj ljudje vedno privzeli, da je razmerje med stevilom povezav 
in tock v omrezju skozi cas konstantno (oz. narasca najvec logaritemsko s stevilom tock). 

Na seminarju bom predstavil rezultate na omrezjih s podrocja racunalniskih (internet) in 
bibliografskih omrezij.  Vsa omrezja, ki smo jih opazovali, strogo sledijo zakonu Growth 
Power Law. Predstavil bom tudi enostaven verjetnostni model za generiranje grafov 
(Community Guided Attachment), ki uposteva Growth Power Law.  Zakljucil bom z 
moznimi razlagami in posledicami, ki jih prinasajo nasa opazanja.

Delo sem opravil v sodelovanju s Christosom Faloustosom z univerze Carnegie Mellon 
in Jonon Kleinbergom z univerze Cornell.