一种基于全局和局部特征的跨在线社交网络用户匹配方法

摘要

本发明公开了一种基于全局和局部特征的跨在线社交网络用户匹配方法，属于社交网络领域的节点匹配技术。所述方法包括初始种子发掘和种子扩张两个阶段。本发明针对使用多个社交网络的同一用户，利用全局和局部的结构化信息，设计高效的匹配算法，来识别属于同一用户的所有账号，从而整合用户多个来源的信息，为社会科学的研究和提供个性化服务奠定基础。本发明将社交网络建模成有权图，将用户之间的亲密程度作为边的权重，更符合实际；较现有技术，本发明具有更高的精度和召回率，更有效地实现了跨网络的用户匹配。

说明书

技术领域

本发明属于社交网络领域的节点匹配技术，具体是指一种基于全局和局部特征的跨在线社交网络用户匹配方法，应用于解决多个在线社交网络间的用户匹配问题。

背景技术

在过去几年里，社交网络变得非常流行并被广泛使用。现在人们通常有多个社交网络账号，比如Facebook，Twitter和Flickr。社交网络用户匹配问题旨在识别一个人在各个社交网络的账号(参见参考文献[1]N.KorulaandS.Lattanzi,“Anefficientreconciliationalgorithmforsocialnetworks,”ProceedingsoftheVLDBEndowment,vol.7,no.5,pp.377–388,2014.)。因此，社交网络用户匹配技术能有效地将用户多个来源的信息整合到一起，丰富用户信息，以便提供进一步的个性化服务。

社交网络用户匹配问题在学术界和工业界引起了广泛的关注。参考文献[2]～[6]提供的技术方案中利用在线社交网络或者在线社区中用户的语义信息(用户名、地理位置、个人资料等)，使用机器学习算法来计算用户之间的相似度，从而跨网络识别共同用户。参考文献[7-9]都考虑社交网络的拓扑结构，将网络建模成无权图，通过挖掘节点的结构特征(节点度、共同邻居数等)来跨网络识别共同用户。参考文献[2]：J.Novak,P.Raghavan,andA.Tomkins,“Anti-aliasingontheweb,”inProceedingsofthe13thinternationalconferenceonWorldWideWeb.ACM,2004,pp.30–39.参考文献[3]：R.ZafaraniandH.Liu,“Connectingcorrespondingidentitiesacrosscommunities.”inICWSM,2009.参考文献[4]：F.Abel,N.Henze,E.Herder,andD.Krause,“Interweavingpublicuserprofilesontheweb,”inUserModeling,Adaptation,andPersonalization.Springer,2010,pp.16–27.参考文献[5]：A.Malhotra,L.Totti,W.MeiraJr,P.Kumaraguru,andV.Almeida,“Studyinguserfootprintsindifferentonlinesocialnetworks,”inProceedingsofthe2012InternationalConferenceonAdvancesinSocialNetworksAnalysisandMining(ASONAM2012).IEEEComputerSociety,2012,pp.1065–1070.参考文献[6]：S.Labitzke,I.Taranu,andH.Hartenstein,“Whatyourfriendstellothersaboutyou:Lowcostlinkabilityofsocialnetworkprofiles,”inProc.5thInternationalACMWorkshoponSocialNetworkMiningandAnalysis,SanDiego,CA,USA,2011.参考文献[7]：A.NarayananandV.Shmatikov,“De-anonymizingsocialnetworks,”inSecurityandPrivacy,200930thIEEESymposiumon.IEEE,2009,pp.173–187.参考文献[8]：P.PedarsaniandM.Grossglauser,“Ontheprivacyofanonymizednetworks,”inProceedingsofthe17thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2011,pp.1235–1243.参考文献[9]：E.Kazemi,H.SHamed,andM.Grossglauser,“Growingagraphmatchingfromahandfulofseeds,”inProceedingsoftheVldbEndowmentInternationalConferenceonVeryLargeDataBases,vol.8,no.EPFL-ARTICLE-207759,2015.

总结来看，现有技术方案存在以下三方面的不足：

(1)只使用语义信息(用户名、位置、兴趣等)，只能识别一小部分用户，且容易遭受虚假用户的攻击，但是可以先通过语义信息匹配一小部分用户作为种子用户，作为算法的初始条件。

(2)忽略了用户间的亲密程度，而把社交网络建模成无权图。但是现实中不同用户间的亲密程度是有差异的。

(3)只使用了局部特征(节点度，共同邻居数)，而忽视了全局特征。然而全局特征可以极大地促进匹配的进程，降低初始条件。

发明内容

为解决上述问题，本发明研究了基于结构信息的社交网络用户匹配问题，针对使用多个社交网络的同一用户，利用全局和局部的结构化信息，设计高效的匹配算法，来识别属于同一用户的所有账号，从而整合用户多个来源的信息，为社会科学的研究和提供个性化服务奠定基础。本发明提供一种基于全局和局部特征的跨在线社交网络用户匹配方法，所述方法包括初始种子发掘和种子扩张两个阶段。

所述的种子发掘阶段，首先假定有个用户已匹配，作为种子用户，简称种子，形成初始种子集合I。

N为现实社交网络G中的节点数量。计算两个在线社交网络中所有节点的GlobalRank值，并按GlobalRank值降序排列，分别存放到链表L₁和L₂中。对于链表L₁中每个未匹配的节点u，将其匹配到链表L₂中的节点v。反向匹配链表L₂中的节点v到链表L₁中节点u，如果节点u和节点v双向都匹配，就将节点u和节点v视为一次成功的匹配，将节点对(u,v)加入种子集合I中，最终得到种子节点集合S。

所述的种子扩张阶段，将第一阶段中发掘的种子节点集合S中所有种子作为根节点，对于每个已发掘的种子节点s∈G₁，从邻居节点中按GlobalRank值从大到小挑选节点。如果节点u是种子节点s的一个邻居并且节点u的已匹配的邻居节点集合N(u)中已匹配节点数目超过了一个预定义的阈值，挑选节点u并利用节点u已匹配的邻居节点来找到节点u的候选节点集合。接下来，根据两个节点的相似度从候选节点集合中挑选出跟节点u具有最高相似度的候选节点v。将节点对(u,v)加入节点集合M中，形成最终的扩张节点集合M。

本发明的优点在于：

(1)社交网络建模成有权图，将用户之间的亲密程度作为边的权重，更符合实际；

(2)提出一个统一的框架整合网络中节点的全局和局部特征，并基于此框架设计了一个两阶段算法，有效地实现跨在线社交网络用户匹配；

(3)较现有技术，实验验证本发明具有更高的精度和召回率，更有效地实现了跨网络的用户匹配。

附图说明

图1A是在不同边保留概率的情况下，NR-GL算法与KL算法的精度对比；

图1B是在不同边保留概率的情况下，NR-GL算法与KL算法的召回率对比；

图1C是在不同边保留概率的情况下，NR-GL算法与KL算法的F1分数对比；

图2是是对于动态α值与各个固定α值，NR-GL算法所取的精度；

图3是在不同边保留概率的情况下，NR-GL算法与KL算法运行时间对比；

图4为社交网络用户匹配实例。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

本发明提供一种基于全局和局部特征的跨在线社交网络用户匹配方法，所述的社交网络，本发明中给出如下定义解释。

本发明将现实社交网络标记为带权无向图G＝(V,E)，其中V表示社交网络中所有节点的集合，E表示社交网络中所有边的集合(简称边集)。每个节点代表着一个用户，每条边代表着两个用户间存在的好友关系。对于每个用户，它跟不同朋友或用户之间存在不同的关系强度。任意两个用户u和u'的边e_uu'的关系强度(参见参考文献[11]:L.Page,S.Brin,R.Motwani,andT.Winograd,“Thepagerankcitationranking:Bringingordertotheweb,”Technicalreport,StanfordDigitalLibraryTechnologiesProject,1998)由计算得来,其中Ngh(u)和Ngh(u')分别代表着节点u和u'的邻居节点集。

每个在线社交网络可以看做是现实社交网络的一个子集。这里用G₁和G₂来表示G的两个子集，即两个在线社交网络。接下来将介绍如何构建G₁＝(V₁,E₁)和G₂＝(V₂,E₂)的节点和边。

构建节点和边：本发明中假设上述的所有在线社交网络与现实社交网络拥有相同的节点集，即|V₁|＝|V₂|＝|V|。但本算法同样适用于|V₁|≠|V₂|，并且在构建边的时候也会给节点集带来一定的噪声，致使|V₁|≠|V₂|。另一个关键问题是如何从G的边集E中来构建G₁和G₂的边集。基于之前的工作(参见参考文献[1][8])，提出了独立删边模型，其包含了两个基本规则：一是边被挑选的概率与边上的权重正相关。如果边e_uu'上权重较大，说明用户u和u'有着较强的好友关系，这样他们更有可能在在线社交网络中继续保持好友关系(参见参考文献10)；二是关于G₁和G₂边集的大小。假设边集E₁和边集E₂是分别以pe₁和pe₂的平均概率从边集E中挑选得来，其中pe₁和pe₂可以不必相等。这也就意味着得到G₁＝(V₁,E₁)要从G＝(V,E)中删除(1-pe₁)*|E|条边；G₂＝(V₂,E₂)同理。

基于上述的在线社交网络，本发明提供一种基于全局和局部特征的跨在线社交网络用户匹配方法，简称NR-GL。NR-GL方法是一种二阶段的社交网络用户匹配方法，包括初始种子发掘和并行种子扩展两个阶段。

第一步，初始种子发掘阶段：给定少量种子用户，发掘更多全局特征明显的用户。具体方法，介绍如下。

(1)首先假定有个用户已匹配，作为种子用户，简称种子，所有种子形成初始种子集合I。

N为现实社交网络G中的节点数量。

对于给定的两个在线社交网络G₁＝(V₁,E₁)和G₂＝(V₂,E₂)，用户匹配就是要找到一对一的节点匹配M：V₁→V₂，并使得正确的用户匹配数目最大化。作为初始条件，本发明假设个用户已匹配，称之为种子用户。这是由于有些用户会将自己的社交网络账号连接起来，例如用同一个邮箱注册，或者是在自己Facebook的个人资料中放上自己Twitter的链接。此外，也可以使用语义信息匹配来挖掘种子用户。利用种子用户和给定两个在线社交网络的结构特征，本发明的匹配算法能高效正确地匹配大部分用户。

(2)计算两个在线社交网络中所有节点的GlobalRank值，并按GlobalRank值降序排列，分别存放到链表L₁和L₂中。

全局特征表现了节点在整个网络中的作用，它包括接近中心性、中介中心性等。本发明采用了最有效的衡量指标，即特征向量中心性。类似于PageRank(参见参考文献[12]：B.Viswanath,A.Mislove,M.Cha,andK.P.Gummadi,“Ontheevolutionofuserinteractioninfacebook,”inProceedingsofthe2ndACMworkshoponOnlinesocialnetworks.ACM,2009,pp.37–42.)，给每个节点定义了全局重要性GlobalRank。

假设有一个随机的步行者游走在带权无向图G中。他可能以给定概率F_uv从一个节点u走到另一个相连的节点v，也可能以另一给定概率J_uw随机地跳到另一个节点w。节点u的全局重要性GlobalRank定义为达到最终稳定状态后随机的步行者停留在节点u上面的概率，记作R(u)。传统的PageRank算法计算GlobalRank值时并不考虑边上的权重，然而这些边上的权重有利于计算节点在整个网络中的作用。因此本发明提出在计算全局特征时个性化PageRank。具体来说，就是把节点u到邻居节点v的转移概率F_uv定义为从节点u到随机节点w的跳转概率J_uw定义为其中，L(v)、L(w)、L(k)分别表示节点v、节点w和节点k的连接强度；Ngh(u)表示节点u的邻居节点集。

在定义完转移概率后，用迭代的方式来计算节点的全局重要性GlobalRank，具体为：

其中，ε是容忍误差，T是包含所有节点转移概率F_uv和跳转概率J_uw的转移矩阵，R是包含了所有节点全局重要性GlobalRank的行向量，δ是两轮迭代所有节点全局重要性GlobalRank的差值和。

局部特征展现了节点自身的特性，全局特征则展现了节点在整个网络中的作用。基于此，本发明设计了一个统一模型UniRank来计算节点u和节点v之间的相似度Sim(u,v)，表达公式为：

Sim(u,v)＝αSim_l(u,v)+(1-α)Sim_g(u,v)

其中，Sim_l(u,v)和Sim_g(u,v)分别为局部特征相似度和全局特征相似度；α为局部特征和全局特征之间的比重，对于不同的节点，α值在匹配过程中会跟着节点的全局特征排名而动态的调整。通过观测数据，将α值设为其中r_G代表着该节点在所有N个节点中的排名，c是介于(1,e-1)的常数。一般α设定成较小的值，如0.5～0.6。

所述的局部特征包括共同已匹配邻居数和连接强度。

如果节点对(u',v')满足：u'∈Ngh(u)，v'∈Ngh(v)，并且节点u'已经匹配节点v'，则把节点对(u',v')称为(u,v)共同已匹配邻居。其中，(u'∈G₁,v'∈G₂)，(u∈G₁,v∈G₂)。

节点u∈V₁与节点v∈V₂共同已匹配邻居数目越多，节点u和节点v越相似，两者越有可能匹配上。

节点u的连接强度L(u)定义为：

L(u)＝Σ_u'∈N(u)W(e_uu')。

其中，W(e_uu')为节点u和节点u'的边e_uu'的权重。

节点u∈V₁与节点v∈V₂连接强度越接近，节点u和节点v越相似，两者越有可能匹配上。

基于以上两个定义，用下面的公式来计算两个节点之间的局部特征相似度：

$>{\mathrm{Sim}}_l(u,v)=\frac{|N\left(u\right)\cap N\left(v\right)|}{|N\left(u\right)\cup N\left(v\right)|}·\frac{min\left(L\right(u),L\left(v\right))}{max\left(L\right(u),L\left(v\right))}$>

其中，N(u)和N(v)分别表示节点u和节点v已匹配的邻居节点集合，L(u)和L(v)分别表示节点u和节点v的连接强度。

如果节点u∈V₁和节点v∈V₂有着大小相似的GlobalRank值(即GlobalRank值最接近的两个节点)，说明两个节点在社交网络G₁和G₂有着相似的重要性，很有可能对应着同一用户。因此用下面的公式来计算两个节点的全局特征相似度：

$>{\mathrm{Sim}}_g(u,v)=\frac{\min \left(R\right(u),R\left(v\right))}{max\left(R\right(u),R\left(v\right))}$>

其中R(u)和R(v)代表了节点u和节点v的GlobalRank值。

对于两个在线社交网络，将节点的GlobalRank值降序排列，并分别存放在链表L₁和链表L₂中。

(3)节点匹配。

对于链表L₁中每个未匹配的节点u，将其匹配到链表L₂中的节点v。

如果节点u和节点v有相似的排名，并且节点v和节点u有着最高的相似度Sim(u,v)，则将节点u匹配到节点v。

所述的相似的排名是指两个节点在各自链表中的排名相差在两倍以内。

由于初始种子发掘阶段的精度至关重要，一个错误的匹配可能会引发之后一连串的错误匹配。因此反向匹配链表L₂中的节点v到链表L₁中节点u，如果节点u和节点v双向都匹配，就将节点u和节点v视为一次成功的匹配。

这一阶段新匹配的节点与起初假定已匹配的节点一起构成了发掘的种子集合，而新的种子集合将作为下一阶段的输入。

该初始种子发掘算法伪代码如下：。

ΔS是指种子节点集合S大小的变化量，比如种子节点集合从2个元素变成3个元素，那么ΔS等于1。设置这个变量是为了步骤3，算法将迭代地运行算法，直到无法匹配更多的节点。

第二步，种子扩张阶段；

依靠全局匹配，第一阶段快速对部分用户进行了匹配。接下来，需要匹配剩余的节点。目标是保证匹配的精度和时间效率，并尽可能提高召回率。为了实现这些目标，本发明设计了一个基于广度优先的并行匹配算法。

基于广度优先的并行匹配算法，将第一阶段中发掘的所有种子作为根节点，并从根节点出发设计了一个种子扩张算法。对于每个已发掘的种子节点s∈G₁，使用广度优先策略从邻居节点中按GlobalRank值从大到小挑选节点。如果节点u是种子节点s的一个邻居并且节点u的已匹配的邻居节点集合N(u)中已匹配节点数目超过了一个预定义的阈值，挑选节点u并利用节点u已匹配的邻居节点来找到节点u的候选节点集合。接下来，根据两个节点的相似度从候选节点集合中挑选出跟节点u具有最高相似度的候选节点v。这些候选节点集合中的候选节点带来了两方面的好处：一是这些候选节点集合中的候选节点更有可能被正确匹配；二是所述的候选节点带来了更多新的邻居，加速了种子扩张的匹配进程。

该种子扩张算法伪代码如下：

根据上述的初始种子发掘算法和种子扩张算法，可以得出初始种子发掘算法的时间复杂度是O(|S|²)，种子扩张算法的时间复杂度是O(|S|·|D|²)，其中|S|代表了第一阶段发掘的节点的数量，|D|代表了G₁和G₂中节点的最大的度。因此，本发明是一个多项式时间复杂度算法，总的时间复杂度是O(|S|²+S|·|D|²)。

下面采用两个数据集来评估和对比本发明方法的优点和有益效果，所述的数据集分别是Facebook的公开数据集(参考文献[13]:D.Chakrabarti,Y.Zhan,andC.Faloutsos,“R-mat:Arecursivemodelforgraphmining.”inSDM,vol.4.SIAM,2004,pp.442–446.)和RMAT随机模型(参考文献[14]：D.Chakrabarti,Y.Zhan,andC.Faloutsos,“R-mat:Arecursivemodelforgraphmining.”inSDM,vol.4.SIAM,2004,pp.442–446.)产生的网络。这两个社交网络的数据都视为现实社交网络G。其中社交网络Facebook的公开数据集包含63731个用户和817090条边，平均度为25.64。RMAT随机模型产生的合成数据包含131072个用户和9712628条边。以现实社交网络G为基础，计算出边上的权重，进而分别以pe₁和pe₂的选择概率用独立删边模型产生了G₁和G₂，并在高GlobalRank值的用户中选择数量的用户作为种子用户(已匹配)。

本发明通过三个指标来评价算法设计，包括精度、召回率和F1分数。精度p可以用下式表示：

$>p=\frac{N_C}{N_M},$>

其中N_C表示正确匹配的数量，N_M表示所取得的全部匹配数量。

召回率r可以用下式表示：

$>r=\frac{N_M}{N},$>

其中N表示现实社交网络G中的节点数量。

给定精度p和召回率r，性能的主要评价指标F1评分可以用下式表示：

$>F_1=2·\frac{p·r}{p+r},$>

其中精度p和召回率r均从每个用户匹配算法所得实验结果中计算得来。

参数设置上默认选择概率pe₁＝pe₂＝0.5，这意味着50％的边将被删除，从而导致节点度和节点数目也发生变化。因此删边对节点和边都带来了噪音，更为逼近真实情况。同时实验中把公式(3)中参数α的常量c设置为1.7。

本发明利用C++实现算法并与最新的社交网络用户匹配算法-KL算法(参见参考文献[1])进行了详细的比较。实验结论以及结果分析如下：

1)与KL算法相比较，本发明提出的算法能够显著地提高精度、召回率和F1分数。首先在Facebook数据集上，图1A～1C分别显示了在G₁和G₂相同边保留概率的情况下，本发明的NR-GL算法显著地提高了匹配的精度、召回率和F1分数。例如，在pe₁＝pe₂＝0.6的情况下，KL算法的精度、召回率和F1分数分别是0.051、0.366和0.09，而NR-GL算法将精度、召回率和F1分数提升到0.755、0.968和0.848，即NR-GL算法将F1分数提高了9倍多。这意味着本发明的算法在种子数较少的情况下更加有效。表1显示了G₁和G₂在不同边保留概率下，NR-GL算法显著地提高了匹配的精度、召回率和F1分数。易发现，边保留概率越大，节点之间的差异性更大，更容易正确匹配。然而在各类情况下NR-GL算法都取得了较好的效果。其次在RMAT数据集上，表2中显示了NR-GL算法取得了较好的效果，明显优于KL算法。原因在于，NR-GL算法在少量种子的前提下，先在第一阶段发掘更多的种子用户，然后再从这些用户开始扩张整个匹配过程。

2)动态变化公式(3)中α值比固定α值取得更高的精确度。实验中固定α值为0.1到0.9，间隔为0.1。图2中显示对于固定的α值，精度在α＝0.8时达到最大。然而全局信息在初始阶段更为有效，所以设计了一个函数来动态调整α值，从而调整全局和局部信息的比例。图2中动态变化的α值下所获得的精度高于任何固定α值下所获得的精度。

3)本发明的NR-GL算法的运行时间明显比KL算法短：本发明用于仿真的服务器记录为：Intel六核2GHzCPU,16GB内存，1.1T硬盘，CentOS6.4操作系统。根据实验结果，NR-GL算法在Facebook数据集上运行时间较为稳定，原因在于NR-GL算法为特定节点选择的候选节点数目较KL算法少，并且随着迭代次数增多，剩余未匹配节点数目变少，运行时间也会变短。

表1不同边保留概率下的结果

表2各类边保留概率下的结果

(pe₁,pe₂)精度召回率F1(0.3,0.3)0.9730.8520.908(0.4,0.4)0.9990.9990.995(0.5,0.5)110.999(0.3,0.5)0.9980.9980.938(0.4,0.6)110.997

本发明可以应用于多个社交网络信息整合中，利用节点的结构特征，匹配相似属性的节点，从而挖掘同一用户的多源信息。NR-GL算法以社交网络的拓扑结构为输入，以用户匹配集合作为输出。根据节点全局属性的幂律分布特征，本发明将匹配的过程分为两个阶段：第一阶段主要利用全局属性来发掘初始种子；第二阶段利用第一阶段发掘的种子和初始种子为根节点，不断扩张匹配的范围直至覆盖近乎整个网络。例如，图4给出了一个实施例。在该图中，带权无向图G₁和G₂分别代表了两个社交网络A和B，给定少量的已匹配用户，应用本发明提供的NR-GL算法，利用节点的全局和局部属性，计算节点对之间的相似分数，找到最有可能正确的一对结果。具体来说，当匹配G₁中的节点u时，通过u'和v'这些已匹配的邻居节点，找到G₂中候选节点v₁、v₂和v，然后计算这些节点与u之间的相似分数，若v取得了最大的相似分数，则匹配u和v并将这对节点放入已匹配节点集合。匹配的新节点对又会促进整个匹配过程，进而用同样方法匹配u₁和v₁、u₂和v₂。至此，两个网络中所有节点都正确匹配完毕。