Kakova razmernost' Platonova mira idej?

Esli sudit' po Chertovym Kulichkam, to okolo 7

D. Manin

1. Postanovka zadachi

Po rabote mne ponadobilos' vyyasnit', kakovo mozhet byt' raspredelenie HTML-stranic po chastote poseschenij (hit rate). Imeya dostup k statistike poseschenij Chertovykh Kulichek, ya otpravilsya tuda i vzyal dannye za fevral' 1998 goda: kolichestvo popadanij dlya 300 samykh populyarnykh stranic. Kulichki -- mesto krupnoe i khorosho poseschaemoe, za mesyac nabezhalo pochti 13 millionov popadanij, tak chto dazhe u poslednej stranicy v spiske nabralos' 1300 -- grafik poluchilsya gladkij. Vot on:

Kak fizik, imevshij delo s ehksperimental'nymi dannymi, mogu zasvidetel'stvovat', chto takaya krasota (tochki lozhatsya na chistuyu pryamuyu) vstrechaetsya nechasto, osobenno esli rech' idet o statistike. Rassmotrim grafik podrobnee.

Po osi X otlozhen poryadkovyj nomer stranicy v spiske, a po osi Y -- kolichestvo popadanij na nee za mesyac. Po obeim osyam masshtab logarifmicheskij, to est', sdvig na odno i to zhe rasstoyanie vdol' osi sootvetstvuet izmeneniyu otlozhennoj velichiny v odno i to zhe chislo raz. Inache govorya, rasstoyanie mezhdu otmetkami 10 i 100 takoe zhe, kak mezhdu 100 i 1000, ili, skazhem, mezhdu 0.37 i 3.7.

Grafik, izobrazhayuschij ehksperimental'nye tochki, prekrasno lozhitsya na nekuyu pryamuyu. V logarifmicheskom masshtabe pryamaya izobrazhaet stepennuyu zavisimost': kogda X uvelichivaetsya v neskol'ko (skazhem, v a) raz, Y tozhe uvelichivaetsya v neskol'ko (skazhem, v b) raz -- znachit, Y = A X^c, gde b = a^c. Pryamaya, pokazannaya na grafike, -- nailuchshee priblizhenie ehksperimental'nykh dannykh stepennoj zavisimost'yu. Ee pokazatel' stepeni c = -0.85.

Estestvenno, voznikaet vopros -- pochemu? Vryad li my smozhem ob~yasnit' konstantu 0.85, da i vryad li ehta konstanta universal'na, no tot fakt, chto raspredelenie imenno stepennoe, bessporen i trebuet ob~yasneniya. Nado skazat', chto stepennye raspredeleniya voobsche vstrechayutsya neredko v estestvennykh processakh, no ehto nablyudenie esche ne zamenyaet ob~yasneniya. Poehtomu my zajmemsya chernoj magiej fiziki -- izobreteniem modeli, kotoraya osnovyvalas' by na "estestvennykh" predposylkakh, i iz kotoroj stepennoe raspredelenie vytekalo by, kak sledstvie.

Ideal'no bylo by, chtoby v ehtoj modeli vovse ne bylo proizvol'nykh chislovykh parametrov, a chislo 0.85 poluchalos' by, kak universal'naya konstanta. Ne rasschityvaya na takuyu udachu, my ogranichimsya odnim chislovym parametrom v modeli, potomu chto model' s bol'shim chislom parametrov mozhno prisposobit' k chemu ugodno, i ee poznavatel'naya sila poehtomu ravna nulyu. Takim obrazom, sam fakt stepennogo raspredeleniya dolzhen poluchat'sya v nashej modeli sam soboj, a pokazatel' stepeni mozhet zaviset' ot parametra. Esli ehtot parametr budet imet' kakoj-nibud' interesnyj smysl, to podobrav ego velichinu (tak, chtoby poluchilas' stepen' 0.85), my mozhem uznat' chto-nibud' interesnoe.

2. Grafy i razmernosti

Posetiteli popadayut na stranicy Kulichek, sleduya po ssylkam. Ne vse, konechno, nachinayut pryamo s zaglavnoj stranicy, no, chtoby ne uslozhnyat' delo, my predpolozhim, chto ehto -- edinstvennaya tochka vkhoda. Nalichie mnozhestvennykh tochek vkhoda situaciyu izmenit' suschestvenno ne dolzhno. Predstavim sebe graf, v kotorom stranicy izobrazhayutsya vershinami (tochkami), a ssylki so stranicy na stranicy -- strelkami, soedinyayuschimi vershiny. Ssylki, konechno, odnonapravlennye, no knopka "nazad" na brodilke vypolnyaet rol' "obratnoj ssylki", tak chto mozhno schitat' graf nenapravlennym (fakticheski, posetitel' mozhet dvigat'sya protiv strelki tol'ko esli on ee uzhe proshel v pryamom napravlenii, no poskol'ku my rassmatrivaem puti mnozhestvennykh posetitelej, mozhno schitat', chto lyubaya strelka mozhet byt' projdena v oboikh napravleniyakh).

Po stepeni udalennosti ot tochki vkhoda stranicy mozhno razdelit' na urovni: zaglavnaya budet sostavlyat' nulevoj uroven', vse stranicy, na kotorye mozhno popast' s nee neposredstvenno, sostavyat pervyj uroven', i t.d. Ochevidno, chto so stranicy n-go urovnya mozhno popast' tol'ko na stranicy (n-1)-go, n-go i (n+1)-go urovnej. Dejstvitel'no, esli s nee mozhno popast' na stranicy urovnya n+2, to ehta vtoraya stranica dolzhna prinadlezhat' ne vyshe, chem (n+1)-mu urovnyu. Analogichno rassmatrivaetsya dvizhenie vniz po urovnyam.

Ochevidno, chto esli posetiteli brodyat sluchajnym obrazom po nashemu grafu, to chastota popadanij na stranicu suschestvenno zavisit ot togo, skol'ko est' stranic na kazhdom urovne (budem nazyvat' ehto chislo naselennost'yu urovnya). Chem ikh bol'she, tem rezhe v kazhduyu iz nikh budut popadat' posetiteli, razbredayas' po raskhodyaschimsya dorozhkam iz tochki vkhoda. Kak mozhno ocenit' ehto raspredelenie?

Dopustim, graf Kulichek izobrazhalsya by kvadratnoj reshetkoj na ploskosti. Togda vse stranicy, v kotorye mozhno dobrat'sya za n shagov, pomestilis' by v kvadrat so storonoj 2n+1, i ikh bylo by (2n+1)², to est' dlya dostatochno bol'shikh n, ehto chislo bylo by proporcional'no n², a naselennost' urovnya -- perimetru kvadrata, t.e. nomeru urovnya. Esli by graf izobrazhalsya kubicheskoj reshetkoj v prostranstve, naselennost' urovnya byla by proporcional'na ploschadi poverkhnosti kuba, t.e. kvadratu nomera urovnya. Zametim, chto naselennost' urovnya svyazana s razmernost'yu prostranstva, v kotorom raspolagayutsya vershiny. Ehto ochen' prostaya svyaz', kotoraya dazhe lezhit v osnove odnogo iz vozmozhnykh opredelenij razmernosti: v prostranstve razmernosti d, ob~em shara radiusa r proporcionalen r^d, a poverkhnost' -- r^d-1.

Razumeetsya, real'nyj graf Kulichek -- ne kvadratnaya reshetka i ne kubicheskaya. I naselennost' ego urovnej zavisit ne ot togo, kak ego narisovat', a ot togo, kak vershiny svyazany mezhdu soboj. Poehtomu otvlechemsya voobsche ot togo, chto graf mozhno izobrazit' tochkami i strelkami, i ostanetsya sut' dela: estestvennoe predpolozhenie, chto naselennost' urovnya proporcional'na nekotoroj stepeni ego nomera. Ehto budet nasha fundamental'naya gipoteza, a pokazatel' stepeni -- tot samyj podgonochnyj parametr, kotoryj my sebe pozvolili. Tochnee, kak chitatel', vozmozhno, uzhe dogadalsya, my vvedem ponyatie razmernosti grafa d, i naselennost' urovnya n budet togda sootvetstvovat' ploschadi poverkhnosti shara radiusa n, t.e. n^d-1.

Napomnim, chto my rassmatrivaem tol'ko urovni otnositel'no fiksirovannoj tochki vkhoda -- zaglavnoj stranicy Kulichek. Odnako velik soblazn rasprostranit' model' na vsyu Pautinu i predpolozhit', chto vzyav pochti lyubuyu stranicu i posmotrev, kak rastet chislo stranic, do kotorykh s nee mozhno dobrat'sya za n shagov, my vsegda poluchim stepennoj zakon s odnim i tem zhe pokazatelem. Inache govorya, predpolozhit', chto Pautina imeet fiksirovannuyu razmernost'. Poskol'ku ssylki svyazyvayut mezhdu soboj asociativno blizkie stranicy, vne zavisimosti ot fizicheskogo mestopolozheniya serverov (vspomnim pereezd tekh zhe Kulichek na druguyu storonu Zemli iz Detrojta v Moskvu), ya ranee predlozhil dlya rasstoyaniya mezhdu stranicami, izmeryaemogo kolichestvom shagov po ssylkam, termin "Platonova metrika", imeya v vidu Platonov mir idej. Teper' my vveli v Platonovom mire i ponyatie razmernosti.

Poka chto, vprochem, vse vysheizlozhennoe -- chistaya gipoteza, nichem ne podkreplennaya. Teper' my dolzhny postroit' na ee osnove model', kotoraya by ob~yasnila stepennoe raspredelenie stranic po chastote obraschenij. Esli ehto poluchitsya, nasha gipoteza priobretet, pust' shatkoe za ogranichennost'yu ehksperimental'nykh dannykh, no vse zhe osnovanie.

3. Model'

Ehtot razdel budet bolee tekhnicheskim, chem predyduschie, i esli vas ne interesuyut podrobnosti, ego mozhno propustit'.

Itak, osnovnye predpolozheniya:

Odna tochka vkhoda
Sluchajnoe bluzhdanie ot nee
Stacionarnoe raspredelenie posetitelej po stranicam -- esli graf beskonechnyj, to dlya ehtogo mozhet potrebovat'sya nepreryvnyj pritok v tochku vkhoda, chtoby kompensirovat' ukhod na beskonechnost'
Razmernost' d
Odnorodnost' vnutri urovnya: budem schitat', chto vse vershiny odnogo urovnya v nekotorom smysle ravnopravny, t.e. vse popadaniya na uroven' raspredelyayutsya mezhdu nimi ravnomerno

Ya ne ochen' staralsya sdelat' ehti predpolozheniya minimal'no neobkhodimymi i dostatochnymi -- vse-taki, ya ne matematik, a fizik. Navernoe, teoriya sluchajnykh bluzhdanij po grafam dostatochno khorosho razrabotana, i izobretat' velosiped ne khochetsya. Menya zdes' interesuet v pervuyu ochered' rezul'tat.

Poslednee predpolozhenie (odnorodnost') pozvolyaet nam otvlech'sya ot mnogoslozhnoj prirody grafa i rassmatrivat' vmesto ehtogo bluzhdaniya posetitelej po odnomernoj cepochke urovnej. Ehto nastol'ko oblegchaet zadachu, chto dazhe kazhetsya zhul'nichestvom. Vozmozhno, tak ono i est', no vse zhe prodolzhim.

Itak, posetiteli popadayut na nulevoj uroven' (v tochku vkhoda) i nachinaetsya sluchajnoe bluzhdanie vniz-vverkh. Esli posetitelej mnogo, to mozhno ehto rassmatrivat', kak diffuziyu ikh funkcii raspredeleniya po urovnyam. Esli predpolozhit', chto raz popav v Pautinu, posetitel' tak v nej i ostaetsya, t.e. utechki net, to nezavisimo ot veroyatnosti ujti urovnem vyshe, nizhe, ili ostat'sya na tom zhe urovne, edinstvennoe stacionarnoe reshenie diffuzionnoj zadachi -- konstanta. (Konechno, ehto spravedlivo pri uslovii uravneniya s postoyannymi koehfficientami, t.e. esli ne vvodit' predpolozhenij o zavisimosti povedeniya posetitelya ot nomera urovnya -- a my uzhe ischerpali limit vvoda proizvol'nykh konstant). Togda chastota popadaniya na stranicu obratno proporcional'na naselennosti urovnya, kotoromu ona prinadlezhit, a znachit, ehta chastota stepennym obrazom zavisit ot nomera urovnya i ranga samoj stranicy. Ura.

Esli zhe utechka est' (na kazhdom shagu est' nenulevaya veroyatnost', chto posetitel' utomitsya i zakroet brodilku), to u stepennogo raspredeleniya poyavitsya ehksponencial'nyj khvost. Dejstvitel'no, raspredelenie po urovnyam stanet togda ehksponencial'nym (sr. skin-ehffekt), no esli koehfficient utechki ne slishkom velik, to dlya neskol'kikh pervykh urovnej, gde nakhodyatsya bolee poseschaemye stranicy, ehksponenta esche ne slishkom otlichaetsya ot konstanty, i raspredelenie budet stepennym. Zato utechka skazhetsya na stranicakh, pogrebennykh dostatochno gluboko. Ikh chastoty i tak neveliki, a utechka ikh esche obrezhet. Zametim, chto ehksperimental'nye dannye u nas okhvatyvayut tol'ko 300 samykh poseschaemykh stranic, iz obschego kolichestva v pochti 100 000, tak chto ehksponencial'nyj khvost vpolne mog ostat'sya vne polya nashego zreniya.

Takim obrazom, pokazatel' stepeni raspredeleniya stranic po chastote poseschenij okazyvaetsya svyazannym s platonovoj razmernost'yu grafa. Imenno, pri razmernosti d chislo stranic na l-m urovne proporcional'no l^d-1, a rang stranicy (ee nomer v poryadke ubyvaniya poseschaemosti) -- n ~ l^d, otkuda sama poseschaemost' (obratno proporcional'naya naselennosti urovnya) vyrazhaetsya, kak

f_n ~ l^1-d ~ n^-(1-1/d)

Inache govorya, iskomyj pokazatel' stepeni raven 1-1/d = 0.85, otkuda poluchaem razmernost' mezhdu 6 i 7.

4. Obsuzhdenie

Itak, oblast' Platonova mira Pautiny, zanimaemaya Chertovymi kulichkami, priblizitel'no semimerna. Mnogo ehto ili malo? Chtoby pochuvstvovat', chto ehto oznachaet, rassmotrim dva krajnikh sluchaya: odnomernyj graf i beskonechnomernyj graf. Odnomernyj -- ehto linejnaya cepochka stranic, svyazannykh ssylkami po poryadku nomerov, bez vetvleniya i skachkov. Vesch' dovol'no skuchnaya. Vse stranicy takoj posledovatel'nosti budut imet' odinakovuyu chastotu poseschenij (opyat' zhe, v predpolozhenii, chto chitatel' terpeliv i ne dezertiruet slishkom skoro) -- t.e. pokazatel' stepeni nashego raspredeleniya raven nulyu, a razmernost' -- edinice.

Vtoroj krajnij sluchaj -- beskonechno razvetvlyayuscheesya derevo s postoyannym koehfficientom vetvleniya: s kazhdoj stranicy idet po N ssylok, i oni ne skleivayutsya -- na kazhduyu stranicu vedet tol'ko odna ssylka. Naselennost' urovnya rastet ehksponencial'no, chto v nekotorom smysle ehkvivalentno stepennomu rostu s beskonechnym pokazatelem stepeni, razmernost' beskonechna, a pokazatel' stepeni raspredeleniya -- minus edinica.

Real'nost' zhe lezhit gde-to poseredine mezhdu ehtimi dvumya krajnostyami. S odnoj storony, pochti s kazhdoj stranicy vedet bolee odnoj ssylki, s drugoj zhe storony, ssylki s raznykh stranic chasto vedut v odno i to zhe mesto (skleivayutsya). Po ehtoj prichine chislo stranic, do kotorykh mozhno dobrat'sya za N shagov, rastet ne ehksponencial'no (v geometricheskoj progressii), a medlennee. I my teper' znaem, naskol'ko imenno medlennee.

Konechno, model', postroennaya v ehtoj stat'e, otchasti igrushechnaya. Mne kazhetsya, odnako, chto ehto zanyatie ne bylo bessmyslennym. Mne bylo interesno. A vam?