Approximation algorithm for partial positive influence problem in social network

DOI10.1007/s10878-016-0005-0zbMath1361.90064OpenAlexW2291861235MaRDI QIDQ511731

Yuqing Zhu, Zhao Zhang, Yingli Ran, Hongwei David Du

Publication date: 22 February 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-016-0005-0

zbMATH Keywords

social networkpartial positive influence dominating setpartial set multicoverpower-law graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks ⋮ Local ratio method on partial set multi-cover ⋮ Pervasive domination ⋮ Approximation algorithm for partial set multicover versus full set multicover ⋮ Connected positive influence dominating set in \(k\)-regular graph ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ An approximation algorithm for the partial covering 0-1 integer program ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ A primal-dual algorithm for the minimum power partial cover problem ⋮ Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting

Uses Software

• plfit

Cites Work

• Unnamed Item
• Unnamed Item
• Partial multicovering and the \(d\)-consecutive ones property
• Polynomial time approximation scheme for \(t\)-latency bounded information propagation problem in wireless networks
• On positive influence dominating sets in social networks
• Approximating covering integer programs with multiplicity constraints
• On the approximability of positive influence dominating set in social networks
• Approximation algorithms for covering/packing integer programs
• A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria
• A Random Graph Model for Power Law Graphs
• The small-world phenomenon
• FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
• Positive Influence Dominating Set in Online Social Networks
• Power-Law Distributions in Empirical Data
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the Greedy Heuristic for Continuous Covering and Packing Problems
• Improved Approximation Guarantees for Packing and Covering Integer Programs

This page was built for publication: Approximation algorithm for partial positive influence problem in social network