2016/10/12 by Gennaro Cordasco, Luisa Gargano, Cordasco, Gennaro +7
Decision Sciences · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Game Theory and Applications #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1610.03721
openalex publication_date 2016/10/12 · openalex created_date 2022/08/15 · openalex updated_date 2026/07/28
Given a network represented by a graph G=(V,E), we consider a dynamical\nprocess of influence diffusion in G that evolves as follows: Initially only\nthe nodes of a given S\⊆ V are influenced; subsequently, at each\nround, the set of influenced nodes is augmented by all the nodes in the network\nthat have a sufficiently large number of already influenced neighbors. The\nquestion is to determine a small subset of nodes S (\a target set) that\ncan influence the whole network. This is a widely studied problem that\nabstracts many phenomena in the social, economic, biological, and physical\nsciences. It is known that the above optimization problem is hard to\napproximate within a factor of 2^\log1-\ε|V|, for any \ε\n>0. In this paper, we present a fast and surprisingly simple algorithm that\nexhibits the following features: 1) when applied to trees, cycles, or complete\ngraphs, it always produces an optimal solution (i.e, a minimum size target\nset); 2) when applied to arbitrary networks, it always produces a solution of\ncardinality which improves on the previously known upper bound; 3) when applied\nto real-life networks, it always produces solutions that substantially\noutperform the ones obtained by previously published algorithms (for which no\nproof of optimality or performance guarantee is known in any class of graphs).\n