基于签到数据进行好友关系推理的关键在于选择合适的特征参数衡量和判断各个用户之间的关系。本文主要是基于Gowalla和Brightkite两组社交网络签到数据集进行实验和分析（见表 1），数据集中除了用户的签到数据外还包含用户间的社交关系数据，用户的签到数据是一个五元组：

式中，$c_{\mathrm{i}\mathrm{n}}(i,j)$为第$i$个用户的第$j$条签到数据；$u_i$为第$i$个用户的用户标识；$t_j$为第$j$条签到数据的时间；$B_j$和$L_j$分别为第$j$条签到数据的纬度和经度；$l_j$为第$j$条签到数据的签到地点标识。用户间的社交关系数据是一个无向图$G_s=(U_s,E_s)$，每一组数据记录了构成好友关系的用户$U_i$和$U_j$的标识。

本文以信息熵^[14]表示社交网络中好友关系（目标属性）的信息量，利用信息增益（information gain，IG）^[15]评估所选特征参数对目标属性的贡献程度。对于目标属性$X$和待评估特征参数$Y$，IG为$X$的信息熵$H(X)$与目标属性$X$关于待评估特征参数$X$的信息期望^[14]的差值，计算如下：

设目标属性$X$有$n$个值$\{x_{\mathrm{1}},x_{\mathrm{2}}\dots x_n\}$，$p(x_i)$为关于$x_i$的概率统计函数，则信息熵计算如下：

设待评估特征参数有$m$个值$\{y_{\mathrm{1}},y_{\mathrm{2}}\dots y_m\}$，$p(y_i)$为关于$y_i$的概率统计函数，$p(x_i|y_j)$为$X=x_i$时$Y=y_i$的条件概率，则信息熵计算如下：

本文以Gowalla数据集中的纽约市的签到数据为例进行信息增益计算，其中用户人数$n$为3 101人，好友数$r$为10 194对，非好友数（$C_n^{\mathrm{2}}-r$）为4 796 356对，则目标属性（社交关系）的信息熵为0.021 892。选取用户居住地、时空共现区、用户签到数目、用户签到频率等几个特征参数计算信息增益，结果如表 2所示。由表 2可知，用户签到数目和用户签到时间的信息增益较小，说明其对目标属性的贡献程度较小。因此本文选取信息增益较大的用户居住地和时空共现区作为特征参数，并分别对用户居住地和时空共现区对好友关系的影响进行了分析。

由于签到数据中并没有明确地给出用户居住地的信息，因此本文将研究区域划分成$s\times s$的离散规则格网，首先通过统计确定包含签到数据数量最多的格网，然后以该格网内所有签到点的中心位置作为用户居住地的预测位置，该方式的判断结果准确度可以达到85%以上^[10]。

如图 1所示，将研究区域划分成$s\times s$大小的空间区域$A_i$，记各空间区域$A_i$包含用户签到数据的数量为$c_i$，若$A_{\mathrm{m}\mathrm{a}\mathrm{x}}$为各个空间区域中$c_i$最大的区域，$A_{\mathrm{m}\mathrm{a}\mathrm{x}}$中所包含签到数据的集合为$\{c_{\mathrm{i}\mathrm{n}\mathrm{1}},c_{\mathrm{i}\mathrm{n}\mathrm{2}}\dots c_{\mathrm{i}\mathrm{n}n}\}$，则用户居住地位置（$\overline{x},\overline{y}$）为：

图  1  签到数据的规则格网划分

Figure 1.  Regular Grid Partition of Check-in Data

好友之间的居住地平均距离远远小于所有用户之间的居住地平均距离^[16]，为了能够更加直观地分析用户居住地对好友关系的影响，本文采用累积分布函数（cumulative distribution function，CDF）描述用户居住地间的距离对好友概率的影响。设$d_i$为距离统计指标（$i\in [\mathrm{0},n]$），$D$为$n$个统计指标的集合，则关于距离的累积分布函数为：

式中，$D\le d_i,i\in [\mathrm{0},n]$。

本文分别根据Gowalla数据集和Brightkite数据集绘制了CDF曲线，如图 2所示。由图 2可知，大约40%~50%的好友居住地距离在100 km以内，超过3%的好友居住地距离在1 km以内，这种现象在不同数据集中的表现是基本一致的，说明用户之间的好友关系很大程度上受限于空间距离，但仅仅从CDF曲线图中较难分析出好友关系与居住地距离之间的函数比例关系。

图  2  关于距离的累积分布函数

Figure 2.  Cumulative Distribution Function of Distance

为了能够进一步分析好友关系是如何受限于用户居住地距离的，本文通过统计居住地距离为$d$的好友关系数$L_d$研究好友的概率$P(d)$与居住地距离$d$之间的函数关系，记$N_d$为用户之间居住地距离为$d$的数目，则有：

图 3为两组数据集好友概率与居住地距离之间的函数关系图，由图 3可以发现，好友概率与居住地距离符合函数关系$P(d)~d^{-\alpha }$。文献[17-18]发现$P(d)~d^{-\mathrm{1}}$，文献[19]发现$P(d)~d^{-\mathrm{2}}$，而文献[20]发现$P(d)\propto d^{-\mathrm{1}}$。本文结果与上述研究结果一致，且认为$\alpha$的不同主要是由于数据源的类型（如微博签到数据、社交软件签到数据、移动通信数据等）不同引起的，即$\alpha$值取决于数据源的类型。本文通过研究发现Gowalla数据集和Brightkite数据集的$\alpha$值更接近于0.5。

图  3  好友概率与居住地距离的函数关系

Figure 3.  Probability of Friendship Between Two Users as a Function of Their Residence Distance

文献[13]通过对Flickr数据集中带有地理标签的照片进行了分析，发现好友的概率随着时空共现区的个数增加而急剧增加，时空共现区的划分尺寸越小，好友概率越大，同时给出了好友概率-时空共现区模型。如图 1所示，假设$\gamma$为两个好友用户选择访问同一个时空区域的概率，在已知两个用户之间有$k$个共现区（事件$C_k$）的条件下，二者为好友关系（事件$F$）的概率^[13]为：

式中，$N$为用户数目；$p_{\mathrm{1}}^k=\gamma +\left(\mathrm{1}-\gamma \right)/N$；$p_{\mathrm{2}}^k=\mathrm{1}/N$。

如图 1所示，设$T_j$为持续时间为$T$的时间段，假设两个用户$u_{\mathrm{1}}$和$u_{\mathrm{2}}$在同一时间段$T_j$均出现在同一空间区域$A_i$，则在$A_i$与$T_j$约束条件下的区域被称为用户$u_{\mathrm{1}}$和$u_{\mathrm{2}}$的时空共现区。当时间段$T$为2时，用户$A$和用户$B$之间的时空共现区个数$k$为3。时空共现区的大小$s$以及持续时间的长短$T$都会对好友关系的判断产生影响，文献[21]通过研究不同时空共现区的大小与样本数的关系，发现随着时空共现区数量的增加，样本总数迅速增加，但这并不意味好友关系的判断更加准确，而文献[22]研究表明，只有在合理的参数设置下，时空共现区的数量才与是否为好友关系密切相关。

为了能够更进一步分析用户之间的时空共现区数量对好友关系的影响，本文通过统计每两个用户之间的时空共现区数量为$c$的好友关系数$Q_c$，研究好友概率$P(c)$与时空共现区个数$c$之间的函数关系，记$N_c$为用户二元组时空共现区数量为$c$的数目，则有：

在进行时空共现区数量统计时，每个$\mathrm{1}°$格网范围内不重复统计时空共现区的个数，这样可以将全球范围划分为180×360=64 800个时空共现区。从本质上来讲，判断两两用户时空共现的条件应该是在时间段$T$内，两个用户签到数据之间的距离小于某一阈值，为了简化计算，本文通过判断两两用户签到数据是否在同一个划分格网来替代判断两两用户之间的距离是否小于阈值，这样时空共现区的大小$s$就代替了阈值。本文在实验过程中发现，如果在1°格网内重复统计时空共现区的数量，会造成好友概率$P(c)$对格网大小$s$不敏感。这是因为落在$c$个小尺寸时空共现区内的签到数据，有可能完全落在同一个较大尺寸的时空共现区内，例如当格网尺寸为0.01°时，$c$个时空共现区虽然在空间上邻近，但这并没有太多的实际意义，因为在0.01°尺寸的格网下用户大都在同一个城市范围内；而$c$个分布在不同城市甚至横跨整个国家的时空共现区，即使格网尺寸为$\mathrm{1}°$，却更有实际意义，更能够代表两个用户之间是好友关系。

本文对Gowalla数据集进行了实验，绘制出了好友概率与时空共现区个数的函数关系图，并根据式（8）计算出了实际值与估计值之间的误差，实验结果如图 4所示。

图  4  好友概率与时空共现区个数的函数关系

Figure 4.  Probability of Friendship Between Two Users as a Function of the Count of Co-occurrences

由图 4可以看出，当格网尺寸固定时，时间段$T$越短，时空共现区的个数越多，则好友的可能性越大；当时间段$T$、时空共现区个数固定时，则格网尺寸s越小，好友的可能性越大。例如，当时空共现区的数目$c$为3，时间段$T$为1 d时，s=1°的好友概率为$\mathrm{5}\mathrm{\%}$左右，而s=0.001°的好友概率增长至82%左右。除此之外，时间段$T$越大，实际值与估计值之间的误差也越大。因此，根据上述分析，本文采用的参数值为s=0.001°，$T=\mathrm{1}$ d。

重力模型是以万有引力公式为依据，表达随着空间距离的增加，地理区域之间的联系强度逐步减弱的规律^[23]，属于一种地理空间分析模型^[24]。由§1可知，随着距离的增加，用户之间的好友概率逐步减小；随着时空共现区个数的增加，用户之间的好友概率逐步增加。受此启发，本文采用重力模型来对好友关系进行判断。

重力模型的基本形式如下：

式中，$m_i$和$m_j$分别是关于用户$i$和用户$j$的相关指标；一般情况下，$f(d_{ij})$为关于空间距离$d_{ij}$的指数模型，即$f\left(d_{ij}\right)=d_{ij}^{-\alpha }$，其中α>0；$k$为重力模型的比例因子，是一个常数。

由于好友概率与时空共现区个数基本呈现指数函数关系^[13]，所以利用$c_{ij}^{\beta }$代替$m_i{m}_j$，其中$\beta$为两用户之间的时空共现区个数，$c_{ij}$为常数，则重力模型变为：

将式（11）两边取自然对数构建多元线性回归方程，则有：

式（12）是一个线性方程，只要通过样本值来标定参数$\alpha$和$\beta$即可。由于$\mathrm{l}\mathrm{n}{G}_{ij}$的取值范围是（$-\mathrm{\infty },+\mathrm{\infty }$），但在进行好友关系判定时，这个值最好限制在[0，1]之间，因此本文对重力模型进行了改进。

本文采用Sigmoid函数将$\mathrm{l}\mathrm{n}{G}_{ij}$的值域映射到[0，1]之间，Sigmoid函数是一个S型函数，常常用于特征映射^[25]，其函数图像如图 5所示。

图  5  Sigmoid函数图像

Figure 5.  Graph of Sigmoid Function

将式（12）代入到Sigmoid函数中，即可得到映射后的模型，该模型的值域为$[\mathrm{0,\; 1}]$，通过$p_{ij}$的值可判定两个用户之间是否是好友关系：

模型的参数标定即通过样本数据，采用一元或多元回归、线性或非线性回归等，计算出回归常数项和回归系数项的过程，本文采用逻辑回归来标定模型参数。

逻辑回归属于分类算法，可以处理二元分类以及多元分类问题^[26]，根据这一特征，可以将其用到好友关系判断问题（即“好友”或“非好友”）。设$A=\{{\alpha }_{\mathrm{1}},{\alpha }_{\mathrm{2}}\cdots {\alpha }_n\}$和B=$\{{\beta }_{\mathrm{1}},{\beta }_{\mathrm{2}}\cdots {\beta }_n\}$为样本输入，$A$为用户之间的居住地距离集，B为用户之间的时空共现区个数集。如果式（13）中$p_{ij}>\mathrm{0.5}$，则分类结果为“好友”；如果$p_{ij}<\mathrm{0.5}$，则分类结果为“非好友”；$p_{ij}$的值越靠近0.5，分类的准确率就越低，当$p_{ij}=\mathrm{0.5}$时，逻辑回归模型本身无法确定分类结果。

逻辑回归的基本步骤如下：（1）构造预测函数，即$p_{ij}$；（2）构造损失函数；（3）通过梯度下降法，确定损失函数的最小值及各个回归参数的值。可见除了构造预测函数之外，还需要构造合理的损失函数。

损失函数就是衡量样本真实值与模型预测值之间差距的函数。当样本真值为1时，若模型的预测输出为1，损失值应尽可能为0，若模型的预测输出为0，损失值应尽量大；当样本真值为0时，若模型的预测输出为0，损失值应尽可能为0，若模型的预测输出为1，损失值应尽可能大。这里直接给出模型的损失函数为：

式中，$p_k$为模型预测的输出值；${\stackrel{̑}{p}}_k$为样本真实值（即“1，好友”或“0，非好友”）。从该损失函数可以看出，当${\stackrel{̑}{p}}_k$分别取0或1时，其函数特性刚好满足要求。由损失函数可以得到$m$个训练样本的损失函数平均值为：

本文将社交网络签到数据集中的社交关系视为无向图G_s（U_s，E_s），节点U_s为用户，节点之间的边$E_s$为用户关系（即“好友”或“非好友”），各个特征参数的值为边的属性。使用Gowalla数据集进行特征参数的有效性检验，把数据集分为训练集和测试集，再通过对模型的特征参数标定实现对好友关系的判断。

分类算法只有在选取的特征参数能够较好地表征用户间的社会关系时才能够有较准确的预测结果^[5]。信息增益在一定程度上可以评估特征参数的贡献程度，但并不能很好地评价特征参数的有效性。受试者工作特征曲线（receiver operating characteristic curve，ROC）是根据一系列不同的二分类方式（分界值或决定阈），以真阳性率（灵敏度）为纵坐标，假阳性率（1-特异度）为横坐标绘制的曲线，ROC曲线可以对特征参数进行有效性评价，ROC曲线下的面积（area under the curve，AUC）越接近1.0，表明结果的准确性越高，特征参数的选择就越有效果。

本文选取Gowalla数据集中的部分用户数据进行特征参数有效性检验，随机选取600名用户共计199 317个签到数据，以当前数据集中的社交拓扑网络数据为基准值，图 6（a）为该数据集特征参数的ROC曲线图，其中，时空共现区特征参数的AUC值为0.710，用户居住地距离特征参数的AUC值为0.634，说明所选择的特征参数如果妥善设置阈值及系数时，会有一定的预测价值。为了能够确保特征参数有效性评估的普适性，本文在对比实验中选取Brightkite数据集中的部分用户数据，随机选取620名用户共计272 396个签到数据，其ROC曲线图如图 6（b）所示，其中，时空共现区特征参数的AUC值为0.760，用户居住地距离特征参数的AUC值为0.647，说明本文选取的特征参数在不同的社交网络签到数据集中具有同样的适用性。

图  6  特征参数ROC曲线

Figure 6.  ROC Curves of Characteristic Parameters

衡量本文所提模型有效性的关键在于该模型能否通过现有的用户社交签到数据挖掘出具有好友关系的用户。本文分别在Gowalla和Brightkite数据集上验证方法的有效性，两两用户分别计算用户居住地距离$d$和时空共现区个数c，将现有的社交关系数据作为真值，其中0代表“非好友”，1代表“好友”，将数据分为70%的训练集和30%的测试集。由于社交网络拓扑的特点是好友关系边相对较为稀疏，也就是说，绝大多数的用户之间是非好友关系的，以Gowalla数据集在纽约市的签到数据为例，其中好友10 194对，非好友4 796 356对，数据的不平衡度约为1∶470，而研究结果表明，相对平衡的数据分布会得到较为理想的结果。

本文随机选取Gowalla数据集中的20 000名用户，共计2 633 751条签到数据，其中社交关系数据中好友关系为840 151对，非好友关系为199 149 849对，不平衡度约为1∶240；随机选取Brightkite数据集中的20 000名用户，共计3 682 104条签到数据，其中社交关系数据中好友关系为322 664对，非好友关系为198 827 185对，不平衡度约为1∶610。为了能够考察数据不平衡度对好友关系判断结果的影响，分别将数据按照不平衡度1∶3、1∶50、1∶100和1∶150的配比输出，形成用于模型训练和测试的数据集。实验采用Python语言，通过逻辑回归实现本文所提出的模型的参数标定，模型的参数值$\alpha$、$\beta$、截距（即$\mathrm{l}\mathrm{n}k$的值），以及准确率、召回率和F值（综合评价指标）的结果如表 3所示。

从表 3可以看出，随着数据不平衡度的增加，模型好友关系判断的准确率提高，而召回率和F值降低，这说明随着数据不平衡度的增加，模型更倾向于将用户之间的关系判定为非好友关系，这也与社交网络拓扑的特点相一致。即使是在不平衡度为1∶150时，该模型依然具有较高的准确率和一定的召回率，说明本文所选择的特征参数和提出的模型对于好友关系的判断具有良好的预测效果。除此之外，从不同的数据集结果来看，Brightkite数据集比Gowalla数据集有更高的准确率和召回率，即模型在Brightkite数据集上更为有效。

交叉对比实验可以验证模型在不同数据集上的稳定性和适用性，即以一个数据集中的数据建立和训练模型，而以另一个数据集中的数据进行测试。

对于交叉验证实验，本文使用§3.2.1中的数据，以70%的Gowalla数据作为训练数据，以30%的Brightkite数据作为测试数据进行实验1；反过来，以70%的Brightkite数据作为训练数据，以30%的Gowalla数据作为测试数据进行实验2。由于社交网络拓扑的好友边相对比较稀疏，不平衡度较大，为了减小数据不平衡度对判断结果的影响，实验将好友关系与非好友关系的平衡度定为1∶3，实验结果如表 4所示，实验1采用Gowalla数据集作为训练数据集构建和训练的模型，在Brightkite数据集上进行测试，得到的准确率为0.846 1，召回率为0.788 5；而实验2采用Brightkite数据集作为训练数据集构建和训练的模型，在Gowalla数据集上进行测试，得到的准确率为0.859 1，召回率为0.853 7。由表 4可以看出，交叉实验依然可以获得较为稳定和一致的结果，即本文所提出的模型在不同数据集之间具有较好的稳定性和适用性。

本文采用文献[13]的好友关系概率模型，在§3.2.1中的Gowalla数据集上进行好友判断对比实验，实验结果如图 7所示。由于文献[13]中的好友关系概率模型只是给出两两用户之间的好友概率值，因此需要设置阈值$\delta$，当概率值不小于该阈值时，用户间关系被判定为好友关系，否则为非好友关系。从图 7中可以看出，随着阈值δ的增加，准确率从0.66提高到0.83，而召回率从0.75几乎降为0。显然，本文的模型判断结果比对比方法提出的模型要好得多。

图  7  对比实验的预测结果

Figure 7.  Prediction Result of Contrast Experiment

本文提出了基于改进重力模型的签到数据好友关系提取方法，选取Gowalla和Brightkite两组社交网络签到数据集对所选特征参数的有效性以及所构建模型对好友关系判断的准确性进行了验证，实验结果表明，本文所提出的模型和方法在仅仅依靠签到位置数据的条件下依然具有较高的准确率和召回率，且在不同的数据集上具有较为一致和稳定的结果，对好友关系的判断明显高于对比方法。

本文目前获取到的签到数据中没有签到地点类型的相关信息，但事实上，签到地点的类型对用户时空共现区的判断是有一定影响的，比如，两个用户在商场具有许多相近的签到点，但由于商场的开放性，可能二者并非好友关系，而对于一些较为封闭的地点，如居民地、院校等，相近的签到点则代表着较高概率的好友关系。采用网络爬虫技术补充签到地点类型信息或者基于数据挖掘技术判断签到地点类型，将签到地点类型融入模型中，采用更加全面的信息建立模型来对好友关系进行判断，将是下一步工作的重点。