Önszerveződő adatbázisok
High Speed Networks Laboratory
1/40
Önszerveződő adatbázisok Hosszu Éva
Önszerveződő adatbázisok 1.
Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → Evolúció alkotta adatbázis
2.
3.
Önszerveződő adatbázis: struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok
• Preferenciális kapcsolódás
4.
Lekérdezés • Lekérdezés önszerveződő adatbázisokban • Internetes keresőmotorok működésének alapjai
2/40
Önszerveződő adatbázisok Hosszu Éva
Paradigmaváltás az adatbázisokban • Mennyi zenét tárolsz a
számítógépeden? • Régen: rengeteg zene a
számítógépen • Hatalmas adatbázisban • Viszonylag struktúrálva • Most: Kevés zene a gépen, csak
amire azonnal szükség van • Túlnyomó részben: YouTube, Spotify, Tidal, Google, … • Egy struktúrálatlan halmazból keressük ki 3/40
Önszerveződő adatbázisok Hosszu Éva
Paradigmaváltás az adatbázisokban • Eddig • Relációs adatbázis • Elosztott adatbázis • Lekérdezés: erősen megnövelte a
kommunikációs költségek részarányát az adatbázis-kezelés költségein belül • Ötlet: próbáljuk meg az adatokat a felhasználás közelében elhelyezni. • Osztott adatbázisok. • Az osztott adatbázis egy fizikailag
megosztott, de logikailag egységes adatbázis.
4/40
Önszerveződő adatbázisok Hosszu Éva
Amerre mozdul a világ: • Megtervezett adatbázis → evolúció alkotta adatbázis • Elosztott adatbázisok: • A kommunikációs költségek csökkenése. • Mindenki a számára ismerős adatokat gondozza. • Egy-egy csomópont kiesése esetén a többi adatai továbbra is
elérhetőek. • Lehetséges a moduláris tervezés, a rugalmas konfigurálás. • Rugalmasabb adatstruktúra kell • Önszerveződő adatbázisok: • A kapcsolódást nem egy központi egység határozza meg • A csomópontok saját maguk döntik el, hova kapcsolódnak 5/40
Önszerveződő adatbázisok Hosszu Éva
Önszerveződő adatbázisok 1.
Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → Evolúció alkotta adatbázis
2.
3.
Önszerveződő adatbázis: struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok
• Preferenciális kapcsolódás
4.
Lekérdezés • Lekérdezés önszerveződő adatbázisokban • Internetes keresőmotorok működésének alapjai
6/40
Önszerveződő adatbázisok Hosszu Éva
Mit az önszerveződő adatbázis? • A szó tág értelmében • Önszerveződő adatbázis = (struktúra,lekérdezés) • Az adatbázis önszerevződő jellege meghatározza a kialakuló topológiát • A topológia meghatározza, milyen a hatékony keresés • Önszerveződő adatbázis példák: • Internet • Blogok • Google Fordító • Szocális hálózat • P2P hálózat
7/40
Önszerveződő adatbázisok Hosszu Éva
Önszerveződő hálózat: Az Internet • Általános értelemben: Nagy bonyolult hálózatok • Hálózat komplexitása • Sok csomópont • Sok kapcsolat • Heterogén csomópont típusok és kapcsolattípusok • Tisztán kivehető tendencia: kommunikációs hálózatok egyre
bonyolultabbakká válnak • Az Internet fejlődési trendek • • • •
Felhasználók számának drámai növekedése Kicsi mobil eszközök Szerteágazó szabványok, sok gyártó Heterogén eszközök Virtuális hálózatok fizikai hálózakon – VPNs, virtual ISPs
• Milyen struktúra lakozik a komplexitás mögött?
8/40
Önszerveződő adatbázisok Hosszu Éva
Pillanatfelvételek • A hálózatok dinamikusak • Még jó, annyira gyorsan változnak az igények • Jelenleg nincs lehetőség a dinamizmus vizsgálatára nagy
léptékben • Legtöbb adatbázis csak a pillanatnyi állapotot tárolja • Ezért egy-egy elemzés csak egy pillanatfelvétel • Előfordulnak statisztikai hibák • Néha később módosított eredmények
9/40
Önszerveződő adatbázisok Hosszu Éva
Önszerveződő adatbázisok 1.
Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → Evolúció alkotta adatbázis
2.
3.
Önszerveződő adatbázis : struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok
• Preferenciális kapcsolódás
4.
Lekérdezés • Lekérdezés önszerveződő adatbázisokban • Internetes keresőmotorok működésének alapjai
10/40
Önszerveződő adatbázisok Hosszu Éva
Számunkra jelenleg lényeges paraméterek 1. Hálózat méret: Csomópontok száma • Ezres, milliós, esetleg milliárdos méretek esetén lehet statisztikai adatokkal jól jellemezni egy hálózatot 2. Klaszterezettség: “Csoportosulás” mértéke • A szomszéd node-jaim kapcsolódnak-e egymáshoz? Ha 1 akkor mindig, ha 0 akkor soha! 3. Átmérő: Kis átmérő, rövid utak, “kisvilág” jelleg • Egy rácsban igen nagy átmérők lehetnek, míg pl. a teljes gráf átmérője 1. 4. Hasonlósági paraméter (γ): Mennyire hasonló a
szerepük? (skálafüggetlen szerkezet) •
Ha a szám magas, akkor az egyének nagyon hasonlítanak, ha alacsony akkor (~ 2) akkor erősen eltérő szerepek vannak
5. Fokszámeloszlás: a csúcsok mekkora hányadának k a
fokszáma?
• Egyenletes? Binomiális? Valami más?
11/40
Önszerveződő adatbázisok Hosszu Éva
Méret és átmérő • Mekkora egy önszerveződő adatbázis? • Csomópontok száma: néhány tíz – milliárdok
• Mekkora az adatbázis átmérője? • 1929: Karinthy Frigyes – Láncszemek • Hat lépés távolság • 1967: Milgram—kísérlet (a másik) • Levélküldés nagy távolságra (szociológiai, földrajzi), véletlenszerűen választott emberek • Információk a célszemélyről • Személyes ismeretség esetén azonnal a célhoz • Egyébként olyanhoz aki valószínűleg személyesen ismeri+levél a Harvardra
12/40
Önszerveződő adatbázisok Hosszu Éva
Milgram kísérlete (további részletek) • • •
Néha 1-2 lépés elég volt néha kilenc kellett 296 levélből 232 nem ért célba A maradékból az átlagos távolság 5.5-nek adódott (ellentmondott a tapasztalatokkal, és várakozásokkal)
• Az utolsó személy igen sokszor ugyanaz • Legtöbbször gyorsan földrajzi közelbe értek, ahol köröztek, amíg rést nem találtak a célszemély belső köreibe • Problémák • Kevés célbeérkező levél • Emiatt hosszabb láncok kevésbé vannak jelen (alábecslés)
• Többször ismételték •
2002-ben e-mail verzió
•
2008, Microsoft .NET Messenger Service: 6.6
• Hatlépésnyi távolság
13/40
Önszerveződő adatbázisok Hosszu Éva
Átmérő
• Példa: Rubik-kocka állapotai
14/40
Önszerveződő adatbázisok Hosszu Éva
Átmérő •
15/40
Önszerveződő adatbázisok Hosszu Éva
The Anatomy of the Facebook Social Graph • Ugander, Karrer, Backstrom, Marlow • arXiv: 1111.4503v1 [cs.SI] • 2011. májusi állapot elemzése • Aktív felhasználók: 1. Bejelentkezett a vizsgálatot megelőző 28 napban 2. Van legalább 1 ismerőse • 721 millió aktív felhasználó (a Föld
lakossága akkor 6.9 milliárd) • 68.7 milliárd kapcsolat • átlagosan 190 ismerős
16/40
Önszerveződő adatbázisok Hosszu Éva
Felhasználók közti átlagos távolság • 4.7 lépés távolság • USÁ-n belül: 4.3 • Független
tanulmány: átmérő ~40 • Az átmérő
önmagában megtévesztő
17/40
Önszerveződő adatbázisok Hosszu Éva
Csoportosulás mértéke • A weboldalak jellemzően szoktak egymásra mutatni • Minél több közös oldalra mutatnak, annál nagyobb valószínűséggel
egymásra is • Melyik tűnik hihetőbbnek mint weboldalak hálózata? Miért?
18/40
Önszerveződő adatbázisok Hosszu Éva
Klaszterezettségi együttható • Globális: • 𝐶=
ℎá𝑟𝑜𝑚𝑠𝑧ö𝑔𝑒𝑘 𝑠𝑧á𝑚𝑎 𝑡𝑟𝑖𝑝𝑙𝑒𝑡𝑒𝑘 𝑠𝑧á𝑚𝑎
• a háromszögek
számának aránya ahhoz képest, hogy mennyi lehetne
C=1
• Lokális:
a kék csúcsra vonatkozóan ckék=1 • 𝐶𝑖 =
2∗𝑠𝑧𝑜𝑚𝑠𝑧é𝑑𝑜𝑘 𝑘ö𝑧ö𝑡𝑡𝑖 é𝑙𝑒𝑘 , 𝑁 𝑖 ∗(𝑁 𝑖 −1)
ckék=1/3
ckék=0
ahol N(i) = #{i szomszédai} 19/40
Önszerveződő adatbázisok Hosszu Éva
Egy adatbázisban
20/40
Önszerveződő adatbázisok Hosszu Éva
Kisvilág-tulajdonság •
21/40
Önszerveződő adatbázisok Hosszu Éva
Fokszámeloszlás • A csúcsok mekkora hányadának k a fokszáma • nk = hány k fokszámú csúcs van 𝑛 • P(k) = k, n a csúcsok száma 𝑛
• hisztogram
22/40
Önszerveződő adatbázisok Hosszu Éva
Fokszámeloszlás • Binomiális
𝑛
• 𝑃 𝑘 = 𝑘 𝑝𝑘 (1 − 𝑝)𝑛−𝑘 • Véletlen hálózat • Nyerőgép
• Hatványfüggvény • 𝑃 𝑘 ~ 𝑘 −γ • γ: Hasonlósági paraméter • Önszerveződő hálózatok
23/40
Önszerveződő adatbázisok Hosszu Éva
Skálafüggetlenség • A fokszámeloszlás hatványfüggvényt követ
24/40
Önszerveződő adatbázisok Hosszu Éva
Skálafüggetlenség szemléletesen 1.
A hálózatra rázoomolva önhasonló szerkezet • Pont így van a természetben is
2.
Nem heterogén szerepű csomópontok • Néhány központ, sok kis node
25/40
Önszerveződő adatbázisok Hosszu Éva
Valós hálózatok
26/40
Önszerveződő adatbázisok Hosszu Éva
Hogyan kapcsolódnak új pontok az adatbázishoz? • Egy már meglévő adatbázis melyik
pontjához fogunk kapcsolódni? • P2P hálózatban melyik fájlt töltöd le? • Egy nemzetségen belül melyik fajok szaporodnak el? • Minél népszerűbb • Népszerűség ~ minél több
kapcsolata van eddig
27/40
Önszerveződő adatbázisok Hosszu Éva
Preferenciális kapcsolódás • Preferenciális kapcsolódás A kapcsolódáshoz a jelölt esélye arányos a fokszámmal Nagyobb fokszámú csúcshoz nagyobb eséllyel kapcsolódik i csúcsra: 𝑝𝑖 =
𝑓𝑜𝑘𝑠𝑧á𝑚 2∗é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎
• A gazdag egyre gazdagabb
lesz • Növekedéssel együtt: skálafüggetlen hálózat
28/40
Önszerveződő adatbázisok Hosszu Éva
Szűkebb értelemben vett önszerveződő hálózatok
• Speciális értelemben 1. Nem véletlenszerű kapcsolatok, “csoportosuló” 2. Kis átmérő, rövid utak, kisvilág 3. Skálafüggetlen szerkezet: erősen változó szerepek a hálózatban
29/40
Önszerveződő adatbázisok Hosszu Éva
Önszerveződő adatbázisok 1.
Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → Evolúció alkotta adatbázis
2.
3.
Önszerveződő adatbázis : struktúra, lekérdezés Struktúra: a hálózatot meghatározó jellemzők • Méret, átmérő • Kisvilág tulajdonság • Skálafüggetlen hálózatok
• Preferenciális kapcsolódás
4.
Lekérdezés • Lekérdezés önszerveződő adatbázisokban • Internetes keresőmotorok működésének alapjai
30/40
Kisvilág-hálózat Kleinberg modellje • Jon Kleinberg: Nem csak a topológia érdekes, hanem hogy
gyorsan meg is lehet találni a célt, térkép nélkül • Az optimális modell kereséshez
High Speed Networks Laboratory
• Távolság: d(u,v) lépkedések
száma a szomszédokon • A rácson két pont között az kapcsolat valószínűsége ~ d(u,v)-r • Mohó keresési algoritmus 31/40
Önszerveződő adatbázisok Hosszu Éva
Navigálás a Kleinberg-modellben • Keresés egy kisvilág-adatbázisban • A rácson két pont között az kapcsolat valószínűsége ~ d(u,v)-r
• gyorsan meg is lehet találni a célt, térkép nélkül = mohó
keresés
32/40
Önszerveződő adatbázisok Hosszu Éva
Hogyan működnek a keresőmotorok?
33/40
Önszerveződő adatbázisok Hosszu Éva
Internetes keresőmotorok • A keresőmotorok két fő funciója 1. Crawling és az oldalak térképének felépítése 2. Válasz a lekérdezésre 1.
Crawling & Indexing • A weben levő dokumentumok, fájlok, oldalak bejárása és indexelése • Indexelés ~ tárgymutató egy könyv végén
2. Válaszadás a felhasználói lekérdezésre • Releváns oldalak listája • Sorrend
34/40
Önszerveződő adatbázisok Hosszu Éva
Honnan tud a keresőmotor egy oldalról? 1.
Megmondjuk, hogy létezik • Home page URL-je • www.google.com/addurl • search.yahoo.com/info/submit.html • search.live.com/docs/submit.aspx • XML oldaltérkép
2.
Ha egy másik oldal mutat rá: keresőrobotok beindexelik • Struktúra miatt működik • A kapcsolatok mentén a keresőmotor bejárja = crawling • Ha találnak egy új oldalt: részleteket tárolnak
35/40
Önszerveződő adatbázisok Hosszu Éva
Egy Google keresés
36/40
Önszerveződő adatbázisok Hosszu Éva
Adjunk választ! • A keresőmotor egy válaszadó gép • Háromféle keresés: • "Do" Tranzakciós keresés – valami végrehajtása: repülőjegy vásárlás, zenehallgatás • "Know" Információs keresés – egy zenekar neve, a város legjobb étterme • "Go" Navigációs keresés – Kifejezetten egy weblap keresése: menj a Facebook-ra, az NFL homepage-re • Csak az a válasz érdekel, ami relevéns • Hasznosság remélt sorrendjében
• A relevancia több, mint hogy “tartalmazza a jó szavakat” • A keresőmotorok első napjaiban ennyi volt • Nem is működött jól • AltaVista → Google 37/40
Önszerveződő adatbázisok Hosszu Éva
Search Engine Optimization • Egy weboldal láthatóságának befolyásolása egy keresőmotor találati
listájában • Nem a keresőmotorok kijátszása
• Jó felhasználói élmény • Az oldal szándékainak közvetítése, hogy a releváns kereséseknél
ajánlhassák • robots.txt: amit a keresőrobotok ne járjanak be • Bejelentkezés után látható oldalak • Személyes információt tartalmazó oldalak: vásárlás • Oldalon belüli keresési eredmények • Korai algoritmusok: • Szerepelnek-e a megadott szavak • Kulcsszó-sűrűség • Keyword meta-tag • Könnyű volt kijátszani 38/40
Önszerveződő adatbázisok Hosszu Éva
Mennyire fontos egy oldal? • A legtöbb keresőmotornál: fontosság = népszerűség • Minél népszerűbb egy oldal, annál fontosabb kell legyen az infó, ami rajta van • Algoritmusokkal szűrik és rangsorolják az oldalakat relevancia és népszerűség alapján
• Ranking faktorok • Tartalom: Az oldal szövege, címek, ismertetők. • Teljesitmény: Milyen gyors? Jól működik? • Megbizhatóság: Elég jó a tartalom ahhoz, hogy más oldalak ide mutassanak? Más oldalak megjelölik referenciaként? • Felhasználói élmény: Hogy néz ki? Könnyű eligazodni? Magas a bounce rate?
39/40
Önszerveződő adatbázisok Hosszu Éva
SEO Success Factors
40/40
Önszerveződő adatbázisok Hosszu Éva
Search Engine Optimization • Oda-vissza ható folyamat • Algoritmus → helyezést javító trükkök → új algoritmus → új trükkök → … • Hogy pontosan hogy működik, azt a tapsztalat alapján sejteni lehet • On-the-page SEO Ami az oldal szerzőjének befolyása alá tartozik • Tartalom • HTML • Felépítés • Off-the-page SEO Az olvasókon, látogatókon és a többi oldal szerzőjén múlik • Linkek • Megbízhatóság • Közösségi média • Személyes paraméterek 41/40
Önszerveződő adatbázisok Hosszu Éva
Search Engine Optimization • White Hat technikák • A felhasználónak szóljon az oldal, ne a keresőnek • A weboldal struktúráját tagolttá kell tenni, megfelelő header használattal. • •A
taget megfelelően kell kitölteni. • •Az oldalon elhelyezett szövegeket is érdemes optimalizálni. • •Helyezzünk el olyan linkeket, amik egyéb aloldalakra mutatnak. • Hosszú távú eredmény • Black Hat technikák • Hogyan tévesszük meg a keresőt • Láthatatlan tartalom • Más oldal megjelenítése, ha a kereső kéri = cloaking • Gyors eredmény, de: ha a kereső rájön: büntetés<br />
<br />
42/40<br />
<br />
Szervező erők adatbázisokban<br />
<br />
High Speed Networks Laboratory<br />
<br />
43/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Szervező erők az adatbázisokban 1.<br />
<br />
Bevezető • Áttekintés: mi az önszerveződő adatbázis? • Mi a szervező erő?<br />
<br />
2.<br />
<br />
A folyamat mögötti dinamika: játékelmélet • Bevezető példa: fogolydilemma • Alapfogalmak, Nash-egyensúly<br />
<br />
3.<br />
<br />
Az adatforgalom modellezése játékelmélettel • Optimális átvitel vs. átvitel önszerveződő hálózatban<br />
<br />
44/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Paradigmaváltás az adatbázisokban • Megtervezett adatbázis → evolúció alkotta adatbázis • Mennyi zene / film van a számítógépeden?<br />
<br />
• Rugalmas adatstruktúra kell • Önszerveződő adatbázisok: • A kapcsolódást nem egy központi egység határozza meg • A csomópontok saját maguk döntik el, hova kapcsolódnak • Struktúra és lekérdezés • Az adatbázis önszerevződő jellege meghatározza a kialakuló topológiát • A topológia meghatározza, milyen a hatékony keresés • Internet, Blogok • Google Fordító • Szocális hálózat • P2P hálózat<br />
<br />
• Folding@home 45/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Struktúra és lekérdezés: hálózatparaméterek 1. Hálózat méret: Csomópontok száma • Ezres, milliós, esetleg milliárdos méretek esetén lehet statisztikai adatokkal jól jellemezni egy hálózatot 2. Klaszterezettség: “Csoportosulás” mértéke • A szomszéd node-jaim kapcsolódnak-e egymáshoz? Ha 1 akkor mindig, ha 0 akkor soha! 3. Átmérő: Kis átmérő, rövid utak, “kisvilág” jelleg • Egy rácsban igen nagy átmérők lehetnek, míg pl. a teljes gráf átmérője 1. 4. Hasonlósági paraméter (γ): Mennyire hasonló a<br />
<br />
szerepük? (skálafüggetlen szerkezet) •<br />
<br />
Ha a szám magas, akkor az egyének nagyon hasonlítanak, ha alacsony akkor (~ 2) akkor erősen eltérő szerepek vannak<br />
<br />
5. Fokszámeloszlás: a csúcsok mekkora hányadának k a<br />
<br />
fokszáma?<br />
<br />
• Egyenletes? Binomiális? Valami más?<br />
<br />
46/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Struktúra és lekérdezés • Evolúció alkotta adatbázis 1. Nem véletlenszerű kapcsolatok, “csoportosuló” 2. Kis átmérő, rövid utak, kisvilág 3. Skálafüggetlen szerkezet: erősen változó szerepek a hálózatban<br />
<br />
47/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Preferenciális kapcsolódás • Egy már meglévő adatbázis melyik<br />
<br />
pontjához fogunk kapcsolódni? • Minél népszerűbb • Népszerűség ~ minél több<br />
<br />
kapcsolata van eddig • Preferenciális kapcsolódás A kapcsolódáshoz a jelölt esélye arányos a fokszámmal<br />
<br />
• A gazdag egyre gazdagabb lesz • Növekedéssel együtt:<br />
<br />
skálafüggetlen hálózat<br />
<br />
48/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Struktúra és lekérdezés • Keresőmotorok 1. 2. 3.<br />
<br />
Feltérképezés: crawling & indexing Adjunk releváns választ Search Engine Optimization<br />
<br />
49/40<br />
<br />
Kisvilág-hálózat Kleinberg modellje • Jon Kleinberg: Nem csak a topológia érdekes, hanem hogy<br />
<br />
gyorsan meg is lehet találni a célt, térkép nélkül • Az optimális modell kereséshez<br />
<br />
High Speed Networks Laboratory<br />
<br />
• Távolság: d(u,v) lépkedések<br />
<br />
száma a szomszédokon • A rácson két pont között az kapcsolat valószínűsége ~ d(u,v)-r • Mohó keresési algoritmus 50/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Navigálás a Kleinberg-modellben • Keresés egy kisvilág-adatbázisban • A rácson két pont között az kapcsolat valószínűsége ~ d(u,v)-r<br />
<br />
• gyorsan meg is lehet találni a célt, térkép nélkül = mohó<br />
<br />
keresés<br />
<br />
51/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Szervező erők az adatbázisokban 1.<br />
<br />
Bevezető • Áttekintés: mi az önszerveződő adatbázis? • Mi a szervező erő?<br />
<br />
2.<br />
<br />
A folyamat mögötti dinamika: játékelmélet • Bevezető példa: fogolydilemma • Alapfogalmak, Nash-egyensúly<br />
<br />
3.<br />
<br />
Az adatforgalom modellezése játékelmélettel • Optimális átvitel vs. átvitel önszerveződő hálózatban<br />
<br />
52/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Játékelmélet, mint szervező erő • Neumann János – 1928 • A fejszámológép :) • A legyes feladat megoldója<br />
<br />
• mi a racionális viselkedés olyan<br />
<br />
helyzetekben, ahol minden résztvevő döntéseinek eredményét befolyásolja a többiek lehetséges választása • stratégiai problémák elmélete • Hogyan jelentkezik az<br />
<br />
önszerveződő adatbázisokban? • Milyen dinamikákban ismerhető fel?<br />
<br />
53/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Játékelmélet, mint szervező erő • Egyensúly megtalálása • Trade-off keresése • gyors keresés vs. bonyolultság • Evolúciós szerveződés vs. tervezett struktúra • Mit csináljunk este?<br />
<br />
54/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Bevezető példa: fogolydilemma • Egy bűncselekmény • • •<br />
<br />
•<br />
<br />
két gyanúsítottal Mindkettő hallgat: egyegy év Mindkettő bevallja: ötöt év Egyik hallgat, másik bevallja: hallgató 20 év, másik szabadul Mi fog történni?<br />
<br />
55/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Fogolydilemma folytatás • Ugyanez a helyzet: • Doppingolás sportversenyen • Cigaretta-reklámozás két gyártó között • Fegyverkezés a hidegháborúban<br />
<br />
56/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Alapfogalmak • Játék, játékosok: A és B • Stratégia: egy játékos lehetséges választási lehetőségei • Lehetséges stratégiák halmaza 1. (confess,confess) 2. (confess, silent) 3. (silent, confess) 4. (silent, silent)<br />
<br />
• Kifizetési (payoff) matrix • cél: a kifizetést minimalizálni<br />
<br />
57/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Alapfogalmak: legjobbválasz-leképezés • Egy játékos legjobbválasz-leképezése: az a stratégia, ami a többi<br />
<br />
játékos adott stratégiája esetén a legkedvezőbb eredményt adja, • Attól kérjük a csomagot egy P2P hálózatban, akitől várhatóan a<br />
<br />
leggyorsabban tudjuk letölteni • Arra megyünk, amerre a legrövidebb az út<br />
<br />
58/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Alapfogalmak: Nash-egyensúly • John Nash • Amerikai matematikus • Közgazdasági Nobel-díj 1994 • Egy csodálatos elme • Nash-egyensúly • Legjobbválasz-leképezés a többiek stratégiájára • Olyan eleme a stratégiahalmaznak, ahonnan senkinek se éri meg elmozdulni, ha a többiek nem változtatnak<br />
<br />
• ZH-n ha mindenki puskázik<br />
<br />
59/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Nash-egyensúly • Mi lesz a Nash-egyensúlyi pont? • (vall,vall) • Ha A vall, B-nek nem éri meg hallgatni • Ugyanígy fordítva<br />
<br />
• Kívülálló szemszögéből nem mindig<br />
<br />
látszik racionálisnak • Érezzük, hogy jobban járnának, ha mindketten hallgatnának • De mégsem • Ezért van egyáltalán a lehetőség,<br />
<br />
hogy valljanak<br />
<br />
60/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Nash-egyensúly megtalálása 1.<br />
<br />
Megsejtjük, és leellenőrizzük a definíciót.<br />
<br />
• Ráérzünk, hogy a (vall,vall) a<br />
<br />
Nash-egyensúlyt adó stratégia • A ráérzünk része felvet némi<br />
<br />
problémát, de ettől most eltekintünk… • Ellenőrizendő: feltéve, hogy a másik<br />
<br />
résztvevő nem mozdul el, nem éri meg változtatni<br />
<br />
61/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Nash-egyensúly megtalálása 2.<br />
<br />
Dominált stratégiák eliminálásával<br />
<br />
• Dominált stratégia: A játékos s<br />
<br />
stratégiája dominált, ha van olyan stől különböző si stratégia, hogy B játékos minden választására jobban megéri s helyett si-t választani • Ha ezek sorozatos elhagyása után<br />
<br />
egyetlen stratégia-pár marad, akkor az Nash-egyensúly • A-nál és B-nél is a “remain silent” dominált stratégia<br />
<br />
62/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Feladat: Nash-egyensúly megtalálása • Dominált stratégiák elhagyásával keressük meg a Nash-egyensúlyi<br />
<br />
pontot az alábbi kifizetési mátrixban!<br />
<br />
63/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Feladat: Nash-egyensúly megtalálása • Dominált stratégiák elhagyásával keressük meg a Nash-egyensúlyi<br />
<br />
pontot az alábbi kifizetési mátrixban!<br />
<br />
64/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Szervező erők az adatbázisokban 1.<br />
<br />
Bevezető • Áttekintés: mi az önszerveződő adatbázis? • Mi a szervező erő?<br />
<br />
2.<br />
<br />
A folyamat mögötti dinamika: játékelmélet • Bevezető példa: fogolydilemma • Alapfogalmak, Nash-egyensúly<br />
<br />
3.<br />
<br />
Az adatforgalom modellezése játékelmélettel • Optimális átvitel vs. átvitel önszerveződő hálózatban<br />
<br />
65/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A játékelmélet önszerveződő adatbázisokban • Játékelmélet: egyensúly megtalálása • Trade-off • Bonyolultság vs. gyorsaság • Tervezés vs. • Egy önszerveződő hálózatban: hogyan dől el, hogy ki mit merre küld? • Evolúció alkotta hálózat: összekapcsolódtak: utána a struktúra már<br />
<br />
megvan, merre továbbítanak? • Merre megy az adat?<br />
<br />
66/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúlyi forgalom • x = 4000 csomagot küld PeerA a PeerB-nek • Egy él súlya: az átviteli idő • pay-off = az áltviteli idő ellentettje • Mennyi idő alatt ér célba?<br />
<br />
67/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Nash-egyensúly az előző hálózatban • Egy Nash-egyensúly: egyenlően elosztják egymást 1.<br />
<br />
Ez tényleg Nash-egyensúly • Próbáljuk ki, ha valaki változtatni akar • Amerre ő megy, 2001/100 + 45 az átvitel ideje > 65 • Jobban megéri nem váltani<br />
<br />
2. Nincs másik • Tegyük fel, hogy van valami más elosztás, ami egyensúly • Aki a lassabb úton van, annak megéri átváltani a gyorsabbra • Egyenlő elosztás jön ki<br />
<br />
68/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess paradoxon • Mi a paradoxon?<br />
<br />
69/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess paradoxon • Adjunk hozzá egy új élet a hálózathoz!<br />
<br />
70/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess paradoxon • Azt várjuk, hogy ha javítunk a hálózaton, egyensúlyi helyzetben<br />
<br />
gyorsabb lesz az átvitel • Naná, rövidítünk, csak nem romlik el…<br />
<br />
• De! a Nash-egyensúlyi pont hosszabb időt jelent • Volt: fele A → C → B,<br />
<br />
fele A → D → B • Mindenkinek megéri az A → C → D → B-t választani • Valóban Nash-egyensúly<br />
<br />
• Összes idő 40 + 40 = 80 • Szemben az eddigi 65-tel<br />
<br />
71/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess-paradoxon: gyakorló feladat • PeerA és PeerB két nagy csomagot küld, x=2000 és y=2000 méretűek • Írjuk fel mátrix-alakban az átfutási időket! • Mutassuk meg, hogy ha mindketten az A → C → D → B-t választják, az<br />
<br />
Nash-egyensúly!<br />
<br />
72/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess-paradoxon: gyakorló feladat • PeerA és PeerB két nagy csomagot küld, x=2000 és y=2000 méretűek • Írjuk fel mátrix-alakban az átfutási időket! • Mutassuk meg, hogy ha mindketten az A → C → D → B-t választják, az<br />
<br />
Nash-egyensúly!<br />
<br />
73/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess-paradoxon: gyakorló feladat • PeerA és PeerB két nagy csomagot küld, x=2000 és y=2000 méretűek • Írjuk fel mátrix-alakban az átfutási időket! • Mutassuk meg, hogy ha mindketten az A → C → D → B-t választják, az<br />
<br />
Nash-egyensúly!<br />
<br />
• x-nek az ACB és az ADB is dominált stratégia, mindkettő ACDB által • y-nak szintén 74/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Braess-paradoxon: megjegyzések • Intuíció: ha upgrade-elünk valamit, akkor az jobb lesz • Paradoxon: egy új kapcsolat hozzáadásával lassabb lett az átvitel • Pl. fogolydilemmában a Vall opció hozzáadása a Hallgathoz<br />
<br />
• Egyetlen él behúzásával mennyire romlik el a költség? • Legfeljebb 4/3-szorosára nő • Az előző példa a legrosszabb, ami előfordulhat • Felmerülő kérdések: 1. 2. 3. 4. 5.<br />
<br />
Van-e egyensúlyi forgalomminta? Ha igen, van-e olyan, aminek a költsége nincs túl messze a közösségi optimumtól? Milyen az a hálózat, amiben beáll az optimum? Hogyan tervezhető olyan hálózat, ami kivédi a rossz egyensúlyi helyzeteket? Mennyivel lehet rosszabb az egyensúly az optimálisnál? 75/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly vs optimum • Már láttuk: átviteli idő az egyensúlyban nem biztos, hogy optimális • Mennyire lehetünk messze az optimumtól? • Minden élre: travel-time függvény • Forgalomminta: a küldött csomagok • Lineáris, átmenő forgalom függvénye által választott útvonalak összessége • Te(x) = aex+be<br />
<br />
76/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly vs optimum • Közösségi költség: a forgalommintához tartozó átviteli idők összege • Egyensúlyi költség: közösségi költség a Nash-egyensúlyi állapotban • Közösségi optimum: a lehető legkisebb közösségi költségű állapot<br />
<br />
• Két fontos kérdés: 1. 2.<br />
<br />
Van-e egyensúlyi állapotra vezető forgalomminta? Ha igen, van-e olyan, aminek a költsége nincs túl messze a közösségi optimumtól? 77/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Forgalmi minta megtalálása az egyensúlyban • Adunk egy algoritmust, ami konkrétan talál egyet, majd megmutatjuk,<br />
<br />
hogy az helyes LEGJOBBVÁLASZ-ALGORITMUS 1. Kiidulás: egy tetszőleges forgalmi minta 2. Ha egyensúly KÉSZ 3. Egyébként: létezik legalább egy csomag, aminek a legjobbválasza a<br />
<br />
többire egy gyorsabb út • Válasszunk egy tetszőleges ilyet; az váltson át erre 4. GOTO 2. • Ha valaha is megáll: • Mindenki olyan állapotban van, ami legjobbválasz-leképezés a helyzetre • Azaz Nash-egyensúly<br />
<br />
• Kell: egy idő után megáll • Nem triviális, hogy megáll • Pl. Matching Pennies játék 78/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A javulás mértéke: mennyire jó az aktuális megoldás? • Adódik: közösségi költség • Van olyan legjobbválasz, amitől nő, és van olyan, amitől csökken • Helyette: egy forgalomminta potenciális energiája • A hálózat élein a potenciális energiák összege • Egy él potenciális energiája • x csomagot küld •<br />
<br />
79/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly beállása • Legjobbválasz-leképezés lépésekkel a forgalomminta potenciális<br />
<br />
energiája csökken<br />
<br />
80/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly beállása<br />
<br />
81/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Állítás: A Legjobbválasz-algoritmus megáll Bizonyítás: elég azt megmutatni, hogy a legjobbválasz-leképezések során a potenciális energia szigorúan csökken Mert: véges sok forgalomminta van csak véges sok különböző értéke lehet; mindig nemnegatív Ha minden lépés során szigorúan csökken: egy idő után nem csökkenhet tovább; mindenki legjobbválasz leképezést ad az adott helyzetre = egyensúly • Pont azért csökken, mert legjobbválasz lépés történik • Az e élen ha x1 csomag megy, a potenciális energia: • Ha egy csomag elhagyja: • Helyette átvált az f élre, ahol eddig x2 csomag volt, a potenciális energia:<br />
<br />
• A rendszer energiájából levonódik: a régi útvonalon az átviteli idő: Te(x1) • Hozzáadódik: az új útvonal átviteli ideje: Te(x2+1) • A változás mértéke pont a csomag átviteli idejének csökkenése: Te(x1)-Te(x2+1) • Tehát a potenciális energia legjobbválasz lépés során szigorúan csökken<br />
<br />
82/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly vs közösségi optimum? • A potenciális energia és a travel time kapcsolata egyetlen élre • Energy(e) = e él potenciális energiája • x csomag esetén: • 𝐸𝑛𝑒𝑟𝑔𝑦 𝑒 = 𝑇𝑒 1 + 𝑇𝑒 2 + . . . +𝑇𝑒(𝑥) • 𝑇𝑜𝑡𝑎𝑙 − 𝑇𝑟𝑎𝑣𝑒𝑙 − 𝑇𝑖𝑚𝑒(𝑒) = 𝑇𝑒 𝑥 + 𝑇𝑒 𝑥 + … + 𝑇𝑒 𝑥 = 𝑥 𝑇𝑒 𝑥 • tehát: 𝐸𝑛𝑒𝑟𝑔𝑦 𝑒 ≤ 𝑇𝑜𝑡𝑎𝑙 − 𝑇𝑟𝑎𝑣𝑒𝑙 − 𝑇𝑖𝑚𝑒(𝑒) • Továbbá:<br />
<br />
83/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A potenciális energia legalább az átviteli idő fele • Mivel<br />
<br />
, ezért<br />
<br />
• Azaz a következő adódik:<br />
<br />
84/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Az egész rendszerre vonatkoztatva: • Legyen Z egy forgalomminta • Energy (Z) = az élek potenciális energiáinak összege, ha a csomagok a Z mintát követik • Social-Cost(Z) = az átviteli idők összege Z forgalmi minta mellett<br />
<br />
• Induljunk ki egy közösségileg optimális Z mintából legjobbválasz-<br />
<br />
leképezések Z’ egyensúlyi minta • A közösségi költség nőhet is, de a potenciális energia csak csökkenhet • A közösségi költség a potenciális energia legfeljebb kétszerese<br />
<br />
• Tehát a közösségi költség tetszőleges állapotban a kiindulási potenciális<br />
<br />
energiának is legfeljebb kétszerese • Azaz az egyensúlyi költség a szociális optimum költségének is legfeljebb kétszerese<br />
<br />
85/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Állítás: Az egyensúlyi költség a szociális optimum költségének legfeljebb 2x-ese Bizonyítás: • Legyen Z a közösségileg optimális minta, Z’ az egyensúlyi minta • A legjobbválasz-leképezések során a potenciális energia csak csökkenhet • Már korábban láttuk:<br />
<br />
• Az eddigieket összerakva adódik:<br />
<br />
A potenciális energia módszerével egy egyensúlyi állapot költségére adható korlát. 86/40<br />
<br />
Terjedés önszerveződő hálózatokban<br />
<br />
High Speed Networks Laboratory<br />
<br />
87/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Terjedés önszerveződő adatbázisokban 1.<br />
<br />
Bevezető és áttekintés • Az előző rész tartalmából… • Forgalommonitorozás játékelmélettel • Milyen terjedési folyamatokat vizsgálunk?<br />
<br />
2. Önszerveződő adatbázis mérete • Meddig nő egy adatbázis? 3. Vírusterjedés adatbázisokban<br />
<br />
88/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Múlt órai áttekintés: játékelmélet alapok • Optimális stratégia keresése: kifizetés minimalizálása • Legjobbválasz-leképezés, Nash-egyensúly beállása, dominált<br />
<br />
stratégiák eliminálása • Braess-paradoxon: elmozdulás a közösségi optimumból<br />
<br />
89/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Múlt órai áttekintés: egyensúly vs optimum • Optimálsi átviteli idő ≠ egyensúlyi átviteli idő • Braess-paradoxon: upgrade ronthat az átviteli időn • Legjobbválasz-leképezések → Nash-egyensúly<br />
<br />
• Az optimumnak legfeljebb kétszerese • Analízis eszköze: potenciális energia • Egy élre, ha x csomagot küld: • Ahol Te(x) = aex+be, travel time függvény<br />
<br />
• Forgalommintára: éleken vett potenciális energiák összege<br />
<br />
90/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Forgalmi minta megtalálása az egyensúlyban LEGJOBBVÁLASZ-ALGORITMUS 1. Kiidulás: egy tetszőleges forgalmi minta 2. Ha egyensúly KÉSZ 3. Egyébként: létezik legalább egy csomag, aminek a legjobbválasza a<br />
<br />
többire egy gyorsabb út • Válasszunk egy tetszőleges ilyet; az váltson át erre 4. GOTO 2.<br />
<br />
• Állítás: A Legjobbválasz-algoritmus véges lépésben megáll<br />
<br />
• Bizonyítás: ötlet: elég azt megmutatni, hogy a legjobbválasz-<br />
<br />
leképezések során a potenciális energia szigorúan csökken<br />
<br />
91/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egyensúly vs közösségi optimum? • A potenciális energia és a travel time kapcsolata egyetlen élre • 𝐸𝑛𝑒𝑟𝑔𝑦 𝑒 ≤ 𝑇𝑜𝑡𝑎𝑙 − 𝑇𝑟𝑎𝑣𝑒𝑙 − 𝑇𝑖𝑚𝑒 𝑒<br />
<br />
• Az egész rendszerre vonatkoztatva: • Legyen Z egy forgalomminta • Energy (Z) = az élek potenciális energiáinak összege • Social-Cost(Z) = az átviteli idők összege • Induljunk ki egy közösségileg optimális Z mintából legjobbválasz-leképezések Z’ egyensúlyi minta • A közösségi költség nőhet is, de a potenciális energia csak csökkenhet • A közösségi költség a potenciális energia legfeljebb kétszerese • Tehát a közösségi költség tetszőleges állapotban a kiindulási potenciális energiának is legfeljebb kétszerese • Azaz az egyensúlyi költség a szociális optimum költségének is legfeljebb kétszerese • Megj. Itt is igaz az állítás 4/3-os szorzóval, de azt nem bizonyítjuk.<br />
<br />
92/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Állítás: Az egyensúlyi költség a szociális optimum költségének legfeljebb 2x-ese Bizonyítás: • Legyen Z a közösségileg optimális minta, Z’ az egyensúlyi minta • A legjobbválasz-leképezések során a potenciális energia csak csökkenhet • Már korábban láttuk:<br />
<br />
• Az eddigieket összerakva adódik:<br />
<br />
A potenciális energia módszerével egy egyensúlyi állapot költségére adható korlát. 93/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Gyakorló feladatok 1. 1.a 1000 csomagot küldünk A → B. Mi a Nash-egyensúlyi állapot?<br />
<br />
94/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Gyakorló feladatok 1. 1.a egyenlően oszlik el a két lehetséges útvonalon 1.b Létrejön egy új kapcsolat a hálózatban: C → D, 0 átviteli idővel. Mi most a Nash-egyensúly?<br />
<br />
0<br />
<br />
95/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Gyakorló feladatok 1. 1.c Javul az átvitel sebessége a C → B és A → D utakon. Mi most a Nashegyensúly?<br />
<br />
5<br />
<br />
0<br />
<br />
5<br />
<br />
96/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A mai óra tartalmából: • Hálózatok növekedése • Egy magára hagyott hálózat meddig nő?<br />
<br />
• Szinkronizáció • Terjedési jelenségek a hálózatban • Hogyan terjednek a vírusok?<br />
<br />
97/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Stabilitás önszerveződő adatbázisokban 1.<br />
<br />
Bevezető és áttekintés • Az előző rész tartalmából… • Forgalommonitorozás játékelmélettel • Milyen terjedési folyamatokat vizsgálunk?<br />
<br />
2. Önszerveződő adatbázis mérete • Meddig nő egy adatbázis? 3. Szinkronizáció adatbázisokban 1. Vírusterjedés<br />
<br />
98/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Egy önszerveződő adatbázis mérete • Meddig nő egy<br />
<br />
önszerveződő adatbázis? • Wi-Fi a K épületben vs. a Q-ban • Populációk növekedése –<br />
<br />
Verhulst modell • Erre a jelenségre is<br />
<br />
használható • 𝑟: időben állandó<br />
<br />
növekedési ráta • 𝐾: teherbírási küszöb<br />
<br />
99/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Malthus-féle lineáris növekedési modell • Legegyszerűbb: • N(t) = az adatbázis mérete t időpontban • r = növekedési ráta •<br />
<br />
d𝑁 d𝑡<br />
<br />
= 𝑟 𝑁(𝑡)<br />
<br />
• A növekedés üteme időben<br />
<br />
állandó r t • Exponenciális növekedés • 𝑁 𝑡 = 𝑁0 𝑒𝑟𝑡, azaz mindig az 𝑒𝑟-szeresére nő • A hálózat felrobban<br />
<br />
• Nem mehet a végtelenségig 100/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Módosítás • Vegyük be a túlnépesedést = túl<br />
<br />
sokan vannak • Korlátos erőforrások = a szerver csak bizonyos számú számítógépet tud kiszolgálni • A növekedési ráta nem időben • • • •<br />
<br />
állandó Kis N-re r még konstans Egyre jobban csökken K = carrying capacity = teherbírás Ha N>K, akkor negatív: többen hagyják el a hálózatot, mint ahányan jönnek<br />
<br />
A növekedési ráta változása az adatbázisban levő számítógépek számának függvényében.<br />
<br />
101/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A Verhulst-féle növekedési modell • Kezelhető verzió: vesszük az egy egységre eső növekedést: • Lineárisan csökkenőnek tesszük fel<br />
<br />
• Kapjuk: logisztikus növekedési modell<br />
<br />
• Ha N kicsi, majdnem visszaadja a Malthus-modellt • Ha N ≈ K, akkor a növekedés üteme közel 0 • Ha N > K, akkor negatív<br />
<br />
• Kérdés: N(t) = ? • Meg lehet oldani analitikusan • És grafikusan<br />
<br />
102/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
A növekedés mértéke • Ábrázoljuk -t függvényében • Mit veszünk észre?<br />
<br />
• a növekedés gyorsasága • K/2-ig nő, utána csökken • K után negatív • Két fixpont: a 0 és a K • Ellenőrzés: legyen • 0 instabil, K stabil<br />
<br />
=0, és oldjuk meg N-re<br />
<br />
103/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Mit jelent mindez? • Mit jelent mindez? • Először gyorsan nő, aztán egyre lassabban • A teherbírást ha túllépi, csökkeni fog • Többen hagyják el a hálózatot, mint ahányan jönnek • 0 fixpont, de instabil: kicsit megváltozik, akkor K-ba konvergál • K fixpont, stabil: perturbáció hatására oda visszatalál<br />
<br />
104/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Még jobban lefordítva • Ez a modell nem mindenható, de az alapvető jelenségeket jól mutatja • Az történik, amit intuitívan várunk • Elkezd nőni, beáll a teherbírás körüli értékre • Ha magára hagyjuk, akkor e körül ingadozik • Előrször gyorsabban nő, majd lassabban • Ha túllépi a teherbírást, akkor csökken<br />
<br />
105/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Stabilitás önszerveződő adatbázisokban 1.<br />
<br />
Bevezető és áttekintés • Az előző rész tartalmából… • Forgalommonitorozás játékelmélettel • Milyen terjedési folyamatokat vizsgálunk?<br />
<br />
2. Önszerveződő adatbázis mérete • Meddig nő egy adatbázis? 3. Vírusterjedés önszerveződő adatbázisban<br />
<br />
106/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Vírusok terjedése önszerveződő adatbázisban • Vírus • utasításhalmaz ami elsősorban önmaga sokszorosításáról szól<br />
<br />
• Mennyire fertőző • Mennyi ideig tartja a gazdát fertőző állapotban<br />
<br />
• Nagyon hasonlít az embert támadó<br />
<br />
vírusokra<br />
<br />
• HIV, Ebola, Influenza<br />
<br />
• Számítógép vírusok • Internet előtt (floppy-n) • Az Internet elterjedésével nulla energiával • Broadcast keresés (mindegy kit) • Exponenciális növekedés • Ma már inkább észrevétlenség, adatszerzés, kapacitás • ILOVEYOU vírus 107/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Vírusterjedés: SIR modell • Vírusterjedés vizsgálata • SIR modell • Természetesen tudni kell, hogy ki kivel érintkezik • S(t),I(t),R(t): fertőződésre hajlamosak, fertőzőek, gyógyultak<br />
<br />
száma t-kor<br />
<br />
• β = S → I contact rate • ν = I → R recovery rate<br />
<br />
Lassú, robbanás, lecsengés 108/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Vírusterjedés véletlen gráfmodellben • Legkönnyebb vizsgálni: véletlen gráf • Nem életszerű, de jó kiindulópont • Reprodukciós arány = egy fertőzött egyed egy egészséges<br />
<br />
• R0 < 1 : hosszú távon kihal a vírus • R0 > 1: hosszú távon mindenki<br />
<br />
megfertőződik<br />
<br />
Fertőzött populáció<br />
<br />
populációban hány újat fertőz meg az élettartama alatt S R0 • Véletlen gráf esetén a reprodukciós arány teljesen meghatározza a lefolyást 1<br />
<br />
R0 1<br />
<br />
Reprodukciós arány<br />
<br />
109/40<br />
<br />
Vírusterjedés kisvilág modellben • Rács esetén csak az igazán durva<br />
<br />
betegség teljed el • A shortcutokon keresztül gyorsan terjed<br />
<br />
Fertőzött populáció<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
1<br />
<br />
1 0 1<br />
<br />
a vírus • Új közösségeket megfertőzve<br />
<br />
az emberek nem érzik a veszélyt • Viszont van esély fellépni a kezdeti szakaszban • Modularitás mesterséges növelése • Reprodukciós arány csökkentése, immunizálás • Egy védekezési stratégia: a shortcutok elvágása • Tűcsere program<br />
<br />
Küszöb<br />
<br />
• A kisvilágságot figyelmen kívül hagyva,<br />
<br />
Fertőzőképesség<br />
<br />
0<br />
<br />
1<br />
<br />
Véletlen élek aránya<br />
<br />
110/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Vírusterjedés skálafüggetlen hálózatban • Ez áll a legközelebb a valós önszerveződő hálózatokhoz • Virus bulletin • A legtöbb számítógép vírus hosszan képes rejtőzködni a hálózatban • Hogy lehetséges ez? (SIR modellben nem lehet) • Skálafüggetlen modell • Eltűnik a küszöb • Kegyetlen védekezési stratégia: • Hubok immunizálása • De hogy találjuk meg őket?<br />
<br />
111/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Vírusok elleni védekezés • Hubokat immunizáljuk • Véletlen alany véletlen ismerősét<br />
<br />
immunizáljuk • Számítógép vírusok • Microsoft minden kompatibilis mindennel • „When you are dealing with rootkits and some advanced spyware programs, the only solution is to rebuild from scratch. In some cases, there really is no way to recover without nuking the systems from orbit" Mike Danseglio, program manager in the Security Solutions group at Microsoft 2006 • "Detection is difficult, and remediation is often impossible," Danseglio declared. "If it doesnt crash your system or cause your system to freeze, how do you know its there?<br />
<br />
112/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Véletlen immunizálás vs hubok védelme • Ha véletlenszeűen immunizáljuk a csomópontokat: • Kiválasztunk 5 csomópontot • Ezeket + a szomszédaikat immunizáljuk • 24 csomópontot érünk el<br />
<br />
113/40<br />
<br />
Önszerveződő adatbázisok Hosszu Éva<br />
<br />
Véletlen immunizálás vs hubok védelme • Hubokat immunizáljuk • 1 lépésben ≈ 60 csomópontot érünk el • A hatékony megoldás a<br />
<br />
hubok védelme • A hubok azonosítása<br />
<br />
felvet némi problémát… • Véletlen node egyik<br />
<br />
kapcsolata nagy valószínűséggel egy hub<br />
<br />
114/40<br />
<br /> </div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="modal fade" id="report" tabindex="-1" role="dialog" aria-hidden="true">
<div class="modal-dialog">
<div class="modal-content">
<form role="form" method="post" action="https://adoc.pub/report/nszervezd-adatbazisok83ab872d0f5581272b83e4f763eb7c3556655" style="border: none;">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-hidden="true">×</button>
<h4 class="modal-title">Report "Önszerveződő adatbázisok"</h4>
</div>
<div class="modal-body">
<div class="form-group">
<label>Your name</label>
<input type="text" name="name" required="required" class="form-control" />
</div>
<div class="form-group">
<label>Email</label>
<input type="email" name="email" required="required" class="form-control" />
</div>
<div class="form-group">
<label>Reason</label>
<select name="reason" required="required" class="form-control">
<option value="">-Select Reason-</option>
<option value="pornographic" selected="selected">Pornographic</option>
<option value="defamatory">Defamatory</option>
<option value="illegal">Illegal/Unlawful</option>
<option value="spam">Spam</option>
<option value="others">Other Terms Of Service Violation</option>
<option value="copyright">File a copyright complaint</option>
</select>
</div>
<div class="form-group">
<label>Description</label>
<textarea name="description" required="required" rows="3" class="form-control" style="border: 1px solid #cccccc;"></textarea>
</div>
<div class="form-group">
<div style="display: inline-block;">
<div class="g-recaptcha" data-sitekey="6LcEnMcZAAAAAFHzKKgaE-Qh57XzUTzpfRElD4dP"></div>
</div>
</div>
<script src='https://www.google.com/recaptcha/api.js'></script>
</div>
<div class="modal-footer">
<button type="button" class="btn btn-default" data-dismiss="modal">Close</button>
<button type="submit" class="btn btn-primary">Send</button>
</div>
</form>
</div>
</div>
</div>
<script>
$(document).ready(function () {
var inner_height = $(window).innerHeight() - 250;
$('#pdfviewer').css({"height": inner_height + "px"});
});
</script>
<footer class="footer" style="margin-top: 60px;">
<div class="container-fluid">
Copyright © 2024 ADOC.PUB. All rights reserved.
<div class="pull-right">
<span><a href="https://adoc.pub/about">About Us</a></span> |
<span><a href="https://adoc.pub/privacy">Privacy Policy</a></span> |
<span><a href="https://adoc.pub/term">Terms of Service</a></span> |
<span><a href="https://adoc.pub/copyright">Copyright</a></span> |
<span><a href="https://adoc.pub/contact">Contact Us</a></span> |
<span><a href="https://adoc.pub/cookie_policy">Cookie Policy</a></span>
</div>
</div>
</footer>
<!-- Modal -->
<div class="modal fade" id="login" tabindex="-1" role="dialog" aria-labelledby="myModalLabel">
<div class="modal-dialog" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close" on="tap:login.close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="add-note-label">Sign In</h4>
</div>
<div class="modal-body">
<form action="https://adoc.pub/login" method="post">
<div class="form-group">
<label class="sr-only" for="email">Email</label>
<input class="form-input form-control" type="text" name="email" id="email" value="" placeholder="Email" />
</div>
<div class="form-group">
<label class="sr-only" for="password">Password</label>
<input class="form-input form-control" type="password" name="password" id="password" value="" placeholder="Password" />
</div>
<div class="form-group">
<div class="checkbox">
<label class="form-checkbox">
<input type="checkbox" name="remember" value="1" />
<i class="form-icon"></i> Remember me
</label>
<label class="pull-right"><a href="https://adoc.pub/forgot">Forgot password?</a></label>
</div>
</div>
<button class="btn btn-primary btn-block" type="submit">Sign In</button>
</form>
</div>
</div>
</div>
</div>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-177279549-1"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-177279549-1');
</script>
<script src="https://adoc.pub/assets/js/jquery-ui.min.js"></script>
<link rel="stylesheet" href="https://adoc.pub/assets/css/jquery-ui.css">
<script>
$(function () {
$("#document_search").autocomplete({
source: function (request, response) {
$.ajax({
url: "https://adoc.pub/suggest",
dataType: "json",
data: {
term: request.term
},
success: function (data) {
response(data);
}
});
},
autoFill: true,
select: function( event, ui ) {
$(this).val(ui.item.value);
$(this).parents("form").submit();
}
});
});
</script>
<!-- cookie policy -->
<div id="ADOCPUB_cookie_box" style="z-index:99999; border-top: 1px solid #fefefe; background: #FFC107; width: 100%; position: fixed; padding: 5px 15px; text-align: center; left:0; bottom: 0;">
Our partners will collect data and use cookies for ad personalization and measurement. <a href="https://adoc.pub/cookie_policy" target="_blank">Learn how we and our ad partner Google, collect and use data</a>. <a href="#" class="btn btn-success" onclick="accept_ADOCPUB_cookie_box();return false;">Agree & close</a>
</div>
<script>
function accept_ADOCPUB_cookie_box() {
document.cookie = "ADOCPUB_cookie_box_viewed=1;max-age=15768000;path=/";
hide_ADOCPUB_cookie_box();
}
function hide_ADOCPUB_cookie_box() {
var cb = document.getElementById('ADOCPUB_cookie_box');
if (cb) {
cb.parentElement.removeChild(cb);
}
}
(function () {
var ADOCPUB_cookie_box_viewed = (function (name) {
var matches = document.cookie.match(new RegExp("(?:^|; )" + name.replace(/([\.$?*|{}\(\)\[\]\\\/\+^])/g, '\\$1') + "=([^;]*)"));
return matches ? decodeURIComponent(matches[1]) : undefined;
})('ADOCPUB_cookie_box_viewed');
if (ADOCPUB_cookie_box_viewed) {
hide_ADOCPUB_cookie_box();
}
})();
</script>
<!-- end cookie policy -->
</body>
</html>
