Modele dla procesów, poprzez które idee oraz wpływy są propagowane przez sieci społeczne badano w wielu dziedzinach, w tym dyfuzji leków i technologicznych innowacji. Nagłe i szerokie stosowanie wielu różnych strategii w teoretycznych grach ustawień i efekty „Word of mouth” w promocji nowych produktów. Ostatnio, zmotywowani projektem strategii marketingu wirusowego, Domingos i Richardson zamieścili podstawowy problem algorytmiczny takich procesów sieci społecznych: czy możemy spróbować przekonać podzbiór osób do przyjęcia nowego produktu lub innowacji, którego celem jest wywołanie kaskadowo kolejnych adopcji. Tylko jaki zestaw początkowych indywidualności powinniśmy wskazać?
Sieci społeczne ( wykres relacji i interakcji w grupie osób) odgrywają zasadniczą rolę jako medium do przekazywania informacji, idei oraz wpływów wśród jej członków. Pomysł lub innowacji pojawi się (na przykład, korzystanie z telefonów komórkowych wśród studentów, przyjęcie nowych narkotyków w zawodzie lekarza, lub powstanie ruch polityczny w niestabilnym społeczeństwie) i może albo umrzeć szybko lub poczynić znaczące postępy w populacji. Jeśli chcemy zrozumieć , w jakim stopniu są przyjęte, może to być ważne, aby zrozumieć w jaki sposób dynamizm adopcji może rozwijać się w danej sieci społecznej, w jakim stopniu decyzje kolegów i przyjaciół wpływają na znajomych. Takie procesy dyfuzji sieci mają długą historię badań w naukach społecznych. Jedne z pierwszych semantycznych badań koncentrowały się na danych dotyczących przyjęcia innowacji medycznych i rolniczych zarówno w krajach rozwiniętych i rozwijających się
częściach świata.
W ostatniej pracy, zmotywowani przez aplikacje do marketingu, Domingos i Richardson zamieścili podstawowy problem algorytmiczny dla takich systemów. Załóżmy, że mam dane w sieci społecznej, z przybliżeniem, w jakim stopniu osoby wpływają na siebie i chcielibyśmy wypuścić na rynek nowy produkt, który zostałby przyjęty przez dużą część sieci. Założeniem marketingu wirusowego jest to, że na początku skierowana jest do wpływowych osobników sieci (dając im darmowe próbki). Tym działaniem możemy wywołać kaskadowy wpływ przez, który przyjaciele będą rekomendować produkt innym, aż ostatecznie duża część sieci skorzysta z tego produktu. Ale jak powinniśmy wybrać te kilka kluczowych osób, aby pobudzić taki proces? Odpowiedź na to pytanie było rozważane w probabilistycznym modelu interakcji. Heurystyki były dawane klientom, mającym duży wpływ na takie sieci.
W tym artykule zostanie rozważona kwestia wyboru wpływowych osób jako problem optymalizacji dyskretnej. Optymalne rozwiązanie jest problemem NP.-trudnym dla większości modeli, które były badane. Z drugiej strony, framework zaproponowany w „Mining Knowlage-Sharing Sites for Viral Marketing” M, Richardson I P. Domingos, opiera się na prostym modelu liniowym, gdzie rozwiązanie problemu optymalizacji można uzyskać poprzez rozwiązanie liniowego systemu równań. Tutaj skupimy się na zbiorze powiązanych ze sobą NP.-trudnych modelach, które były intensywnie badane w sieciach społecznych oraz na uzyskaniu pierwszych dowodów zbliżenia się do efektywnego algorytmu w kilku ogólnych przypadkach. Ogólność modeli leży pomiędzy rozwiązywalnymi modelami w czasie wielomianowym oraz bardzo podstawowymi modelami, gdzie problem optymalizacji nie może być nawet przybliżany.
Zaczniemy od podejścia nieco odmiennego od framework’a Domingosa-Richardsona, w następującym sensie. Jeżeli ich charakter mają w istocie charakter opisowy, to określając wspólną dystrybucję nad zachowaniem wszystkich węzłów w sensie globalnym, skupiamy się na modelach bardziej operacyjnych z punktu widzenia matematycznej socjologii i interakcji systemów cząstek, które wyraźnie przedstawiają krok po kroku dynamikę przyjęcia.
Dwa podstawowe modele dyfuzyjne. Rozważając modele operacyjne rozprzestrzeniania się idei i innowacji poprzez sieć społeczną G, reprezentowaną przez Graf, będziemy mówić o poszczególnych węzłów, jako aktywnych lub nieaktywnych. Skupimy się na ustawieniach, kierując się motywacją omówioną wcześniej, w której tendencja każdego węzła do stania się aktywnym wzrasta monotonicznie w zależności od ilości sąsiadów stających się aktywnymi. Ponadto, skupimy się teraz na przypadku, w którym węzły mogą zmieniać się z nieaktywne w aktywne, ale nie w przeciwnym kierunku. Okazuje się, że to założenie może być łatwo zniesione później. Tak więc, proces będzie wyglądał mniej więcej jak wynika z perspektywy początkowo nieaktywnego węzła v. Z biegiem czasu im więcej węzłów sąsiedzkich do węzła v staje się aktywnymi, w którymś momencie może to spowodować, że węzeł v również stanie się aktywny i może to wywołać dalsze decyzje w węzłach sąsiadujących z v.
Granovetter i Schelling byli jednymi z pierwszych, którzy zaproponowali modele, które oddają ten proces. Ich podejście opiera się na wykorzystaniu w węzłach odpowiednich progów. Wiele modeli tego pokroju zostało już zbadanych, ale następujący liniowo progowy model leży na rdzeniu większości późniejszych uogólnień. W tym modelu węzeł v jest pod wpływem X przez każdego sąsiada w zależności od wagi, w taki sposób, że Σb v, w ≤ 1. Dynamika procesu przebiega potem w następujący sposób: każdy węzeł wybiera próg v losowo z przedziału [0 ; 1], co stanowi ułamek ważonej wierzchołków sąsiadujących z v, które muszą stać się aktywnymi, jeśli v ma stać się aktywnym. Biorąc pod uwagę losowy wybór progów, oraz wstępny zestaw wierzchołków aktywnych , proces dyfuzji rozwija się deterministycznie w kolejnych krokach: w kroku t, wszystkie wierzchołki są aktywne w t=1, oraz aktywujemy każdy wierzchołek, którego łączna waga jego aktywnych sąsiadów wynosi co najmniej Θv:
Σ b v, w ≥ Θv
aktywujemy sąsiadów v
Progi intuicyjnie reprezentują różne ukryte tendencje, węzłów do przyjęcia innowacji, gdy ich sąsiad przyjmuje. Fakt, że progi są wybierane losowo jest przeznaczony do modelu brak wiedzy na temat ich wartości, w efekcie uśredniano możliwe wartości progowe dla wszystkich węzłów. Na podstawie pracy nad systemami aktywnych cząsteczek z teorii prawdopodobieństwa, możemy również wziąć pod uwagę dynamiczne modele kaskadowe procesów dyfuzyjnych. Koncepcyjnie najprostszym modelem z tego typu jest to, co przez niektórych jest nazywane Niezależny Model Kaskadowy, zbadany niedawno w kontekście marketingu Goldenberga, Libai i Mullera. Znów zaczniemy od wyjściowego zbioru aktywnych węzłów ,. Proces ten postępuje w odrębnych etapach, zgodnie z następującymi regułami. Po raz pierwszy węzeł staje się aktywny w kroku t, mając jedną szansę, aby aktywować każdy obecnie nieaktywny węzeł sąsiadujący w z prawdopodobieństwem . Węzeł w (parametr systemu) niezależnie od historii do tej pory. (Jeśli w ma wielu nowo aktywowanych sąsiadów, ich próby są w dowolnej kolejności). Jeśli v się powiedzie, to stanie się aktywny w kroku t + 1, ale w zależności czy v się powiedzie bądź nie, nie może on podjąć kolejnych prób aktywacji w, w kolejnych próbach. Ponownie , proces działa do czasu gdy już więcej aktywacji nie może być wykonanych.
Liniowe progi oraz Niezależny Model Kaskadowy to dwa z najbardziej podstawowych i najczęściej badanych modeli dyfuzji, ale oczywiście wiele rozszerzeń może być uznanych.
Arkadiusz Stachowiak, 84882
tsiss@PUT 
Dodaj komentarz