UVM Theses and Dissertations
Format:
Print
Author:
Cao, Tianyu
Dept./Program:
Computer Science
Year:
2012
Degree:
PhD
Abstract:
Social networks are ubiquitous in the spread of opinions, ideas, innovations and recommendations. Weak social ties play an important role in decision making for people living in a society. A better insight to this dynamic process gives birth to a new kind of marketing strategy "viral marketing". In "viral marketing" a company sends their products to some test users. The test users will recommend the product to their friends and some of their friends will try the product and even recommend it to the friends' friends. This process goes on until no more friends make recommendations on it. Given this assumption, the influence maximization problem is defined as how to select the test users so that the number of potential product buyers is maximized. In this thesis, we are interested in solving the influence maximization problem and the information diffusion model learning problem. The three major contributions of the dissertation are as follows.
1. We provide an effcient algorithm to solve the influence maximization problem. We devise an algorithm that makes use of modularity of the social networks. The time complexity of the proposed algorithm is O(nlogn), which is an improvement compared to the greedy algorithm's quadratic time complexity.
2. We define the problem of how to construct the information diffusion trace so that we can learn the information diffusion model as accurately as possible. We propose a weighted sampling algorithm based on least confidence sampling to solve the problem.
3. We show the implications of sparsity of information diffusion traces to learning information diffusion models. We propose to use regularization schemes to resolve the over-fitting problem resulted from the sparsity of diffusion trace. Experiments show that the proposed regularization scheme can improve the learning process.
The above contributions provide efficient algorithms to solve two important problems in "viral marketing" on social networks, which are the influence maximization problem and the information diffusion model learning problem.
1. We provide an effcient algorithm to solve the influence maximization problem. We devise an algorithm that makes use of modularity of the social networks. The time complexity of the proposed algorithm is O(nlogn), which is an improvement compared to the greedy algorithm's quadratic time complexity.
2. We define the problem of how to construct the information diffusion trace so that we can learn the information diffusion model as accurately as possible. We propose a weighted sampling algorithm based on least confidence sampling to solve the problem.
3. We show the implications of sparsity of information diffusion traces to learning information diffusion models. We propose to use regularization schemes to resolve the over-fitting problem resulted from the sparsity of diffusion trace. Experiments show that the proposed regularization scheme can improve the learning process.
The above contributions provide efficient algorithms to solve two important problems in "viral marketing" on social networks, which are the influence maximization problem and the information diffusion model learning problem.