Fast Routing in Location-Based Social Networks Leveraging Check-in Data

摘要

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.