英语原文共 8 页
适用于移动用户的轻量级隐私保护的短信推荐系统
Becchetti L,Bergamini L,Colesanti U M
摘要
本文提出了一种完全分散的方式来推荐手机用户社交网络中的新联系人。关于现有的解决方案, 我们的方法具有一些显著的特点。特别是, 我们提出的申请不需要进行任何集中协调:它透明地收集和处理任何移动电话中可以访问的用户信息, 如通话记录、 联系人列表或短消息的收件箱/发件箱并与其他用户交换。此信息用于向其他用户推荐新的友谊。此外, 执行建议所需的信息是以保护隐私的方式在用户之间收集和交换的。最后, 通过使用用户之间偶尔交换的标准短消息中的剩余空间, 以透明和适时的方式交换实现应用程序所需的信息。因此, 我们不会要求用户改变使用短信的习惯。
1．导言
移动社交网络是一个新兴的趋势。eMarketer 预测到 2012年, 世界移动社交网络用户的数量将从2007年的8200万增长到超过8亿。在大多数移动社区中, 移动用户可以创建自己的个人资料、交友、创建和参与聊天室、举行私人对话、共享照片和视频。社交网络的主要参与者, 如脸谱、 Myspace和 LinkedIn, 已经部署了其应用程序的移动版本。
此外, 移动应用程序可以扩展到支持物理状态检测, 从而最终在虚拟和现实世界之间建立链接和某种融合。例如, Centrl (centrl。 comn。 mobile) 是一个智能手机应用程序, 可以让你看到你的 facebook 好友在身边, Pelago (www。pelago。com) 为 twitter 用户提供了类似的应用程序。
另一方面, 虽然西方国家正在经历高速连接的日益普及和上一代智能手机的普及, 这些手机具有先进的接口来访问移动社交网络, 但许多国家仍然认为短消息是即时消息交换最方便的方式 。在任何情况下, SMS 流量仍然是非语音流量的一致部分。根据Lloyd #39;s的数据，2008年个人对个人的短信流量达到了4。5万亿。这些数字似乎证明了一些公司在基于短消息的社交网络应用中的投资是合理的, 例如jyngle 和peekamo。此外, 在世界大部分地区, 特别是亚洲和非洲, 预计短信将继续是数据通信的主要手段, 至少在不久的将来是如此。2007年, 亚太地区发送了近1。5万亿手机信息。
因此, 移动社交网络的受欢迎程度越来越高, 但同时也给用户和公司带来了明显的好处,一些主要与隐私问题有关的担忧也在出现。在上一次关于社交网络未来的 W3C研讨会上, 就这一问题发表了几份立场文件。例如, 在社交网络中建立 '友谊' 的基本操作, 无论具体应用的术语意味着什么, 都是一个简单的操作 (例如点击鼠标), 但这必然需要信任可能的私人信息交流。事实上, 隐私是移动社区关注的主要问题之一。正如数字民主中心执行主任杰夫·切斯特所说: “事实上，他们为移动广告开发的商业模式是收集大量用户数据，分析用户资料 '和'你谈论的关于多层监控的核心移动营销商模商业模式, 提高了人们对严重的隐私的关注。
论文的贡献。在本文中，我们提出了一种利用手机上的短消息(SMs)和本地信息来设计一个完全分散的应用程序，用于在手机用户的社交网络中推荐新的联系人。推荐新的联系人是几乎每个社交网络应用程序提供的基本服务。关于现有的解决方案, 我们的方法具有一些显著的特点:
我们建议的社交网络应用程序是完全分散的。这意味着社交网络并不像现在的社交网络应用程序那样以集中的方式维护, 而是通过用户设备的集体努力以一种完全分布式的方式更新和管理的。它透明地收集和处理任何移动电话中可访问的用户信息, 如通话记录、 联系人列表或短消息的收件箱/发件箱可能由用户配置信息丰富。此信息用于推荐新联系人。
我们建议的技术大大减少了披露的个人信息的数量, 因为这些信息是以紧凑的摘要形式与其他用户交换的, 允许有限地提取私人数据。此外, 我们还提供了一个简单而实用的加密协议, 可用于确保在不泄露任何其他私人信息的情况下进行推荐系统所需的计算。
通过使用用户偶尔交换的标准短消息中的剩余空间, 可以透明和及时地交换实现应用程序所需的信息。因此, 我们不会要求用户改变使用短信的习惯。
过去的研究还考虑了分散系统的项目推荐, 例如在中作者提出了基于 P2P 的置位架构。我们知道这是我们的工作, 但使用过去用户交易的统计信息推荐项目并不是我们工作的重点, 我们工作的重点是相关但很突出的 '社会匹配' 问题, 我们要在这个问题中推断潜在的问题社交网络的结构。
论文的组织.本文的其余部分按如下方式进行了组织: 在第2节中, 我们描述了我们遵循的方法。特别是, 在分析 (移动) 电话网络中用户的行为时, 我们讨论了一些自然产生的社交网络 。然后, 我们讨论了在这种网络中建议新联系人的问题, 首先讨论了用户之间相似的概念。在第3部分中, 我们回顾并讨论了复杂的哈希技术的应用, 这些技术允许以完全分散和隐私保护的方式估计用户之间的相似度。在第4节中, 我们讨论了评估我们的方法在真实的、可公开的数据集上的有效性的实验工作, 在第5节中, 我们快速介绍了我们的重新设计系统的工作原型 。
2. 通过短信发送的社交网络
在这项工作中, 手机用户社交网络中的一个节点是手机用户产生一定数量的用户对用户的通信。连接两个节点的链接表示相应用户之间正在进行的社会关系 (例如, 节点是朋友、同事、同学等)。在我们的方法中, 这种社会关系只能推断用户的社会概况相似性。一般来说, 当两个用户的社会形象相似时, 他们是相似的。事实上, 用户的配置文件是一个一般的概念, 取决于系统可用的信息。在某些情况下,这包括一些生物数据 , 如出生日期、性别、关于口味、兴趣或活动的信息。配置文件还通过可以透明地从系统中提取信息来完成, 而无需明确的用户干预, 如通话记录、 联系人列表或联系人列表或短消息的收件箱/发件箱。
我们强调, 在许多情况下, 即使是有限的信息, 例如通讯簿或通话记录, 也可以用来推断可能的关系: 例如, 出现在对方通讯簿中的两个用户可能与社会有关系, 无论是通过共同的兴趣, 职业关系, 或仅仅因为他们是朋友。
挖掘网络的基础电话通信在过去被考虑了, 例如在 [8, 7]。在这里, 如果 A 在某个时候调用 B, 就有一个从 A 到 B 的链接 (可能有标签)。[8, 7] 的主要目标是研究这种网络随着时间的推移而演变的方式, 以便推断和分析描述其演化的概率生成模型。
2.1推荐社会关系
推荐新的社会关系是社交网络应用提供的最基本的服务之一。在我们的环境中, 我们对向用户推荐潜在感兴趣的新联系人的策略感兴趣。这里的挑战显然是找到可能具有一些共同特征的联系人, 或者换一种说法, 在某种程度上与向其提供建议的用户 '相似'。如上所述, 这个问题非常接近liben-Nowell 和 kleinberg 研究的链接预测问题, 他们的重点是社会亲密的统计指标, 而不是他们的有效和分散的计算。
更正式地说, 如果节点a 将节点 b 推荐到第三个节点c, 则 a 建议 c 在与 b 建立联系时具有潜在的兴趣或效用(除非此联系方已经存在)。建议是根据对 l (b) 和l(c) 的社会概况的了解执行的, 这些概况用于估计b。c 是 '相似的'。第2.2 小节中更精确的基本假设是, b 和c越相似, 它们就越有可能有联系, 或者他们可能从建立联系中受益。
隐私要求使得对应用程序显式交换私有概要信息或用户联系人列表变得不现实。此外, 数据必须适合人与人之间短消息的剩余空间, 因此必须以紧凑的形式 (即草图) 表示。图1概述了我们考虑的一般应用程序方案。在步骤1中, 用户 a 和 b 计算其各自社会概况的草图 sk(L(A)) 和sk(L(B))。正如之前所观察到的, 这是用户的社会概况的紧凑表示, 保护她的隐私。在步骤2和3中, A 和 B 偶尔会向 C 发送短消息。消息空间部分充满了一些个人文本 (例如 SM 文本 = '我们今晚将见面吗？'), 而剩余空间被用来传递草图。观察用户与 SMS 的交互情况, 而剩余空间则由合适的应用程序透明地管理。在步骤4中, 用户 C
(即推荐人) 根据 A和 B 各自的草图推断 A和 B 之间的高度相似性。在步骤5和6中, C 最终向用户推荐了一种可能的友谊 A 和 B。
图 1: 一个场景
2.2局部推断群落结构
社交网络推荐系统的主要问题之一是预测用户之间新联系的潜在好处。在我们在这里考虑的完全分散的场景中, 这相当于回答了以下问题: 用户 A 何时应该推荐她知道的其他两个用户B和 C 之间的联系人。这反过来又意味着其他一些问题: (一) A结合了B和C的哪些信息来决定如果B和C之间没有联系，她是否应该建议联系;(二) 如何获得、操纵和交换这些信息; (三) 如何满足计算、储存和通信限制;(四) 如何保护隐私.
与许多网络应用程序一样, 我们建议在用户相似的基础上建立新的联系人。因此, 如果 A 评估 B 和 C '相似', A 将建议 B 和 C 建立联系。特别是, 如果我们将配置文件视为功能集, 我们说两个用户A 和B在其社交配置文件L(A) 和L(B)时相似) 明显重叠。在这个角度下, 我们用 Jacard 系数来估计用户的相似性, 这是一种广泛接受的集合间相似度的度量方法。在我们考虑的社交网络场景中, 它抓住了一个众所周知的事实 [17, 15], 即社交网络在地方一级是紧密相连的, 或者大致说, 同一个人的两个朋友明显比任意两个随机选择的人更有可能成为朋友。
3. 有效挖掘短信用户的社交网络
我们考虑的应用程序的一个关键方面是以完全分散的方式估计两个用户的社会配置文件之间的交集大小。更准确地说, 如果用户 C 收到来自 A和B的短消息, 她应该能够从有关LA) 和L(b) 在消息本身中搭载。显然, 短消息大小对可搭载的信息量构成严格的限制。这最多是140个字节, 但回顾我们只使用消息上的剩余空间, 这些字节的可变数将被消息正文本身占用。下面我们将演示如何通过以下方式解决这些问题: i) 我们将最初为 web 页相似度估计而设计的技术调整为我们考虑的方案。采用这种技术可以计算每个社会概况的紧凑摘要或草图, 进而能够有效地估计社会概况之间的贾卡德系数。拟议草图所需的空间约为十分字节;ii) 在此假设下，我们解决了可变短信大小的问题[20], 即 SMS 大小是 (近似) 均匀分布。具体来说, 对于在人与人之间通信中创建的消息, 长度似乎均匀地覆盖了允许的消息大小 [20] 的整个范围, 其最大值取决于用于每条消息的编码, 但通常为140字节。在下面, 我们将参考基于用户联系人列表的配置文件, 因为几乎所有最近的商用设备都可以在本地获得联系信息。因此, 术语 '社交配置文件' 和'联系人列表' 将互换使用。我们强调, 其余部分中描述的技术可以扩展到更一般的用户配置文件概念, 如第2节所述.
3.1雅高系数的估计.
考虑一组可能的联系人标识符。回想一下, 如本节所述, 它们可以被视为落在 [n] = {0,..., n-1}范围内的整数适用于 n 。我们唯一需要的假设是, 它们是独特的, 这是我们考虑的应用程序中实际满足的制约因素; 它们是用户的电话号码或用户的电话号码的适当表示。因此, 如果考虑到任何两个用户 A 和B, 其联系人名单L(A) 和L(B) 可被简单地视为 [n] 的两个子集。我们的目标是使用 Jacard 系数测量它们的重叠: Broder 等人以几种等效形式提出了一种非常简单和优雅的估计雅卡德系数的技术。假设我们能够随机选择一个排列的pi;(·) 均匀映射 [n] 到本身。对于每一个 X sube;[n], 表示由(x) 的元素的图像集在x 时, (·) 被应用, 并让最小 ((X)) 表示其最小值。然后可以显示 [10] (i) 考虑了集合s sube; [n] 和为每个aisin; S, P[a = argmin(pi;(S))] = 1/|S|; (ii) 对于每一个 S1, S2 sube; [n]: P[min(pi;(S1)) = min(pi;(S2))] = J(S1,S2).。此属性立即产生一种估计J(S1,S2)的技术 。
该算法由以下过程的m个独立执行组成: i)均匀地从n! 可能的随机选择一个排列(·], ii)在第i个迭代中，让min(S1) = min(pi;(S1)) and min(S2) = min(pi;(S2)).。我们在min(S1) = min(S2).时增加计数器Cm。在这个过程的最后, 我们对J(S1,S2)的估计是Cm/m.概率论中的标准工具告诉我们, Cm是对J(S1,S2). 越来越 (用m) 精确估计的方法)。
3.2 计算和维护联系人名单草图.
不幸的是, 随机均匀地生成排列需要大量真正的随机位, 这些位的顺序是n。幸运的是, 简单的线性哈希函数的合适族在实践中表现良好 (例如, 请参见 [14, 9])。
UPDATE(sk(A), pn)
Require: Sketch sk(A), number pn
1: x = hash(pn) {Hash pn to an integer in [n]}
2: for i: 1 ...m do
3: Mi = hi(x) {Map x according to a random permutation} 4: if Mi lt; mini(A) then
5: mini(A)
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
