Boosting node activity by recommendations in social networks

Wenguo Yang (), Shengminjie Chen (), Suixiang Gao () and Ruidong Yan ()
Additional contact information
Wenguo Yang: University of Chinese Academy of Sciences
Shengminjie Chen: University of Chinese Academy of Sciences
Suixiang Gao: University of Chinese Academy of Sciences
Ruidong Yan: Renmin University of China

Journal of Combinatorial Optimization, 2020, vol. 40, issue 3, No 13, 825-847

Abstract: 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 $${\overline{E}}$$ 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.

Keywords: Activity Probability; Non-submodularity; Greedy algorithm; Sandwich method (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00629-6 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:3:d:10.1007_s10878-020-00629-6

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

DOI: 10.1007/s10878-020-00629-6

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