臺灣博碩士論文加值系統

This thesis investigates finding the influential nodes in the location-based social network (LBSN). When the users write comments about a location, it is likely that their writing behavior is influenced by others. We observe the real LBSN data and propose a general method to find the influential nodes in an LBSN. We use the Foursquare data to fit the information diffusion model and compute each node’s influence degree, and use a greedy algorithm to find the set of top-k influential nodes of the LBSN. The set of top-k influential nodes can influence the largest number of nodes in an LBSN. The previously best way to find influential nodes uses the information diffusion model to trace all of the nodes in an LBSN and thus costs a lot of time. This thesis uses the information diffusion model to trace each user’s friends and proposes an algorithm to extract the k nodes with high influence among friends. Compared with the previously best result, we show that our method saves a lot of time and the error of our approximation is small.

口試委員會審定書 ii
中文摘要 iii
Abstract iv
Chapter 1 Introduction 1
1.1 Background 1
1.2 Research Problem 3
1.3 Methodology Overview and Contributions 3
1.4 Thesis Organization 4
Chapter 2 Related Work 6
Chapter 3 Building an Attractiveness Model for the Foursquare Data 8
3.1 The Foursquare Data 8
3.2 An Attractiveness Model with Spatial and Temporal Features in Foursquare 10
Chapter 4 Finding Influential Nodes in an LBSN 14
4.1 Wave Diffusion Model 14
4.2 Algorithms for Influence Maximization 14
4.3 Time Complexity Analysis 19
Chapter 5 Performance Evaluation 21
5.1 Settings 21
5.2 Degree of Influence Maximization 22
5.3 Efficiency Analysis 25
5.4 WGA and WGAOF 26
Chapter 6 Conclusion 29
References 30

[1]N. Benchettara, R. Kanawati and C. Rouveirol, “Supervised Machine Learning Applied to Link Prediction in Bipartite Social Networks,” ASONAM, 2010, pp. 326–330.
[2]X. Cai, M. Bain, A. Krzywicki, W. Wobcke, Y. S. Kim, P. Compton and A. Mahidadia, “Reciprocal and Heterogeneous Link Prediction in Social Networks,” PAKDD, 2012, pp. 193–204.
[3]E. Cho, S. A. Myers and J. Leskovec, “Friendship and Mobility: User Movement in Location-Based Social Network,” KDD, 2011, pp. 1082–1090.
[4]W. Chen, Y. Wang and S. Yang, “Efficient Influence Maximization in Social Network,” KDD, 2009, pp. 199–208.
[5]S. Debnath, N. Ganguly, P. Mitra, “Feature Weighting in Content Based Recommendation System Using Social Network Analysis,” WWW, 2008, pp. 1041–1042.
[6]P. Domingos and M. Richardson, “Mining the Network Value of Customers,” KDD, 2001, pp. 57–66.
[7]M. Granovetter, “Threshold Models of Collective Behavior,” American Journal of Sociology 83(6), 1978, pp. 1420–1443.
[8]D. Kempe, J. Kleinberg and E. Tardos, “Influential Nodes in a Diffusion Model for Social Network,” ICALP, 2005, pp. 1127–1138.
[9]D. Kempe, J. Kleinberg and E. Tardos, “Maximizing the Spread of Influence through a Social Network,” KDD, 2003, pp. 137–146.
[10]C. T. Li and S. D. Lin, “Social Flocks: a Crowd Simulation Framework for Social Network Generation, Community Detection, and Collective Behavior Modeling,” KDD, 2011, pp. 765–768.
[11]I. Konstas, V. Stathopoulos and J. M. Jose, “On Social Networks and Collaborative Recommendation,” SIGIR, 2009, pp. 195–202.
[12]Y. Wang, G. Cong, G. Song and K, Xie, “Community-Based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks,” KDD, 2010, pp. 1039–1048.
[13]D. Lopez-Pintado, “Diffusion in Complex Social Networks,” Journal of Economic Literature 62(2), 2004, pp. 573–590.
[14]H. Ma, H. Yang, M. R. Lyu and I. King, “Mining Social Networks Using Heat Diffusion Processes for Marketing Candidate Selection,” CIKM, 2008, pp. 233–242.
[15]M. Ye, P. Yin, W. C. Lee and D. L. Lee, “Exploiting Geographical Influence for Collaborative Point-of-Interest Recommendation,” SIGIR, 2011, pp. 325–334.
[16]A. Noulas, S. Scellato, C. Mascolo and M. Pontil, “An Empirical Study of Geographic User Activity Patterns in Foursquare,” ICWSM, 2011.
[17]M. A. Vasconcelos, S. M. R. Ricci, J. M. Almeida, F. Benevenuto and V. A. F. Almeida, “Tips, Dones and Todos: Uncovering User Profiles in Foursquare,” WSDM, 2012, pp. 653–662.
[18]J. Xie and B. K. Szymanski, “Towards Linear Time Overlapping Community Detection in Social Networks,” PAKDD, 2012, pp. 25–36.
[19]V. W. Zheng, B. Cao, Y. Zheng, X. Xie and Q. Yang, “Collaborative Filtering Meets Mobile Recommendation: A User-centered Approach,” AAAI, 2010.
[20]L. Zhang, J. Wu, Z. C. Wang and C. J. Wang, “Multi-relational Topic Model for Social Recommendation,” ICTAI, 2010, pp. 349–350.
[21]V. W. Zheng, Y. Zheng, X. Xie and Q. Yang, “Collaborative Location and Activity Recommendations with GPS History Data,” WWW, 2010, pp. 1029–1038.
[22]Y. Zheng, “Tutorial on Location-Based Social Networks,” WWW, 2012.