Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

Details Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

2012-04-13

arxiv.org/abs/1204.3074v1

Computer Science

Social and Information Networks

18 pages, 9 figures. Extended abstract appears in proceedings of AAAI 2012

Scientific paper

Influence maximization is a problem of finding a small set of highly influential users, also known as seeds, in a social network such that the spread of influence under certain propagation models is maximized. In this paper, we consider time-critical influence maximization, in which one wants to maximize influence spread within a given deadline. Since timing is considered in the optimization, we also extend the Independent Cascade (IC) model and the Linear Threshold (LT) model to incorporate the time delay aspect of influence diffusion among individuals in social networks. We show that time-critical influence maximization under the time-delayed IC and LT models maintains desired properties such as submodularity, which allows a greedy approximation algorithm to achieve an approximation ratio of $1-1/e$. To overcome the inefficiency of the greedy algorithm, we design two heuristic algorithms: the first one is based on a dynamic programming procedure that computes exact influence in tree structures and directed acyclic subgraphs, while the second one converts the problem to one in the original models and then applies existing fast heuristic algorithms to it. Our simulation results demonstrate that our algorithms achieve the same level of influence spread as the greedy algorithm while running a few orders of magnitude faster, and they also outperform existing fast heuristics that disregard the deadline constraint and delays in diffusion.

Affiliated with

Also associated with

No associations

Rating

Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-144692