[****INFORMATIKA****]
Az erőmű-meghibásodás egyfajta modellezésére is alkalmas általános technikáról hallottam ma egy alapvetően matematikai indíttatású előadást.
2007-11-22 Az információ terjedése szociális hálózatban
(Angol) kulcsszavak a téma mélyebb elsajátításához: social networks, viral marketing, diffusion of innovations
Az előadás hivatkozott linkjei:
Maximizing the Spread of Influence through a Social Network
http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf
On the Submodularity of Influence in Social Networks (2006-11-19)
http://stat-www.berkeley.edu/~sroch/research_files/submod.pdf
Nemhauser/Wolsey/Fischer lemma
http://www-rcf.usc.edu/~dkempe/CS59905/cs59920050411.pdf
E.Rogers: Diffusion of Innovations (1975) -> jó bevezető:
http://www.anu.edu.au/people/Roger.Clarke/SOS/InnDiff.html
http://en.wikibooks.org/wiki/Communication_Theory/Diffusion_of_Innovations#Everett_M._Rogers
Matroid
http://hu.wikipedia.org/wiki/Matroid
Adva vagyon egy irányított gráf. A csúcsok vagy inaktívak (0), vagy aktívak (1). Ezen felül kell egy un. (f) szubmoduláris függvény. Ennek pontos definiciója az első cikkben (is) le van írva. Ennek révén lesz valahogy 0-ból 1 egy adott csúcs. Természetesen, ha egy csúcs aktív ("tud valamit"), azt már nem felejti el, tehát nem lehet 0. Illetve ha egy iterációs lépés után nem lesz újabb csúcs aktív, akkor kész, vége, le lehet állni -> nincs további terjedés a hálózatban.
Úgy kell elképzelni ezt a szubmoduláris függvényt konyhanyelven, hogy amikor először seprünk, akkor szedjük össze a legtöbb szemetet, aztán minél többször húzzuk aztán a seprüt annál kevesebb lesz már a szemét. Vagy körlapokat dobálunk egy asztalra (véletlenszerűen), kezdetben nagyobb területet fedünk le, mint később. Vagy adatbányász analógia: a felügyelt tanítás központi problémája, hogy új információ bejövetelekor az a jó, ha a régiek nem vem (nagyon) rendeződnek át.
Az első cikk néhány speciális esetre bizonyít csak, a sokkal frissebb (2006-11-19) általános esetre is kiterjesztett bizonyítást is közlő második cikkből következik a végkövetkeztetés (Nemhauser/Wolsey/Fischer): a mohó algoritmus jó közelítést ad a címbeli probléma megoldási algoritmusaként.
Az első cikk a maga korlátozottabb eszközeivel egy gyakorlati példán is kipróbálta a modellt: Vette az www.arxiv.org -on található részecske fizikával foglalkozó cikkeket (10.000) és (társ)szerzőit (50.000). Érdekes volt látni, hogy a legnagyobb fokú csúcsokból indulva (sok szerzős cikk) vagy a 'központi szerzős' csúcsokból indulva (akik sok cikket írtak különböző társszerzőkkel) gyenge eredmények születtek ugyanis 'látens klaszterek' alakultak ki. Lásd még klikkesedés ;)
E szubmoduláris függvényt használja a kombinatorikus optimalizálás, a matroid-elmélet, vagy fizikában a rúd szerkezeti gyengeségeit modellezik vele.
Az egész téma hátterében ott nyüzsög a marketingesek problémája: k embert tudnak csak megszólítani (ennyire van csak pénzük), és szeretnék minél hatékonyabban elterjeszteni az információjukat a (leg)teljes(ebb) populáció körében. E. Rogers foglalkozott a témával kimerítően (1975-ös könyvében). Ő azt mondja, hogy 5 nagy csoportja van az embereknek (természetesen csoporton belül és között is van információ áramlás, persze az utóbbi az izgalmas, hozzágondolva azt a tapasztalatot, hogy - mint például egy mobiltelefon - annál értékesebb egy eszköz minél inkább elterjedt)
03% innovators (venturesome);
14% early adopters (respectable);
33% early majority (deliberate);
33% late majority (sceptical);
16% laggards (traditional).
