Influence maximization, definierad av Kempe, Kleinberg, och Tardos (2003), är problemet med att hitta en liten uppsättning frönoder i ett socialt nätverk som maximerar spridningen av inflytande under vissa inflytande kaskade modeller. I detta dokument föreslår vi en utvidgning av den oberoende kaskadmodellen som omfattar uppkomsten och spridningen av negativa åsikter. Den nya modellen har en explicit parameter som kallas kvalitetsfaktor för att modellera det naturliga beteendet hos människor som blir negativa till en produkt på grund av produktdefekter. Vår modell innehåller negativitetsfördomar (negativa åsikter dominerar vanligtvis över positiva åsikter) som är allmänt erkända i den sociala psykologiska litteraturen. Modellen bibehåller några fina egenskaper som submodularitet, vilket tillåter en girig approximationsalgoritm för att maximera positiv påverkan inom ett förhållande på 1 − 1/e. Vi definierar ett kvalitetskänslighetsförhållande (qs-ratio) för influensgrafer och visar en snäv gräns för (n/k) på qs-ratio, där n är antalet noder i nätverket och k är antalet utvalda frön, vilket indikerar att utsädesval är känsligt för kvalitetsfaktorn för allmänna grafer. Vi designar en effektiv algoritm för att beräkna påverkan i trädstrukturer, som är icke-trivial på grund av negativitet partiskhet i modellen. Vi använder denna algoritm som kärna för att bygga en heuristisk algoritm för att påverka maximering för allmänna grafer. Genom simuleringar visar vi att vår heuristiska algoritm har matchande inflytande med en standard girig approximation algoritm samtidigt som order av magnitud snabbare.
Chen och Al. Ref överväga en ny modell som innehåller negativitet partiskhet och designa en algoritm för att beräkna påverkan i trädstrukturer.
Influence maximization in social networks when negative opinions may emerge and propagate
{'venue': 'In: SDM, SIAM / Omnipress (2011) 379–390', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}