Total positive influence domination on weighted networks

2016/04/26 by Danica Vukadinović Greetham, Greetham, Danica Vukadinović, Nathaniel Charlton +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1604.07661

openalex publication_date 2016/04/26 · openalex created_date 2019/12/05 · openalex updated_date 2026/07/28

Abstract

We are proposing two greedy and a new linear programming based approximation algorithm for the total positive influence dominating set problem in weighted networks. Applications of this problem in weighted settings include finding: a minimum cost set of nodes to broadcast a message in social networks, such that each node has majority of neighbours broadcasting that message; a maximum trusted set in bitcoin network; an optimal set of hosts when running distributed apps etc. Extensive experiments on different generated and real networks highlight advantages and potential issues for each algorithm.

Related

• More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives
• Optimizing Spread of Influence in Weighted Social Networks via Partial Incentives
• Distance-Based Influence in Networks: Computation and Maximization
• Spread of Influence in Weighted Networks under Time and Budget Constraints
• Scalable Fair Influence Maximization