Influence maximization problem: properties and algorithms
- PDF / 399,914 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 238 Views
Influence maximization problem: properties and algorithms Wenguo Yang1
· Yapu Zhang1 · Ding-Zhu Du2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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 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
B
Wenguo Yang [email protected] Yapu Zhang [email protected] Ding-Zhu Du [email protected]
1
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
2
Department of Computer Science, University of Texas at Dallas, Richardson, USA
123
Journal of Combinatorial Optimization
1 Introduction With the rapid development of social networks and its extensive applications in viral marketing, content recommendation and so on (Domingos and Richardson 2001; Richardson and Domingos 2002; Kempe et al. 2003; Zhu et al. 2010; Chaoji et al. 2012; Zhang et al. 2013; Wang et al. 2017), an influence function maximization problem (IFMP) is proposed as follow: max σ (S),
|S|≤k
where σ (S) is a non-negative increasing set function. In fact, the influence maximization (Kempe et al. 2003), content maximization (Chaoji et al. 2012), and activity maximization (Wang et al. 2017) all belong to the IFMP. This is a hard combinatorial optimization problem because it has been proved that calculating the function value of a set is #P hard. Fortunately, a simple but effective greedy algorithm on the submodular IFMP was first proposed by Cornuejols et al. (1977), Nemhauser et al. (1978), and a 1 − 1/e approximation ratio was guaranteed. However, in some cases, objective functions are not submodular. How can the non-submodular version of IFMP be solved? Is there an approximation algorithm similar to the submodular case? How to judge that a solution is optimal, and how can we further improve the soluti
Data Loading...
