2015/02/15 by Ferdinando Cicalese, Gennaro Cordasco, Cicalese, Ferdinando +9
Computer Science · Engineering · Physics and Astronomy · #Advanced Graph Theory Research #Advanced Optical Network Technologies #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1502.05599
openalex publication_date 2015/02/15 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Given a network represented by a weighted directed graph G, we consider the\nproblem of finding a bounded cost set of nodes S such that the influence\nspreading from S in G, within a given time bound, is as large as possible. The\ndynamic that governs the spread of influence is the following: initially only\nelements in S are influenced; subsequently at each round, the set of influenced\nelements is augmented by all nodes in the network that have a sufficiently\nlarge number of already influenced neighbors. We prove that the problem is\nNP-hard, even in simple networks like complete graphs and trees. We also derive\na series of positive results. We present exact pseudo-polynomial time\nalgorithms for general trees, that become polynomial time in case the trees are\nunweighted. This last result improves on previously published results. We also\ndesign polynomial time algorithms for general weighted paths and cycles, and\nfor unweighted complete graphs.\n