A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks

Weidong Chen (), Hao Zhong (), Lidong Wu () and Ding-Zhu Du ()
Additional contact information
Weidong Chen: South China Normal University
Hao Zhong: South China Normal University
Lidong Wu: University of Texas at Tyler
Ding-Zhu Du: University of Texas at Dallas

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 1, 20 pages

Abstract: Abstract In social networks, the minimum positive influence dominating set (MPIDS) problem is NP-hard, which means it is unlikely to be solved precisely in polynomial time. For the purpose of efficiently solving this problem, greedy approximation algorithms seem appealing because they are fast and can provide guaranteed solutions. In this paper, based on the classic greedy algorithm for cardinality submodular cover, we propose a general greedy approximation algorithm (GGAA) for the MPIDS problem, which uses a generic real-valued submodular potential function, and enjoys a provable approximation guarantee under a wide condition. Two existing greedy algorithms, one of which is unknown for having an approximation ratio, both can be viewed as the specific versions of GGAA, and are shown to enjoy an approximation guarantee of the same order. Applying the framework of GGAA, we also design two new greedy approximation algorithms with fractional submodular potential functions. All these greedy algorithms are $$O(\ln \alpha )$$ O ( ln α ) -approximations where $$\alpha $$ α is the maximum node degree of the network graph, while it is shown experimentally that these two new algorithms can yield better solutions on typical real social network instances. In this work, as a by-product, we achieve a new approximation ratio of the classic greedy algorithm for cardinality submodular cover, which slightly generalizes two existing results.

Keywords: Social network; Positive influence dominating set; Submodular function; Greedy approximation (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00812-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00812-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00812-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().