• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Chen, Shengminjie (Chen, Shengminjie.) | Yang, Wenguo (Yang, Wenguo.) | Zhang, Yapu (Zhang, Yapu.) | Gao, Suixiang (Gao, Suixiang.)

Indexed by:

EI Scopus SCIE

Abstract:

In the last few decades, profit maximization (PM), which is mainly considered for maximizing net profits, i.e., the difference between gain and cost, has been a prominent issue for online social networks (OSNs). However, the output-to-input ratio, which is an important metric in economics, is also worth studying for OSNs. In this article, we present a novel problem that considers the PM problem from the ratio of gain and cost, known as output-to-input ratio maximization (OIRM). Unfortunately, it is neither submodular nor supermodular. The hill-climbing greedy algorithm for solving this problem is a 1-e<^>-(1-c_g) approximation algorithm, where c_g is the curvature of the monotone submodular set function g. To speed up the hill-climbing greedy algorithm, we propose the threshold decrease algorithm and prove that its approximation ratio is 1-e<^>-(1-c_g)<^>2-epsilon . In addition, based on the relationship between classical net PM and OIRM, the algorithms for solving PM can also solve OIRM. Finally, we evaluate the performance of our algorithms using massive experiments on real datasets. To the best of our knowledge, this is the first time to study the OIRM in viral marketing.

Keyword:

Stochastic processes nonsubmodular maximization Costs Hill-climbing greedy threshold decrease algorithm profit maximization (PM) Approximation algorithms Greedy algorithms Social networking (online) Cost function Integrated circuit modeling

Author Community:

  • [ 1 ] [Chen, Shengminjie]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 2 ] [Yang, Wenguo]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 3 ] [Gao, Suixiang]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 4 ] [Zhang, Yapu]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS

ISSN: 2329-924X

Year: 2022

Issue: 3

Volume: 10

Page: 958-969

5 . 0

JCR@2022

5 . 0 0 0

JCR@2022

JCR Journal Grade:1

CAS Journal Grade:2

Cited Count:

WoS CC Cited Count: 2

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 6

Affiliated Colleges:

Online/Total:560/10625870
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.