Boosting node activity by recommendations in social networks
- PDF / 918,406 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 31 Downloads / 191 Views
Boosting node activity by recommendations in social networks Wenguo Yang1
· Shengminjie Chen1 · Suixiang Gao1 · Ruidong Yan2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In a social network, the propagation of information has sparked intense research. Influence Maximization (IM) is a well-studied problem that asks for k nodes to influence the largest users in the social network. However IM is submodular at the most time. In recent years, many non-submodular problems have been proposed and researchers give a lot of algorithms to solve them. In this paper, we propose Activity Probability Maximization Problem without submodular property. For a given social network G, a candidate edge set E and a constant k, the Activity Probability Maximization Problem asks for k edges in the candidate edge set that make the all nodes of G with highest probability of being activated under a pre-determined seed set S. Using the marginal increment, we give a general way to construct submodular lower bound and submodular upper bound functions of the non-submodular objective function at the same time. Interestingly, the optimal solution of upper bound is the same as that of lower bound. Therefore, we develop the Sandwich framework called Semi-Sandwich framework. Based on the same optimal solution of lower and upper bounds, we propose a Difference Minimizing Greedy (DMG) algorithm to get an approximation solution of the original problem. Through massive experiments, we show that the method and algorithm are effective.
B
Suixiang Gao [email protected] Wenguo Yang [email protected] Shengminjie Chen [email protected] Ruidong Yan [email protected]
1
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
2
School of Information, Renmin University of China, Beijing 100872, China
123
Journal of Combinatorial Optimization
Keywords Activity Probability · Non-submodularity · Greedy algorithm · Sandwich method
1 Introduction With the growth of social media and the rise in popularity of its users, social network, which has users (nodes) and relationships (edges) between users, plays an important role as a medium for the spread of information. For example, a large number of Internet users are involved in the dissemination of information (news, photos, videos, reviews etc) through Twitter, Facebook, Wechat et al. The research on the dissemination of information in social network has attracted lots of researchers. Domingos and Richardson (2001) and Richardson and Domingos (2002) proposed the Influence Maximization Problem by viral marketing. The general aim of IM is selecting k nodes from graph G which can (directly or indirectly) influence the largest number of nodes. Kempe and Kleinberg (2003) firstly constructed the formal statement of influence maximization as a discrete combinatorial optimization problem. This groundbreaking work has inspired a large number of related research in the past decade (Bharathi et al. 2007; Chen et al. 2009; Wang et al. 2010; N
Data Loading...
