Kis világ (szám)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 28-án felülvizsgált verziótól ; az ellenőrzések 15 szerkesztést igényelnek .

A Small World gráf (kis világ)  egy olyan gráf , amely a következő tulajdonsággal rendelkezik: ha veszünk két tetszőleges csúcsot a és b , akkor nagy valószínűséggel nem szomszédosak, hanem kis számú átmeneten keresztül az egyik elérhető a másikból. más csúcsokon keresztül. Ugyanis a "kis világ" gráf egy olyan hálózat, amelyben két tetszőlegesen kiválasztott csúcs közötti tipikus L távolság (az egyik eléréséhez szükséges lépések száma) az N csúcsok számának logaritmusával arányosan nő . a hálózat, így [1] :

,

de a globális klaszterezési együttható nem kicsi. [2]

Ez egy közösségi háló kontextusában a „kis világ” jelenséghez vezet, vagyis az idegeneket kevés köztes ismeretség köti össze. Sok valós grafikon jól modellezhető a Small World grafikonokon keresztül. A közösségi hálózatok, az internetkapcsolat, a wikik, például a Wikipédia és a génhálózatok a „Kis világ” grafikon tulajdonságait mutatják. Duncan Watts és Stephen Strogatz 1998 - ban a "kis világ" gráfok egy bizonyos kategóriáját a véletlen gráfok osztályaként azonosította [1] . Megjegyezték, hogy az ilyen gráfokat két független szerkezeti jellemző szerint lehet osztályozni, nevezetesen a klaszterezési együttható és az egyik csúcstól a másikig terjedő átlagos távolság (más néven az átlagos legrövidebb úthossz ) szerint. Az Erdős-Rényi modell szerint felépített, teljesen véletlenszerű gráfok átlagosan kicsi a legrövidebb úthosszal (a gráf csúcsainak számának logaritmusaként nő) és kicsi a klaszterezési együtthatójuk. Watts és Strogatz azt találta, hogy a legtöbb valós hálózatnak átlagosan rövidebb a legrövidebb úthossza, de klaszterezési együtthatójuk lényegesen magasabb a véletlenszerű kiválasztás által vártnál. Ezt követően Watts és Strogatz egy új gráfmodellt javasoltak, most Watts-Strogatz modellnek , amelyet (i) egy kicsi átlagos legrövidebb úthossz és (ii) egy nagy klaszterezési együttható jellemez. A Watts és Strogatz modellben a "nagy világ" (például rácsgráf) és a kis világ metszéspontját először Bartelmy és Amaral írta le 1999 -ben [3] . Ezt a munkát számos tanulmány követte [4] [5] [6] .

A "Kis világ" grafikon tulajdonságai

A kis világ gráfjai általában klikkeket és közel-klikkeket tartalmaznak, amelyek olyan alhálózatok, amelyekben szinte minden csúcs között van kapcsolat. Ez egy ilyen gráftulajdonság magas klaszterezési együtthatóként való meghatározásából következik . Másodszor, a legtöbb csúcspárt legalább egy rövid út köti össze. Pontosabban, az átlagos távolság az egyik csúcstól a másikig (más néven az átlagos legrövidebb úthossz ) viszonylag kicsi. A legrövidebb út átlagos hosszát a következő képlettel számítjuk ki [7] :

 - távolság fentről felfelé  a gráf csúcsainak száma

Néhány egyéb jellemző, amelyeket később ismertetünk, gyakran megtalálhatók a „Kis világ” oszlopokban. Az ilyen gráfoknak általában sok csomópontja van  , amelyek foka jelentősen (sokszor) nagyobb, mint a gráf legtöbb csúcsának foka. Ezek a hubok csökkentik a grafikon átlagos legrövidebb útját. A „Kis világ” grafikon tipikus példája a repülőterek csomópontokkal rendelkező hálózata. A világ bármely két városa között valószínűleg legfeljebb három járatra lesz szükség, mivel a legtöbb járat a csomóponti repülőtereken halad át .

Ennek a tulajdonságnak (nevezetesen a hubok jelenlétének) elemzéséhez figyelembe veszik a hálózatban a nagyfokú csúcsok arányát. A vártnál több csomóponttal rendelkező hálózatokban nagyobb arányban lesznek magas fokú csúcsok és nagyon sok alacsony fokú csúcsok. Ezért a gráf csúcsainak fokszámainak eloszlása ​​„nehéz farok eloszlás” lesz . A nagyon eltérő topológiájú grafikonok kisvilágú gráfoknak minősülnek, ha a fenti két feltétel teljesül.

A "Kis világ" gráfok osztályába való tartozást úgy becsüljük meg, hogy összehasonlítjuk ennek a hálózatnak a klaszterezését és úthosszát egy azonos átlagos csúcsfokozatú, ekvivalens véletlenszerű hálózat megfelelő paramétereivel [8] . Egy másik módszer annak becslésére, hogy egy hálózat a „Small World” gráfosztályba tartozik-e, a „Small World” gráf eredeti definícióját használja, összehasonlítva egy adott hálózat klaszterezettségének fokát egy ekvivalens rácsgráf klaszterezettségi fokával és hosszával . az átlagos út hosszával egy tetszőleges gráfban [9] . A "Kis világ" ( ) osztályba tartozó gráf mértékét a következőképpen határozzuk meg

 a vizsgált grafikon legrövidebb útjának átlagos hossza  a vizsgált gráf klaszterezési foka  a legrövidebb út átlagos hossza egy véletlenszerű gráfban  a gráfrács klaszterezési foka

R. Cowen és Shlomo Havlin [10] [11] analitikusan kimutatta, hogy a skálamentes hálózatok  rendkívül kicsi világok. Ebben az esetben a hubok miatt a legrövidebb utak jelentősen lerövidülnek és as méretűek

Példák "kis világ" grafikonokra

Kis világgráf-tulajdonságokat találtak számos valós világ objektumában, beleértve az útiterveket, a táplálékláncokat, az elektromos hálózatokat, az anyagcsere-feldolgozó hálózatokat, a neurális hálózatokat , a szavazói hálózatokat, a telefonhívás-grafikonokat és a társadalmi befolyásolási hálózatokat.

A fehérje-fehérje kölcsönhatásoknak van egy olyan tulajdonsága a "Kis Világ" gráfnak, mint a teljesítményelosztási törvénynek való megfelelés [12] .

Hasonlóan, a transzkripciós szabályozás a „kis világ” gráf tulajdonságaival rendelkezik , amelyben a gének a csúcsoknak felelnek meg , és akkor kapcsolódnak össze, ha az egyik gén felfelé vagy lefelé szabályozó genetikai hatással van a másikra [13] .

Hálózati megbízhatóság

Egyes kutatók (például Barabási ) felvetették, hogy a kisvilág gráfjainak elterjedtsége a biológiai rendszerekben egy ilyen topológia evolúciós előnyeit tükrözheti. Ennek a feltételezésnek az az oka, hogy a „Kis Világ” gráfok stabilabbak különböző külső hatások hatására, mint más hálózati topológiák. Ha ez a hipotézis helyes lenne, akkor előnyt jelentene a mutációknak és vírusfertőzéseknek kitett biológiai rendszerek számára [14] .

A csúcsfokok hatványtörvényes eloszlású kisvilágú gráfjaiban egy véletlen csúcs eltávolítása ritkán okoz jelentős növekedést az átlagos legrövidebb úton (vagy a klaszterezési együttható jelentős csökkenését ). Ez abból a tényből következik, hogy a legtöbb legrövidebb utak áthaladnak a hubon, és ha egy perifériás csomópontot eltávolítanak, nem valószínű, hogy az zavarja a többi perifériás csomópont közötti átjárást. Mivel a perifériás csúcsok aránya a Small World oszlopban lényegesen nagyobb, mint a hubok aránya, egy fontos csúcs eltávolításának valószínűsége rendkívül kicsi [15] . Például, ha a petrozsényi kis repülőtér megszűnik működni, akkor ez nem fogja növelni az utasoknak a célállomás eléréséhez szükséges átlagos járatok számát. Ha azonban egy véletlenszerű törlés eléri a hubot, az átlagos legrövidebb úthossz jelentősen megnőhet. Ez minden évben megfigyelhető, amikor az Egyesült Államok északi repülőtereit, például a chicagói O'Hare repülőteret hó borítja, és sokan kénytelenek járatot váltani, és körforgalmat kell megtenni úti céljuk felé.

A „Small World” gráftól eltérően egy véletlenszerű hálózatban, amelyben az összes csúcs megközelítőleg ugyanannyi kapcsolattal rendelkezik, egy véletlen csúcs eltávolítása átlagosan kissé megnöveli a legrövidebb út hosszát, de ugyanannyit minden eltávolított csúcs esetében. Ebben az értelemben a véletlenszerű hálózatok sebezhetőek a véletlenszerű perturbációkkal szemben, míg a Small World gráfok stabilak [16] . A "kis világ" grafikonjai azonban sebezhetőek a központok elleni célzott támadásokkal szemben, míg véletlenszerű hálózatokban lehetetlen olyan célpontokat kiválasztani, amelyek megsemmisítése katasztrofális következményekkel jár [17] [18] .

Ennek megfelelően a vírusok úgy fejlődtek ki, hogy kölcsönhatásba lépnek olyan hub fehérjékkel, mint a p53 , ezáltal jelentős változásokat vezettek be a sejtek viselkedésében, amelyek kedveznek a vírusreplikációnak [19] .

Kis világgráfok felépítése

A "kis világ" gráfok felépítésének fő mechanizmusa - Watts-Strogatz modell

A kis világgráfok időkésleltetésű felépítése [20] lehetővé teszi nemcsak fraktálok létrehozását, hanem megfelelő feltételek mellett káoszt is [21] , vagy dinamikus hálózatokban a káoszba való átmenetet [22] .

Az átmérő fokának problémájának megoldása során olyan gráfot készítünk, amelyben az egyes csúcsok szomszédjainak száma korlátozott, miközben a csúcspárok közötti távolság ( hálózati átmérő ) minimálisra csökken. Az ilyen "kis világ" grafikonok felépítése a Moore-határhoz közeli sorrendű gráfok keresésének részeként történik .

Barmputis és Murray [23] mutat be egy másik módszert a "Small World" gráfok létrehozására , ahol egy hálózat nagyon kis átlagos távolsággal és nagyon nagy átlagos klaszterezéssel épül fel. A kapott grafikonok megbízhatóságának mérésével együtt egy állandó bonyolultságú gyors algoritmust adunk meg. A területtől függően lehet kezdeni egy ilyen "ultra kis világ" gráfot, majd újra beilleszteni néhány élt, vagy használhat néhány kisebb hálózatot egy nagyobb gráf részgráfjaként.

Alkalmazások és alkalmazások

A "Kis világ" grafikont különféle területeken modellezésre használják.

Alkalmazások a szociológiában

A Small World gráfok egyik előnye a társadalmi mozgás számára, hogy megvédik az erősen összekapcsolt csúcsokat használó szűrőeszközöktől . Egy másik előny az információátvitel jobb hatékonysága, miközben minimálisra csökkenti a hálózathoz való csatlakozáshoz szükséges kapcsolatok számát [24] .

A „kis világ” gráfmodell közvetlenül alkalmazható az affinitáscsoportok elméletére, amelyet William Finnegan szociológiai érvelésben mutatott be . Az affinitási csoportok olyan társadalmi mozgalmak, amelyek kicsik és félig függetlenek, de jelentős célokkal és célkitűzésekkel rendelkeznek. Annak ellenére, hogy az egyes résztvevők viszonylag függetlenek és önellátóak, több nagy fokú kapcsolódási képességgel rendelkező résztvevő a „Kisvilág” grafikon hubjainak felel meg – ezek különböző csoportokat összekötő csomópontok. Ez a Small World Earl-modell rendkívül hatékony taktikának bizonyult a rendőri akciók elleni tiltakozások szervezésére [25] . Clay Shirky azzal érvel, hogy minél inkább egy közösségi hálózat kis hálózatokon alapul, amelyek a „Kis világ” gráfot alkotják, annál értékesebbek a hálózat erősen összekapcsolt csomópontjai [24] . Ugyanez mondható el az affinitási csoportmodellről is, ahol minden csoportban néhány ember kötődik olyan külső csoportokhoz, amelyek sokkal nagyobb fokú mobilizációt és alkalmazkodást tesznek lehetővé. Ennek gyakorlati példája a "Kis világ" grafikonja az affinitási csoportokon keresztül, amelyet William Finnegan az 1999-es seattle -i tiltakozás során felvázolt

Alkalmazás a földtudományokban

Sok geológiában és geofizikában vizsgált hálózat jellemzőiben hasonló a Kisvilág gráfjához. A repedések és porózus anyagok rendszerében meghatározott hálózatok mutatják ezeket a jellemzőket [26] . A dél-kaliforniai régió szeizmikus hálózatai "Kisvilág" grafikonok lehetnek [27] . A fenti példák a térbeli léptékek széles skáláján fordulnak elő, bemutatva egy jelenség skálaváltozatlanságát a geotudományokban .

Alkalmazások a számítástechnikában

A „Kis világ” oszlopok segítségével értékelték a nagy adatbázisokban tárolt információk felhasználásának lehetőségét. Az értékelési intézkedés neve "Small World Data Transformation Measure" [28] [29] . Minél inkább úgy néznek ki az adatbázis-hivatkozások, mint egy kis világgrafikon, annál valószínűbb, hogy a felhasználó információkat nyerhet ki a jövőben. Ez a kényelem általában az ugyanazon a tárolóban tárolható információmennyiség rovására érhető el.

A Freenet P2P hálózat egy "kis világ" grafikont alkot [30] , amely lehetővé teszi az információk tárolását és helymeghatározását oly módon, hogy a hálózat növekedésével hatékonyan skálázható legyen.

Számítja a "kis világot" az agy neurális hálózataiban

Az agy anatómiai kapcsolatai [31] és a kortikális neuronok szinkronizációs hálózatai [32] a kisvilági grafikonok példái.

A neuronok „kis világa” grafikonja munkamemória -tulajdonságokat mutathat . A Solla és munkatársai [33] [34] számítógépes modelljének két stabil állapota van; ezt a tulajdonságot bistabilitásnak nevezik , és fontosnak tartják a memóriatárolásban . Az aktiváló impulzust a neuronok közötti kommunikációs tevékenység önfenntartó hurkai generálják. A második impulzus befejezi ezt a tevékenységet. Az impulzusok átkapcsolják a rendszert a stabil állapotok között: áramlás (rögzítési "memória") és nyugalmi állapot (memória tárolása).

Általánosabb szinten az agy sok nagy neurális hálózata, mint például a látórendszer és az agytörzs , a „kis világ” gráf tulajdonságait mutatja [35] .

A "kis világ" gráf a számítógépes nyelvészetben és szövegfeldolgozási problémákban

A nyelvek történetéről és fejlődéséről keveset tudunk. Minden nyelvnek vannak közös jellemzői: például szintaktikai és szemantikai kategóriák. A legtöbb nyelvet a Zipf-törvény jellemzi . A nyelvek különféle tulajdonságainak tanulmányozására szavak hálózatait használják (vagyis olyan hálózatokat, amelyekben a csúcsok a szavaknak, az élek pedig a szavak közötti kapcsolatoknak felelnek meg). A nyelvek fejlődésével kapcsolatos különféle hipotézisek alátámasztására is felhasználhatók. Például a nyelvek hasonlósága alapján arra a következtetésre jutnak, hogy közös ősük van. A hasonlóságot azonban okozhatja a nyelvek egymásra gyakorolt ​​hatása és a szavak kölcsönzése [36] .

Az angol WordNet szemantikai hálózatában a poliszémia óriási hatással van a szemantikai gráf szervezésére. Emiatt a szemantikai gráf a "Kisvilág" gráf [37] . A magas fokú csúcsok (hubok) olyan absztrakt fogalmakat reprezentáló csúcsok, mint a vonal, fej vagy kör [38] .

A természetes nyelvi feldolgozás  egyik feladata a szöveg szerzőjének azonosítása. Az egyik módszer a szerző invariánsának megtalálása . Először a szöveget dolgozzák fel, eltávolítják belőle a zajszavakat (elöljárószavakat, kötőszavakat stb.) . Ezután egy hálózat épül, amelyben a csúcsok a szavaknak felelnek meg, és a szövegben egymás mellett elhelyezkedő szavaknak megfelelő csúcsok közé húzzák az éleket. Megállapítást nyert, hogy az eredményül kapott gráf a "Kisvilág" gráf [39] . Ha kiszámítunk néhány paramétert egy irodalmi műre épített hálózatra (például egy csúcs átlagos foka, a klaszterezési együttható, a csúcsok fokszámának korrelációja), akkor láthatjuk, hogy egy szerző munkáiban ezek a paraméterek viszonylag kis tartományban változnak, míg a különböző szerzőknél ezek a paraméterek sokkal erőteljesebben térnek el [40] .

Ha a Wikipédia-cikkeket csúcsként, az oldalak közötti hivatkozásokat pedig a megfelelő csúcsok közötti élekként ábrázoljuk, akkor olyan gráfot kapunk, amely egy Small World gráf tulajdonságaival rendelkezik. Ennek oka a szavak szemantikai hálózatának „Kisvilág” gráfok osztályába való fentebb említett tartozása, valamint a csomópontként működő listák és kategóriák jelenléte a Wikipédiában. A Wikipédia magas fokú összekapcsolhatóságát a Connectedness projekt is támogatja [41] .

Kisvilág gráf linkhossz-eloszlással

A „Small World” gráfmodell a linkhosszak egyenletes eloszlását tartalmazza, egy hatványtörvény eloszlásnak engedelmeskedve, a két csúcs közötti átlagos távolság az eloszlás erősségétől függően változik [42] .

Decentralizált keresési algoritmus

Ha Stanley Milgram kísérletében a kutatónak pontosan a legrövidebb utat kell megtalálnia , akkor levelet kell küldenie minden ismerősének, és rá kell vennie őket erre. Egy ilyen " özönvíz " a hálózatban a lehető leggyorsabban eléri a célt, de egy ilyen tömeges postázás szinte lehetetlen. A kísérlet másik változata, hogy egyszerre csak egy személynek küldünk e-mailt. A Small World kísérlet eredményeként megdöbbentő algoritmikus felfedezés született: a Kisvilág rovatban azoknak az embereknek, akik nem ismerik a gráf teljes szerkezetét, de csak helyi információval rendelkeznek (ismerőseikről), közösen sikerül megtalálniuk egy viszonylag rövid út a célhoz (a viszonylag rövid út jelenléte a „kis világ” típusú gráfok jól ismert tulajdonsága) [43] .

Felmerül a kérdés: miért van a közösségi hálózat úgy felépített, hogy egy ilyen decentralizált keresési algoritmus optimális eredményt adjon? Hasonló decentralizált keresési algoritmusok működnek a világhálón , a neurális hálózatokban és sok más területen is. Ezért a decentralizált keresési algoritmusok algoritmusainak megértése biztosítja azok széles körű alkalmazását [44] .

A további érveléshez szükséges a decentralizált keresési algoritmus szigorúbb definíciójának megfogalmazása. Az algoritmus rekurzív: a csúcson állunk, el kell érnünk a csúcsot , csak a csúcs szomszédjait ismerjük , közülük kell kiválasztani egy csúcsot , és abból futtatni az algoritmust. A decentralizált algoritmust a szállítási idő  – a cél eléréséhez szükséges lépések várható száma – becsüli meg, míg a Small World gráfot, a kezdő- és célcsúcsokat véletlenszerűen generálják. A kutatás célja olyan decentralizált keresési algoritmusok megtalálása, amelyek tekintetében polilogaritmikus . Ezeket a tanulmányokat John Kleinberg végezte "Complex networks and decentralized search algoritms" [44] című munkájában .

Lásd még

Jegyzetek

  1. ↑ 1 2 Kisvilági hálózatok kollektív dinamikája .
  2. ↑ Alekszej Savvatejev: Az internet és a közösségi hálózatok modelljei / Habr . Letöltve: 2022. április 27. Az eredetiből archiválva : 2022. április 27..
  3. ↑ Barthelmy és Amaral, 1999 .
  4. ↑ Barrat és Weigt .
  5. ↑ Dorogovcev és Mendes .
  6. ↑ Barmpoutis és Murray .
  7. ↑ Összetett hálózatok Szerkezet és dinamika , p. nyolc.
  8. ↑ Humphries, 2007 .
  9. ↑ Telesford, Joyce, Hayasaka, Burdette, Laurienti, 2011 .
  10. ↑ Cohen és Havlin és ben-Avraham, 2002 .
  11. ↑ A skálamentes hálózatok ultrakicsiek, 2003 .
  12. ↑ Proteins, 2004 , p. 292–299.
  13. ↑ Génhálózat, 2004 , p. 280-4.
  14. ↑ Che, Ali, Reynolds, 2010 .
  15. ↑ Kézikönyv a biológiai hálózatokról, 2010 , p. 23.
  16. ↑ szabadalom .
  17. ↑ Lamanna, Longo, 2007 , p. 90.
  18. ↑ Robust Road Networks tervezése, 2010 , p. 13.
  19. ↑ Protein Interaction, 2006 , p. 17.
  20. ↑ Fraktálok időkésleltetéssel, 2002 , p. 215-219.
  21. ↑ Káosz a kisvilágú hálózatokban, 2001 .
  22. ↑ Átmenet a káoszba .
  23. ↑ Barmpoutis, Murray, 2010 .
  24. ↑ 12 Shirky , 2008 .
  25. ↑ Finnegan, 2003 .
  26. ↑ Yang, 2001 .
  27. ↑ Jimenez, Tiampo, Posadas, 2008 .
  28. ↑ Információelmélet és üzleti intelligencia stratégia .
  29. ↑ Hillard, 2010 .
  30. ↑ Sandberg .
  31. ↑ Sporns, 2004 .
  32. ↑ Yu, 2008 .
  33. ↑ Cohen .
  34. ↑ Solla .
  35. ↑ Humphries, 2007 , p. 367-375.
  36. ↑ Talp .
  37. ↑ WordNet , p. egy.
  38. ↑ WordNet .
  39. ↑ Antiqueira , p. négy.
  40. ↑ Antiqueira .
  41. ↑ Masucci .
  42. ↑ Térbeli beágyazott hálózatok dimenziója, 2011 .
  43. ↑ Kleinberg, 2006 , p. 5.
  44. ↑ Kleinberg 12. , 2006 , p. 6.

Irodalom

Linkek