跨社区的用户链指技术综述

刘璟　刘挺

摘要：随着各种在线社区呈现出爆炸性的发展，网络中已经积累了大量的用户信息，这些用户信息已经成为了社会计算相关研究和应用的宝贵的数据资源。由于各种社区在功能和主题上的不同，用户的信息碎片化地散布在不同的社区中，这为获取用户完整信息以及跨社区的研究等都带来了挑战。用户链指技术是解决用户信息跨社区问题的关键。本文分析和总结了近些年用户链指技术相关的研究与工作，剖析了各个工作的优势和局限，并对其它领域的相关研究进一步作了综合的分类与比较。

关键词：跨社区； 用户链指； 用户信息

中图分类号：TP391 文献标识码：A文章编号：2095-2163（2014）04-0039-04

Abstract：With the development of various online communities， there is a huge amount of user information cumulated on the web. The user information is the basis for the research and applications of social science. Since different communities are various in terms of functions and topics， all different aspects of user information are distributed in different communities， which makes it challenging to acquire the complete user information and conduct cross-community research. The technologies of user linking are the keys to address the cross-community problem of user information. This paper introduces the state-of-the-art user linking technologies， analyzes the advantages and limitations of each method， and conducts categorization and comparison of the related work in other research areas.

Key words：Cross-community； User Linking； User Information

0引言

近些年，互联网服务正日益呈现社交化的态势，各种在线社区例如论坛社区、问答社区、博客社区、微博社区等也相继涌现。数量庞大的用户群体每天都会进入这些在线社区中发表微博和日志，提出和回答问题，分享心得体会，或者做出留言点评等等。为此，这些社区已积累了大量的用户信息数据，为社会计算的相关研究提供了生动丰富的基础海量数据。例如，Zhang等[1]和Liu等[2]分别研究了论坛和问答社区中的用户专业水平估计问题。Gruhl等[3]则研究了微博社区和博客社区中用户的影响力估计问题。Leskovec等[4]还研究了社区结构的动态变化的问题。但是这些研究工作却仅仅关注了面向单个社区的社区结构分析和用户计算，具体原因即在于不同社区的用户之间往往没有显式的链接，因而使得一个社区的用户图与其它社区的用户图之间并不连通。同时，尽管每个用户在不同的社区拥有不同的用户信息，并且这些用户信息在不同社区之间依然是非共享的，这也在无形中又导致了不同社区之间的用户图是相互分割、以及互不连通。

可以观察到，由于各类在线社区在主题以及功能上的不同，用户的各种信息都碎片化地散布在各个社区中。如图 1所示，一个用户在Facebook社区中的信息包含着其详细的基本资料，包括性别、年龄、家庭住址以及朋友关系等；而该用户在图片社区Flickr中的信息则包含着有关的旅游经历；同时，该用户在购物社区中的信息即包含了相应的购买记录；另外，该用户在论坛社区中还分享着个人的兴趣爱好；以及该用户在问答社区将会求助其在家庭生活中遇到的各类问题。为保护用户隐私，本文已对该例中的用户进行了匿名化处理。

Zafarani等[5]第一次提出了用户链指这个问题：即将一个自然人在不同社区的用户身份链接起来。用户链指技术具有非常广泛的应用。首要地，用户链指技术有助于理解不同社区之间用户的迁移模式[6]，例如可以观察到MySpace的哪些用户是迁移到了Facebook的，进而帮助社区的运营人员有针对性地调整日常策略，以保持或增加社区的流量。同时，用户链指技术还可以将一个自然人在不同社区的信息都聚合起来，形成更丰富的个人信息，从而解决推荐系统和个性化系统中的冷启动问题[7-8]。通常情况下，如果将一个自然人在不同社区的用户信息聚合起来，可能会暴露用户的隐私。用户链指技术可通过聚合用户信息，并进行自动监测，为用户提供一定的隐私暴露提醒服务[9]。此外，用户链指技术也可以帮助建立跨社区的专家推荐系统，以及在跨多个社区的用户图上进行用户影响力分析。综上，用户信息碎片化地散布在各个不同的社区，跨社区的用户信息为社会计算相关研究的开展带来了很大的挑战。因此，跨社区的用户链指研究即显得尤为必要，并具有高度的科技实用价值。

1主要工作介绍和分析

近几年，用户链指问题已经引起了众多研究人员的兴趣与关注。Zafarani等[5]第一次正式提出了用户链指问题，即将一个自然人在不同社区的用户身份链接起来。按照模型方法，用户链指的相关工作可以分为基于数据抽取的、无指导的和有指导的学习三类。本节将从这三个方面，依次介绍相关工作，并具体分析其各自优势和相应局限。第4期刘璟，等：跨社区的用户链指技术综述智能计算机与应用第4卷

1.1基于数据抽取的用户链指方法

Yuan等[10]发现某些社区的用户可能会在自己的个人用户页面（User Profile Page）中显式地标出自己在其他社区的个人用户页面的链接。例如，某个新浪微博用户即在该用户的微博个人页面中给出了自己在豆瓣中的个人页面的链接。Yuan等[10]则利用用户的这种行为，通过人工撰写模板的方式抽取数据，链指了来自4个社区的100万左右的用户，并进一步在具有用户链指信息的数据集合上研究了不同群组用户的不同行为。Yuan 等[10]的用户链指方法主要依赖于用户给出的标示信息，却未能进行更深入的统计学习，因此还无法推广到更多的社区中。

类似地，Zafarani等[5]也发现了有些用户会在自己的个人页面中显式标出自己在其他社区的个人页面的链接，并基于这个观察提出了一个基于网页搜索的启发式解决方法。该方法主要基于两个假设：

（1）一个自然人在社区A的个人页面所对应的网页链接中包含了其在社区A的用户名；

（2）该自然人在社区B的用户个人页面中标示出了该自然人在社区A的用户名。

然而，在Liu等[11]的数据集上，实验结果已经表明，75.47%的社区并不同时符合以上两个假设。

1.2无指导的用户链指方法

Vosecky等[12]提出通过收集用户在社交网络中用户个人页面的信息，将用户在每个社区的个人信息表示成一个向量。向量中每一维都是一个用户个人信息域，例如用户名、个人描述、头像和地点等。当用户个人信息向量生成后，无指导的和有指导的方法均可行之有效地进行用户链指。Vosecky等[12]使用无指导的方法计算每两个用户之间的用户个人信息向量的相似度，若相似度大于某个预先设定的阈值，则这两个用户将视作属于同一个自然人。其缺点是预先设定的相似度阈值的选取难度将会很大。

以上方法没有对社区的类型加以限制。Iofciu等[13]研究了社会化标签系统中的用户链指问题，提出了一个将用户名编辑距离和用户标签分布相似度进行线性组合的方法。其基本假设为：

（1）一个自然人在不同社区所使用的用户名是相同或者相近的，因此可使用编辑距离用于度量两个用户名的相似性；

（2）一个自然人在两个社会化标签系统中给出的标签分布也应该是接近的，因此还可使用标签分布相似度进行度量。

这个方法的局限在于会依赖特定的网站信息，例如标签。同样地，该方法还需要预先设定的阈值才能进行判断。而阈值的人工选取是非常困难的，相应地不同的社区所需要的阈值也可能是不相同的。

1.3基于有指导学习的用户链指方法

Malhotra等[8]和Nunes等[14]首先借助用户个人页面的信息，构建用户信息向量。这与Vosecky等[12]提出的构造用户信息向量的思想类似，但与其相区别之处却在于，Malhotra等[8]和Nunes等[14]提出了使用标注数据学习分类器。这些研究所获得的实验结果均已表明，基于有指导学习的方法可以达到较高的准确率。然而，Narayanan等[15]又明确指出不同类型社区的用户个人信息类型也是互不相同的。而且由于人工为每类在线社区都标注训练数据很难实现，就使得以上有指导的方法也将很难扩展到各种不同的在线社区中。

为了解决这一问题，Liu等[11] 提出了一种无指导的方法自动生成训练数据，这就使得该方法可以很容易地扩展到任何类型的在线社区。具体地，Liu等[11] 将用户链指任务分为两步：同名消歧（Alias-disambiguation）和不同名消解（Alias-conflation）。第一步，同名消歧是指，对于一个来自不同社区的使用相同用户名的用户集合，需要判定该用户集合中的用户是否都属于同一个自然人。换句话说，就是要对使用相同用户名的用户实现明确区分。第二步，不同名消解是指，收集一个自然人所使用的所有不同的用户名。Liu等[11]只是关注于解决第一步同名消歧问题。文章中首先通过用户问卷调查和基于About.me数据集的分析，量化地说明了解决同名消歧任务的重要性。其中，用户问卷调查结果表明89.17%的人有一个主要使用的用户名；而基于About.me的数据分析结果则表明，平均每个人使用了2.44个用户名，解决同名消歧即可将46.8%的用户对链接起来。人们倾向于将一个用户名作为主要使用的用户名的原因主要包括：

（1）这样将有助于用户减轻记忆上的负担，因为如果每个社区都使用不同的用户名，记忆起来将会非常地困难；

（2）同时，使用一个主要的用户名，可以帮助用户维护在线的声誉，因为其他人能够通过用户名很轻松地对该人做出判别。

Zafarani等[16]也有与其接近的发现。Liu等[11] 提出的无指导的自动生成训练数据的方法，主要基于以下假设：由非常独特的字符串构成的用户名通常都只为一个自然人所使用，例如：bennystar99 和travelbug61。Liu等[11]又提出使用概率语言模型来度量用户名的独特性。进而，Liu等[11]将同名消歧问题看做了一个成对分类问题（pairwise classification），因此来自两个社区、使用相同用户名的两个用户将作为一个实例。基于以上假设，如果一个实例对应的用户名语言模型概率偏低，该实例则可以视作训练数据中的正例；反之，一个实例对应的用户名语言模型概率较高，该实例即可视作训练数据中的反例。Liu等[11]还利用Yahoo！ Answers的数据集验证了该假设。实验结果表明，在自动标注的训练集上学习得到的分类器是实用有效的。Liu等[11]提出的方法虽然较好地解决了同名消歧，但却没能解决不同名消解的问题。

Malhotra等[8]、Vosecky等[12]和Nunes等[14]等方法的一个主要局限是依赖于用户个人信息页面的公开性。然而很多社区的用户个人信息页面都是非公开可访问的。而Liu等[11]提出的方法仅需借助用户生成内容页面（User-Generated Content）的信息，而这在大部分社区却都是公开可访问的。

2其它领域相关工作介绍和比较

2.1实体消解

用户链指和其他研究领域的一些问题均彼此相关。而与其相关的这些问题中的一类重要研究即是实体消解，具体可分为：

（1）自然语言处理领域中的指代消解任务[17-18]（coreference resolution）。该任务是指将文本文档中代表同一个实体的多个表述（mention）识别出来；

（2）数据库领域中的数据记录链指任务[19-20]（data record linkage）。该任务是指将来自不同数据库的、描述同一个对象的两条数据记录识别出来，例如将两个产品数据库中共同描述iPhone5s的数据记录识别出来；

（3）信息检索领域中搜索结果页面的人名消歧任务[21-22]（people name disambiguation）。该任务是指对于人名的搜索结果网页，按照每个网页所描述的自然人进行聚类。以上问题均统称为实体消解[20]（entity resolution）。

目前，面向这些任务的性能最优系统主要采用了两类有指导的方法：

（1）成对分类[17，23]；

（2）有指导或半指导的聚类[18，20，22]。在本文所关注的跨社区的用户链指的任务上，基于聚类的方法并不适用。因为一个自然人通常只参与了少量的社区，例如2-3个，其所对应图中的簇（cluster）也就只是包含了2-3个节点，此时聚类的方法在这种图中并不适用。因此用户链指的相关工作即都选择了基于成对分类的方法[8，11，14，16]。

2.2社交网络中的反匿名化

近些年，随着社交网络的发展，越来越多的企业将其数据库匿名化后提供给学术界与其共享，并展开相关的学术研究。但是涉及数据安全和隐私方向的研究人员却发现一个匿名数据库的用户极有可能与一个公开数据库中的用户被链指起来，这样用户的个人隐私信息的安全防护就会降低[15]。研究人员将这一问题称作社交网络中的反匿名化。迄今为止，这一方向的研究成果主要可以分为两类：

（1）统计意义上的稀有属性值可以帮助在高维稀疏数据集上反匿名化[24-25]，例如一个冷门电影的观看记录很有可能将两个数据库中的用户链指起来，因为一个冷门电影只可能获得少数人的关注和观看；

（2）Labitzkeg 等[26]和Narayanan 等[27]均发现仅利用社交网络的结构信息即可以成功地破解匿名网络，原因在于一个自然人在两个在线社区的朋友集合也是相似的。由此可知，社交网络的结构信息也可以有助于进行用户链指。Liu等[11]利用的也是社交网络的结构信息进行用户链指。

2.3作者识别

作者识别（Authorship Attribution）是统计自然语言处理领域的一个基础课题。该课题是指通过分析文章的内容，识别作者的写作风格，从而判断一篇文章的作者。作者识别任务的一些研究成果同样可以帮助用户链指的获取。Novak等[28]提出了使用语言模型识别论坛帖子的作者。Sanderson等[29]又研究发现文本的语言模型也可以助力作者识别任务的完成。同时，Gamon等[30]则发现词性的语言模型也是作者识别任务的有效特征。而且，Graham 等[31]又相继提出标点符号的使用习惯也可以有助于作者辨别。基于此，Rao等[32]又进一步发现一些功能词汇（例如，of、for、the 等）的使用习惯是作者识别的另外一个重要特征。作者识别任务的这些重要特征也将同样有助于跨社区的用户链指。Liu等[11]即通过分析用户的文本内容，相应抽取了文本语言模型、词性语言模型、标点符号使用频率分布、功能词汇使用频率分布等作为特征而获得了具有较高性能的研究成果。

3结束语

用户链指技术是聚合跨社区的用户信息的基础。然而，用户链指技术是一个极具挑战的研究问题，因为不同社区的用户信息类型是多样化和异构化的，这就为无指导和有指导的方法都带来了一定的挑战。本文介绍和分析了当前主流的用户链指技术，比较了每种方法各自的优势和局限，并对其它领域的相关研究更深入地开展了综合性的分类与比较。可以看到，结合用户行为数据（例如用户名等）和有指导学习的方法是用户链指技术发展的重要方向。同时，基于用户链指信息的应用研究也存在着很大的机遇。

参考文献：

[1]ZHANG J， ACKERMAN M S， ADAMIC L. Expertise networks in online communities： structure and algorithms[C]//WWW， 2007.

[2]LIU J， SONG Y I， LIN C Y. Competition-based user expertise score estimation[C]// SIGIR， 2011.

[3]GRUHL D， GUHA R， LIBEN-NOWELL D. Information diffusion through Blogspace[C]//WWW， 2004.

[4]LESKOVEC J， KLEINBERG J， FALOUTSOS C. Graphs over time： densification laws， shrinking diameters and possible explanations[C]// KDD， 2005.

[5]ZAFARANI R， LIU H. Connecting corresponding identities across communities[C]// ICWSM， 2009.

[6]KUMAR S， ZAFARANI R， LIU H. Understanding user migration patterns in social media[C]//AAAI， 2011.

[7]ABEL F， HENZE N， HERDER E. Interweaving public user profiles on the Web[C]//UMAP， 2010.

[8]MALHOTRA A， TOTTI L， MEIRA W. Studying user footprints in different online social networks[C]//ASONAM， 2012.

[9]LIU K， TERZI E. A framework for computing the privacy scores of users in online social networks[C]// TKDD， 2010.

[10]YUAN NJ， ZHANG F， LIAN D. We know how you live： exploring the spectrum of urban lifestyles[C]// COSN， 2013.

[11]LIU Jing， ZHANG Fan， SONG Xinying， et al. Whats in a name？ an unsupervised approach to link users across communities[C]//WSDM， 2013.

[12]VOSECKY J， HONG D， SHEN V. User identification across multiple social networks[C]//NDT， 2009.

[13]IOFCIU T， FANKHAUSER P， ABEL F. Identifying users across social tagging systems[C]// ICWSM， 2011.

[14]NUNES A， CALADO P， MARTINS B. Resolving user identities over social networks through supervised learning and rich similarity features[C]//SAC， 2012.

[15]NARAYANAN A， SHMATIKOV V. Myths and fallacies of personally identifiable information[C]// CACM， 2010.

[16]ZAFARANI， REZA， LIU Huan. Connecting users across social media sites： a behavioral-modeling approach[C]//KDD， 2013.

[17]SOON W M， NG H T， LIM D C Y. A machine learning approach to coreference resolution of noun phrases[C]//CL， 2001.

[18]CAI J， STRUBE M. End-to-end coreference resolution via hypergraph partitioning[C]//COLING， 2010.

[19]ELMAGARMID A K， IPEIROTIS P G， VERYKIOS V S. Duplicate record detection： a survey[C]// TKDE， 2007.

[20]BHATTACHARYA I， GETOOR L. Collective entity resolution in relational data[C]//TKDD， 2007.

[21]KALASHNIKOV D V， CHEN Z， MEHROTRA S. Web People search via connection analysis[C]// TKDE， 2008.

[22]MANN G S， YAROWSKY D. Unsupervised personal name disambiguation[C]//CONLL， 2003.

[23]BENGTSON E， ROTH D. Understanding the value of features for coreference resolution[C]//EMNLP， 2008.

[24]FRANKOWSKI D， COSLEY D， SEN S. You are what you say： privacy risks of public mentions[C]// SIGIR， 2006.

[25]NARAYANAN A， SHMATIKOV V. Robust de-anonymization of large sparse datasets[C]//S&P， 2008.

[26]LABITZKE S， TARANU I， HARTENSTEIN H. What your friends tell others about you： low cost linkability of social network profiles[C]//SNA-KDD， 2011.

[27]NARAYANAN A， SHMATIKOV V. De-anonymizing social networks[C]//S&P， 2009.

[28]NOVAK J， RAGHAVAN P， TOMKINS A. Anti-aliasing on the Web[C]//WWW， 2004.

[29]SANDERSON C， GUENTER S. Short text authorship attribution via sequence kernels， Markov chains and author unmasking： an investigation[C]//EMNLP， 2006.

[30]GAMON M. Linguistic correlates of style： authorship classification with deep linguistic analysis features[C]//COLING， 2004.

[31]GRAHAM N， HIRST G， MARTHI B. Segmenting documents by stylistic character[C]//NLE， 2005.

[32]RAO J R， ROHATGI P. Can pseudonymity really guarantee privacy？ [C]//USENIX， 2000.

[33]YOSHIDA M， IKEDA M， ONO S. Person name disambiguation by Bootstrapping[C]//SIGIR， 2010.