(arra gondoltam, hogy az év utolsó posztja ne egy tádzsik szotyilovagról szóljon, hanem valami érdekesről, ünnepelvén, hogy megvan a húszmilliomodik letöltés a Vincenten, whatever "húszmillió letöltés" means...)
Néhány éve már írtam a skálafüggetlen hálózatokról, leginkább arról a sokak által elfogadott nézetről, hogy a Való Világ, úgyismint VV, hálózatai skálafüggetlenek. Az elmúlt évben két fontos cikk is megjelent ezzel kapcsolatban. Az egyik címe Scale-free networks are rare. A másiké pedig, szóvicc következik, Scale-free networks are well-done. Ezek a cikkek mintha ellentmondanának egymásnak, de leginkább csak mintha. Nagyon sok múlik azon, hogy mit is értünk skálafüggetlenség alatt, mennyire vesszük komolyan a power-law-t. Ha nagyon komolyan vesszük, akkor az első cikknek van igaza, ha "with a grain of salt", akkor a másodiknak.
Tekintettel a többszörös tekintendőkre (CEU kormányzati kinyírása és Barabási pozitív szerepe, a Synergy Grant és Barabási pozitív szerepe ismét) nem fogok én itt keménykedni, nem egy lánczibuburól van szó, hanem a világ egyik (állítólag nyolcvanhatodik) legidézettebb kutatójáról, akivel mondjuk úgy, nem mindenben értek egyet. Amit most leírok, az végtelenül egyszerű, bárki ellenőrizni tudja, aki nem unta nagyon a számtant a gimnáziumban.
Az történt, hogy valamire már elég régen kíváncsi voltam, és most volt időm és energiám arra, hogy utánanézzek. Ez a most valóban most volt, éppen a poszt elkezdése előtt. Kissé meglepődtem, hogy ez az egész ennyire egyszerű.
1. Ha valaki esetleg nem tudná a skálafüggetlenség azt jelenti, hogy egy hálózatban a csúcsok fokainak eloszlása nagyjából olyan, mint valamiféle hatvány. Tehát, jó közelítéssel a k-fokú csúcsok aránya k a mínusz alfaadikon, ahol alfa valamilyen egynél nagyobb szám, nem feltétlenül egész szám. Ennek a mondatnak valójában csak akkor van értelme, ha egyre nagyobb hálózatokat nézünk, de akkor tényleg van értelme, és attól függően, hogy mit nevezünk jó közelítésnek, akár igaz is lehet VV hálózatokban. Lásd a két fenti cikket a skálafüggetlenség és a steak elkészítése viszonyáról.
2. Barabásinak van egy kedvenc véletlen konstrukciója, amit Preferential Attachment gráfoknak neveznek, és arról biztosan lehet tudni, hogy skálafüggetlen, nagyon, nagyon skálafüggetlen. Ezek a gráfok, hálózatok ahogy akarjuk, nem nagyon támadhatók meg ollóval. Azaz, ha két nagyjából egyenlő részre akarjuk szétvágni őket, akkor rengeteg élt kell szétvágnunk, mondjuk az élek egytizedét vagy ilyesmi (mármint ha nem fát gyártunk, azaz nem egy csúcshoz kötődik be az új hús, a fát persze nagyon könnyű feldarabolni) . Ezt a tulajdonságot expander tulajdonságnak nevezik. Spielman írja a jegyzetében, hogy "the difference I found most profound is that real life graphs are very rarely expanders". Arról persze fogalmam sincs, hogy milyenek a VV hálózatok, de azt tudom, hogy a legtávolabb az expandertől a síkba rajzolható gráfok vannak. Az ilyeneket, nagyon kevés él elvágásával sok kicsi darabra lehet vágni (már ha kevesen vannak a nagyon nagy fokú csúcsokhoz tartozó élek, és a skálafüggetlenség kicsit ezt is jelenti). Az egyikkel szinte semmit sem lehet csinálni algoritmikus szempontból, a másikkal meg szinte mindent. Ég és föld különbségéről van szó.
3. Tudtam, hogy Barabásinak volt még egy konstrukciója, de ma végre meg is kerestem. Ez a Barabási-Ravasz-Vicsek féle determinisztikus modell, amire azért még mindig elég sokan hivatkoznak. Elképesztően egyszerű dologról van szó. Fogsz egy csúcsot és összekötöd két másik csúccsal. Most van három csúcsod és két éled. Ezt a gráfot két példányban az előző alá másolod és a legfelső csúcsot (aminek eddig kettő volt a fokszáma) összekötöd a négy legalsó csúccsal. Azaz, most lesz kilenc csúcsod és tíz éled. A következő gráf pedig pont az, amire gondolsz. Ezt a kilenc csúcsú gráfot másolod le két példányban az eredeti alá és a felső csúcsot összekötöd az alsó nyolc csúccsal. És így tovább. Ez a gráfsorozat baromira skála-független.
De... Ezek a gráfok is olyanok, mint a síkgráfok. Nagyon kevés olyan él van (ha elég sokat iterálunk), amiből legalább ezer él fut ki, és ha ezeket eldobjuk a gráf kis darabokra esik szét.
4. Van egy rivális, sokat idézett determinisztikus konstrukció, a Dorogovstev, Goltsev, Mendes, amiről még videó is van a neten. Ez is megkerestem. Elindulsz egy háromszögből és minden élhez választasz egy új csúcsot és azt összekötöd az él két csúcsával. Ezt folytatod. Mocskosul skálafüggetlenek.
És ők valóban síkgráfok.
Mindkét fenti esetben úgy kell szétvágni pici darabokra a gráfokat, hogy elvágod a nagyfokú csúcsokhoz tartozó éleket, ez akár még ellenőrizhető is lehet hálózatokban.
5. Itt az én kis problémám. Nagyon nem mindegy ám, hogy miben hiszünk. A VV hálózatok inkább a Preferential Attachmentre hasonlítanak, vagy a másik kettőre? Mert hát ezek mind skála-függetlenek. Nagyjából élet és halál kérdése az, hogy egyik vagy másik modell írja-e le csinosabban a VV hálózatokat. Erős a gyanúm, hogy jóval gyakoribb a második esetre hajazó VV hálózat, mint az elsőre hasonlító, de ezt biztosan nem tudhatom.
