Kisvilág-tulajdonság

Egy kisvilág-tulajdonságú gráfban vagy hálózatban a csúcsok közötti átlagos távolság a csúcsok számához képest kicsi. Az elnevezés Stanley Milgram kisvilág-kísérletéből származik, ami azt vizsgálta, legkevesebb hány személyes ismeretségi kapcsolaton keresztül lehet eljutni egy embertől egy másikig, vagyis mekkora az ismeretségi kapcsolatokat leíró szociális hálóban az átlagos távolság.

A kisvilág-tulajdonság számos fontos hálózatra jellemző, például a szociális hálókra, az Internetre vagy a génexpressziós hálózatokra.

A véletlen gráfok legtöbb fajtája kisvilág-tulajdonságú: ha egy nagy átmérőjű gráfba felveszünk néhány véletlen élt, az átmérő nagyon gyorsan csökken. Három gyakran használt, kisvilág-tulajdonságú modell az Erdős–Rényi-modell, a Watts–Strogatz-modell és a Barabási–Albert-modell; az átlagos úthossz mindháromban kicsi, de egyéb fontos jellemzőikben, például a klaszterezettségben vagy a fokszámeloszlásban eltérnek.

Külső hivatkozások

• Összement a hat lépés távolság – Index, 2011. november 22.