Spread of influence in weighted networks under time and budget constraints
Copyright policy )Spread of influence in weighted networks under time and budget constraints
Given a network represented by a weighted directed graph G, we consider the problem of finding a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible. The dynamic that governs the spread of influence is the following: initially only elements in S are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. We prove that the problem is NP-hard, even in simple networks like complete graphs and trees. We also derive a series of positive results. We present exact pseudo-polynomial time algorithms for general trees, that become polynomial time in case the trees are unweighted. This last result improves on previously published results. We also design polynomial time algorithms for general weighted paths and cycles, and for unweighted complete graphs.
This paper will appear in the special issue of Theoretical Computer Science devoted to selected papers presented at Fun 2014
- University of Campania "Luigi Vanvitelli" Italy
- University of Primorska Slovenia
- Università degli studi di Salerno Italy
- University of Verona Italy
- Simon Fraser University Canada
Dynamic monopolies; Exact pseudo-polynomial time algorithms; Social networks; Spread of influence; Viral marketing, FOS: Computer and information sciences, social networks, Analysis of algorithms and problem complexity, Social networks; Spread of influence; Viral marketing; Dynamic monopolies; Exact pseudo-polynomial time algorithms, viral marketing, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), info:eu-repo/classification/udc/004.021, exact pseudo-polynomial time algorithms, Social and Information Networks (cs.SI), exact polynomial time algorithm, Computer Science - Social and Information Networks, dynamic monopolies, spread of influence, Graph theory (including graph drawing) in computer science, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Combinatorics (math.CO), Social networks; opinion dynamics
Dynamic monopolies; Exact pseudo-polynomial time algorithms; Social networks; Spread of influence; Viral marketing, FOS: Computer and information sciences, social networks, Analysis of algorithms and problem complexity, Social networks; Spread of influence; Viral marketing; Dynamic monopolies; Exact pseudo-polynomial time algorithms, viral marketing, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), info:eu-repo/classification/udc/004.021, exact pseudo-polynomial time algorithms, Social and Information Networks (cs.SI), exact polynomial time algorithm, Computer Science - Social and Information Networks, dynamic monopolies, spread of influence, Graph theory (including graph drawing) in computer science, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Combinatorics (math.CO), Social networks; opinion dynamics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).25 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!