Influence maximization problem: properties and algorithms

Wenguo Yang (), Yapu Zhang () and Ding-Zhu Du ()
Additional contact information
Wenguo Yang: University of Chinese Academy of Sciences
Yapu Zhang: University of Chinese Academy of Sciences
Ding-Zhu Du: University of Texas at Dallas

Journal of Combinatorial Optimization, 2020, vol. 40, issue 4, No 5, 907-928

Abstract: Abstract The influence maximization problem has become one of the fundamental combinatorial optimization problems over the past decade due to its extensive applications in social networks. Although a $$1-1/e$$ 1 - 1 / e approximation ratio is easily obtained using a greedy algorithm for the submodular case, how to solve the non-submodular case and enhance the solution quality deserve further study. In this paper, based on the marginal increments, we devise a non-negative decomposition property for monotone function and a non-increasing decomposition property for monotone submodular function (NDP). According to the exchange improvement (EI), a necessary condition for an optimal solution is also proposed. With the help of NDP and EI condition, an exchange improvement algorithm is proposed to improve further the quality of the solution to the non-submodular influence maximization problem. For the influence maximization, we devise effective methods to compute the influence spread and marginal gain in a successive iteration update manner. These methods make it possible to calculate the influence spread directly and accurately. Next, we design a data-dependent approximation algorithm for a non-submodular topology change problem from a marginal increment perspective.

Keywords: Submodular function; Marginal increment; Approximation algorithm (search for similar items in EconPapers)
Date: 2020
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-020-00638-5 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:40:y:2020:i:4:d:10.1007_s10878-020-00638-5

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

DOI: 10.1007/s10878-020-00638-5

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 ().