Abstract-influence maximization är problemet med att hitta en liten uppsättning frönoder i ett socialt nätverk som maximerar spridningen av inflytande under en viss diffusion modell. Den Greedy algoritm för influens maximisering först föreslås av Kempe, senare förbättras av Leskovec lider av två källor för beräkningsbrist: 1) behovet av att utvärdera många kandidat noder innan du väljer ett nytt frö i varje omgång, och 2) beräkningen av påverkan spridning av varje frö uppsättning bygger på Monte-Carlo simuleringar. I detta arbete tar vi itu med båda problemen genom att ta fram effektiva algoritmer för att beräkna påverkan sprids och avgöra den bästa kandidaten för utsädesval. Den grundläggande insikten bakom de föreslagna algoritmerna är kopplingen mellan bestämning av påverkansspridning och trosförökning på en riktad acyklisk graf (DAG). Experiment med verkliga sociala nätverksgrafer med skalor från tusentals till miljontals kanter visar den överlägsna prestandan hos de föreslagna algoritmerna med måttliga beräkningskostnader.
Författarna till REF visar att prestandan för deras algoritm inte är väsentligt sämre än för den giriga algoritmen.
Influence Spread in Large-Scale Social Networks – A Belief Propagation Approach
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}