INFLUENCE MAXIMIZATION IN TRAJECTORY DATABASES
ABSTRACT
In this paper, we study a novel problem of influence maximization in trajectory databases that is very useful in preciselocation-aware advertising. It finds k best trajectories to be attached with a given advertisement and maximizes the expected influencea a large group of audience. We show that the problem is NP-hard and propose both exact and approximate solutions to find thebest set of trajectories. In the exact solution, we devise an expansion-based framework that enumerates trajectory combinations in abest-first manner and propose three types of upper bound estimation techniques to facilitate early termination. In addition, we proposea novel trajectory index to reduce the influence calculation cost. To support large k, we propose a greedy solution with anapproximation ratio of (1-1/e), whose performance is further optimized by a new proposed cluster-based method. We also propose athreshold method that can support any approximation ratio _ 2 (0; 1]. In addition, we extend our problem to support the scenario whenthere are a group of advertisements. In our experiments, we use real datasets to construct user profiles, motion patterns and trajectorydatabases. The experimental results verified the efficiency of our proposed methods.\ \
PROPOSED SYSTEM:
our contributions of the paper are as follows.1) We are the first to study and formulate the influencemaximization problem in trajectory databases. 2) We devisean expansion-based framework with three effective upperbound estimation techniques and a novel trajectory index. 3)We propose three approximate methods with performanceguarantees to solve the problem when k is large. In addition,we extend the influence maximization problem to find kbest trajectories for a group of advertisements. 5) We usereal datasets to construct user profiles, motion patternsand trajectory databases. Experimental results show thatour proposed methods can solve the trajectory influencemaximization problem efficiently.
EXISTING SYSTEM:
Influence Maximization in Social Networks. The influencemaximization problem was proposed in andhas attracted much attention since. Initially, the proposedmethods are probabilistic and have no bounded influencespread guarantee. To fix the issue, Kempe et al. proposedtwo discrete influence spread models: Independent Cascade(IC) model and Linear Threshold model. They proved theinfluence maximization problem is NP-hard based on thespread models and proposed a greedy framework with(1 1=e) approximation ratio guarantee. There are manysubsequent studies aiming at improving the efficiency of thegreedy framework. When Independent Cascade (IC) modelis considered, Kimura et al. used the shortest path toapproximate the actual spread process. Leskovec et al. proposed a “lazy-forward” algorithm. Chen et al. proposeda degree-discount heuristics for an IC model whereall propagation probabilities are the same. Chen et al. proposed the PMIA algorithm to solve the influence spreadmaximization problem. Similar ideas have also beenapplied to support Linear Threshold model. The latest workcomes from Tang et al. who proposed an algorithmwith near-optimal time complexity and novel heuristics forimproving empirical efficiency.Topic-aware Influence Maximization. Barbieri et al. proposed the Topic-Aware Influence Cascade (TIC) model.In the TIC model, the relationship strength between twovertices was computed by their topic preference learnedfrom history activities on a social network. Based on theTIC model, Barbieri et al. proposed a similarity-basedmethod, INFLEX, and Chen et al. developed a preprocessingbased strategy, MIS, for topic-aware influencemaximization. However, both INFLEX and MIS have noinfluence spread guarantee. Chen et al. [16] proposed abest effort method which has an influence spread guaranteewhile keeping high performance.Location-aware Influence Maximization. Recently twoworks extended the influence maximization problemby considering the spatial context. finds top-k usersin a location-aware social network that have the highestinfluence upon a group of audience in a specified region,while studies influence maximization under the O2Oenvironment which takes into account the user historicalmobility behaviors.In this paper, we consider a novel influence maximizationproblem in trajectory databases to exhibit its usefulnessin location-aware advertising. The core difference with existingIM work is that we don’t have influence propagation inour model, but propagation is a fundamental assumptionin existing IM problems in social network and leads toperformance bottleneck because a seed user can influencea huge number of other users. The existing work on IMfocuses on how to efficiently and effectively estimate theinfluence propagation, i.e., the number of users influencedby a set of seed users in the social network (which is a #Phardproblem), while most of the existing work use greedyalgorithm to select seed user one by one. In contrast, ourproblem does not have such a social network, and thusour research focus in totally different from those studieson the traditional IM problem. In our work, users aredirectly influenced by trajectories, but not by other users,and calculating the individual influence for each trajectorycan be done in polynomial time (rather than a #P-hardproblem in the traditional IM). Thus, current techniques onIM focus on the optimization of processing the influencepropagation and thus cannot be applied to our problem
CONCLUSION
In this paper, we formulated the influence maximizationproblem in trajectory databases and proved it is NP-hard.To calculate the accurate results efficiently, we devised anexpansion-based framework that enumerates the trajectoryin a best-first manner and proposed three effective upperbounds. To support the problem with large k, we proposedthree approximate methods with performance guarantees.In addition, we extended the problem to find k best trajectoriesfor a group of advertisements. Experimental resultson real datasets showed that our methods can solve thetrajectory influence maximization problem efficiently.
REFERENCES
[1] F. Bonchi, “Influence propagation in social networks: A datamining perspective,” in WI-IAT, 2011.
[2] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan, “A data-basedapproach to social influence maximization,” Proc. VLDB Endow.,2011.
[3] Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie, “Simulatedannealing based influence maximization in social networks,” inAAAI, 2011.
[4] P. Domingos and M. Richardson, “Mining the network value ofcustomers,” in KDD, 2001.
[5] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread ofinfluence through a social network,” in KDD, 2003.
[6] M. Richardson and P. Domingos, “Mining knowledge-sharingsites for viral marketing,” in KDD, 2002.
[7] M. Kimura and K. Saito, “Tractable models for information diffusionin social networks,” in PKDD, 2006.
[8] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen,and N. S. Glance, “Cost-effective outbreak detection in networks,”in KDD, 2007.
[9] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximizationin social networks,” in KDD, 2009.
[10] W. Chen, C.Wang, and Y.Wang, “Scalable influence maximizationfor prevalent viral marketing in large-scale social networks,” inKDD, 2010.
[11] W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximizationin social networks under the linear threshold model,” in ICDM,2010