Near Optimal Social Promotion in Online Social Networks

Simple item page
dc.contributor.ORCID0000-0001-6407-834X (YUAN, J)
dc.contributor.advisorWu, Weili
dc.creatorYuan, Jing
dc.date.accessioned2019-04-25T21:28:15Z
dc.date.available2019-04-25T21:28:15Z
dc.date.created2018-12
dc.date.issued2018-12
dc.date.submittedDecember 2018
dc.date.updated2019-04-25T21:30:26Z
dc.description.abstractDue to dramatic growth of user population in the past decade, online social networks have become attractive channels for companies to launch marketing campaigns. We study a couple of closely related problems in online social networks. We first study the problem of active friending, which can be considered as a service provided by the social platforms to stimulate user engagement. The idea is that a source user can name a target user and the social platform offers a friending strategy to maximize the probability of the target accepting the invitation from the source. We prove that the problem is NP-hard and propose a discrete semi-differential based algorithm with guaranteed approximation ratio. As for the profit maximization problem, we consider the scenario when a profit is generated from group activities, captured by a hypergraph where hyperedges are introduced to represent the interactions among multiple users. We prove that the problem is NP-hard and develop an approximation algorithm along with an exchange-based technique to maximize the profit generated from group activities. In social advertising, the goal of online social platforms is to optimize the ad allocation with multiple advertisers. We access the tradeoff between maximizing the revenue earned from each advertiser and reducing free-riding to ensure the truthfulness of advertisers. We prove that both budgeted and unconstrained ad allocation problems are NP-hard and then develop constant factor approximation algorithms for both problems. We also study the adaptive version of the seed selection problem and the discount allocation problem. The goal is to find a limited set of highly influential seed users to assign proper discounts, such that the number of users who finally adopt the product is maximized. We propose a series of adaptive policies with bounded approximation ratio for both problems.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10735.1/6381
dc.language.isoen
dc.subjectApproximation algorithms
dc.subjectOnline social networks
dc.subjectViral marketing
dc.subjectInternet advertising
dc.titleNear Optimal Social Promotion in Online Social Networks
dc.typeDissertation
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.levelDoctoral
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETD-5608-011-YUAN-9433.17.pdf
Size:
3.01 MB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description:
Download

Collections

UTD Theses and Dissertations