Vi anser att problemet med att hitta en uppsättning k hörn av maximal total påverkan i ett givet oriktat nätverk, under den oberoende kaskad (IC) modellen för inflytande spridning. Det är känt att påverkan är submodulär i IC-modellen, och därmed en girig algoritm uppnår en (1 - 1/ e) approximation till detta problem; dessutom är det känt att det är NP- svårt att uppnå en bättre approximationsfaktor i riktade nätverk. Vi visar att för oriktade nätverk kan denna approximationsbarriär övervinnas: den giriga algoritmen får en (1 − 1/e + c) approximation till uppsättningen av optimal påverkan, för vissa konstant c > 0. Våra bevis fortskrider genom probabilistisk analys av bindningsperkolering i godtyckliga finita nätverk. Vi visar också att påverkan maximering problem fortfarande APX-hård i
Som tidigare nämnts visade Khanna och Lucier REF för den oberoende kaskadmodellen med oriktade grafer att den giriga algoritmen uppnår en (1 − (1 − 1/k) k + c) - approximation för vissa konstant c > 0.
Influence Maximization in Undirected Networks
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}