胡开先梁 英许洪波毕晓迪左 遥

1(中国科学院网络数据科学与技术重点实验室(中国科学院计算技术研究所) 北京 100190)2(中国科学院大学 北京 100049)(kaixian.hu@gmail.com)



一种社会网络用户身份特征识别方法

胡开先1,2梁 英1许洪波1毕晓迪1,2左 遥1,2

1(中国科学院网络数据科学与技术重点实验室(中国科学院计算技术研究所) 北京 100190)2(中国科学院大学 北京 100049)(kaixian.hu@gmail.com)

社会网络是现代信息社会重要的组成部分.社会网络用户身份不透明、不可见的特性带来一系列社会安全问题.提出了一种社会网络身份特征识别方法，分别利用基于位置的社会网络和社交关系进行社会网络用户的身份特征识别，融合2种识别结果推测社会网络用户真实身份.提出了一种基于位置的社会网络用户身份识别方法，通过计算中文分词和二元组分词的基本匹配权重和完全匹配权重得到近似度权重，并用它衡量实体为用户所属实体的可能性；通过实体名称聚合算法，对近似度权重计算结果进行优化.根据好友之间倾向于拥有相似的身份特征和相同的兴趣爱好的观察，提出了一种基于社交关系的多数投票的身份识别方法，对社交关系中的用户身份特征进行统计，推测当前用户的地址信息、实体信息和用户兴趣.基于微博数据，进行了样本数为1 000名用户和10 000名用户的2组实验，涵盖了超过250万条社交关系.实验结果表明，提出的虚实映射方法有很高的准确率和覆盖率，与现有方法相比，该方法着眼于推测个人用户细粒度的身份特征，具有较高的实际应用价值.

身份识别；用户身份特征；基于位置的社会网络；社交关系；去匿名化

社会网络在人们生活中扮演着重要的角色，微博、微信、人人网等社会网络已经成为人们获取信息、展示自我和营销推广的重要途径.由于社会网络的匿名性，人们可以方便地以虚拟身份自由发表观点和意见，每个人都是信息的生产者和消费者.信息的快速发布和传播，使社会网络成为一把双刃剑，它既是应对突发事件的利器，也是谣言传播的温床.例如，新浪微博博主“秦火火”虚构的动车事故等谣言、微博博主“染香”捏造的“名人被去世”等谣言，这些造谣事件，严重扰乱网络秩序、侵害他人名誉、败坏社会风气、危害社会安全.社会网络的虚拟性和匿名性使之不易追踪网络虚假消息的发布者、不易定位危害国家治安言论的发布者、不易在网络中追查违法犯罪行为等.因此，开展识别用户社会网络虚拟ID对应的真实身份的研究，对于维护网络治安具有积极的社会意义.

目前，针对社会网络中用户身份识别的研究主要是通过社会网络用户公开的信息推测用户群体的信息或倾向.通过挖掘用户特征推测个体用户所属群体，将用户按兴趣爱好分类，可以为用户提供个性化的产品营销和广告投递等服务；将用户按社交关系分类，可以应用于用户群推荐和用户群检测等服务.通过挖掘用户地理位置，可以推测用户频繁出现的地区和事件发生体.然而，上述方法主要是挖掘用户的特征属性对用户群体进行分类，而不是面向用户个体的识别.

本文提出了一种基于位置和社交关系的社会网络身份特征识别方法.通过用户在社会网络上发布的带位置信息的博文，挖掘分析用户当前所属的学校和工作单位；同时利用用户自身及其社交圈的信息，挖掘分析该用户的地址信息、学校、工作单位和兴趣；最后融合上述2步结果对用户的真实身份做出推断，给出社会网络用户身份识别的方法.

1 相关工作

近年来，对社会网络的数据挖掘和分析受到了学术界、工业界的广泛关注，代表性研究包括话题事件分析、情感分析、社交关系分析、用户信息检索推荐等[1].其中，社会网络用户信息挖掘的相关研究主要是针对社会网络用户的兴趣、位置和社交关系等进行分析，推测个体用户所属群体.由于不同的年龄、性别、教育背景、地理位置和观点的人群在使用社会网络时的差异性，通过分析个体用户特征、言语行为，对用户进行群体分类和个体定位，一方面可以进行个性化服务、产品营销和广告投递等商业活动，另一方面也可以进行具有相同兴趣爱好、主观倾向、观点言论的群体推荐或检测.

挖掘社会网络用户兴趣一般是利用用户的历史地理位置信息或者社交关系将用户按照兴趣爱好分类，并据此向用户作推荐，推荐内容包括地理位置、产品、好友等.在根据兴趣推荐地理位置的研究中[2-4],Bao等人[2]研发了一个基于位置的兴趣认知推荐方法，利用用户的历史地理位置信息和某地理位置的用户评价，在线为拥有相同兴趣爱好的社会网络用户推荐他们感兴趣的地理位置.在根据兴趣推荐兴趣点的研究中[5-6]，Wei等人[5]提出了一种基于位置的兴趣点标识方法，通过提取访问兴趣点的用户团体的特征描述用户个体兴趣点的特征，将获得标识的兴趣点推荐给有相同兴趣的用户.在根据签到信息推测用户倾向的研究中[7-8]，李敏等人[7]通过分析用户签到信息和用户对签到位置的评论，推测用户的主观倾向性，使社会网络能更好地为不同类别的用户作个性化推荐.除上述研究方向外，还有通过某用户社交圈推测该用户兴趣的研究[9-10]，Xu等人[9]通过某用户的社交关系中兴趣属性公开的用户，利用贝叶斯分类方法推测该用户的兴趣.

社会网络用户社交关系挖掘利用用户的社交关系、属性或历史地理位置检测不同用户之间的相似性，并在此基础上向用户推荐好友.一类是通过用户行为模式挖掘[11]社会网络结构进行好友推荐[12-13]，Crandall等人[12]发现经常在相同时间出现在相同的地理位置上的用户之间有较强的社交联系，并利用此结论挖掘用户的社交结构向用户推荐好友；另一类是通过挖掘社交关系推荐好友[14-16],王玙等人[14]认为拥有相似社交圈的用户更易成为朋友，并在此基础上提出了社交圈检测算法，定义用户间的社交圈相似性，根据相似程度划分好友圈.另外，一个用户通常会在多个社会网络注册不同账号，账号对齐研究通过分析用户在不同社会网络中的信息，利用社交关系图、好友关系等识别出同一用户在不同社交平台的身份.如Bayati等人[17]将特征转化为二部图的一组结点，待对齐的所有实例为另一组结点，然后根据结点的度、排名、权重、聚类相关度来对齐；Korula和Lattanzi[18]利用朋友关系的网络图将跨社会网络的账号映射进行了数学建模.

社会网络用户地理位置推测主要通过某用户社交圈的地理位置信息来推测该用户所在的地理位置[19-21].Backstrom等人[19]利用Facebook上用户的好友关系来推测当前用户的地理位置，该文得到的结论是：当用户好友关系中有5个以上可定位用户时能有效利用社交关系推测其地理位置，否则应当使用IP地址推测其地理位置.Clodoveu,Diogo等人[21]通过Twitter用户粉丝中可定位的用户，运用多数投票方法来推断其他用户发布博文的地理位置.

社会网络去匿名化方法研究如何去除匿名化伪装的影响，根据已知的用户信息推测其敏感信息和倾向.在针对图结构数据的去匿名化研究中[22-23]，Narayanan等人[22]利用同一人在不同社会网络中社交关系具有一定相关性进行多账号身份识别，从已知的少量信息出发，寻找相似结构完成种子节点映射，通过扩散不断找出新节点的映射关系，成功匹配了13同时使用Twitter和Flicker的用户.基于文本数据的去匿名化研究中，Narayanan等人[24]抽取文本数据特征建立高维文本特征向量，用机器学习分类器识别文本作者或其博客.

除上述研究成果外，也有一些产品化的用户特征分析工具.iResearch公司提供的网民用户行为分析工具TargetPlus通过分析网络用户群网络行为范式与特点，帮助广告主了解不同类别的目标用户需求，优化网络营销策略.Mixpanel公司推出的用户特征分析工具Mixpanel[25]可以分析网站访客的性别、国家等信息，对用户分类，把相关信息精确地送达某一用户群体.Webtrends公司的Reinvigorate工具和Chartbeat公司的Chartbeat工具可以实时监测网站的用户行为.除此之外，大型电商网站如Amazon、淘宝、eBay、京东等通过分析网站用户数据推测用户生活特征和购物兴趣或倾向，以此向用户提供个性化购物体验和更精确的产品推荐.

综上所述，关于社会网络用户特征属性挖掘的研究已被广泛关注，当前研究主要着眼于挖掘用户群体的信息和倾向，并没有对个体用户的特征属性作深入分析；在分析用户群体特征属性时粒度不够细化，难以推测个体用户的真实身份.相比上述研究成果，本文主要贡献为:

1) 利用用户的地理位置信息和博文推测用户的学校和工作单位，将地理位置的粒度细化到具体的某个实体；

2) 利用某用户社交关系群体特征，推测该用户的地址、学校和工作单位信息；

3) 融合上述2步结果，对用户身份特征做出综合性推测，进一步缩小用户真实身份范围，建立起社会网络用户虚拟身份和真实身份之间的虚实映射.

2 用户身份特征识别方法

2.1 方法概述

为了从社会网络用户的虚拟身份信息推测其真实身份，需要不断缩小用户真实身份的范围.地址信息、学校和工作单位对确定用户身份具有重要作用，为方便分析，本文将其定义为用户身份特征，示例如图1所示.

Fig. 1 Sample of user identity feature.图1 用户身份特征示例

定义1. 用户身份特征(UID).该特征特指地址信息、学校、工作单位和兴趣.可用一个四元组UID=L,E,W,I描述.其中，L代表该用户地址信息集合，可表示为：L={(li,Pli)|i=1,2,…,nL} ，li代表省、市、区、街道和门牌号等地址信息，Pli代表用户地址为li的概率；E代表学校集合，可表示为：E={(ej,Pej)|j=1,2,…,nE}，ej代表用户毕业或就读的学校，Pej代表用户毕业或就读学校为ej的概率；W代表工作单位集合，可表示为：W={(wk,Pwk)|k=1,2,…,nW}，wk代表用户曾经工作或在职的工作单位，Pwk为用户在职或曾经工作的单位为wk的概率；I代表用户兴趣集合，可表示为：I={(ik,Pik)|k=1,2,…,nI}，ik代表用户的兴趣，Pik代表用户兴趣为ik的概率.

Fig. 2 Flow chart of user identity feature recognition method.图2 用户身份特征识别方法总体流程图

定义2. 实体指学校和工作单位的集合.该集合是E和W的并集，可表示为：S={SP|SP∈E∪W,P=1,2,…,nE+nW}.

本文从社会网络用户(简称用户)的地理位置信息和社交关系出发，推测用户的地址信息、学校、工作单位和兴趣，以缩小用户真实身份的范围.整体的流程如图2所示，主要包括数据获取、数据分析、结果融合和结果推送.

1) 数据获取.通过给定的微博用户唯一标识(昵称)获取该用户的个人信息(特征属性)、粉丝列表、博文内容和签到信息.

2) 数据分析.包括2种分析方法：①地理位置方法.通过用户开启GPS服务后博文数据带有的经纬度信息得到用户的频繁地理位置，进而得到该位置周边的实体信息，与用户签到的实体信息合并得到候选实体列表；实体列表中每个实体是用户可能所属的学校和工作单位，用近似度权重衡量可能性大小；通过实体名称聚合算法合并实体名称、优化近似度权重计算结果，推测用户的地址信息、学校、工作单位和兴趣.②社交关系多数投票方法.通过用户的粉丝列表得到用户的互粉好友，提取用户互粉好友的用户身份特征，并对得到的用户身份特征集合L,E,W,I进行多数投票，选取各集合中满足条件且计数靠前的各项作为当前用户身份特征.

3) 结果融合.地理位置方法覆盖开启GPS服务的用户，社交关系多数投票方法覆盖有健壮社交关系的用户(通过粉丝列表中互粉好友数目体现)，通过对2种方法结果的融合，能够提高用户身份识别的覆盖率.

4) 结果推送.在结果融合后，整理汇总所得地址信息、学校、工作单位和兴趣，推送给最终用户.

在2.2节和2.3节中，将重点介绍基于位置的身份识别方法和基于社交关系的身份识别方法.

2.2 基于位置的社会网络用户身份识别方法

基于位置的社会网络用户身份识别方法根据社会网络用户的地理位置信息和博文内容来推测该用户所属的学校或工作单位.与社会网络用户相关的地理位置信息主要包括2种：1)用户主动分享的数据，如签到信息；2)开启GPS服务的代价，例如博文带有的地理位置坐标.本方法同时用到上述2类地理位置信息，再利用博文内容来匹配分词后的实体名称，本方法的主要步骤如下：

步骤1. 从用户发布的博文中提取地理位置信息；

步骤2. 对得到的地理位置信息作频率统计，获得前N个频繁的地理位置；

步骤3. 通过新浪微博API获得这N个频繁地理位置周边的实体列表；

步骤4. 将上述列表和用户的签到信息合并，得到候选实体列表；

步骤5. 分析候选实体与用户博文匹配度，计算其近似度权重；

步骤6. 使用实体名称聚合算法聚合所有候选实体信息并去除冗余，优化近似度权重计算结果.

最终，根据新的近似度权重对实体排序，得到降序的候选实体列表.其中，最为关键的步骤是实体名称近似度权重计算和实体名称聚合，下面我们分别对这2个步骤进行专门介绍.

2.2.1 近似度权重计算

用户的博文内容中包含和用户直接相关的信息，如地址信息、学校、工作单位等.因此，我们可以通过将实体名称匹配用户博文的方法计算实体列表中各实体为用户所属实体的可能性.考虑到实体全称在用户博文中被提到的可能性低，为了提高命中率，我们先对实体列表中各实体名称进行分词处理(二元组分词和中文分词)，并在分词过程中通过别名词库将分词得到的实体简称、别名加入到分词结果中以防止实体名称漏配用户博文中用户习惯用语的情况.匹配的结果由近似度权重衡量，近似度权重越高，对应实体即为用户所属实体的可能性越大.近似度权重的大小和匹配内容的长度及匹配次数成正比，匹配内容的长度越大、次数越多,近似度权重越大.

实体名称对应的分词结果与博文内容进行匹配分为完全匹配和基本匹配.完全匹配表示实体名称的全称在博文内容中得到匹配(博文内容包含实体名称的全称“北京大学”)；而基本匹配表示实体名称的分词结果中的分词(不包括实体名称的全称)在博文内容中得到匹配(博文内容只包含“北京”、“大学”等词组).完全匹配的实体近似度权重高；基本匹配的实体近似度权重低.基于以上分析，设计了实体名称s完全匹配的近似度权重Weightf(s)和实体名称s的分词结果si基本匹配的近似度权重Weightb(s)为

(1)

(2)

式(1)中，s代表输入实体名称，Weightf(s)代表输入实体名称的近似度权重，Len(s)代表输入实体名称的长度；式(2)中，si代表实体名称s的一个分词结果，Weightb(s)代表输入实体名称分词的近似度权重，n代表实体名称s分词的总数，msi代表si与博文内容的匹配次数.

由式(1)和式(2)得到实体名称s的近似度权重Weight(s)为

(3)

式(3)中，α和β代表可调参数.其中，α=qm，代表可调乘数因子，取值范围为大于1的实数；m代表实体名称s与博文内容的匹配次数，取值为正整数；qm代表权重增长的速率.β的取值范围为大于等于0的实数.

计算得到候选实体列表各实体名称的近似度权重后，对实体列表按近似度权重降序排列，得到用户可能所属的实体名称列表序列.

2.2.2 实体名称聚合算法

对于具有相同近似度权重的实体，需要再次计算近似度权重并优化排序结果.在实际项目中发现，通过地理位置信息和博文内容得到的实体名称的粒度可能会精细到单位内的某个具体地点，比如“北京大学食堂”和“北京大学教学楼”，本文识别的是“北京大学”这个单位的名称.因此，提出了一个实体名称聚合算法，通过合并具有相同前缀的实体名称，提取表示单位名称的实体名称，滤掉细粒度的实体名称；计算合并近似度权重，优化实体名称排序结果.

实体名称聚合算法用到了Trie树，又称字典树或前缀树，是一个利用字符串的公共前缀来描述字符串序列的多叉树.本文利用Trie树描述从用户地理位置信息获得的实体序列，并满足3点性质：1)根节点不包括字符，其他每个节点只包括一个汉字；2)从根节点到某一个叶子节点，路径上经过的汉字连接起来，为一个实体；3)每个节点的所有子节点包含的字符串不同.

首先创建前缀树.在生成实体序列前缀树的过程中每个节点要记录汉字出现的频数，以及节点的深度.以具有相同近似度权重(均为1)的实体序列“北京大学食堂”、“北京大学教学楼”、“清华大学图书馆”和“中科院计算所”为例，图3展示了该实体序列对应前缀树建树过程，其中节点右侧标注的数字表示节点出现的频数，图3最左侧标注的数字表示节点的深度.

Fig. 3 Building process of trie tree.图3 前缀树的建树过程

前缀树建立后，合并有最大共同前缀的实体名称并计算对应的近似度权重.求解最大共同前缀方法的步骤如下：1)寻找出现频数最大的节点；2)如果出现频数相同，寻找节点深度最大的节点；3)找到上述节点后，将该节点到根节点路径上经过的汉字连接起来即为最大共同前缀；4)如果所有节点出现频数都为1，当前实体序列没有最大共同前缀；5)如果出现频数最大的节点深度不满足条件，即最大共同前缀不满足最短长度要求或者并不包含于前缀词库中，当前序列没有最大共同前缀.在图3的示例中，“北京大学”即为最大共同前缀.

得到最大共同前缀后，聚合实体名称，其步骤如下：1)合并拥有最大共同前缀的实体名称为最大共同前缀；2)计算1)中被合并实体名称近似度权重之和作为最大共同前缀的近似度权重；3)根据新的近似度权重计算结果重新对候选实体列表排序.在图3的示例中，“北京大学食堂”和“北京大学教学楼”合并为“北京大学”，并计算其近似度权重为2.最终得到的实体序列为“北京大学”、“清华大学图书馆”和“中科院计算所”，相应的近似度权重分别为2，1，1.

在聚合当前近似度权重对应的实体名称后，迭代聚合其他近似度权重对应的实体名称.最后，根据别名词库聚合不同近似度权重间实体名称相同或互为别名的实体名称，并合并其近似度权重.接下来根据近似度权重计算对应实体为当前用户所在实体的概率PWeight(si)为

(4)

算法1. 实体名称聚合算法.

输入:Sall，P，N;

输出:MSall.

① while(Sall≠∅) /*遍历Sall*/

②new_tree=createTrie();

/*初始化前缀树*/

③ while(SWeighti∈Sall且SWeighti≠∅)

/*生成前缀树*/

④ for eachSP∈SWeighti

⑤insertTrie(SP); /*将SP逐字插入前缀树中*/

⑥ end for

⑦ end while

⑧prefix=new_tree.findMaxPrefix();

/*遍历前缀树获得最大共同前缀*/

⑨ ifLen(prefix)≥Lengthorprefix∈P

then /*最大共同前缀长度满足要求*/

⑩ while(SPi∈SWeighti且prefix⊆SPi)

/*求或包含于前缀词库*/

/*计算最大共同前缀的近似度权重*/

删除有最大共同前缀的实体*/

前缀到实体列表集合*/

/*合并两者近似度权重*/

重新对Sall排序*/

实体名称聚合完成后就得到了最终的实体排序结果.

2.3 基于社交关系的多数投票身份识别方法

2.3.1 方法描述

社会网络的发展把人们的社交圈从现实生活中映射到网络世界，可通过社会网络上互为好友或者互为粉丝等社交关系体现.属于同一个社交圈的人拥有更多的共同点，例如居住在较近的地理区域、就读或毕业于相同学校、在相同的工作单位等.本方法基于社会网络用户的社交关系邻居节点的属性信息，利用互粉用户地址信息条目和实体信息条目，通过多数投票的方法推测当前用户的地址信息、学校和工作单位.

多数投票是一种简单有效的方法，它利用分类器对给定的测试样本输出分类类别及各类别的投票结果.设当前用户样本Xu的分类器为C，有m个类别Tji(j=1,2,3,4;i=1,2,…,nj;nj≤m)，分类器C输入一个分类样本Xu，输出一个分类编号ji，即C(Xu)=ji.每个类别Tji对应一个投票计数count(Tji)，其中：

count(Tji)=

(5)

其中，xfeature为当前用户待推测的某个身份特征的集合，可以取为地址信息L或学校E或工作单位W或兴趣I；xk是xfeature对应的条目；Tji是当前用户所有互粉的身份特征对应的条目，当j取不同的值时，分别代表地址信息L或学校E或工作单位W或兴趣I，如j=1代表地址信息L，Tji可以为北京市海淀区、北京市中关村南路80号等.

(6)

其中，Lv是最低有效投票数.最低有效投票数限定了地址信息、学校、工作单位或兴趣的计数结果必须超过的数，如果计数结果小于最低有效投票数，则结果无效.

最后，对j的每一个取值分别计算概率Tji为

(7)

对j的不同取值，按概率结果降序排序，得到当前地址信息地址信息L或学校E或工作单位W或兴趣I的推测结果.

2.3.2 参数选取与结果判断

地址信息的最低有效投票数Lv可以设为1，因为每个用户注册信息都有地址信息，有充足的投票数用来判断结果，判断标准为用户填写的地址信息出现在计算结果Tj的前3个条目中就认为计算结果是准确的.

学校工作单位最低有效票数Lv可通过实验统计获得，实验结果如图4所示：

Fig. 4 The Least effective friends number corresponding to the minimum effective vote count.图4 各最低有效互粉数对应的最低有效票数统计

由图4的统计结果得到，当互粉数量小于25时，设置学校工作单位最低有效投票数为2；当互粉数量大于25时，设置其最低有效投票数为4.

用户兴趣的投票结果通过该用户的博文内容和用户自己填写的兴趣标签(如果该用户在信息中填写了兴趣字段)验证其正确性.如果投票结果和该用户博文内容中出现的高频词存在交集或者符合用户自己填写的兴趣字段，则判定其准确，反之则判定其不准确.

2.4 基于概率的结果融合

(8)

其中，若Lg中的身份特征li在Lr中无对应项，默认其概率为0，反之亦如此.计算方式不变.

为了简化表达方式，我们定义一种新的运算符号⊙表示上述运算，则融合结果为

Lg⊙Lr,Eg⊙Er,Wg⊙Wr,Ig⊙Ir.

(9)

上述规则中，考虑到地理位置方法获取的用户身份特征是近期的、实时的，它的时间属性比较新；而社交关系多数投票方法获取的用户身份特征是用户填写的，可以包含小学、中学等项，有些时间属性可能不是最新的.但2种方法得到的结果都有一定的合理性并可以互补，因此，我们将2个结果根据式(9)计算平均概率，得到融合后的推测结果.

3 实验与效果评估

为了准确评价基于位置的方法和基于社交关系方法的推断准确性，我们用新浪微博开放API收集了新浪微博的用户数据，包括用户信息、用户签到信息、用户博文和用户的社交关系.验证基于位置方法的准确率时，保留用户博文内容带有地理位置信息的数据；验证基于社交关系方法的准确率时，保留拥有互粉关系并且互粉数满足最低有效互粉数的用户数据.

实验收集的新浪微博数据超过1.2亿用户，我们从中随机选择3组样本.其中，组1为注册用户，样本数为1 000；组2、组3为认证用户，样本数分别为1 000和10 000.本文以样本用户的互粉列表为基础，从新浪微博获得其互粉好友共 2 521 925名用户信息及其互粉列表.

3.1 数据集分析

从新浪微博获得的2 521 925名用户中随机抽取40 621名用户用来分析样本数据.如图5所示，纵坐标表示用户数量的对数，横坐标代表统计量.图5(a)展示了互粉数量情况分布；图5(b)展示了互粉好友的地址信息条目数的分布情况；图5(c)展示了互粉好友的学校工作单位条目数的分布情况；图5(d)展示了互粉好友的兴趣条目数的分布情况.图5(a)和图5(b)数据分布吻合，说明所有的用户都有地址信息，地址信息的出现率接近100%；从图5(c)和图5(d)的数据分布可以看出，与图5(a)和图5(b)相比，互粉学校工作单位条目数和互粉兴趣条目数小于互粉数和互粉地址信息条目数，这说明只有部分用户有学校工作单位信息和兴趣字段.注意到图5中4幅图的纵坐标刻度是用以10为底的对数作为单位，说明满足条件的用户数随着互粉数的增加呈指数下降.

Fig. 5 Data distribution charts.图5 数据分布图

3.2 实验与效果评估

在实验中，我们使用了第3节第2段提到的3组样本用户作为实验数据，对实验效果进行验证.我们采用2个被广泛使用的指标来分析实验的有效性：准确率与召回率，考虑到覆盖率更能体现本文“最低有效互粉数”的概念，同时还使用覆盖率作为实验效果的衡量指标.

3.2.1 基于位置的身份识别方法实验结果分析

本方法适用于用户的博文内容中带有地理位置信息，对于用户的互粉关系并没有要求.在1 000名认证样本用户中有地理位置信息的用户有188名，占18.8%.

在实验中，我们用2个指标衡量基于位置方法的准确性，即地址信息推测的准确性和学校工作单位推测的准确性.

在地址信息准确性判断中，如果有至少1条频繁地理位置与用户填写的地址信息吻合，我们就判定其地址信息推测是准确的.

在学校工作单位准确性判断中，我们设定了3条判断标准，如果学校工作单位推测满足下述任何1条，则我们判定其地址信息推测是准确的：1)经过计算排序后的候选实体列表与用户信息相符；2)候选实体列表前3名中有完全匹配且实体名称满足一定长度；3)推测出的频繁地理位置信息精确到门牌号.

基于上述判断标准，我们得到实验结果如表1所示.基于位置的身份识别方法只适用有地理位置信息的用户，我们选取包含地理位置信息的188个用户数据做测试，得到准确率和召回率，并通过覆盖率衡量本方法的适用范围.

Table 1 Experimental Results of Geo-Location Based Identity Recognition Method

从表1中观察到，地址信息推测和学校工作单位推测覆盖率都为18.80%，因为两者的覆盖率都取决于开启GPS服务的用户比例.学校工作单位推测结果中，有114例样本不准确.其中36.84%的样本是因地理位置信息过于稀疏(即虽有地理位置信息，但是地理位置信息条目数不足导致实体位置推测不准确)；39.47%的样本是因缺少博文信息导致实体匹配准确率下降；17.54%的样本地理位置信息过于稀疏，同时还缺少博文信息.因此，本方法在用户有充足地理位置信息和博文信息的时候最为适用.

3.2.2 基于社交关系的身份识别方法实验结果分析

基于社交关系的身份识别方法中互粉数的取值对准确率、召回率和覆盖率有一定影响[17].

本文为充分研究互粉数和实验结果之间的关系，设置学校工作单位最低有效互粉数为0、最低有效投票数为2作为实验的基准情况.实验中，本文用了2组信息已知的微博认证用户数据，样本数分别为1 000名用户和10 000名用户.实验结果如表2所示.注意到表2中实验只是基准情况，对所有用户都适用，并且都能得到推测结果.因此，表2中实验准确率和召回率的值相同，实验覆盖率均为100%.其中，对于样本数为1 000名用户的组别，本文使用人工核实和程序自动判断2种验证方法比较推测结果与已知用户信息是否相符计算准确率.表2结果显示2种验证方法结果的误差不大于3.2%，说明程序自动判断的验证方法可行.

Table 2 Experimental Results of Education and Work Inference Method Based on Social Relationships

从表2中观察到，学校工作单位推测的准确率低于地址信息推测的准确率,这是因为填写学校工作单位信息的用户少于填写地址信息的用户.此外，地址信息推测准确率最低为96.10%，学校工作单位推测准确率最低为80.60%，说明在最低有效互粉数为0、最低有效投票数为2时，本方法已经有了较高的准确率.不准确的情况是因为用户的社交关系不够健壮，即互粉数量不足.

考虑到在实际应用中，对推测准确率会有更高的要求，我们对不同最低有效互粉数作了实验并对结果进行统计(见图6(a)和图6(b)).从统计结果可知：

1) 用户互粉数量越多，推测准确率越高，覆盖率越低；

2) 人工核实和程序自动判断2种验证方法结果基本相符.

Fig. 6 Precision and coverage of address, education and work inference on 1 000 users with two kinds of verification.图6 2种验证方法验证1 000名用户的地址、学校和工作单位推测的准确率和覆盖率

从图6(a)可以看到当最低有效互粉数为0时，地址信息推测准确率超过95%，同时有100%的覆盖率.从图6(b)可以看到当最低有效互粉数为30时，学校工作单位推测准确率超过85%；当最低有效互粉数为70时，学校工作单位推测准确率达到88.37%，但是覆盖率下降到68.80%.结合上述规律，在实际应用时，应根据对准确率和覆盖率的要求选取不同的最低有效互粉数.此外，从图6中可以看到人工核实和程序自动判断2种验证方法得到的准确率结果误差不大于3.2%，证明程序自动判断的验证方法是可行的.在此基础上，本文利用程序自动判断的验证方法计算样本数为10 000名用户的组别的准确率和覆盖率，结果如图7所示:

Fig. 7 Inference precision and coverage on 10 000 users verified by program.图7 程序验证10 000名用户的推测准确率和覆盖率

从图7可以看到，随着最低有效互粉数的增加，程序验证的推测准确率上升、覆盖率下降.其中当最低有效互粉数为0时，地址信息推测准确率超过95%，学校工作单位推测准确率超过80%，覆盖率100%；当最低有效互粉数为30时，学校工作单位推测准确率超过85%，覆盖率87.47%；当最低有效互粉数为90时，学校工作单位准确率超过90%，覆盖率下降到61.32%.

从图8可以看到，用程序自动验证的方法推测不同样本数对应的地址信息推测准确率、学校工作单位推测准确率和覆盖率非常接近，证明对于不同的样本数，实验得到的准确率和覆盖率是一致的、有效的.

Fig. 8 Inference precision and coverage comparison between 1 000 users and 10 000 users verified by program.图8 程序验证1 000名用户和10 000名用户结果对比

在基于社交关系的身份识别方法推测用户兴趣的实验中，本文同时利用认证用户的样本和注册样本.其中，认证样本中，样本数1 000的用户中有兴趣投票结果的用户为952名，根据博文内容和用户信息验证正确的用户为750名；样本数为10 000的用户中有兴趣投票结果的用户为9 613名，验证正确的用户为8 050名.注册样本中，有兴趣投票的用户为889名，验证正确的用户为640名.为充分研究互粉数和实验结果之间的关系，设置最低有效互粉数为0、最低有效投票数为3.当推测结果出现在用户填写的兴趣信息中或者在博文内容中出现3次以上则判定该结果正确.实验结果如表3所示:

Table 3 Experimental Results of Interests Inference Using Method Based on Social Relationships

从表3观察到认证用户中，样本数1 000组推测准确率为78.78%；样本数10 000组推测准确率为83.74%;注册用户样本推测准确率为71.99%，相比认证用户有所降低.考虑到注册用户推测结果人工验证很困难，本文下面主要采用认证用户数据进行实验，并简称为用户.在实际应用中，对推测准确率会有更高的要求，我们对不同最低有效互粉数作了实验并对结果进行统计，如图9所示.从统计结果可知用户互粉数量越多，推测准确率越高，覆盖率越低.

Fig. 9 Precision and coverage of interests inference.图9 用户兴趣推测的准确率和覆盖率

从图9可以看到，随着最低有效互粉数增加，2组样本数据准确率和覆盖率的变化趋势基本相同.1 000名用户推测准确率上涨约20个百分点，10 000名用户推测准确率上涨11个百分点.1 000名用户推测结果中，当最低有效互粉数为20时，推测准确率超过80%，同时仍有90%以上的覆盖率；当最低有效互粉数为70时，推测准确率超过90%，但是覆盖率下降到70%左右.10 000名用户推测结果中，推测准确率在最低有效互粉为0时就达到将近85%，同时有超过95%的覆盖率.这说明本方法具有很好的泛化能力.

为了进一步验证本文方法的效果，我们在上述1 000名用户的样本数据上，将本文兴趣推测方法和TextRank方法[26]、直接博文推测方法进行对比实验.根据相同的验证方法得到的结果如图10所示:

Fig. 10 Precision comparison of different interests inference methods on 1 000 users.图10 1 000名用户兴趣推测准确率对比结果

从图10看到，本方法推测准确率明显高于直接用博文推测的准确率,且本方法的推测准确率高于TextRank方法的推测准确率.

综上实验结果表明，用户的社交关系越健壮，基于社交关系的推测准确率越高.

3.2.3 方法融合效果分析

基于地理位置的方法和基于社交关系的方法有不同的适用范围.基于地理位置的方法要求用户开启GPS服务，因此方法覆盖率较低；而基于社交关系的方法只要求用户有互粉，有较高的覆盖率.因此，我们在基于社交关系的方法推测结果的基础上使用基于地理位置的方法提高相同特征属性的推测准确率和召回率.此外，由于基于地理位置的方法不涉及用户兴趣的推测，故只针对地址信息、学校工作单位信息进行讨论.

(10)

(11)

图11和图12是方法融合前后的实验结果对比，地址信息、学校工作单位推测的准确率和召回率比融合前都有了进一步的提升.

Fig. 11 Improvements of inference precision on address, education and work.图11 地址信息、学校工作单位推测准确率的提升

图11中准确率随着最低有效互粉数的增加而减少，这是因为基于社交关系的方法准确率高，基于地理位置的方法准确率低，随着最低有效互粉数的增加适用基于社交关系方法的用户N1减少，适用基于地理位置方法的用户N2增加，使得融合后的准确率趋向于基于地理位置方法的准确率.注意到图11中最低有效互粉数为10时，准确率达到最高点.

Fig. 12 Improvements of inference recall on address, education and work.图12 地址信息、学校工作单位推测召回率的提升

综上所述，基于位置的方法和基于社交关系的方法融合后，实验结果的准确率和召回率都有提升，同时可以得到具有高准确率及较高召回率和覆盖率的最低有效互粉数.

通过以上实验与分析可知，本文提出的基于位置的方法适用于有充足地理位置信息和博文内容的用户，挖掘其所属学校和工作单位；基于社交关系的身份特征识别方法适用于社交关系强壮、互粉数量多的用户，可以应用到学校、工作单位、兴趣等身份特征属性的推测，且都有较高的准确率和覆盖率，并具有较好的泛化能力.2种方法互补结合，可以更准确识别用户的身份特征.

3.3 案例运行结果

实验结尾，我们用引言中提到的制造“名人被去世”谣言的微博博主“染香”和微博粉丝最多的大V博主“姚晨”为例，运用本文提出的方法推测其用户身份特征.注意到上述两者并没有开启GPS服务，因此只适用于基于社交关系的方法，得到结果如表4、表5所示：

Table 4 Experimental Results of Case “Ranxiang”

Table 5 Experimental Results of Case “Yao Chen”

从表4观察到，“染香”地址推测结果主要为“北京”和“广州”.因为没有“染香”的真实身份官方信息，本文只能根据现有资料对实验结果作推断.其中，“北京”符合网络猜测的“染香”的地址，如图13(a)所示；“广东广州”符合网友推测“染香”身份中的地址，如图13(b)所示.其学校工作单位推测结果中，“清华大学”等学校也符合网络对“染香”真实毕业院校的猜测，如图13(a)所示.其兴趣推测结果中“互联网”、“读书”和“媒体”符合其自媒体人的身份.

在上述案例中，本方法计算出的匿名博主“染香”的用户身份特征与网络猜测相符，实名博主“姚晨”的用户身份特征与其真实身份相符(如图14所示)，说明本方法有较高的准确性和实用性.

Fig. 13 Guesses on Ranxiang’s real identity.图13 网络对“染香”身份的猜测

Fig. 14 Yao Chen’s biography on Sina Weibo and Baidu Baike.图14 新浪微博大V博主“姚晨”资料

4 结束语

本文提出了一种基于位置和社交关系的社会网络用户身份特征识别方法.其中基于位置的方法和基于社交关系的方法通过互补的方式有效推测用户的地址信息、学校、工作单位和兴趣等用户身份特征.与当前社会网络用户信息挖掘方法多着眼于用户群体不同，本文方法针对个体用户挖掘身份特征推测出更细粒度的用户信息，如学校和工作单位，能更有效地定位用户.实验证明本文方法有较高的准确率和覆盖率.

下一步，我们将基于社会网络用户推文及其他身份特征对社会网络用户个体的身份进行挖掘，探索更精准的社会网络用户身份的识别方法.

[1]Ding Zhaoyun, Jia Yan, Zhou Bin. Survey of data mining for microblogs[J]. Journal of Computer Research and Development, 2014, 51(4): 691-706 (in Chinese)

(丁兆云, 贾焰, 周斌. 微博数据挖掘研究综述[J]. 计算机研究与发展, 2014, 51(4): 691-706)

[2]Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C] //Proc of the 20th Int Conf on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208

[3]Ye M, Yin P, Lee W C. Location recommendation for location-based social networks[C] //Proc of the 18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2010: 458-461

[4]Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C] //Proc of the 18th Int Conf on World Wide Web. New York: ACM, 2009: 791-800

[5]Wei L Y, Yeh M Y, Lin G, et al. Discovering point-of-interest signatures based on group features from geo-social networking data[C] //Proc of the 18th Conf on Technologies and Applications of Artificial Intelligence (TAAI). Piscataway, NJ: IEEE, 2013: 182-187

[6]Liu B, Xiong H. Point-of-interest recommendation in location based social networks with topic and location awareness[C] //Proc of the 13th Conf on Data Mining(SDM). Philadelphia, PA: SIAM, 2013: 396-404

[7]Li Min, Wang Xiaocong, Zhang Jun, et al. Study on check-in and related behaviors of location-based social network users[J]. Computer Science, 2013, 40(10): 72-76 (in Chinese)

(李敏, 王晓聪, 张军, 等. 基于位置的社交网络用户签到及相关行为的研究[J]. 计算机科学, 2013, 40(10): 72-76)

[8]Cheng Z, Caverlee J, Lee K, et al. Exploring millions of footprints in location sharing services[C] //Proc of the 5th Int Conf on Weblogs and Social Media (ICWSM). Menlo Park, CA: AAAI, 2011: 81-88

[9]Xu W, Zhou X. Inferring privacy information via social relations[C] //Proc of the 24th IEEE Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2008: 525-530

[10]He J, Chu W W, Liu Z V. Inferring privacy information from social networks[G] //Intelligence and Security Informatics. Berlin: Springer, 2006: 154-165

[11]González M C, Hidalgo C A, Albert-László B. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782

[12]Crandall D J, Lars B, Dan C, et al. Inferring social ties from geographic coincidences[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010, 107(52): 22436-22441

[13]Nathan E, Alex S P, David L. Inferring friendship network structure by using mobile phone data[J]. Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(36): 15274-15288

[14]Wang Yu, Gao Lin. Social circle-based algorithm for friend recommendation in online social networks[J]. Chinese Journal of Computers, 2013, 37(4): 801-808 (in Chinese)

(王玙, 高琳. 基于社交圈的在线社交网络朋友推荐算法[J]. 计算机学报, 2013, 37(4): 801-808)

[15]Guy I, Ronen I, Wilcox E. Do you know? Recommending people to invite into your social network [C] // Proc of the 14th Int Conf on Intelligent User Interfaces. New York: ACM, 2009: 77-86

[16]Yoshida T. Toward finding hidden communities based on user profile[J]. Journal of Intelligent Information Systems, 2013, 40(2): 189-209

[17]Bayati M, Gerritsen M, Gleich D F, et al. Algorithms for large, sparse network alignment problems[C] //Proc of the 9th IEEE Int Conf on Data Mining. Piscataway, NJ : IEEE, 2009: 705-710

[18]Korula N, Lattanzi S. An efficient reconciliation algorithm for social networks[J]. Proceedings of the VLDB Endowment, 2014, 7(5): 377-388

[19]Backstrom L, Sun E, Marlow C. Find me if you can: Improving geographical prediction with social and spatial proximity[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 61-70

[20]MaxMind LLC. GeoIP city accuracy for selected countries[OL]. 2010[2015-03-12]. https://www.maxmind.com/zh/home

[21]Clodoveu A, Diogo R, Rocha O, et al. Inferring the location of Twitter messages based on user relationships[J]. Transactions in GIS, 2011, 15(6): 735-751

[22]Narayanan A, Shmatikov V. De-anonymizing social networks[C] //Proc of the 30th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2009: 173-187

[23]Narayanan A, Shmatikov V. Robust de-anonymization of large sparse datasets[C] // Proc of the 29th Symp on Security and Privacy. Piscataway, NJ: IEEE, 2008: 111-125

[24]Narayanan A, Paskov H, Gong N Z, et al. On the feasibility of internet-scale author identification[C] // Proc of the 23rd Symp on Security and Privacy. Piscataway, NJ: IEEE, 2012: 300-314

[25]Mixpanel Inc. Mixpanel[OL]. 2013[2015-03-12]. https://www.mixpanel.com

[26]Mihalcea R, Tarau P. TextRank: Bringing order into text[C] //Proc of the 42nd Conf on Annual Meeting of the Association for Computational Linguistics. New York: ACM, 2004: 404-411

Hu Kaixian, born in 1989. Received his MSc degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2015. His main research interests include network data and science, big data, etc.

Liang Ying, born in 1962. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Senior member of China Computer Federation. Her main research interests include data mining, big data process, middleware, service computing, etc.

Xu Hongbo, born in 1975. Associate professor in the Institute of Computing Technology, Chinese Academy of Sciences. Member of China Computer Federation. His main research interests include Web search and data mining, text classification, information filtering, etc (hbxu@ict.ac.cn).

Bi Xiaodi, born in 1992. Master candidate. Student member of China Computer Federation. Her main research interests include network data and science, big data, etc (bixiaodi@ict.ac.cn).

Zuo Yao, born in 1991. Received his MS degree in computer software and theory from the Institute of Computing Technology, Chinese Academy of Sciences in 2016. His main research interests include big data and data mining (laike9m@gmail.com).

A Method for Social Network User Identity Feature Recognition

Hu Kaixian1,2, Liang Ying1, Xu Hongbo1, Bi Xiaodi1,2, and Zuo Yao1,2

1(KeyLaboratoryofNetworkDataScienceandTechnology(InstituteofComputingTechnology,ChineseAcademyofSciences),ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

Social network is an important part of modern information society. The anonymity of social network users brings a series of problems concerning social security. This paper presents a method to recognize social network user identity feature by location-based social network (LBSN) and social relationships, and combine the results of those two to infer social network user true identity. The method of geo-location uses approximation weight which is calculated by computing full match weight and basic match weight based on Chinese segmentation and bi-word segmentation to evaluate the possibility that the entity is where the user studies or works, and the method uses entity name aggregation algorithm to optimize the result of approximation weight calculation. According to the observation that friend relationship between users on social network tends to indicate a certain same identity features or a share of common interests, the method of social relationships uses majority voting scheme to count user’s friends identity features to infer user address, entity information and interests. Based on microblog data, we conduct experiments on two samples which cover 1 000 users and 10 000 users respectively and involve a total of more than 2.5 million users relationships. Results shows that our method has a high rate of precision and recall. Compared with the existing methods, our method focuses on individual user identity feature and is valuable in practice.

identity recognition; user identity features; location-based social network (LBSN); social relationships; de-anonymizing

2015-03-19；

2015-12-22

国家重点研发计划项目(2016YFB0800403)；国家“九七三”重点基础研究发展计划基金项目(2014CB340406,2013CB329602);国家“八六三”高技术研究发展计划基金项目(2015AA015803);国家自然科学基金重点项目(61232010);国家自然科学基金面上项目(61173064);国家科技支撑计划基金项目(2015BAK20B03)；山东省自主创新及成果转化专项(2014CGZH1103)

梁英(liangy@ict.ac.cn)

TP391；TP393

This work was supported by the National Key Research and Development Program of China (2016YFB0800403), the National Basic Research Program of China (973 Program) (2014CB340406,2013CB329602), the National High Technology Research and Development Program of China (863 Program) (2015AA015803), the Key Program of the National Natural Science Foundation of China (61232010), the General Program of the National Natural Science Foundation of China (61173064), the National Key Technology R&D Program of China (2015BAK20B03), and the Independent Innovation and Achievement Transformation Project of Shandong Province (2014CGZH1103).