Friendship Recommendation in Location-based Social Networks

Proposed Solution

\label{sec:solution} In this section, ...

Intuition

The goal of this work is to recommend friends for users based on their mobility information. The main hypothesis behind is that friends tend to visit similar places, it is in fact an example of the social homophily theory which states that friends tend to share similar behaviors.

The most straightforward implementation of our hypothesis is to recommend those who have visited many same places as a user as friends. For example, if a user Alice often visits the same coffee shop and restaurant as Bob, then there is a good chance that they will become friends.

Besides, properties of locations that a user has visited such as location category (e.g., a restaurant or a bar) and visiting hours (10pm or 8am) can reflect his behavior as well. Users visiting same kinds of locations at roughly the same time are probably sharing the same hobbies or life patterns. Following the above mentioned social homophily theory, these users are more likely to become friends than others. For example, Bob and Charlie may often visit different model shops on weekends, then it is meaningful to recommend them to be friends.

Taking the user side, a user’s demographic information, such as age and gender, also contributes to the friends he has. For example, suppose that Alice, Bob and Charlie often visit one same place, Alice and Bob have the similar age while Charlie are 20 years older than them, then it is more reasonable to recommend Bob not Charlie as Alice’s friend.

Following the above discussion, our intuition can be summarized as follows:

  • a user is more likely to become friends with those who visit same places as him;

  • a user is more likely to become friends with those who visit similar types of places at the similar time as him;

  • a user is more likely to become friends with those who share the same profile information as him.

Data model

To capture the above intuition, we first model our information into three types of networks including user-location network (\({G_{{U},{L}}}\)), user-profile network (\({G_{{U},{P}}}\)) and location-category network (\({G_{{L},{C}}}\)).

User-location network. A user-location network is a directed weighted bipartite graph denoted by \({G_{{U}, {L}}} = ({U}, {L}, {E_{{U}, {L}}})\). \({U}\) and \({L}\) represent users and locations, respectively, while \({E_{{U}, {L}}} \subseteq {U}\times {L}\) contains all the edges. Each edge \({e_{i, j}^{{U}, {L}}}\) is affiliated with a weight \({w_{i, j}^{{U}, {L}}}\) which is simply defined as the number of times \({u}_i\) visits \({\ell}_j\).

We exploit matrix \({X}\) to represent \({G_{{U}, {L}}}\), \({X}_{i,j}={w_{i, j}^{{U}, {L}}}\) if there exists a link from \({u}_i\) to \({\ell}_j\), otherwise, \({X}_{i, j} = 0\). The transpose of \({X}\) is defined by \({\cal{X}}\). We further use \({\bar{X}}\) and \({\bar{\cal{X}}}\) to denote the column stochastic matrices of \({X}\) and \({\cal{X}}\) where \({\bar{X}}(i, j) = \frac{{w_{i, j}^{{U}, {L}}}}{\sum_{k} {w_{k, j}^{{U}, {L}}}}\) and \({\bar{\cal{X}}}(i, j) = \frac{{w_{j, i}^{{U}, {L}}}}{\sum_{k} {w_{j, k}^{{U}, {L}}}}\).

User-profile network. A user-profile network is a bipartite graph denoted by \({G_{{U}, {P}}} = ({U}, {P}, {E_{{U}, {P}}})\). \({P}\) represents profile nodes and \({E_{{U}, {P}}}\subseteq {U}\times {P}\) contains all the edges in \({G_{{U}, {P}}}\).

Matrix \({Y}\) represents \({G_{{U}, {L}}}\) where \({Y}_{i, j} = 1\) if \({u}_i\) has profile \({p}_j\). We use \({\cal{Y}}\) to represent \({Y}\)’s transpose, \({\bar{Y}}\) and \({\bar{\cal{Y}}}\) are the column stochastic matrices of \({Y}\) and \({\cal{Y}}\), respectively.

Location-category network. A location-category network is a bipartite graph denoted by \({G_{{L}, {C}}} = ({L}, {C}, {E_{{L}, {C}}})\). \({C}\) contains all the location types and \({E_{{L}, {C}}}\subseteq {L}\times {C}\). As presented in our second intuition, a category here is in fact a combination of category and time, e.g., food places during evening. We will talk about it in detail in our experiment.

Matrix \({Z}\) represents \({G_{{L}, {C}}}\) where \({Z}_{i, j}\) indicates that \({\ell}_i\) falls into category \({c}_j\). Similar to the definitions for \({G_{{U}, {L}}}\) and \({G_{{U}, {P}}}\), we use \({\cal{Z}}\) to denote \({Z}\)’s transpose and \({\bar{Z}}\) (\({\bar{\cal{Z}}}\)) to denote the stochastic matrix of \({Z}\) (