《基于带权超图的跨网络用户身份识别方法-徐乾.pdf》由会员分享，可在线阅读，更多相关《基于带权超图的跨网络用户身份识别方法-徐乾.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Joumal of Computer Applications计算机应用，2017，37(12)：34353441，347lISSN 1001908lCODEN JYIIDU20171210http：wnVjocacn文章编号：100l-908l(2017)12343507 DOI：1011772jissn100l一90812017123435基于带权超图的跨网络用户身份识别方法徐乾，陈鸿昶，吴铮，黄瑞阳(国家数字交换系统工程技术研究中心，郑州450002)(+通信作者电子邮箱549529376qqcom)摘要：随着各种社交网络的不断涌现，越来越多的研究者开始从多源的角度分析社交网络数据，多社
2、交网络的数据融合依赖于跨网络用户身份识别。针对现有的基于好友关系(FRul)算法对社交网络中的异质关系利用率不高的问题，提出了基于带权超图的跨网络用户身份识别(wHul)算法。首先，通过在好友关系网络上构建带权超图来准确地描述同一网络中的好友关系及异质关系，以此提高表示节点所处拓扑环境的准确性；然后。在构建好的带权超图的基础上，根据节点所处拓扑环境在不同网络中大致相同这一特性，定义节点之间的跨网络相似性；最后，结合迭代匹配算法，每次选取跨网络相似性最高的用户对进行匹配，并加入双向认证和结果剪枝来保证识剐准确率。在合作网络DBLP和真实社交网络上进行了实验，实验结果表明，在真实社交网络上，所提算
3、法相比FRuI算法，平均准确率提高了55个百分点，平均召回率提高了34个百分点，平均F值提高了46个百分点。在只有网络拓扑信息的情况下，所提wHuI算法有效提高了实际应用中身份识别的准确率和召回率。关键词：跨网络用户身份识别；带权超图；异质关系；节点相似度；迭代匹配中图分类号：m914 文献标志码：AUser iden倘caltion method acro豁social networl【s b嬲ed on weigllted hyper掣隐phxU Qian，CHEN Hongchang，wU Zheng，HUANG Ruiyang(如Mf魄例鼬如嘶跏觚E嚼，蒯增肋f嘶删脓rcce眦r，驰n
4、g如u胁Mn 450002，劭iM)Abstnct：With the emergence of v丽ous social networks，tle social media network data is蚰alyzed fmm the perspectiveof v“ety by more and more researchersThe data fusion of multiple social networks relies on user identification across socialnetworks Conceming the low utiIiza“on problem o
5、f heterogeneous relation between social net、vorks of the tI_aditional FriendRelationshipbased User Identi6cation(FRUI)aIgodthm， a new Weighted Hyper目阻ph based User Identification(WHUl)a190dthm across social networks w髂pmposed Firsdy， t11e weighted h)rpergraph was accurately constmcted on the mendrel
6、ation networks to desc曲e the mend relation弛d the heterogeneous relation in the same network， which improved tleaccuracy of presenting topolo舀cal envimnment of nodesnen，on the b踮is of the constnlcted weighted hypergraph，the cmssnetwork simil撕ty between nodes was defined according to the consistency o
7、f nodestopolo画cal envimnment in di乳rentnetworks FinaUy，the user pair with the highest cmss network simil撕ty w船chosen to match each time by combining with theiterative matching algodthm， while two-way autllentication卸d result pmning were added to ensure the reco印i“on accllracy，Ihe experimentS were ca
8、而ed out in the DBLP coopemtion networks arId real social networks ne experimental results showthat，compared with山e e)【isting FRUI algorithm，tIle average precision，recau，F of the pmposed a190rithm is respectiVelyimproved by 55 percentage points，34 percenk唔e points，46 percenta唔e points in the real soc
9、ial networksThe wHUIalgothm can efEbctively improve the precision锄d recall of user identification in practical applicatiofls by utilizing onlynetwork topology inf0丌nationKey words： user identmcation across social network； weighted hyper铲aph； hetemgeneous relation；node siIIlilarity；itera“ve matchin只0
10、 引言多种多样的社交网络极大地丰富了人们的生活，人们通过QQ、微信与朋友保持联系，通过微博关注自己喜爱明星的动态，通过LinkedIn来发展职场社交。然而大多数社交网络间没有建立起公开的连接，因此用户的信息分散在多个社交网络中。识别出网民在不同网络中的虚拟账号的问题就是跨网络用户身份识别问题。这一问题的解决在现实应用中具有十分重要的意义：社交网络的管理者识别出用户的多个虚拟账号之后，可以获取用户在其他社交网络中的信息，从而在自己的网络中进行准确的推荐；公安机关在识别出用户的多个虚拟账号之后，可以全面地了解某一用户，为侦查工作提供支持。除此之外，这项研究还在信息检索等多个领域有着广泛的应用前景拉
11、J。收稿日期：20170523；修回日期：201708一10。 基金项目：国家自然科学基金资助项目(61521003)。作者简介：徐乾(1993一)，男，辽宁大连人，硕士研究生，主要研究方向：社交网络挖掘、机器学习；陈鸿昶(19“一)，男，河南郑州人教授，博士，主要研究方向：电信网信息关防、信息通信安全；吴铮(1992一)，男，江苏徐州人，硕士研究生，主要研究方向：复杂网络、网络大数据分析与处理；黄瑞阳(1986一)，男，福建漳州人，副研究员，博士，主要研究方向：网络大数据分析与处理、大数据分布式处理。万方数据3436 计算机应用 第37卷目前，在跨网络用户识别技术的研究上，现有的方法主要分为
12、三类：基于属性信息2一。、基于用户产生内容p“o以及基于网络拓扑结构71的用户身份识别方法。基于属性信息的方法是利用用户名、所在地、用户头像等用户在注册社交网络时填写的档案信息进行身份识别；基于用户产生内容的方法是利用用户在使用社交网络过程中产生的微博、状态及地理位置等信息进行身份识别；基于网络拓扑结构的方法是利用用户在社交网络中的好友关系信息进行身份识别。由于好友关系信息较易被获取，而且好友关系与他人完全重叠的现象非常少见，所以本文选择基于网络拓扑结构进行跨网络用户身份识别。文献7仅仅利用网络拓扑结构进行识别，将不同网络中的两个节点所共有的种子节点数作为节点的跨网络相似性，选择相似性较大的进
13、行匹配。文献8提出利用扩展的AdamicAdar指数、Jaccard相关系数来计算用户节点间的跨网络相似性。文献9提出有向网络上的身份识别，节点的跨网络相似性使用共有的inout邻居个数以及出度、入度来度量。文献10使用属性信息和网络结构信息构建目标函数对目标函数进行优化得到最优的匹配结果，其中节点相似性使用Dice系数进行度量。纵观现有方法，主要是在好友关系网络中的拓扑信息的基础上，利用共同邻居个数、Ad姗ic-Adar指数等传统的节点相似性度量方法得到节点之间的跨网络相似性。然而现实网络中的节点之间的关系具有异质性，节点之间不仅存在好友关系或者关注与被关注关系，还存在更加复杂多样的关系，例
14、如多个用户同时加入了某个兴趣小组、同时加入了某次活动、共同关注某一个用户等。现有的节点相似性计算方法忽略了节点间关系的异质性，因此造成身份识别的准确率不高。针对上述问题，本文提出了一种基于带权超图模型的跨网络用户身份识别(weighted Hypergmph b硒ed userIdenImcation，wHuI)算法。该算法分为两个阶段：第一个阶段是超图构建阶段，首先从普通好友关系网络结构出发，在两个待匹配网络上分别构建超图模型来反映网络中的好友关系及异质关系，其次在超图模型基础上定义同一网络中节点问的相似性，以此实现对于同一网络用户节点间相似性的准确刻画，然后利用种子节点计算得到两个网络中未
15、匹配节点之间的跨网络相似性。第二阶段是身份识别阶段，这一阶段解决的问题是如何根据节点之间的跨网络相似性进行节点匹配。主要方法是在节点跨网络相似性的基础上，每次选取跨网络相似性最大的节点对进行匹配，并加入双向认证保证识别的准确率。最后迭代更新种子节点集，以达到跨网络用户身份识别的目的。实验结果表明，该算法在准确率和综合评价指标上都得到了改善。1 相关定义11用户身份识别社交网络中用户间的好友关系网络可以采用图G(y，E)来表示，其中：y为用户集合，E是用户的关系集合。用户身份识别可以定义为如何在两个好友关系网络G1(伊，)和G7(矿，E7)中，挖掘属于同一个真实用户的账号，即挖掘出用户对(”j，
16、”?)，它们属于同一个真实用户并且”；、”jy7。12种子节点种子节点定义为网络中身份已经被识别出来的用户，用(sj，sj)表示，其中：sj和sjy7对应同一个线下真实用户，i为种子节点的编号。所有种子节点组成的集合称为种子节点集，用集合s=(s：，s：)，(s：，s；)，(s：，s：)表示。13基于好友关系的跨网络用户身份识别现有的基于好友关系的跨网络用户身份识别(FriendRelationship-baSed user Identi6cation，FRuI)，主要是通过计算两个节点之间的相似性来判断它们是否匹配。其计算用户节点”?伊和”j E矿的相似性方法如式(1)所示：职卟cr。s趴e
17、埘。rsim(j，)=I F彳n F了l (1)其中：，。5和F。!分别是?和”j好友中所有种子节点组成的集合；，。一n f，r表示”：和”j所共有的种子节点邻居。有了节点间的相似性之后，可以通过迭代匹配的方法进行身份识别，即每次选取相似性最大的两个节点进行匹配，然后设置一定的相似度阈值控制算法的结束。由此可见，身份识别算法的核心在于节点的相似性计算，FRuI算法的节点相似性计算过程可以分为两个部分，一部分是：对节点所在的网络环境进行表示，即认为一个节点所在的网络环境可以用与它相邻的种子节点组成的集合来表示；另一部分是：对分别属于不同网络的两个节点进行网络环境相似度的计算，即计算表示两个节点所
18、在网络环境的两个集合的交集的大小。FRuI算法的不足之处主要体现在节点的网络环境表示部分，它仅仅考虑了节点与种子节点的好友关系，然而现实网络中节点间的关系具有异质性，例如两个用户可能同时加入了某个兴趣小组或者同时加入了某次活动。FRuI算法忽略了节点之间的异质关系，从而导致了身份识别准确率的不足。本文通过引入带权超图来准确描述节点所在的网络环境，以提高身份识别的准确率。2超图模型构建21超图超图2。1纠的定义为：设K=，”：，”。是一个有限集，若e。(i=l，2，m)，且Ue。=K，记瓯=e。，e：，e。，则称二元关系G=(K，瓦)为超图，其中：K中的元素称为超图的节点，E中的元素成为超图中的
19、超边。超边带有权重的超图称为带权超图，对于超边e，其权重用叫(e)来表示。超边的度定义为6(e)=I e I，即超边中包含的节点的个数。节点超边函数定义如式(2)所示：(叩)：J 1， ”8 (2)、【0， 其他 、22超图模型本文使用超图来描述用户间的社会关系，图l所示为两个待识别网络对应的超图c：(瞄，磺)和G：(“，E：)，其中：W=口Jl，也，舶，E： = exl，e船，e躬，E： = en，e住，en，碟=(”。，”。，口b)。超图中的每一个节点”K表示社交网络中的用户，超边用来描述用户间各种各样的社会关系，例如超边e=”。，”，”和”H的关系可以是好友关系、同时加入某个兴趣小组或者
20、同时加入了某次活动。(”肌，”n)和(”船，”，2)是已经被识别的种子节点，其余的节点是待匹配节点。本文的目的是在待匹配网络上构建如图l所示超图模型，然后考察超图中未匹配节点与种子节点的关系，从而识别出其他未知的匹配节点。23在好友关系网络上构建超图模型在实际应用中，如果有已知的异质关系信息，例如多个用万方数据第12期 徐乾等：基于带权超图的跨网络用户身份识别方法 3437户加入了同一个兴趣小组，或者同时参加了某个活动，那么就可以直接将这些用户划分到一个超边中，然后通过设置超边权值来体现超边中的节点之间具有某种程度的亲密关系。但是上述信息通常难以获取，有时只能获取用户好友关系信息。所以本文根据
21、普通的好友关系网络来得到近似的用户关系信息，从而构建超图模型。如果同一个网络中的两个用户”和”：直接相连，就将”。和”：划分到同一个超边中，例如图2所示的有向图中，由于”。和”：以及”和之间都是直接相连关系，这种关系通常是反映了现实中的好友关系，在另一个网络可能也存在这样的关系，因此分别构建超边e，=，”：、ez=h，分别表示”。和”：以及。和如之间的好友关系，为下一步计算节点相似性提供支撑。图I 用于跨网络身份识别的超图模型Fig1 Hype唱mph model for user identmcation acro鹪social networks图2直接相连关系对应的超边划分Fig2 Hyp
22、eredge constnlction of direct connected relation除此之外，本文在拥有共同邻居的两个或多个节点上构建超边，例如图3所示，”：、”，、”。是”。的所有邻居节点且都和”，直接相连，在这种网络结构下，可以认为”：、”。都具有“与”。是好友”这个属性，因此在其上构建超边e，=”：，”，”。，表示”：、”，、”。所在的拓扑环境有部分相似之处，从而为下一步计算节点相似性提供支撑。图3拥有共同邻居的两个或多个节点上的超边划分Fig 3 Hyperedge cons咖ction of two or more nodeswith common neighbo舟231
23、超边权重设定通过上述分析可知，超图不仅保留了好友关系网络中原始的拓扑信息，而且还可以体现网络中的异质关系。这些关系有些是紧密的关系，有些则是相对疏远的关系，因此需要通过设置超边的权重来表示超边内节点的亲密度，权重越大则认为超边中的节点关系越紧密。对于在直接相连关系上建立起的超边，超边内节点对应的是社交网络中的好友关系，将这种超边权重设置为p，p相对较大；对于在拥有共同好友的节点上构建的超边，由于超边内节点彼此之间不一定直接相连，因此这种超边节点关系通常比直接相连的好友关系疏远，将这种超边权重统一设置为叮，g相对较小。本文的实验部分，会考察p和q的设置对于实验结果的影响。232超图模型构建算法基
24、于以上分析，本文给出在好友关系网络上构建带权超图的算法，算法描述如算法l所示。算法1 带权重超图构建算法。输入好友关系网络G(y，E)，超边权重p、g；输出 带权超图G(K，E)。HypergmphCons岫ction(G，P，g)1)初始化“=y，既=，i=12) for U E K do3) forH肫培6Dr()do4) ei=，“5) if超边集中含有仅包含，u髓边权重为p的超边d06) continue7) el8) E=E+e，加(e。)=p，i=i+19) end if10) endfor11) ife培胁Dr(”)中含有两个或两个以上的节点12) e。=e培60r(口)13)
25、E=E+e。，埘(e。)=g，i=i+114) end if15)endfor16)retum(n，B)上述算法中，肌培h60r(”)是”的所有邻居节点组成的集合，第3)10)行是在直接相连的两个节点上构建超边，第11)14)行是在拥有共同好友的两个或多个节点上构建超边。3 基于带权超图的用户身份识别31节点相似性计算由于好友关系在不同社交网络中非常容易保持一致性“，所以两个网络中互相匹配的两个节点，它们与种子节点的相似性也具有跨网络的一致性。这种一致性可以用来计算未匹配节点间的跨网络相似性，进而判断这两个节点是否匹配。由于超图可以准确地描述网络中节点之间的关系，所以本文利用超图来计算身份未识
26、别节点与种子节点的同网络相似性，然后根据的跨网络一致性，定义不同网络中节点间的跨网络相似性，为下一步节点匹配提供支撑。311 同一网络中的节点间相似性已知用户好友关系网络G(y，E)，根据在其上构建的超图G(K，邑)，超图G中的两个节点”。H和”，K的相似性计算方法如式(3)所示：劬，：奎l业警叫 式(3)体现的思想是，如果”。和q同时所在的超边个数越多，”。和q的相似度就越高。埘(e。)是超边的权重，它体现超边中各个节点关系的紧密性，权重越大说明超边中的节点关系越密切，相似度越高。6(气)是超边的度，6(e。)=2时超边中的节点在好友关系网络中是直接相连的关系，此时超边中的两个节点之间的关系
27、较为紧密，相似度较高；6(e。)2时，超边中的节点在好友关系网络中只是拥有共同关注的好友，它们可能并不直接相连，所以此时超边中的节点之间的关系相对疏远，相似度较低。(”，e)是节点一超边函数，当”e时，(，e)=l，否则(u，e)=0。312跨网络的节点问相似性对于互相匹配的两个节点，它们与种子节点的相似性具有跨网络一致性，所以本文利用未识别节点与种子节点的同网络相似性来计算两个节点跨网络的相似性。万方数据3438 计算机应用 第37卷对于分别属于两个网络的身份未识别节点”：蟛和”j“，称式(4)为”j与”j关于种子节点(s：，s：)的跨网络相似性：s(”j，(s：，s：)=exp(一I s咖
28、(”j，s：)一sim(”?，s：)1) (4)式(4)基本思想是：以种子节点(s：，s：)为参照，分别计算”j和s：、”j和s：在同一网络中的相似性s溉(”j，s：)、s拥(”j，s：)，如果”j和”j对应线下同一个真实用户，那么它们与种子节点的相似性的差的绝对值旧m(”j，s：)一sim(”j，s：)l就会很小”?和关于种子节点(s：，s：)的相似性就会很大。为了提高节点的辨识度，本文考察待识别节点关于所有种子节点的跨网络相似性，即”j E碟和”?以的跨网络相似性，定义如式(5)所示：cr05姗e埘。以sim(pj，一)=sexp(一旧m(”j，s：)一sim(，s：)1) (5)其中：s
29、表示所有种子节点组成的集合；(s：，s：)表示|s中第个种子节点。”?与”j关于所有种子节点的相似性的和越大，表明它们所在的网络拓扑环境越相似，两者的跨网络相似性就越大。32跨网络节点匹配有了跨网络相似性之后，接下来面对的问题就是如何进行跨网络节点的匹配，算法在身份识别阶段解决的就是这一问题。本文将跨网络节点匹配分解成逐步迭代求取的过程(如图4所示)，在每一步迭代的过程里，算法的计算过程分为节点选择、节点匹配和双向认证，在每一步迭代过程中选取当前跨网络相似性最大的两个节点进行匹配，加入到种子节点集s中，新加入的种子节点也作为计算跨网络相似性所参照的种子节点，从而提高识别准确度。当没有可以匹配的
30、节点时，算法停止迭代。最终通过结果剪枝，删除一部分算法后期挖掘出的种子节点以保证准确率，剪枝后的结果即为最终的结果。算法进行跨网络匹配的流程如图4所示。入构建好的超图G，、Gj，种子节点蜇攀熹嘉器哭怛配节点对加入F种子节点集l结果剪枝将选择出来的账号加入未匹配队列没有可以匹配的节点对输出剪枝后的种子节点集s图4 wHuI算法在身份识别阶段的流程Fig4 Flow chaof WHUI a190rithm at identi6cation st89e321 节点选择wHuI算法在用户身份识别阶段，每一次迭代运行的第一个步骤就是从两个网络中选择一个最有可能在另一个网络中存在匹配的节点。由于用户使用
31、社交网络的习惯很大程度上受好友的影响，用户的好友中种子节点越多，他在另一个网络中存在匹配节点的概率就越大，因此本文优先选择好友中种子节点数量多的优先进行匹配，算法描述如算法2所示。算法2节点选择算法。输入网络x中尚未匹配的节点集合吃。州，网络y中尚未匹配的节点集合屹。ped；输出 待匹配的用户节点”“。userselect(蠊。pPedy：。ppcd)1) if unmapped queue非空then2) retum队列中第一个元素3) end if4)for each Fo吃。”Ped do5) 计算的邻居中种子节点的个数61 end for7)对吃。，Ped中的节点按照好友中种子节点的个
32、数由大到小进行重排序8)对吃m印ped执行同样的步骤9)if吃m印Pedo吃m叩刚o小en10)”。=屹删o11)else12)。=吃ppedo131 end if14)retum。dect其中unmapped queue表示未匹配队列，未匹配队列中的节点，是在之前迭代过程中被选中了但并未成功匹配的节点。第4)8)行是在计算两个网络中每一个节点相邻的种子节点的个数，并且对两个网络中的节点集合，按照之前计算的相邻的种子节点个数进行降序排列。第9)一13)行是在对比两个网络中排在首位的节点，返回较大的作为最终选中的节点。322节点匹配当得到节点选择过程中返回的待匹配节点”。，接下来就需要基于312
33、节提出的跨网络相似性进行匹配。节点匹配算法首先需要确定该用户节点是来自于网络x还是来自于网络y；然后选择与”。跨网络相似性最高的节点”。汕作为最有可能的匹配返回。节点匹配算法描述如算法3所示。算法3节点匹配算法。输入待匹配的用户节点u。，带权超图G：、G：，网络x中尚未匹配的节点集合雌，删，网络l，中尚未匹配的节点集合矿一，Pcd；输出 候选匹配节点”。userMatch(u虻，吃mIP一，矿：。mP一，G：，G：)1)if”。I。来自网络xtllen2) for eachy品。PPed do3) 计算crMI-s拥(u。，G：，G；)4) end for5) MIch=agmax crojs
34、聊flIor矗s溉(耖，c：G：)。6：PPed6) retummmch7、 else8) 对吃。ped执行同样的步骤91 end if323双向认证考虑到在节点选择和节点匹配阶段都需要用到种子节点，根据已有的种子节点来选择待匹配节点”。及候选匹配节点”。，使得因此一个错误的种子节点将会对接下来的迭代过程造成误导，并且这种坏的影响会不断积累导致算法失败。因此本文使用双向认证的方法来保证每次产生的种子节点的准确性。即验证与”。砌跨网络相似性最大的节点是否为”。：如果是则将(”。，”。)加入到种子节点集；如果不是，则将”。加入到未匹配队列中等待机会再匹配，并将”。重置为”。进入新的一轮迭代。双向认
35、证算法描述如算法4所示。万方数据第12期 徐乾等：基于带权超图的跨网络用户身份识别方法 3439算法4双向认证算法。输入待匹配的用户节点p。，候选匹配节点”。，种子节点集s，网络x中尚未匹配的节点集合屹一，叫，网络l，中尚未匹配的节点集合吃。ped；输出一个新的种子节点。Cms8Matching(u。J。I，”mkh，|s)1)F。砒ch=仉er忆c(F。lch，q。Pped，y：。pped)2)if口m砒。h is u。I。t tlen3) S=S u p一4) 屹。P”d=屹。P删一。5) 吒。qped=“十删一。6) 。l。t=NULL7) retum NULL8) el9) 将”池。t
36、加入到unmpped queue中lO) Flect=。h11) Fm砒ch=口mmh12) retum(k1mh)13)end if其中”。表示新生成的种子节点。第3)一7)行是在双向认证成功后，将匹配成功的节点对从尚未匹配的节点集合中删除，并将它们加入到种子节点集中。第9)一12)行是算法在双向认证失败后，将”。加入到unmapped queue中等待合适的节点与之匹配，并将”。胁和”。互换并返回，返回之后将会在”。和”。基础上继续执行双向认证过程。324结果剪枝考虑到本文仅仅利用拓扑信息进行匹配，因此即使加入了双向认证的过程，算法前期的准确率也不能够达到100，也就是说在算法的最后阶段，
37、会产生大量的错误配对，因此需要一个剪枝的过程将结果中错误的匹配排除在结果之外。由于算法在身份识别阶段优先选择最有可能匹配的节点并且使用双向认证算法，因此有理由相信，早期产生的种子节点有很高的可信度，而后面产生的种子节点错误的可能性比较大。所以本文采取一个非常简单的方式，也就是只选取前期产生的结果作为最终结果。选择95、90或者其他百分比，这个取决于具体的网络环境。本文实验部分验证了剪枝百分比对准确率的影响。33 wHuI算法算法5展示了基于带权超图的跨网络用户身份识别(WHUI)算法的完整过程。输入两个好友关系网络及种子节点集合，然后通过在好友关系网络上构建超图从而得到节点的跨网络相似性，最终
38、在身份识别阶段通过持续的选择、匹配、双向认证，最终对结果剪枝得到完整的结果。算法5双向认证算法。输入好友关系网络G。(，)和G7(y7，E7)，超图权重p、g，匹配前已知的种子用户集合s；输出 最终的种子用户集合s。1) Gf(嵋，E：)=Hypergraphconstnlction(Gx，p，q)2) Gf(嵋，E：)=Hypergraphconst兀lction(G7，P，q)3) S。uh=S4)初始化空队列unmapped queue5)while吃ppedd y：ppeddo6) if”髓I。d=NULL then7) 。kd=userSelect(心pPedy：。PPed)8) 口
39、。h=userMatch(出。y：m印叫，y。pPed，钟，cr)91 end ifl O) (口。I。I，”。I。h)=crossMatching(。l。I，”。kh，s。lI)11)end while12)对S。ulI进行结果剪枝13)retum|s。ll34时间复杂度分析设待匹配的两个好友关系网络为G。(，)和G7(，E)，其中未匹配节点个数分别为肘=I屹。“I，=I吒。ped l，假设肘。算法的复杂性分为两个部分：一部分是超图的构建，由于算法在直接相连节点和具有共同好友的节点上构建超边，因此复杂度分别为D(II+E。I)和D(I y7 I+I E7 I)。另一部分是跨网络账号匹配产生的
40、复杂度，在账号选择过程中，需要计算每一个未匹配节点的好友中种子节点的个数，它随种子节点的增加而改变。因此第一次花销为肘+，v；第二次只需要计算与新加入的种子节点直接相连的未匹配节点，在最坏的情况下，每一个未匹配节点都需要计算，花销为M一1+一1；第三次需要M一2+一2。以此类推，每一项的通项公式为肘+，v一2n，到，v一1次后算法结束，所以总时间为(肘+，v)(一1)一(，v1)，化简后为M(，v1)。接着要计算的是账号匹配和双向认证阶段，需要找出与”。跨网络相似性最大的节点然后进行双向认证，假设”。，因此第一次在账号匹配过程中最多需要计算”。与，v个节点的跨网络相似性，对应双向认证需要计算M
41、1次，第一次时间开销为M+，vl，第二次为(肘一1)+(一1)一1。每一项的通项公式为M+一2几一l。同样到，v一1次后算法结束，所以总时间为(M+，v)(7、，一1)一(，v1)一，化简后为肘(一2)。所以账号在跨网络匹配部分的复杂度为0(肘)。综合超图构建与跨网络账号匹配，得到总的时间复杂度为O(|JlfJ、r)。4 实验及结果分析41 实验数据411 DBLP网络为了验证算法的有效性，本文使用文献15中的英文文献数据库DBLP来建立一个模拟的社交网络：DBLP中包含很多文章，每篇文章由多个作者合作完成。将每一个作者作为社交网络中的用户，将作者之间的合作关系认为是社交网络中的好友关系。然后
42、将DBLP数据集中的所有文章随机分为两个部分，按照上述方法在这两个部分上分别构建模拟的社交网络，从而得到两个DBLP网络。这样，对于属于两个部分的两篇文章，如果这两个文章中都包含同一作者，那么这个作者在两个网络中的两个账号就可以组成种子节点。两个网络中的用户数量分别为2 317和2 327。DBLP网络具体信息如表l所示。表l DBLP网络数据统计Tab1 DBLP nelwork data slatistics图5是两个网络度的分布，近似服从幂律分布。412真实社交网络数据为了验证算法的实用性，本文使用文献10提出的标准数据集，该数据集在T“tter和Facebook这两个社交网络上，万方数
43、据3440 计算机应用 第37卷以16位在两个网络上都注册账号的用户为起点，通过好友关系逐步扩展网络，最终得到了l 475个账号，如表2所示，其中：Facebook账号有422个，Twitter账号有l 053个。其中有152个对应关系已知的种子节点。k碍壅窖赛丑魁臣节点度X 节点度K(a)DBLP网络l (b)DBLP网络2图5 DBLP网络的度分布Fig 5 DeFee dis晡bution of DBLP networks表2 Faceb00k和Twiller社交网络数据统计Tab2 Social network data statis“cs of Faceb00k and Twitte
44、r节点度K 节点度X(a)TwiIter (b)Facebook图6 Twitter网络和Faceb00k网络的度分布Fig6 Degree dis埘bution of Twitter networI【们d Facebook networl【42评价指标本文评价指标采用信息检索中的准确率P、召回率屁、综合指标F，其计算公式为：R=NNt 06)P=N_N t，j)F=2尺P(尺+|P) (8)其中：以是算法识别出的正确匹配的用户节点的对数；，是实验数据中实际存在的匹配节点对个数；M是算法识别出的匹配的节点对(包括正确匹配的和正确匹配的)。43实验分析本文选取度数排名靠前的一部分种子节点作为初始
45、时已知的种子节点，其余的种子节点在初始时作为未匹配节点，在算法结束后用来验证算法的准确性。431超图权值的影响为了验证超图权值对实验结果的影响，令权重_p=l，权重口从l递减到0。在DB”网络和真实社交网络(Facebook和Twitter)上实验结果如图7所示。在DBLP网络上，当p比g约等于45时，F达到最大值624。在真实社交网络上，当权重Jp一定(p=1)，g从l开始逐渐减小时，共同好友关系在计算节点相似性时所占比重减小，当g减小到约为JD值的十分之一时(pg10)，F值达到最大值724，说明共同好友关系比于直接相连关系相对较弱，过多地依靠共同好友关系来得到节点相似性时，F值将会大幅降
46、低；当口值从01继续减小时，F值降低，说明了共同好友关系在计算用户相似性时也应该占一定比重，忽略了共同好友关系会导致，值下降。07慧吒器O2黜p|q p|q(a)DBLP网络 (b)真实社交网络图7综合指标F随权重的变化Fig7 charIge of comprehensive index F with weigIt432剪枝率的影响此外，本文还验证了在不同的剪枝率下算法的评价指标。剪枝率为算法在迭代得到的种子节点集合上所减去的种子节点的比例，结果如图8所示。剪技率 剪枝率(a)DBLP网络 (b)真实社交网络图8评价指标随剪枝率的变化Fig8 Ch肌ge of evaluation inde
47、xes with pnlning mte在DBLP网络上，随着剪枝率的增加，算法的召回率减小，准确率增大；剪枝率为45时，F达到最大值624。由于数据集合中种子节点所占比例非常小仅为18，算法前期可能就挖掘出大部分种子节点，之后便会产生大量错误匹配，因此需要减去大部分迭代产生的结果，来保证最优的，值。在真实社交网络上，当剪枝率为35的时候，F值达到最大值724。此时虽然召回率不高，但是保证了一定的准确率。433算法性能对比为了验证算法的有效性，本文将提出的wHuI与传统的FRuI算法进行对比，实验中的参数均选用最佳情况下的取值(p=1，q=03，剪枝率在DBLP网络上设置为90，在真实社交网络
48、上设置为35)。表3汇总了在DBLP网络和真实社交网络的测试结果。图9是两种算法的评价指标对比。通过在DBLP网络上的实验测试，发现当种子节点数量较少时，对于FRUI算法，由于可以利用的种子节点不多，因此通过节点跨网络相似度来区分不同的用户准确率和召回率都相对较低；对于wHuI算法，由于充分利用当前所有种子节点来计算跨网络相似性，在种子节点数较少时，其准确率、召回率高于FRuI。当种子节点数量增多时，FRuI在召回率和，值上拥有微小的优势。总的来说，在DBLP网络上，wHuI相对于FRuI算法，平均F值提高了12个百分点。在真实社交网络上的测试结果表明，wHuI算法在准确率、召回率和，值上全面优于FRuI，这是因为wHuI算法中使用的超图模型不仅保留了好友关系网络中的拓扑信息，还万方数据第12期 徐乾等：基于带权超图的跨网络用户身份识别方法 3441加入了网络中的异质关系信息，从而更加准确地度量出节点间跨网络相似性，实现了相对准确的匹配。在真实网络上，