(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 CN 105427173 A (43)申请公布日 2016.03.23
(21)申请号 201510793720.2(22)申请日 2015.11.18
(71)申请人广东工业大学
地址510006 广东省广州市越秀区东风东路
729号(72)发明人成英超 郝志峰 蔡瑞初 温雯
王丽娟(74)专利代理机构广州市红荔专利代理有限公
司 44214
代理人张文(51)Int.Cl.
G06F 17/30(2006.01)
G06Q 50/00(2012.01)
(54)发明名称
一种基于位置服务的社交关系推断方法以及服务器(57)摘要
一种基于位置服务的社交关系推断方法以及服务器。其中，该方法包括以下步骤：记录用户登录社交应用时的用户名、登录地点和登录时间；判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；若处于，设定该两个用户的相会向量
；建立用户i与用户j的相会地点多样性函数
；建立加权相会频率函数
；对相会
权利要求书2页 说明书6页 附图2页
地点多样性函数和加权相会频率函数
做线性回归，得到用户i与用户j的社交关系
。本申请综合考虑了
相会地点的多样性和加权相会频率，相会地点的多样性减少了偶遇对社交关系的影响，而加权相会频率增加了特定位置对社交关系的影响，因此，本申请所推断的社交关系更加准确。
C N 1 0 5 4 2 7 1 7 3 A CN 105427173 A
权 利 要 求 书
1/2页
1.一种基于位置服务的社交关系推断方法，其特征在于：包括以下步骤：
记录用户登录社交应用时的用户名、登录地点和登录时间；
判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；若处于，设定该两个用户的相会向量用户j的相会向量，
=（
;；;
;其中，q为多样性的阶，其满足;…;
），其中
为用户i与
表示在地点l的相会次数；
建立用户i与用户j的相会地点多样性函数当q=1时，
当01时，q>=0,为用户i和用户j相会次数的总和；
；，
点l相对于所有用户登录的概率，数，为所有用户在地点l的登录次数；
对相会地点多样性函数社交关系
社交关系
和加权相会频率函数。
；其中，
建立加权相会频率函数
,其中，为用户u在地
，其中，
表示用户u在地点l的登录次
做线性回归，得到用户i与用户j的
2.根据权利要求1所述的方法，其特征在于：
和为回归参数，其从训练样本中得到
或者由用户提供。
3.根据权利要求1或2所述的方法，其特征在于：q=0.1。4.一种服务器，其特征在于：所述服务器执行以下步骤：记录用户登录社交应用时的用户名、登录地点和登录时间；
判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；
若处于，设定该两个用户的相会向量用户j的相会向量，
=（
;；;
;其中，q为相会地点多样性的;…;
），其中
为用户i与
表示在地点l的相会次数；
建立用户i与用户j的相会地点多样性函数当q=1时，
当01时，阶，其满足q>=0,为用户i和用户j相会次数的总和；
；
，
,其中，为用户u在
，其中，
2
建立加权相会频率函数
地点l相对于所有用户登录的概率，数，为所有用户在地点l的全部登录次数；
表示用户u在地点l的登录次
CN 105427173 A
权 利 要 求 书
和加权相会频率函数。
和加权相会频率函数
；其中，
2/2页
对相会地点多样性函数社交关系
做线性回归，得到用户i与用户j的
5.根据权利要求4所述的服务器，其特征在于：服务器用于对相会地点多样性函数与用户j的社交关系
做线性回归，得到用户i和为回归参数，其从训练样本
中得到或者由用户提供。
6.根据权利要求4或5所述的服务器，其特征在于：q=0.1。
3
CN 105427173 A
说 明 书
一种基于位置服务的社交关系推断方法以及服务器
1/6页
[0001]
技术领域
本申请涉及社交网络应用领域，尤其是一种基于位置服务的社交关系推断方法以及服务器。
[0002] [0003]
背景技术
随着互联网技术的发展，我们可以很方便地在网络上收集人们上传到网络中的个
人位置信息的精准时空数据。例如，可以从一个人的信用卡交易记录或移动设备使用情况（手机基站响应，GPS或WiFi热点）悄悄地收集位置信息。这些信息也可以更公开地获取，例如，用户发布标记有用户地理信息的内容到因特网（例如微信，或者上传实时实地的照片到qq空间、人人网或开心网），使用基于地理位置的交互式网络服务（如登录Foursquare），等等。由此而产生一个问题：能否通过这些收集到的位置信息来推断用户间的社交关系。[0005] 现在，市面上有很多基于社交关系的网络应用，如市场营销类的应用（例如，定向推送，以朋友推荐为代表的推荐引擎），社会研究（例如，人物影响力研究）和文化研究（例如，新思想、新风尚和谣言的传播模式）。同时也有其他的独特用途，例如，定位一个犯罪团伙或的新成员，或通过人的接触行为研究传染病的传播模式和途径。[0006] 然而，通过人的位置信息的时空数据推断社交关系仍然具有许多挑战。首先，两个人相会事件的总次数称之为相会频率，相会频率越高在一定程度上说明两个人越有可能具有社交关系。但是，并不能完全从相会频率来推断两人的社交关系。举个例子，假设两个人都有每天在一个固定时间去图书馆学习的习惯，这会导他们的相会频率非常高，但是他们实际上并不认识对方。因此，两个人的这种偶遇并不能表示两人具有社交关系。我们将两个人之间相会事件所发生地点的数目的度量定义为多样性。其次，两个人相会的地点的特征属性也会对推断两人社交关系产生影响，在多样性较小的情况下，相会的地点的特征属性的作用会更加凸显。例如，在小型的、私人的地方的约会比在商场、博物馆等大型公共场所的相会更能说明两人之间具有社交关系。[0007] 因此，现有技术对社交关系的推断并不准确。
[0004] [0008]
发明内容
本申请提供一种基于位置服务的社交关系推断方法以及服务器，解决现有技术中，对社交关系的推断不准确的问题。
[0009] [0010]
根据本申请的第一方面，本申请提供一种基于位置服务的社交关系推断方法，包括以下步骤：记录用户登录社交应用时的用户名、登录地点和登录时间；判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；若处于，设定该两个用户
4
CN 105427173 A
说 明 书
=（
;
;…;
），其中
为用户i与用户j的相会向量，
；
2/6页
的相会向量表示
在地点l的相会次数；建立用户i与用户j相会的相会地点多样性函数
当q=1时，
当01时，阶，其满足q>=0,为用户i和用户j相会次数的总和；
；
，
地点l相对于所有用户登录的概率，
，其中，
数，为所有用户在地点l的登录次数；对相会地点多样性函数做线性回归，得到用户i与用户j的社交关系
[0011]
;
;其中，q为相会地点多样性的
建立加权相会频率函数
,其中，为用户u在
表示用户u在地点l的登录次
和加权相会频率函数。
根据本申请的第二方面，本申请提供一种服务器，服务器执行以下步骤：记录用户登录社交应用时的用户名、登录地点和登录时间；判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；若处于，设定该两个用户的相会向量;
;…;
），其中
为用户i与用户j的相会向量，
；
建立用户i与用户j相会的相会地点多样性函数当q=1时，
当01时，阶，其满足q>=0,;
;其中，q为相会地点多样性的
；=（
表示在地点l的相会次数；
为用户i和用户j相会次数的总和；建立加权相会频率函数
，
,其中，为用户u在
，其中，
表示用户u在地点l的登录次
和加权相会频率函数。
地点l相对于所有用户登录的概率，
数，为所有用户在地点l的登录次数；对相会地点多样性函数做线性回归，得到用户i与用户j的社交关系
[0012]
本申请的有益效果是，由于本申请在推断用户之间社交关系时，综合考虑了相会地点的多样性和加权相会频率，相会地点的多样性减少了偶遇对社交关系的影响，而加权相会频率增加了特定位置对社交关系的影响，因此，本申请所推断的社交关系更加准确。
[0013]
附图说明
图1为实施例1的四分图；
图2为实施例2中三种召回级别下相会地点多样性的阶(即q的取值)影响准确度的曲线图；
图3为实施例2中另外三种召回级别下相会地点多样性的阶(即q的取值)影响准确
[0014]
5
CN 105427173 A
说 明 书
3/6页
度的曲线图。
[0015]
具体实施方式
[0016] 下面通过具体实施方式结合附图对本发明作进一步详细说明。[0017] 实施例1：
一种基于位置服务的社交关系推断方法，包括以下步骤：S101:记录用户登录社交应用时的用户名、登录地点和登录时间。[0018] 每当用户登录社交应用，如qq空间、人人网或开心网等社交应用，视为一个登录事件，登录事件可以表示为一个三元组，其中，u为用户名，l为登录地点，其中包括经纬度的值和代表一个特定的地方的唯一ID，如商场，剧院，客厅等，t为登录时间。[0019] S102：判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之内；为了有效地存储稀疏数据，我们使用图1的四分图，其中每个象限称为小区，具有唯一ID，编号从1到10。图中示例了三个用户，分别被示为圆形，棱形和正方形并用ID1、2、3作为唯一标识。箭头表示用户出现在该小区的时间ti。图中颜色越深表示人口密度越大。小区中的每个用户共享小区ID，并由箭头ti确定相会事件。可以判断任意两个用户是否在预订的时间间隔内位于同一地点，若位于，可认为这两个用户相会。图1中，在小区1中，用户1和2在小区1于时刻t2相会。
[0020]
S103：若处于，设定该两个用户的相会向量=（;;…;），其中
为用户i与用户j的相会向量，
[0021]
表示在地点l的相会次数。
=（
;
如果两个用户在某一地点相会，设定该两个用户的相会向量）。图1中，用户1和用户2的访问向量如下：
;…;
V1=（，，，，，0，0，0，0，0）；V2=（，，，，，，0，0，0，0）。[0022]
可以看出，这两个用户有一次相会事件发生在t2时间并位于位置1处，一次相会
=（1，1，1，
在时间t3并位于位置2处，等等，因此用户1和用户2之间的相会向量是：1，1，0，0，0，0，0）。
[0023]
S104：建立用户i与用户j的相会地点多样性函数
;
；
当q=1时，
当01时，阶，其满足q>=0,[0024]
;其中，q为相会地点多样性的
为用户i和用户j相会次数的总和。
相会地点的多样性是两个人之间相会事件所发生地点的数目的度量，这些地点必须是不同的、有着各自的内在特征属性，如公共场所和私人场所。当相会地点多样性的阶q为1时，使用香农熵建立相会地点多样性函数。[0025] 首先，用户i和用户j在地点l相会的概率是：
6
CN 105427173 A
说 明 书
4/6页
如果从集中随机选取一个相会事件，并将其地点当作一个随机变量，那么这个随机
变量的不确定性可以由用户i和用户j的香农熵给出：
但是熵和多样性是不同的概念，熵是用作多样性的一个指标。基于现有技术，将熵和多样性的关系比作球体的半径和体积的关系，即得到：
D代表多样性，表征了总体样本的多样性，因此用户i和用户j间的这种多样性可由上述方程确定：
由于之前定义了相会向量，所以可以以相会向量的形式重写多样性的表达式：
；
其中，为用户i和用户j相会次数的总和。
但是，上述基于香农熵的相会地点多样性函数不能区分一次相会事件到底是不是偶遇，并且不能控制偶遇对社交关系的影响。当01时，使用Renyi熵构建函数：[0026]
；
Renyi熵可以控制影响社交关系的关键参数q，它对相会地点频率是非常敏感的，当q>1,就赋予高值相会频率高权值，0[0027]S105：建立加权相会频率函数
，
；
,其中，为用户u在
，其中，
表示用户u在地点l的登录次
地点l相对于所有用户登录的概率，数，为所有用户在地点l的登录次数。
[0028]
步骤S104建立的相会地点多样性函数可以减少偶遇对社交关系的影响，但是，没有考虑相会地点的特征属性对社交关系的影响，因此，建立加权相会频率函数，增加在相会地点的特征属性对社交关系的影响。[0029] 首先需要说明的是，用户在登录应用时，基于位置服务程序可以获知登录地点，地点的特征属性是预置的，一旦确定了登录地点，就赋予了该地点对应的特征属性，也就获知了相会地点的特征属性。例如，确定酒吧、咖啡店为私人属性，确定图书馆、博物馆为公共属性。
7
CN 105427173 A[0030]
说 明 书
，
；，其中，
5/6页
其中，为用户u在地点l相对于所有用户登录的概率，用户u在地点l的登录次数，为所有用户在地点l的登录次数。
[0031]
表示
S106：对相会地点多样性函数
；
和加权相会频率函数做线性回归，得到用户i
与用户j的社交关系：
其中φ和ψ是两个线性方程，通过上式即可从两个用户的位置信息的时空数据中推断两人的社交关系。[0032] 进一步的，为了方便进行多元回归，我们通过优化参数α、β和γ重新确定社交关系：
；
其中，
和为回归参数，其从训练样本中得到或者由用户提供，本实施例从训练样
本中确定得到：
实施例2：
本实施例中，确定q值的最优值。将q值以0.1为单位从0开始分为N份，然后对于q的每一个值，我们基于相会地点多样性函数计算确定。为此，定义多样性的阈值是
，如果
>=
。两个用户是不是具有社交关系，由则用户i和用户j被认为是朋友，否则
。以用户对的
他们不是。因此，我们从0开始，以MAX（多样性
>=
）/1000为步长，改变阀值的值
与真实的社交数据进行比较并计算精度P和召回R.
图2和图3表示了q如何影响精度的结果。x轴示出了相会地点多样性的阶q，y轴示出了精度。为了图形可视化，在图中各示出了三条曲线，每条曲线对应于一个召回级别。此外，我们只显示q的结果，其范围从0到2，以更准确的观察实验结果。通过上述实验，可以得出：主要观察的是在6个不同的召回的级别的所有曲线表现出同样的行为，上述6个级别都在q=0.1达到峰值，即q=0.1是用于控制偶遇对社会影响力的影响的最佳值。[0034] 实施例3：
一种服务器，该服务器执行以下步骤：记录用户登录社交应用时的用户名、登录地点和登录时间；判断任意两个登录地点相同的用户的登录时间之差是否处于预定时间间隔之
[0033]
内；若处于，设定该两个用户的相会向量=（
8
;;…;），其中为用户i与
CN 105427173 A
说 明 书
6/6页
用户j的相会向量，函数
；当q=1时，
表示在地点l的相会次数；建立用户i与用户j的相会地点多样性
;
;其中，q为多样性的阶，其满足
当01时，q>=0,为用户i和用户j相会次数的总和；
，
地点l相对于所有用户登录的概率，
，其中，
建立加权相会频率函数Fij；
,其中，为用户u在
表示用户u在地点l的登录次
和加权相会频率函数。
和加权相会频率函数
；其中，
做线性
数，为所有用户在地点l的登录次数；对相会地点多样性函数做线性回归，得到用户i与用户j的社交关系
[0035]
进一步的，服务器用于对相会地点多样性函数
回归，得到用户i与用户j的社交关系和为回归参
数，其从训练样本中得到或者由用户提供。[0036] 实施例4：
作为实施例3的优选，选定q=0.1为最佳值。
[0037] 以上内容是结合具体的实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换。
9
CN 105427173 A
说 明 书 附 图
1/2页
图1
图2
10
CN 105427173 A
说 明 书 附 图
2/2页
图3
11
