在行動社群網路上基於移動行為的影響最大化分析

Abstract

影響最大化的分析是在一群使用者當中找到幾個影響力最大的種子使用者，最常見的應用就是病毒式行銷。基於不同的推薦商家，使用者的喜好也會隨之改變，然而現有的研究當中大多數都假設是固定的傳播模型，並沒有考慮到商家的地理因素。例如，使用者會傾向到過去曾經到過的地點附近，而我們稱使用者過去的歷史紀錄為移動行為。

由於智慧型手機與web 2.0的興起，使用者能夠發布打卡訊息在行動社群網路上，且與朋友分享。在這研究當中，我們專注在使用者的移動行為與推薦地點的地理關係，且提出基於移動行為的影響最大化問題，此問題主要結合傳統的影響最大化與使用者的移動行為。

為了解決包含推薦商家的影響最大化問題，傳統的方法是去從使用者的移動行為去學習此使用者到推薦商家的機率，然後在應用影響最大化的技術去找出種子使用者。為了提高效率，我們首先提出CELF與Estimation兩種貪婪框架的方法，這兩種方法皆可以達到1-1⁄e的保證。之後我們提出RegionSample的方式更進一步減少計算時間且達到ε*(1-1⁄e)的保證。實驗結果顯示在兩個資料集合中，在此研究提出的方法能同時兼顧效率與效用。

Influence maximization is the problem that find the set of small seed users who can influence maximum number of users. The most popular application of influence maximization is viral marketing. Based on different promoted location, the preference of user will change, but most of works only consider the static propagation model and do not take properties of promoted location into consideration. For example, users are more likely go to the location which satisfy his historical movement behavior(user mobility).

Thanks to the explosion of smartphones and web 2.0 techniques, users can post check-in records on location-based social networks (LBSNs) platform and share the experience with their friends. In this paper, we focus on geospatial properties between user and promoted location and propose the mobility-based influence maximization, which combine user mobility with traditional influence maximization problem for location promotion.

To perform the query contained promoted location, the naive approach is to learn the probability from check-in records and then utilize the existing influence maximization algorithms to extract seed. To speed up the procedure, firstly, we propose CELF-based method and Estimation-based method with three index methods with 1-1⁄e guarantee. Further, we provide a approximation approach to get better efficiency with ε*(1-1⁄e) guarantee. Experiment results on two real datasets to demonstrate the effectiveness and efficiency of our methods and state-of-art algorithms.