Abstract-Sociala nätverk möjliggör snabb spridning av idéer och innovationer, medan negativ information också kan spridas brett. När kaskader med olika åsikter når samma användare, är kaskaden som anländer först den mest sannolika att tas av användaren. Därför, när fel information eller rykte upptäcks, en naturlig inneslutningsmetod är att införa en positiv kaskade tävlande mot ryktet. Med tanke på en budget k, det rykte blockera problemet ber k frö användare att utlösa spridningen av den positiva kaskaden så att antalet användare som inte påverkas av rykte kan maximeras. De tidigare verken har visat att ryktet blockera problemet kan approximeras inom en faktor av (1 − 1/e − δ) av en klassisk girig algoritm i kombination med Monte Carlo simulering med körtiden av O( ), där n och m är antalet användare respektive kanter. Tyvärr är Monte-Carlo-simuleringsbaserade metoder extremt tidskrävande och de befintliga algoritmerna antingen handel prestanda garanterar praktisk effektivitet eller vice versa. I detta dokument presenterar vi en randomiserad algoritm som körs i O( km ln n δ 2 ) förväntad tid och ger en (1 − 1/e − δ) - approximation med stor sannolikhet. De experimentella resultaten på både de verkliga och syntetiska sociala nätverken har visat att den föreslagna slumpmässiga ryktesblockerande algoritmen är mycket effektivare än hjärtstatsmetoden och den kan hitta frönoder som är effektiva för att begränsa spridningen av rykten.
I REF tas problemet med ryktesblockering upp under den konkurrenskraftiga IC-modellen och en randomiserad algoritm utvecklas för valet av fröuppsättningen som kan ge maximal minskning av antalet dåligt infekterade noder.
An efficient randomized algorithm for rumor blocking in online social networks
{'venue': 'IEEE INFOCOM 2017 - IEEE Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2017 - IEEE Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}