基于CLA算法的跨社交平台用户身份匹配

王李冬 胡克用 周微微 张 赟

1(杭州师范大学 浙江 杭州 310018) 2(浙江传媒学院 浙江 杭州 310018)

0 引 言

社交网络可以让人们通过Internet进行联系和互动，类似现实社会当中的社交行为，典型的如美国的Facebook、Twitter、Instagram，以及我国的人人网和微博。社交网络提供的服务越来越丰富，从最早期的文本发布到后期的图像与视频共享、用户间关注、评论等，使得越来越多的用户会在不同的社交网络上进行注册以获得不同的服务。

然而不同的社交网络之间信息完全孤立，网民的不同社交网络上的活动行为在不同网站上有不同的表现和侧重性。例如新浪微博以媒体属性为主，人人网以社交属性为主。如果要获得一个用户的完整图像，最大的困难就在于虚拟用户账号及其相应的用户行为分散在不同的社交网络中[3]。对网民在不同社交网络当中的虚拟用户账号进行匹配(如图1所示)，是实现用户完整图像构建的前提基础。此外，跨社交网络的用户身份匹配对商业应用，好友推荐，网络安全，通信录合并等有重要的意义。

图1 身份匹配示例

目前的跨社交平台用户匹配技术可以大致分为基于用户图像的方法[4-5]，基于内容的方法[6-7]和基于网络结构的方法[8-9]。在基于用户图像的方法中，Perito等[4]计算用户名的相似度并通过二分类器进行识别。Motoyama等[5]通过计算用户的属性(教育、职业等)相似度进行匹配。属性信息虽然很容易获得，但在大型社交网络中存在较大的重复性，单纯依靠用户属性方法并无法解决大社交网络的用户匹配问题，而且多数社交网络将用户的属性信息设定为隐私数据。在基于内容的方法中，Kong等[6]将用户的时间信息、空间信息和文本信息综合起来计算相似度。Goga等[7]利用用户的地理位置、时间戳和书写风格进行识别。虽然基于内容的方法具备一定的有效性，但上述的地理和空间信息在社交网络中存在稀疏特性，方法难以适用大范围社交网络。在基于网络结构的方法中，Bartunov等[8]提出基于JLA(Joint Link-Attribute)的识别方法，该方法共同考虑了用户属性和链接信息。Narayanan[9]等提出完全基于链接属性的识别方法。现有研究表明，融合用户图像信息、内容信息和网络信息的方法往往比单个方法的效果要好[10,12]。

本文主要研究跨社交网络的局部身份匹配问题，在给定先验种子节点集的基础上，在两个社交网络中推断出所有潜在的匹配用户对集合。基于上述思想，本文提出融合链接信息和属性信息的CLA(Combined Link and Attribute)算法。该算法首先通过特定的属性信息和人工选取得到先验种子用户，然后利用好友亲密度获得候选用户进行匹配。针对候选匹配用户，通过融合链接信息和属性相似度匹配准则计算得到匹配值最高的用户作为匹配用户，然后将匹配用户作为种子用户迭代运行，直到没有新的匹配用户产生。

1 CLA算法

CLA算法的目的是为了准确匹配尽可能多的用户，算法的大致流程如图2所示。算法首先根据用户的用户名、email等信息选取先验种子用户，再从种子用户的好友集中选择候选用户进行匹配，根据属性相似度和链接相似度计算匹配准则，将匹配得到的用户作为新的种子用户，迭代运行，直到没有新的匹配用户产生。

图2 CLA算法流程

1.1 先验配对用户对选取

定义1(配对用户对) 给定两个社交网络，分别表示为GA=(UA,EA,SA)、GB=(UB,EB,SB)。UA表示网络GA的用户实体集合，EA为网络GA的用户关系(链接关系)，UB表示网络GB的用户实体集合，uAi代表用户集合UA中的第i个用户，uBj代表用户集合UB中的第j个用户。SA表示网络GA的用户属性集合，sAi代表用户uAi属性向量。若用户uAi和用户uBj在现实生活中属于同一个体，则uAi和uBj被认定为配对用户对，记为UMP。

定义2(先验种子用户) 先验种子用户是指通过特定方法找出的先验配对用户，由此找到更多的配对用户对，本文记为PUMP。

目前没有通用的方法适用于获取任意两个社交网络的先验种子用户，一般需要针对特定社交网络选取特定的属性信息进行识别。Balduzzi等[1]提出利用email对用户进行判定。由于email的唯一性，利用email进行判定是较好的方法。

此外，文献[3]指出，同个用户往往在不同的社交网络使用同一个昵称(nickname)。因此，若两个社交网络中用户的用户名完全一样，可认定为该对用户为同一对象，匹配用户对。然而，部分社交网络允许不同的用户以相同用户名进行注册，如人人网。单单通过用户名无法直接判断两用户是否属于同一人，一种简单的解决方法就是通过其他可获取的因素，如地理位置、生日、工作单位、性别等属性信息进行进一步确认。此外，部分网络会提供额外的信息，如twitter，该网络提供独特的URL地址用于用户自识别，因此针对twitter的先验配对用户获取可直接利用该URL与Facebook进行用户身份识别。本文拟综合利用Email、URl等信息的相等匹配获得先验种子用户，并结合生日、工作单位、性别等属性信息通过人工挑选对用户进行准确性的甄别。

1.2 候选配对用户对选取

文献[11]对129个同时在新浪网和人人网注册的用户进行调研，发现这些用户的好友集中有67.5%同时存在于新浪网和人人网。基于此，本文假设：若两个用户相配对，则他们的好友中存在匹配用户对的概率较大。为了选取候选配对用户，可以从种子用户的好友集出发。本文将候选用户选取分为初始候选用户选取和最终用户选取。其中，初始候选用户选取的规则定义如下：

定义3(初始候选用户对) 若uAi和uBj为两个社交网络中的种子用户，uAk∈friend(uAi)，uBl∈friend(uBj)，则(uAk,uBl)属于初始候选用户对CMP_P，定义为：

CMP_P= {(uAk,uBl)|uAk∈friend(uAi)∧uBl∈

friend(uBj)}

(1)

式中：uAk和uBl分别代表两个社交网络的种子用户；friend(uAi)代表用户uAi的好友集。

在大规模的社交网络环境下，部分种子用户的好友集数量较多。若对两个网络的种子用户的好友集用户进行两两比对，则需要耗费较长的运行时间，尤其在海量社交网络的大数据环境下无法保证运行效率。为了提高匹配效果，本文通过特定的机制预先获得在另一个网络中更有可能存在匹配节点的用户，然后将此类用户与另一个网络中的种子点用户的好友集逐一进行匹配度计算。为了对初始候选用户对进一步缩小范围以提高匹配效率，我们拟利用用户聚簇特性对某一个网络中的用户是否可能在另外一个网络中存在匹配用户进行评估。文献[3]提出，如果一个用户与已经识别的用户为好友关系且具备较高的亲密度，则该用户可以被优先选择。本文将好友亲密度定义如下：

定义4(好友亲密度(Friend Intensity，FI)) 若uAi和uAj代表社交网络GA中的两用户，uAm属于用户uAi和uAj的共同好友。FAi、FAj和FAm分别表示用户uAi、uAj和uAm的好友集合。好友亲密度函数定义如下：

FI(uAi,uAj)=

(2)

式中，deg()代表用户的度。

基于某用户的所有好友亲密度，我们通过用户的好友评分对该用户是否有可能在另外一网络中存在匹配用户进行评估。假设已经识别的用户集表示为umatch，本文将某用户uAi的好友评分FC(uAi)定义如下：

(3)

若用户uAi的FC值越大，则该用户在另一个网络中存在匹配用户的可能性也越大。基于上述定义，先将先验种子集的朋友集设定为初始候选用户，再根据好友亲密度从初始候选用户集中选择特定用户作为最终候选用户账号集uselect。该类用户具备较大概率在另外一个网络中存在匹配用户，从而大大提升匹配效率。具体算法如下：

算法1候选用户选取

输入 社交网络GA，GB，先验种子用户集PUMP。

输出 候选用户账号集合uselect。

1 根据式(1)得到初始候选用户对集合CMP_p={uA,uB}；

2 for eachuAi∈uA，uBj∈uB

3 根据式(3)计算FC(uAi)，FC(uBj)

4 end for

5 根据FC(uAi)和FC(uBj)对uA，uB的元素进行排序；

6uselect={uA[0],uA[1],uB[0],uB[1]}

1.3 用户链接匹配度计算

为了实现两个用户之间的匹配，需要计算链接匹配度CR，现有的NS算法[2]通过度数计算实现：

(4)

式中，sin和sout分别代表用户uAi和用户uBj的共享入度邻居好友和共享出度邻居好友的数目。入度好友指社交网络中好友的单向关注关系。din-Bj和dout-Bj分别代表用户uBj的入度和出度。然而，该算法需要假设不同社交网络中的同一用户具备相同的入度和出度，该假设与现实世界的社交网络不符。在本文方法中，我们拟引入朋友关系实现用户链接匹配度计算。

定义5(朋友匹配度(Friend Match Degree，FMD))FAi和FBj分别代表用户uAi和用户uBj的好友集，FAi∩FBj代表两用户的共同好友，则两用户的朋友匹配度定义如下：

(5)

式中：

(6)

若FAi=FBj，则FMD(uAi,uBj)=1。然而，该方法存在一个弊端，若FAi的数目较少，则会出现错误匹配的情况。如图3所示，FA1=FB7={u3}，则FMD(uA1,uB7)=1，使得uA1和uB7被错误配对。

图3 网络对示例

为了解决式(5)带来的错误匹配问题，我们加入共同好友因子进行调整，将式(5)调整如下：

(7)

|FAi∩FBj|代表已经识别的共同好友个数，包括初始种子点。FMD(uAi,uBj)值越高，代表两用户为匹配用户的概率就越大。

1.4 属性相似度计算

用户之间的属性相似度拟采用用户名、姓名、URL和Email信息。

用户名和姓名都可表示为字符串。部分文献采用Levenshtein距离进行度量[14]。Levenshtein距离作为计算两个字符串间的差异程度的字符串度量，曾被多次应用于用户名的差异度量并取得较好的效果[11]。两个用户名之间的用户名相似度计算如下：

(8)

式中：lev(n1,n2)表示用户名n1和用户名n2之间的Levenshtein距离；l(ni)表示ni的字符数。该方法可针对用户名信息进行相似度度量，但针对姓名信息无法实现有效衡量。

姓名信息(可选)，在多数的网络中都会出现，例如Facebook和Twitter。该信息可作为与用户名同等重要的属性字段进行身份匹配，但无法作为身份识别的唯一判定信息[13]。Levenshtein距离对顺序较敏感，完全相同的名字，若“姓”和“名”的顺序倒置，将产生完全不一样的计算结果。鉴于国外社交网络的姓名中，“姓”和“名”的顺序并无统一规则，本文利用VMN算法[6]对姓名进行度量。VMN是一种非常有效的名字匹配技术，可以对姓名等信息实现模糊匹配，得到0或1的匹配结果值。在VMN算法中，名字“Tony Xie”和“Xie Tony”的相似度为1。

URL信息(可选)，若某社交网络提供URL信息助于身份识别，则根据URL信息与相应社交网络的链接地址进行比对，若完全相同，则返回1，否则为0。

Email信息(可选)，若两个用户的Email完全相同，则该属性相似度为1，否则为0。不同社交网络上的两用户若具备相同的Email，则他们为同一个体的概率非常大。Email信息是进行身份识别的有效属性字段。

上述信息中，姓名信息、URL信息以及Email信息需要根据特定的社交网络做相应的选择。通过上述的属性相似度计算可以得到用户u1和用户u2之间的相似度向量H(s1,s2)，s1和s2为其各自的属相向量。将已知的匹配用户对的属性相似度向量作为训练向量，不同属性信息的相似度作为不同的向量维度值。基于此，用户身份是否匹配转化为一个二分类问题，即C(H(s1,s2))∈[0,1]，C代表分类器，1代表u1和u2为同个用户，否则为不同用户。本文利用SVM分类器将向量集合进行监督学习训练，根据得到的SVM分类器来对新的向量进行分类。

1.5 用户匹配准则

定义6(用户匹配度) 给定不同社交网络的两个用户uAi和uBj，两者的账号属性向量分别为sAi和sBj。他们之间的用户匹配度计算如下：

Mat(uAi,uBj)=C(H(sAi,sBj))×α+FMD(uAi,uBj)

(9)

式中：C(H(sAi,sBj))∈[0,1]代表用户uAi和uBj的属性相似度分类结果，FMD(uAi,uBj)代表用户uAi和uBj的链接匹配度结果(见式(7))，参数α用于平衡属性相似度和基于链接的用户链接匹配度，本文将其定义为已经识别出的用户个数。

具体的匹配算法如算法2。该算法将式(1)得到的初始候选用户对和算法1得到的候选用户账号集合uselect作为输入，然后针对候选用户账号集合中的每一个用户，在另一个网络中的初始候选用户对范围内搜索匹配用户。若两者之间的用户匹配度最高，则视为配对。

算法2匹配准则计算

输入：初始候选用户对集合uA,uB；

候选用户账号集合uselect。

输出：匹配用户账号umatch。

1umatch=∅

2 for eachuselect(i)∈uselect

3 ifuselect(i)∈uAthen

4 for eachuBi∈uBdo

5 根据式(9)计算Mat(uselect(i),uBi)

6 end for

7umatch=umatch∪argmaxuBi∈uB(Mat(uselect(i),uBi))

8 else

9 若uselect(i)∈uB用同样方法执行

10 end for

2 实验与讨论

本文使用文献[8]的Facebook和Twitter基准数据集。Facebook和Twitter基准数据集共包含16个来自Facebook和Twitter的网络对。帐号的属性信息包含用户名、姓名和URL信息。由于在ego-network上研究，因此在样例网络中，任意两个用户之间的距离不会超过两个人。数据集已经标注两个网络中的匹配用户对，并同时标注了种子用户，具体相关信息如表1所示。图4显示了Facebook-Twitter的一个数据集示例，该数据集共10对匹配用户，图中标示出了5对。

表1 Facebook-Twitter数据集信息

图4 Facebook-Twitter数据集示例

此外我们从人人网和新浪网上搜集了相应的数据组成数据集。新浪微博数据库是从新浪微博的搜索界面上抓取，而人人网的数据库则是从其开放的API获取。人人网和新浪网的数据如表2所示。其中，新浪爬取的用户信息包括用户ID、用户名、微博数、粉丝数、关注数，以及关注关系等。人人网用户信息包括用户名，户主的所有好友、户主及好友关注的公共主页等。

表2 新浪-人人数据集信息

在评价方案中，本文利用传统的准确率、召回率以及F1-measure综合进行衡量。具体如下：

recall=tp/(tp+fn)

(10)

precision=tp/(tp+fp)

(11)

(12)

式中：tp代表被正确匹配的用户对；fp代表被错误匹配的用户对，fn代表未被匹配的用户对。

采用不同的基准算法与本文方法进行比较，分别为JLA方法[8]、NS方法[2]。算法实验在Windows7环境下采用Matlab编写。由于Facebook-Twitter数据集已经具备种子用户，则本文算法CLA在执行过程中省略了先验种子用户选取的步骤。

其中，JLA方法使用监督分类器的剪枝手段。所有方法的结果都是取16对网络对的均值。由表3可得，无论从Facebook到Twitter的匹配，还是Twitter到Facebook的匹配，JLA算法可以保持最高的准确率，但是该方法的召回率并不十分理想。其中，NS方法效果最差，可见，仅仅以网络拓扑为计算依据的方法远比综合属性因素和链接关系的方法要差。CLA方法的效率和JLA相比稍显优越，而且JLA中基于条件随机场的最优用户映射实现方法比CLA方法中基于判定准则的匹配方法比更加复杂，JLA方法需额外利用基于监督分类器的剪枝操作才可获得相对满意的效果。若应用于海量用户的跨社交平台，JLA的繁琐步骤无法保证效率。

表3 Facebook-Twitter数据集的身份匹配效果

针对新浪-人人数据集，我们抽取四个子网络进行实验。由于获得的用户数据并不包含具体属性信息，本文的CLA方法在进行匹配度计算时仅计算用户链接匹配度。抽取子网络时，针对两个网络中的相同用户对进行二层好友的深度遍历。然后，针对每个子网络人工标注20个种子用户并分别执行CLA算法和NS算法。由于子网络中的匹配用户对的总数目未知，我们仅计算准确率进行效果分析。由表4数据可得，Sina微博抽取的子网络规模约1 000节点，人人网抽取的子网络规模约3 000节点。CLA方法和NS方法都可以获得一定数量的匹配用户对，但是CLA方法在所有的实验中都保持较高的准确率。该结果表明，在仅考虑网络链接结构的情况下，本文提出的方法性能依然比NS方法更加优越。

表4 新浪-人人数据集的身份匹配效果

3 结 语

本文提出一种基于CLA方法的跨社交网络的身份识别，并将其应用于真实社交网络的数据集上。通过在不同数据集上的实验，结果表明该方法可获得较高的准确率，效果优于传统的JLA和NS方法，而且单单基于网络链接结构的用户身份识别效果依然优于NS方法。然而，CLA方法依然存在一定的不足。该方法可应用于海量社交网络群的用户匹配，但主要还是面向两两社交网络。若针对三个或三个以上的社交网络，可能存在两两社交网络之间的用户匹配结果不一致的情况。因此，在今后的工作中，本文拟针对上述问题进行改进，以适应多社交网络的用户身份匹配，同时在算法效率上拟作进一步提升。