|
Koniec dwudziestego wieku przyniósł wielkie zainteresowanie tematyką sieci
społecznych. Zagadnienia początkowo podejmowane głównie przez socjologów,
przyciągnęły fizyków, matematyków i informatyków. Osobliwe zjawiska
występujące w sieciach społecznych, jak to, że zachłanny algorytm przesyłanie
wiadomości przez sieć osobistych kontaktów pozwala przesłać list pomiędzy
dwoma oddalonymi zakątkami USA z wykorzystaniem zaledwie pięciu pośredników
(eksperyment Milgrama) stały się przedmiotem interdyscyplinarnych badań.
Ze strony matematyki i informatyki teoretycznej, duży wkład w tę młodą dziedzinę
pochodzi od niedawnego laureata nagrody Nevalinny, Jona Kleinberga. Między innymi,
to właśnie on zaproponował jeden z pierwszych modeli sieci, gdzie niewielka
ilość losowych połączeń dalekiego zasięgu (dodanych do prostej "geograficznej"
lokalnej struktury pozwala zmniejszyć średnicę grafu z liniowej do
logarytmicznej, względem liczby wierzchołków. Chodzi tu o kratownicę  , gdzie
każdy wierzchołek jest połączony z 4 najbliższymi (metryka Euklidesa)
wierzchołkami, wzbogaconą o jedno losowe połączenie "długodystansowe" dla
każdego wierzchołka. Już tak prosta struktura pozwala, by zachłanny algorytm
oparty wyłącznie na lokalnej wiedzy i powszechnej znajomości "geografii"
pozwalał odnajdywać ścieżki logarytmicznej długości.
W podobny sposób, studiowanie prostych modeli opartych na kratownicach pomaga
zrozumieć zjawiska fizyczne takie jak magnetyzm, stany skupienia, perkolacja, czy
dyfuzja. Szczególnie perkolacja jest tematem o bogatej literaturze matematycznej,
wliczając monografię Bollobása. Od tego samego autora (ze współautorami)
pochodzą niedawne wyniki dotyczące większościowej perkolacji "bootstrap" w
kratach  , która stanowi ciekawy model dyfuzji w k-wymiarowej przestrzeni.
Ze strony informatyki teoretycznej, Kleinberg et al. badali problem wybrania zbioru
wierzchołków, których początkowa aktywizacja rozprzestrzeni się na jak
największą część grafu. W tym modelu, dynamika dyfuzji jest pewnym
uogólnieniem właśnie większościowej perkolacji "bootstrap". Ta prosta i
naturalna zasada: ,wierzchołek, którego większość sąsiadów jest aktywna,
zostaje zaktywizowany raz na zawsze", stanowi dla autorów interesujący model dla,
między innymi, marketingu wirusowego.
W naszej pracy zadajemy pytanie o wpływ struktury grafu na łatwość aktywizacji
całego grafu przy pomocy początkowej próbki losowo wybranych wierzchołków. Na
przykład, dla zbioru niezależnych wierzchołków lub cyklu, prawdopodobieństwo
początkowej aktywizacji musi wynosić 1 by zapewnić, że dynamika "zostaję
zaktywizowany przez aktywność większości moich sąsiadów" opanuje cały graf.
Dla kliki, wystarczy by prawdopodobieństwo początkowej aktywizacji było silnie
większe niż 0,5. Czy istnieją klasy grafów, gdzie początkowa ,mniejszość"
opanowuje cały graf? Czy istnieją klasy grafów, gdzie wystarczy zaktywizować
dowolnie mały ułamek losowo wybranych wierzchołków?
|