Časovni razvoj velikih omrežij

author: Jure Leskovec, Computer Science Department, Stanford University
published: Feb. 25, 2007,   recorded: January 2005,   views: 173

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography

Description

Kakšni zakoni in vzorci veljajo, ko se grafi in omrežja skozi čas spreminjajo in razvijajo? Na seminarju bom predstavil naše rezultate na področju časovnega razvoja grafov. Opazovali smo časovni razvoj množice omrežij iz različnih domen in ugotovili, da postajajo omrežja skozi čas vedno bolj gosta -- povprečna stopnja točke skozi čas narašča. Z drugimi besedami to pomeni, da število povezav (E) raste super-linearno v odvisnosti od števila točk (N) v omrežju. Izkaže se, da lahko zgoščevanje omrežja zelo lepo opišemo s potenčnim zakonom (power law): število povezav v času t E(t) v odvisnosti od števila točk N(t) opisuje enačba E(t) = N(t)^a, kjer je koeficient (a) realno število med 1 in 2 neodvisen od časa. Temu zakonu pravimo Growth Power Law. Naša najdba predstavlja zasuk v primerjavi z dosedanjim delom na področju časovnega razvoja omrežij, saj so do sedaj ljudje vedno privzeli, da je razmerje med številom povezav in točk v omrežju skozi čas konstantno (oz. narašča najvec logaritemsko s številom točk). Na seminarju bom predstavil rezultate na omrežjih s področja računalniških (internet) in bibliografskih omrežij. Vsa omrežja, ki smo jih opazovali, strogo sledijo zakonu Growth Power Law. Predstavil bom tudi enostaven verjetnostni model za generiranje grafov (Community Guided Attachment), ki upošteva Growth Power Law. Zaključil bom z možnimi razlagami in posledicami, ki jih prinašajo naša opazanja. Delo sem opravil v sodelovanju s Christosom Faloustosom z univerze Carnegie Mellon in Jonon Kleinbergom z univerze Cornell.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: