Matematiniai interneto modeliai

Matematiniai interneto modeliai

Andrejus Михайлович Ражгородский
"Kvantas" №4, 2012

Kas yra internetas?

Dar dešimtojo dešimtmečio viduryje, maždaug prieš 15-20 metų, beveik niekas nežinojo apie internetą. Ir jei jis žinotų apie savo egzistavimą, jis vargu ar turėjo prieigą prie jo. Todėl klausimas, pateiktas šio skirsnio antraštėje, atrodytų tinkamas tada skaitytojui. Tačiau dabar, kai internetas tvirtai įsitraukė į mūsų gyvenimą, šis klausimas turėtų sukelti sumišimą: "Na, kas yra" kas "? Tai aišku, tai yra informacijos šaltinis, patogi bendravimo platforma. Yra svetainių, jų puslapių, tinklaraščių, socialinių tinklai, šlamštas ir tt ". Visa tai tiesa. Ir vis dėlto, ar mes tikrai žinome apie pasaulinio interneto įrenginį? Visų pirma, ar mes suprantame, kokie įstatymai lemia jo formavimąsi? O gal nėra įstatymų? Galų gale atrodytų, kad internetas yra visiškai atsitiktinė, nekontroliuojama aplinka, todėl niekas jo neužkerta kelio. nenuspėjamas plėtra. Na, aptarkime.

Interneto išdėstymas iš interneto-map.net

Mes reprezentuosime internetą diagramos pavidalu. Šio grafiko viršūnės bus svetainės ir tarp dviejų viršūnių A, B mes atkreipiame tiek daug kraštų, nukreiptų iš A į BKiek nuorodų yra iš svetainės A į svetainę Bir tiek daug kraštų nukreipta iš B į AKiek nuorodų yra iš svetainės B į svetainę A. Mums bus įdomu šios grafiko įrenginys, kuris dėl akivaizdžių priežasčių yra vadinamas žiniatinklio grafika. Pasirodo, priešingai nei minėta prielaida apie visišką nenuspėjamą "World Wide Web" elgesį, žiniatinklio grafike yra keletas stabilių savybių – savybės, kurios lieka nepakitę per internetinių tyrimų istoriją. Nepateikiant išsamumo, mes apibūdinome keletą tokių savybių. Joms jau pakaks, kad suprastų, kaip dažnai tikra pasaulio įvaizdis prieštarauja mūsų intuicijai.

Pirmasis žiniatinklio grafiko turtas yra gerai žinomas daugeliui žmonių, nors paprastai jis yra apie kitą. Jie kalba apie "šešių rankos" įstatymą. Būtent kiekvienas žmogus turi pažįstamų, šie žmonės taip pat turi pažįstamų ir pan. Pastebėta, kad nuo bet kurio asmens iki bet kurio kito žmogaus Žemėje jūs galite "praleisti" tokią abipusių pažįstamų grandinę ir kad "nuorodų" "jis neviršys šešių. Kitaip tariant, aš pasikalbėsiu su savo draugu, jis pasikliaudamas rankomis su vienu iš jo draugų ir per ne daugiau kaip šešis tokius rankdarbius (su tinkamu jų pasirinkimu) prezidentasšalis ar keletas Ohio pizza peddleris – apskritai bet koks iš anksto nustatytas asmuo. Tokia pati istorija su internetu. Tik čia "rankos" pakeičiamos "paspaudimais" (kompiuterio pelė ant nuorodų) ir nurodoma, kad iš bet kurios svetainės iš bet kurios kitos svetainės (tinkamai pasirinkus jų grandinę) reikės ne daugiau kaip šešių paspaudimų.

Kalbant apie grafikos teoriją, tai yra skersmuo suskaičiuoti Mes pateikiame apibrėžimą. Atstumas tarp grafiko viršūnių yra kraštų skaičius trumpiausioje krašto grandinėje, jungiančio šiuos viršūnius. Jei grafika yra orientuota (kaip, pavyzdžiui, žiniatinklio grafika), tada visi kraštai nagrinėjamose grandinėse turėtų sekti vienas kitą toje pačioje kryptyje. Skersmuo yra didžiausias atstumas tarp diagramoje esančių viršūnių. Žinoma, yra atjungtų grafų. Kiekvienas iš jų turi skersmenį, lygų begalybę. Šešių paspaudimų teisė yra faktas, kad žiniatinklio grafiko skersmuo yra šeši. Nurodyti diagramos skersmenį G naudokite įrašų diam G.

Aprašytas turtas puikiai apibūdinamas išraiška "mažas pasaulis". Atrodytų, kad tai turėtų reikšti, kad žiniatinklio grafike yra nemažai briaunų. Tarsi ne taip! Ir čia intuicija mus atneša.Antroji žiniatinklio grafiko savybė yra išskirtinė "spraga". Apytiksliai tariant, jei viršūnėse yra interneto grafikas n, tada jis neturi daugiau šonkaulių mn su kai kuriais pastoviais m ≥ 1. Supraskime, kodėl to nepakanka. Tiesą sakant, net jei mes neatsižvelgia į tai, kad žiniatinklio grafike yra kelis kraštus ir keletą kilpų (iš vienos šios svetainės puslapio gali būti ir nuorodų į kitus tos pačios puslapius), tai netrukdo turėti šonkauliai. Tačiau pastaroji vertė kvadratine dalimi auga. no faktinis kraštų skaičius yra žymiai mažesnis: maksimaliai mn. Tam tikra prasme, tai yra ypač mažai ir negali būti: jei yra grafikas n viršūnių mažesnis nei n – 1 kraštas, tada ši schema nėra prijungta.

Ir dar viena, trečia, nuosavybė. Pažvelkime į laipsniai viršutinės žiniatinklio schemos viršūnės. Čia, žinoma, yra subtilumas, susijęs su tuo, kad gali būti nukreipta grafika atvykstantys laipsniai (kraštų, kurių dešinysis galas yra nurodytas viršūnių, skaičius ) ir taip Išeinantys laipsniai . Jei nenurodyta kitaip, pagal viršūnės laipsnį supratome jo gaunamų ir išeinančių laipsnių sumą, t. Y. visų kraštų, kurių pabaiga yra: = + . Esame suinteresuoti žiniatinklio grafiko viršūnių santykiu su šiuo laipsniu. Kitaip tariant, leiskite n – žiniatinklio grafiko viršūnių skaičius ir d – tam tikras fiksuotas numeris. Pažymėkite # (n, d) dydis

t. y. mes suskirstome laipsnio viršūnių skaičių d (modulis žymi komplekto galingumą, įterptų garbanotose skliaustuose) dėl bendro viršūnių skaičiaus ir mes gauname pageidaujamą frakciją. Pasirodo, kad visada

Čia d ≠ 0, nes interneto grafika yra prijungta, ir c – konstanta, kurią lengva rasti, nes mes žinome, kad visų kiekių suma lygus niš kur # (n, d) = 1. Iš esmės # (n, d) – tai tikimybė tai, kad grafiko viršuje yra laipsnis d, o visų tikimybių suma turi būti lygi vienai. Daug nenuostabu, kad pastovus 2,3, kuris laikui bėgant nesikeičia! Apibūdinta savybė yra vadinama galios teisės platinimas žiniatinklio grafiko viršūnių laipsniai.

Taigi, situacija yra labai įdomu. Nepaisant atrodo, kad interneto švietimo procese yra chaosas, yra labai griežti statistiniai apribojimai, dėl kurių jis buvo taikomas daugelį metų. Kodėl tai taip? Kas yra už visas interneto savybes? Kokie yra tinklo formavimo įstatymai? Ne tik visi šie klausimai yra labai svarbūs, norint suprasti pasaulio struktūrą, tačiau atsakymai į juos gali ne tik padaryti rimtų praktinių pranašumų: turėti teisingai interneto modelį, galite pabandyti geriau identifikuoti tam tikrus šlamšto tipus ("nenatūralios orientacinės struktūros", vadinamos nuorodų žiedai), patikrinkite paieškos roboto "Internet" nuskaitymo algoritmus ir kt. Toliau aptariame visus šiuos aspektus – ir modelius, ir programas.

Pageidautina priedėlio idėja

1999 m. Du tyrėjai – AL Barabashi ir R. Albertas – pasiūlė labai paprastą idėją, kuri vis dėlto pasirodė esanti labai produktyvi. Idėja buvo ta, kad kai gimsta nauja svetainė, jis greičiausiai "nori" nurodyti tas svetaines, apie kurias jau minėjo daugelis. Tiksliau, tikimybė, su kuria naujoji svetainė susies su svetainės pirmtaku, yra proporcinga (gaunamajam) šios svetainės tinklalapio viršaus viršaus. Vienas iš patogiausių ir matematiškai griežtų "Barabashy-Albert" idėjos įgyvendinimo idėjų (idėjos apie pageidaujamas ryšys) 2000 m. suformulavo matematikai B. Bollobashas ir O. Riordanas.

"Bollobash-Riordan" modelio konstrukcija susideda iš dviejų etapų. Pirmiausia sukurta grafikų seka. G1n, n = 1, 2, 3, … Šie stulpeliai turės n viršūnės ir n šonkauliai.Tada ši seka paverčiama seka naudojant paprastą triuką. Gnmkur m – natūralus skaičius ir grafiko G kraštų skaičiusnmturintys n viršūnės lygus mn. Taigi grafikai Gnm automatiškai pasirodys antroji žiniatinklio grafiko savybė.

Taigi pradėkime nuo G1n. Mes sukursime šias diagramas indukcija. Leisk G11 yra grafas su viena viršūnė (mes tiesiog žymime 1) ir viena kilpa (1, 1).1 Tarkime grafiką G1n – 1 su n ≥ 2 jau pastatytas. Apibūdinkite jo viršūnių 1, …, n – 1 ir nepamirškime, kad jo kraštai, kaip antai viršūnės, n – 1. Count G1n mes gauname pridedant grafiką G1n – 1 viena verte (viena svetainė) su "pavadinimu" n ir vienas kraštas (nuoroda, kurią sukuria nauja svetainė). Šis kraštas bus nukreiptas arba iš n į n (jei tu vėl juokėsi, šiuo atveju reikia kalbėti ne apie vienatvę, o apie savigarbą), ar iš n kažkur viršūnėje {1, … , n – 1}. Pati kryptis parenkama atsitiktinai: su tikimybe nuoroda iš n eis pats n ("narcisizmas"); su tikimybe svetainė n citata svetainėje {1, … , n – 1}. Čia – viršūnių laipsnis grafike G1n – 1t. y. savo gryna forma, suprantama, kad norima pritvirtinti idėja. Padalinta į 2n – 1 taip pat nieko paslaptingo. Tik tikimybių suma turėtų būti viena, bet yra dvigubas grafikos kraštų skaičius G1n – 1t. y. 2n – 2.

Mes pabrėžiame, kad sukonstruota diagramų seka atsitiktinis. Iš esmės tai gali būti labai įvairi forma, priklausomai nuo to, kas vyksta kitame jos statybos etape. Bet tai gerai: galų gale nuo pat pradžių intuicija mums pasakė, kad internetas yra "atsitiktinis". Tik svarbu, kokie įstatymai reglamentuoja šią nenumatytą atvejį, ir dabar mes manome, kad vienas iš šių įstatymų – iš tikrųjų psichologinis – yra lengvatinio įstojimo teisė.

Mes pereiname į antrąjį etapą. Nustatyti natūralų m ≥ 2. Apsvarstykite pirmame etape esantį grafiką. G1mn. Jis turi mn viršūnės ir mn šonkauliai. Pažymėk 1 pirmoji grupė m jo viršūnės, t. rinkinys {1, …, m}. Pažymėk 2 kita viršūnių grupė {m + 1, … , 2m}. Ir taip toliau. Taigi turėsime grupes 1, … , n. Mes juos laikysime naujos diagramos viršūnėmis. Gmn. Už kiekvieną i forma viršuje i kiek daugelis kilpų, nes grafike yra kraštai G1mn tarp jo viršūnių, kurių rinkinį mes pažymėjome i. Už bet kokį i, j su sąlyga 1 ≤ i < jn atkreipkite tiek daug kraštų nuo j į ikiek yra grafike G1mn kraštai, kurių dešinysis galas yra nustatytame rinkinyje j, o kairėje – rinkinyje, kuris atitinka i. Tam tikra prasme mes išstumti viršūnių G1mn "metasitais", ir visos ankstesnės nuorodos yra išsaugomos. Išėjime mes turime grafiką su n viršūnės ir mn šonkauliai. Pereinamojo nuo grafiko pavyzdys G112 suskaičiuoti G26 parodyta 1 paveiksle.

Pav. 1

Dizainas atrodo gana dirbtinis ir, bent jau labai supaprastintas. Tačiau tai stebėtinai gerai atspindi tikėtinas žiniatinklio grafiko savybes. Nėra reikalo kalbėti apie antrąjį turtą, nes jis tiesiogiai įtraukiamas į konstrukciją. Diskutuokime apie pirmąjį turtą. Modelio autoriai – Bollobash ir Riordan – įrodė, kad su m ≥ 2 ir bet kuriai ε> 0, padidinus grafiko G viršūnių skaičiųmn arčiau vienybės, tikimybė, kad tampa grafo G skersmuomn slypi (1 – ε) diapazone iki (1 + ε). Kitaip tariant, nors grafikas yra atsitiktinis, jo skersmuo "beveik neabejotinai" yra beveik toks pats kaip ir nedidelė. . Kodėl tai gera? Ir faktas, kad žiniatinklio grafikas yra apie 107-108 viršūnės. Pakeisdami abu numerius n atsižvelgiant į logaritmus, gauname 5,8-6,2, t. y. 6, nes skersmuo yra sveikas skaičius. Tiesą sakant, net su n = 109 logaritmų santykis neviršija septynių. Tai yra labai lėtai auganti funkcija, ir tai gali paaiškinti, kodėl šešių rankos signalų teisė yra tokia nepakenčiama.Ar tai ne puikus smūgis?

Bet tai dar ne viskas. Yra trečioji nuosavybė. Tai taip pat pastebima Bollobash-Riordan modelyje. Modelio autoriai tai įrodė esant tam tikriems vertės apribojimams dpasirodys nuosavybe. Neseniai Maskvos valstybinio universiteto ir Nepriklausomo universiteto mechaniko ir matematikos fakulteto absolventas E.Grečnikovas, šiuo metu dirbantis teorinių ir taikomųjų tyrimų skyriuje "Yandex", įrodė, kad visiems m ir d su augimu n artėja prie tikimybės, kad kiekis # (n, d), apibrėžta grafike Gmn, praktiškai nesiskiria nuo vertės kur c priklauso tik nuo m.

Paskutiniame rezultate viskas šiek tiek mažesnė nei rezultatas apie skersmenį: galų gale 3 nėra 2.3. Taip, tai taip pat yra galios įstatymas, ir tai nuostabu, bet jo laipsnis šiek tiek skiriasi. Na: niekas nesakė, kad trivialus modelis iš karto išspręstų visas problemas.

Bollobash-Riordan modelio tobulinimas

Ankstesnio skyriaus pabaigoje supratome, kad Bollobash-Riordan modelis nevisiškai tinkamai atspindi net tris interneto grafiko savybes, kurias mes nustatėme nuo pat pradžių. Būtent, yra mažų problemų dėl galios teisės.Šios problemos yra lengvai išspręstos, ir daugelis įvairių laikų mokslininkų atėjo į tą patį paprastą sprendimą. Čia pabrėžti P. Buckley ir D. Ostgus, kurie pirmieji pateikė tokį požiūrį griežtą pagrindą. Po Buckley ir Ostgus, paimkite savavališką skaičių. a > 0. Mes sukursime grafikus Hna, m pagal beveik tą pačią schemą kaip grafikai buvo pastatyti Gmn. Tik šiek tiek pakeiskite apibrėžimo tikimybes G1n. Jei jie buvo lygūs ir tada čia mes juos lygiu . Su suma, viskas gerai vėl:

Be to, su a = 1 mes turime Bollobash-Riordan modelį. Skaičius a vadinamas pradinis pritraukimas aukštyn. Idėja yra tai, kad, nepriklausomai nuo viršūnių laipsnio, tai dar labiau prisideda prie prisijungimo tikimybės.

Kas yra puikus, tai yra pakankamai! Pareiškimas apie skersmenį išlieka nepakitęs, o vertė # (n, d), apibrėžta grafike Hna, mtampa beveik beveik lygus . Taigi, su a = 0.3 mes gauname pilną tikrovės dalies modelio atitikimą, kuris atsispindi trijose identifikuojamos interneto savybėse.

Deja, šio ir ankstesnių skirsnių rezultatų įrodymai yra labai sudėtingi ir techniniai. Todėl jie nepatenka į šio straipsnio taikymo sritį.Suinteresuoto skaitytojo kreipiamės į knygas [1], [2] ir straipsnį [3].

Ir kitame skyriuje kalbėsime apie dar vieną interneto modelio kūrimo idėją.

Kopijuoti modelį

Čia idėja yra tokia: kai pasirodys nauja svetainė, ji nurodo tam tikrą "atsitiktinį" (iš išorės) pirmtaką, arba kopijos Nuorodos iš kai kurių (taip pat ir atsitiktinių) svetainių, kurių tema yra šalia jos autoriaus. Šia idėja siekiama paaiškinti ne tik galios teisę, bet ir tai, kad internete yra gana gausių bendruomenių, kurių narius vienija bendrieji interesai.

Glaudus paprastos kopijos modelio versijos aprašymas yra toks. Atsižvelgiant į natūralų skaičių m ir tikrasis skaičius α (0, 1). Kaip ir Bollobash-Riordan ir Buckley-Ostgus modelių atveju, yra sudaryta atsitiktinė diagramų seka . Ir taip pat pastatyta indukcija. Pradiniu momentu yra viena viršūnė 1 ir m kilpos joje. Leisk n ≥ 2 ir skaičiavimas su viršūnėmis 1, …, n – 1 jau pastatyta. Pridėkite prie jo viršūnę n ir m išeina iš jos šonkaulių. Šį kartą "narcisizmas" yra pašalintas, o kraštai eina į viršūnių 1, …, n – 1. Mes apibūdinome, kaip pasirinkti jų kairiuosius galus. Pirma, pasirinkta atsitiktinė viršūnė. p {1, … , n – 1}. Tai reiškia, kad p užima vieną konkrečią formą su tikimybe . Gerai pasirinkta p ir nustatytas. Tai bus ta pati svetainė, kurios tema yra įdomi svetainės autoriui. n. Iš jo jis kartais nukopijuos nuorodas. Dabar mes nurodome pirmąjį kraštą, kuris prasideda nuo n. Norėdami tai padaryti, mes išmėginsime "kreivės" monetą, kuri su tikimybe α kyla į viršų ereliu ir su tikimybe 1 – α yra iki uodegos. Jei uodegos nukrito, mes siunčiame savo kraštą iki pirmosios didžiausios smailės tarp tų, apie kuriuos nukreipta svetainė. p. Kitaip tariant, su tikimybe 1 – α nukopijuojame pirmąją nuorodą iš svetainės. p. Jei erelis nukrito, mes nieko nereikia kopijuoti, bet atsitiktinai pasirinkti viršūnę tarp {1, …, n – 1} ir nusiųskite kraštą į jį. Antrasis kraštas kilęs iš nAtrodė taip pat. Su tikimybe 1 – α, ji yra antras aukščiausia smailė tarp nurodytųjų p; su tikimybe α, jos kairysis galas yra pasirinktas atsitiktine tvarka. Ir taip toliau. Kadangi kiekviename statybos etape išmeta kitas vertes m tada riešutai p tiksliai m kaimynai, ir aprašyta tvarka galėsime atlikti reikalingus veiksmus m kartus

Galima parodyti, kad su tikimybe arti vieno, vertė # (n, d), apibrėžta grafike elgiasi panašiai kur c – nuolatinis priklauso nuo m ir α. Rezultatas yra nepaprastai svarbus, nes vėlgi, naudojant tinkamą α pasirinkimą, galime gauti bet kokį eksponentą d, didesnis dviem, o ypač rodiklis – 2.3. Pastaruoju atveju kopijavimo tikimybė yra gana artima vienai.

Ar tai visi?

Klausimas, pateiktas šio skirsnio antraštėje, gali būti įdomus skaitytojo vadovas. Taip, žinoma, mes kalbėjomės apie keletą idėjų, kurios gražiai paaiškina "interneto gyvenimo" modelius – modelius, kurie iš pradžių atrodė tokie nuostabūs. Tačiau akivaizdu, kad aprašytuose modeliuose yra daug trūkumų.

Pavyzdžiui, diagramose, kurios gali kilti modelių sistemoje, kiekviena viršūnė turi fiksuotas Išeinantis laipsnis. Nėra nieko panašaus į internetą! Iš tiesų paaiškėja, kad modeliuotose diagramose orientacija yra labai sąlyginė. Mažai tikėtina, kad diagramų struktūra daug pasikeis, jei pašalinsime visas strėles nuo kraštų.

Be to, akivaizdu, kad modeliuose vyresnio amžiaus viršūnės yra labiau linkę gauti aukštesnį laipsnį nei naujesnės viršūnės. Akivaizdu, kad tai yra blogai suderinta su kasdien internete vykstančiomis naujienų "sprogimais": vargu ar pasirodys svarbių naujienų puslapis, prie kurio prie jo prisijungia tūkstančiai nuorodų.Mes nesakome, kad svetainės, puslapiai ir nuorodos į juos dažnai miršta, ir tai taip pat neatsispindi modeliuose.

Žinoma, žmonės, kurie atlieka tinklo tyrimus, tai puikiai supranta. Iki šiol išrado daugybė skirtingų interneto modelių, kurie realybei yra daug tinkamesni nei "Bollobash-Riordan", "Buckley-Ostgus" modeliai ar kopijavimo modeliai. Tai yra didžiulis įspūdingas teorijos sritis. atsitiktiniai grafikaikuri dar turi būti plėtojama ir sisteminama. Išnagrinėtų pavyzdžių patosas yra tas, kad jie puikiai parodo, kaip paprasti principai yra labai sudėtingi reiškiniai. Ir toli gražu nėra išsamaus problemos sprendimo, ir tai tiesiog malonu: dabartinis skaitytojas, žinoma, turi kažką daryti, jei nori ištirti žiniatinklio grafikus.

Galėtume tai padaryti, tačiau mes taip pat pasakysime keletą žodžių apie modelių taikymą internetinės paieškos praktikai.

Apie vieną programą

Pažvelkime į vieną iš šlamšto veiklų. Būtent, pakalbėkime apie "ryšių žiedus". Iš karto pastebime, kad istorinis vardas išryškėjo: kai spameriai, kurie nori apgauti paieškos variklį ir pakelti savo pozicijas paieškos rezultatuose, cituoja vienas kitą ratu, t. Y. A1 įdėti nuorodą į A2, A2 – apie A3, … , An – apie A1. Ši schema buvo greitai išmokta atskleisti, nepageidaujamo e. Pašto platintojai turėjo tapti gudresni, tačiau vardas "ryšių žiedas" išliko.

Dabar tipinė konstrukcija yra dviejų dalių grafika (2 pav.). Vertikaliai iš (sąlygiškai) teisingos dalies yra nuorodų pirkėjai, tie, kurie taip tikisi parodyti, kad jie turi aukštą "citavimo indeksą", todėl turi būti pakelti į aukščiausią paieškos rezultatų viršūnę. Viršūnės iš kairės skilties yra

Pav. 2

nuorodų pardavėjai. Pastarosios nebūtinai yra tam tikros išeivijos rūšys. Priešingai, nuorodos dažnai perkamos iš gana garbingų savininkų, kuriems reikia pinigų, kad išspręstų bet kokias problemas: nuo paieškos sistemos požiūriu svetainė, kurią cituoja garbinga svetainė, tampa kandidatu į "gerbiamų piliečių klubą". Ryšio žiedo kraštai vyksta daugiausia iš kairės į dešinę; Be to, daug kraštų gali būti viduje kairėje skiltyje (arba tiesiog dėl pagarbos, arba dėl "sukčiavimo").

Geros paieškos sistemos uždavinys yra automatiškai nustatyti nesąžiningus savininkus. Kodėl automatiškai? Ir todėl, kad tą pačią nuorodą žiedai šimtai tūkstančių (!) ir sugauti juos "rankos" yra tiesiog fiziškai neįmanoma. Bet kaip mokyti automobilį atskirti žiedą nuo struktūros, kuri nėra žiedas?

Įsivaizduokite, kad mes turime idealų (arba tiesiog pakankamai tinkamą) internetinį internetinį modelį be šlamšto. Leiskite mums apskaičiuoti šiame modelyje tikimybę, kad pasieksite kraštą tarp tam tikro gaunamo laipsnio viršūnių. Kitaip tariant, apie viršūnių A ir B žinoma, kad indeg A = aindeg B = b. Ir leiskite, atsižvelgiant į šias žinias, iš juostos tikimybės A į B lygus f (a, b) (atitinkamai, krašto tikimybė B į A lygus f (b, a)).

Tegul dabar turime internetą, kuri, ko gero, yra žiedas. Pažymėk A1, … , Ak – kairės skilties viršūnės, ir B1, … , Bl – dešiniąją skilties viršūnę. Gaunamų laipsnių dydžiai žymimi atitinkamai a1, … , ak, b1, … , bl. Mes randame . Iš esmės M – tai laukiamas skaičius kraštų, kurie eina iš kairės mūsų struktūros dalies į dešinę dalį "gero" interneto. Galiausiai tegul realus skaičius iš kairės į dešinę kraštų turi būti μ. Ir viskas aišku: lieka tik palyginti M ir μ. Jei tikimasi, kad kraštų skaičius yra mažesnis nei tikrasis, tai struktūra greičiausiai yra anomalinga.

Žinoma, visada yra klaidų tikimybė. Ir klausimo kaina gali būti labai didelė.Todėl dažniausiai užfiksuotų žiedų svetainės nėra tiesiogiai išbrauktos; jiems priklauso tik tam tikra skaitinė charakteristika M ir μ, ir mašina kruopščiai atsižvelgia į šią charakteristiką, kai reitinguoja dokumentus pagal pareikalavimą.

Nuorodos:
1. A. M. Райгородский. Atsitiktinių grafikų modeliai. – M: ICNMO, 2011 m.
2. B. Bollobás. Atsitiktiniai grafikai, antrasis leidimas. – Kembridžo universitetas. Spauda, ​​2001.
3. E. A. Grechnikov. Įvertinta Bollobas-Riordan modelio atsitiktinių grafų. – Maskvos žurnalas "Kombinatorikos ir skaičių teorija", 1 (2011), Nr. 2, p. 40-73.


1 Kartą paskaitoje aš juokavo: jie sako, visų laikų pradžioje buvo viena svetainė, ji buvo labai vieniška, ir jis nusprendė įdėti sau sau … Balsas iš auditorijos: "Kokia buvo ši svetainė?" Žinoma, tai yra modelis, o ne realybė.


Like this post? Please share to your friends:
Parašykite komentarą

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: