Paper Info
Title
Fast Routing in Location-Based Social Networks Leveraging Check-in Data
Abstract
With the extensive use of sensor-embedded smart phones, Location-Based Social Networks (LBSN) become more and more popular among online social networks in recent years. In social networks, constructing the shortest path with minimum cost between any two nodes efficiently is vital for both graph analysis and implementation of applications. This is well known as the routing problem in social networks. However, existing approaches of routing in social networks all fail in the scenario of LBSN which are large and dynamic. In this paper, we work out a fast routing system in LBSN leveraging check-in data to tackle this challenging problem. To be specific, firstly, we demonstrate the existence of the small world phenomenon in LBSN. Secondly, we reveal the friendship-inverse-geography property in LBSN. Thirdly, we design a Location-Based Fast Routing System LBFRS which can accomplish fast routing in LBSN leveraging geographical knowledge predicted from check-in data. Experiments on two real Location-Based Social Networks Go Walla and Bright kite have shown that LBFRS performs much more accurate prediction in geography than the baseline method and accomplishes dozens of times faster routing than Dijkstra in average.
Year
DOI
Venue
2014
10.1109/iThings.2014.77
iThings/GreenCom/CPSCom
Keywords
Field
DocType
small world phenomenon,location-based fast routing system,routing problem,routing algorithm,location-based social networks,sensor-embedded smart phones,location prediction,lbfrs,shortest path,online social networks,lbsn,graph theory,go walla and bright kite,smart phones,social networking (online),graph analysis,friendship-inverse-geography property,mobile computing,prediction algorithms,clustering algorithms,algorithm design and analysis,routing
Algorithm design,Social network,Check-in,Shortest path problem,Static routing,Computer science,Power graph analysis,Cluster analysis,Dijkstra's algorithm,Distributed computing
Conference
Citations 
PageRank 
References 
3
0.38
8
Authors
4
Name
Order
Citations
PageRank
Yulong Gu183.85
Weidong Liu29317.66
Yuan Yao382.51
Jiaxing Song4509.62