Location-Based Social Networks

Location-Based Social Networks
The content from Microsoft Research LBSN

The dimension of location brings social networks back to reality, bridging the gap between the physical world and online social networking services. In this project, we introduce and define the meaning of location-based social network (LBSN) and discuss the research philosophy behind LBSNs from the perspective of users and locations.

Concepts

  • Social Networks: A social network is a social structure made up of individuals connected by one or more specific types of interdependency, such as friendship, common interests, and shared knowledge. Generally, a social networking service builds on and reflects the real-life social networks among people through online platforms such as a website, providing ways for users to share ideas, activities, events, and interests over the Internet.
  • Location: a location can be represented in absolute (latitude-longitude coordinates), relative (100 meters north of the Space Needle), and symbolic (home, office, or shopping mall) form. By the meantime, a location usually has three kinds of geospatial represenations: 1) A point location, 2) a region, and 3) a trajectory.
  • Location-Based Social Networks (LBSN): A LBSN does not only mean adding a location to an existing social network so that people in the social structure can share location-embedded information, but also consists of the new social structure made up of individuals connected by the interdependency derived from their locations in the physical world as well as their location-tagged media content, such as photos, video, and texts. Here, the physical location consists of the instant location of an individual at a given timestamp and the location history that an individual has accumulated in a certain period. Further, the interdependency includes not only that two persons co-occur in the same physical location or share similar location histories but also the knowledge, e.g., common interests, behavior, and activities, inferred from an individual’s location (history) and location-tagged data [1][2].

[1] Yu Zheng. Location-based social networks: Users. In Computing with Spatial Trajectories, Zheng, Y and Zhou, X, Eds. Springer, 2011.
[2] Yu Zheng. Tutorial on Location-Based Social Networks. WWW2012.

Two Major Tasks and Objects in LBSN

Location and Social networks

  • Location is not only a dimension but also an important object in LBSN
  • Location and social networks (users) have a mutual reinforcement relationship

Sharing and Understanding

  • A good sharing experience attracting more user-generated data for understanding.
  • A deep understanding of LBSNs provide a better sharing experience in turn.

________________________________________________________

Research Philosophy of LBSNs

Three Major Graphs in a LBSN

  • A user-user graph
  • A location-location graph
  • A user-location graph

Sharing

  • Making sense of raw data
  • Fast and effective information retrieval

Understanding

  • Understanding users
    • User similarity or link prediction
    • Experts/influencers detection
    • Community discovery
  • Understanding locations
    • Interesting locations and travel sequences detection
    • Trip/itinerary planning
    • Location-activity recommendation
    • Preference-aware location and friend recommendation
  • Understanding events
    • Life patterns discovery
    • Unexpected\anomalous\unsual events detection

Unique Challenges of LBSNs

Heterogeneous Networks

  • Locations and users
  • Geo-tagged media and trajectories

Special properties

  • Hierarchy/granularity of locations
  • Sequential property of locations

Fast evolving

  • Users can easily access a new location
  • User experience/knowledge changes fast

______________________________________________________________ 

Selected Representative Research

Inferring User Similarity Based on Location History

 

  • Abstract: An individual’s location history in the real world implies, to some extent, her interests and behaviors. Accordingly, people who share similar location histories are likely to have common interests and behavior. This paper reports on a research that mines similarity between users based on their geographic location histories, considering the sequential, heirarchical and popularity properties of location. The user similarity can enable friend recommendations and community discovery. We further improve this work by exploring the semantic meaning of a user’s location history, e.g., going to a move theater or dining in a restaurant. This would be more effective in measuring two users’ similarity….(refer to the following publications for details).
  • Publication:

____________________________________________________________

Location Recommendation using User-based CF

  • Abstrat: In this scenario, the similarity between each pair of users (introduced above) is incorporated into a collaborative filtering (CF) model to conduct a personalized location recommendation system, which offers locations matching an individual’s preferences. The general idea behind CF model is that similar users vote in a similar manner on similar items. Thus, if similarity is determined between users and items, predictions can be made about a user’s potential ratings of those items. For instance, if we know user A and B are very similar (in terms of their location histories), we can recommend the locations where user A has already been to user B and vice versa.
  • Publication: Yu Zheng, Lizhu Zhang, Zhengxin Ma, Xing Xie, Wei-Ying Ma. Recommending friends and locations based on individual location history. In ACM Transaction on the Web (ACM TWEB),5(1), 2011.

Learning Correlation between Locations Using Human Mobility

  • Abstract: This section focuses on introducing the correlation between locations in the spaces of user behavior, specifically, to what extent two locations are correlated in people’s minds. However, mining the correlation from people’s location histories faces the following two challenges. First, the correlation between two locations does not only depend on the number of users visiting the two locations but also lies in these users’ travel experiences. Second, the correlation between two locations, A and B, also depends on the sequences in which both locations have been visited. In short, the correlation between two locations can be calculated by integrating the travel experiences of the users visiting them on a trip in a weighted manner.
  • Publications: Yu Zheng, Xing Xie. Learning Location Correlation from GPS trajectories. Short paper (6 pages), In proceedings of the International Conference on Mobile Data Management 2010 (MDM 2010), Kensas, Missouri, USA.

Personalized Location Recommendation using Item-based CF

  • Abstrat: User-based collaborative filtering is able to accurately model an individual’s behavior. However, it suffers from the increasing scale of users (in a real system) since the model needs to calculate the similarity between each pair of users. To address this issue, location-based collaborative filtering is proposed. This model regards a physical location as an item and computes the correlation between locations based on the location histories of the users visiting these locations. Given the limited geographical space (i.e., the number of locations is limited), this location-based model is more practical for a real system. The main challenge to the location-based model is how to embody an individual’s behavior which is the advantage of a user-based model. The key is to replace the item similarity with the correlation between locations learnt above.
  • Publications: Yu Zheng, Xing Xie. Learning travel recommendations from user-generated GPS traces. In ACM Transaction on Intelligent Systems and Technology (ACM TIST), 2(1), 2-19.

____________________________________________________________

Mining Interesting Locations and Travel Sequences

  •  Abstract: In this paper, we aim to mine interesting locations and classical travel sequences in a given geospatial region based on multiple users’ GPS trajectories. Here, interesting locations mean the culturally important places, such as Tiananmen Square in Beijing, and frequented public areas, like shopping malls and restaurants, etc.  The key insight is that users’ travel experiences and location interests have a mutual reinforcement relationship. We also mine the classical travel sequences among locations considering the interests of these locations and users’ travel experiences. We evaluated our system using a large GPS dataset collected by 107 users over a period of one year …(refer to the following publication for details).
  • Publication: Yu Zheng, Lizhu Zhang, Xing Xie, Wei-Ying Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of International conference on World Wild Web (WWW 2009), Madrid Spain. ACM Press: 791-800.

___________________________________________________________

Location-Activity Recommendations

  • Abstract: In this paper, by using the location data based on GPS and users’ comments at various locations, we can discover interesting locations and possible activities that can be performed there for recommendations. Our research is highlighted in the following location-related queries in our daily life: 1) if we want to do something such as sightseeing or food-hunting in a large city such as Beijing, where should we go? 2) If we have already visited some places such as the Bird’s Nest building in Beijing’s Olympic park, what else can we do there? By using our system, for the first question, we can recommend her to visit a list of interesting locations such as Tiananmen Square, Bird’s Nest, etc. For the second question, if the user visits Bird’s Nest, we can recommend her to not only do sightseeing but also to experience its outdoor exercise facilities or try some nice food nearby. To achieve this goal, we first model …(refer to the following publication for details).
  • Publication:

___________________________________________________________

Constructing Popular Routes from User Check-in Data

  • Abstract: We present a Route Inference framework based on Collective Knowledge (RICK) to construct the popular routes from uncertain trajectories, e.g., a user’s check-in sequence in FourSquare, geo-tagged photos in Flickr, or the migratory trails of a bird. Explicitly, given a location sequence and a time span, the RICK is able to construct the top-k routes which sequentially pass through the locations within the specified time span, by aggregating such uncertain trajectories in a mutual reinforcement way (i.e., uncertain + uncertain → certain). Our work can benefit trip planning, traffic management, and animal movement studies.
  • Publications:
    • Ling-Yin Wei, Yu Zheng, Wen-Chih Peng, Constructing Popular Routes from Uncertain Trajectories. 18th SIGKDD conference on Knowledge Discovery and Data Mining (KDD 2012).
    • Hechen Liu, Ling-Yin We, Yu Zheng, Markus Schneider, Wen-Chih Peng. Route Discovery from Mining Uncertain Trajectories. Demo Paper, in IEEE International Conference on Data Mining (ICDM 2011).

___________________________________________________________

Location-based and preference-aware recommendations using sparse check-in data

  • Abstract: In this paper, we present a location-based and preference-aware recommender system that offers a particular user a set of venues (such as restaurants and shopping malls) within a geospatial range with the consideration of both: 1) User personal preferences, which are automatically learned from her location
    history and 2) Social opinions, which are mined from the location histories of the local experts. This recommender system can facilitate people’s travel not only near their living areas but also to a city that is new to them.
  • Publication:

____________________________________________________________

Useful Information

Tutorials

  • 3-hour tutorial, “Location-based social networks”, at WWW2012. (Sldies) New!
  • 1-hour tutorial, “Location-Based Social Networks”. ACM SIGSPATIAL GIS’11 (Slides)

Dataset Downloads

Related Books

Related Conferences and Workshops

  • ACM SIGSPATIAL International Workshop on Location-Based Social Networks (LBSN)
  • The 4th International Workshop on Location-Based Social Networks (LBSN 2012) will be held in conjunction with UbiComp 2012 at (CMU) Pittsburgh, USA.

Representative Projects

___________________________________________________________

Publications