英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
移动社交网中群体相似度和潜在朋友关系数据挖掘
Ke Xu a,b, Keju Zou c, Yan Huang a, Xiaoyang Yu a, Xinfang Zhang a,n
a School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China
b College of Computer Science, South-Central University for Nationalities, Wuhan, China
c School of Engineering, Sun Yat-Sen University, Guangzhou, China
摘要：随着移动终端和无线技术的迅速发展,移动社交网络服务非常受人们欢迎。最近,许多基于位置服务开发的移动社交平台允许用户与朋友分享他们的签到和朋友的状态。基于地理位置的移动社交网络的签到数据以及移动通信网络中的呼叫详细记录(CDR)可以洞察社会结构、人际关系和网络中的成员。在本文中,我们研究预测在移动社交网络中检测群体和预测朋友关系的问题。我们提出了一种基于联合熵的群体结构发掘方法,并评估虚拟校园移动网络(V-Net)的模块。结果表明,该算法根据用户注册信息能够挖掘出很有意义的群体信息。通过用户与朋友之间的链接信息以及Gowalla的不同签到位置信息研究分析出用户之间潜在友谊关系。这项工作描述友谊分布的概率，朋友的数量,签到的数量和访问地点的数量。研究结果证实了，我们的方法相比其他方法，在实现用户特性聚合相似度和位置熵，取得了较好的结果。此外,用户揭示了在两个网络中不同社交属性,在V-Net影响用户倾向于保持共同群体,而在Gowalla全体成员可能会访问共同地点。
1.简介
越来越多的丰富的传感器和通信设备带来了感知环境中的创新方法和机会。如今的智能手机不仅作为重要的通信和计算移动终端的选择，它也配备摄像头，麦克风，加速度计陀螺仪丰富，范围、数字罗盘和GPS等嵌入式传感器。一般来说，这些传感器在各种领域促进新的应用，如社交服务[1,2]，运输[3,4]，用户便携性[5,6]，旅游线路[7,8]，商业选址[9,10]。最受欢迎的应用是在移动社交网络中基于位置的服务平台。
基于位置的社交网络（LBSNs）变得越来越流行，引起一部分人的极大兴趣，这些人每天都在彼此的网络空间发表自己的看法，聊天，写博客，写评论，发布和关注图片和视频，准备活动，以及更新他们的现状。随着智能手机和GPS设备等移动设备，基于位置的服务社交网络平台，如Facebook Place，Foursquare，Gowalla，和Brightkite，受到越来越多的青少年欢迎。例如，在一月，2014，Foursquare声称全球有超过4500万人，超过五十亿次的签到并且每天都有百万以上的增加。一个基于位置的社交网络平台的用户可以选择他们的好友列表，并将其列为其他用户以及传统社交网络的好友列表[ 11–13 ]。他们可以通过社交网络来签到和分享他们的位置和事件给他们的朋友。此外，用户可以通过他们的移动电话提醒他们的朋友看到他们参观某地的签到（例如，博物馆，旅馆和购物中心）[14-16]。用户被鼓励在某地点签到，是为了获得徽章，更高等级和特别优惠。
在社交网络领域，群体探测和朋友关系预测是一个重要的话题，提供特殊的方法，使研究可以惠及科学以及商业等不同领域。群体结构是一个重要的属性，它可以使一个给定的网络显露一些未知的特性。属于同一群体或群体的成员有可能有共同的兴趣或类似的性质。社交网络可以代表不同的人际关系，包括友谊、亲属关系和参与者之间的关系。zheleva调查潜在现实世界中的[ 17 ]三个有趣的社会网络中的友谊和家庭关系的预测能力。用户可以在基于位置的社交网络LBSNS上发布和展示他们与其他用户的户外活动，比如旅游和庆祝，他们可以方便地管理他们的足迹并与朋友分享。参考文献[ 18 ]研究了朋友关系和用户的属性相关性，这些用户属性包括他们的流动性特点，社会网的性质，和用户在一个商业的基于位置的社交网络LBSNs的特性。一个潜在的个体间的朋友关系可以通过他们的在移动社交网络共同的朋友，兴趣和访问的地点预测。社会结构往往是高度动态的对象，因为它们通过增加新的节点或边的时间而迅速发展和变化，因此，友谊链接预测问题变得更具挑战性。
在本文中，我们提出了一个在移动社交网络中的用户的手机产生的不同的数据集中进行群体探测和挖掘潜在友谊的研究方法。手机通信数据集是一个虚拟的校园移动网络（V-Net）由中国的主要移动通信服务有限公司提供的。V-Net用户是来自一个学院或大学的学生或教师，他们可以彼此更方便、便宜地通过拨打虚拟短号进行对话。我们提取在3个月内的个人呼叫详细记录（CDR）和他们的注册信息。第二数据集是一个在线的基于位置的社交网络，即Gowalla，是一个于2007推出于2012关闭的基于位置服务平台。用户可以通过在移动设备上的一个特殊应用程序在他们所在地点附近的街道签到。
我们的主要成果可以概括如下：
（1）我们提出了一种寻找群体和评估虚拟校园移动网络的模块化的算法（V-Net）。我们发现，群体结构被重要节点，边密度和内部深度（见3节）影响。在网络中的群体的数量组合熵阈值多样化（见5节）。
（2）我们不仅通过分析用户朋友的朋友，也同时访问的用户朋友在Gowalla的位置来研究潜在的朋友联系（见4节）。我们描述的每个友谊关系中朋友的数量,签到的数量和访问地点的数量的分布的概率遵循对数正态分布（见第5节）。
（3）我们将地方属性和用户的相似性考虑进友谊预测的研究（见第4节）。当地点熵值增加时，一对访问共同地点的人是朋友的概率会下降，根据曲线的发展趋势，友谊概率和用户相似性存在强关联性（见5节）。
我们的研究发现，用户在两个移动社交网络中显示不同的社会活动，例如，在一些V-Net的关键用户倾向于促进友谊产生从而产生群体，但是，在Gowalla社区成员更倾向访问的共同地点和并在这些地点附近产生友谊（见5节）。
2.相关工作
社交网络，如Facebook、Foursquare和陌陌，新浪微博，激起了数百万用户的兴趣，像这样的社交平台比过去的一年增长超过四分之三。最近的统计报告显示，目前的应用程序中社交网络服已超越搜索引擎。eMarketer [ 19 ]宣称，预计在2014年的时候全球有45.5亿人用手机，从2013到2017年间，移动电话普及率将从61.1 % 增长到69.4%的，根据eMarketer名为全球手机用户的报告：H1 2014年预测和估计。这揭示了手机用户如何让社交网络融入他们的日常生活。已经有很多通过用户手机和无线连接到网络移动应用被开发。移动电话或智能手机将很快变成人类生活中最重要的息平台和通讯装置。
近来基于地理定位的社交网络（LBSNs）提供了一种明确的机制来鼓励用户分享位置信息和活动信息。因此，用户可以看到他们的朋友在哪里，在做什么，可以在他们的社交网络里生成或查询有位置标记的信息，也可以遇见与自己可能有共同的爱好的人。主要的移动社交网络有Foursquare，Brightkite和Gowalla，而其他广受欢迎的社交网络平台，如脸谱网、推特和微信也引入了基于地理定位的服务。移动定位服务得以全面发展开来，并提供了一个特别的机会来收集细粒度化的用户访问景点的时空信息。
社群结构研究主要是社会学数据的挖掘和分析任务。了解社会共同体的结构和动态是社会网络分析的主要目标，因为这样的子集很可能会与更大的社群相结合[20,21]。一个社群的发展主要是通过其他朋友间积极的吸纳扩散，这将随着时间的推移出现一个子分支在网络里迅速连接扩散开来。纽曼提出了一种层次凝聚算法，从亚马逊购买网络中来找寻更有意义的社区，从消费者的购买行为数据中来挖掘一个大范围的模式。Kimura则在讨论组合最优化的问题，从一个大型社交网络中来寻找一个最具影响力的节点将社群链接在一起[23]。一个基于重叠社群特性的算法，ComTector（社区检测器），用于现实生活网络的社群检测，如Zachary Karate Club, American College Football, Scientific Collaboration, and Telecommunications Call networks[24]。Lancichinetti对几种方法进行了实验，与最近推出的一项基于异构分布程度和社区规模的基准图进行了比较，提出一份比较分析报告[25]。杨提出了一个重叠社区发现算法BIGCLAM（大网络的聚类关系模型），覆盖了数百万计的节点和链接的大型网络。他们设计了一个基于模型的社群检测方法，可以在庞大网络中发现社群密集重叠，层次嵌套和非重叠社群[26]。Backstrom研究如何评估社群社会属性的影响，包括底层社交网络下的结构，图密度和演化趋势。他们发现，无论是成员加入社群的意向，还是社群的偏好，在底层网络架构中都依赖一种微妙的方式得以快速发展[27]。
近年来，在Liben-Nowell和Kleinberg的开创性研究之后，朋友关系链预测已经变成了一项有趣的研究课题[28]。关系链预测课题也提到了在不同领域内，在已观测到的网络下的推断丢失关系链，它构成了一个在可视数据上建立的互动网络，然后去试着推测未观测到但可能存在的附加关系链。现有的方法主要聚焦在网络拓扑结构上定义各种相似性的测量方法，他可能会考虑网络节点的特殊属性，而不是去评估单单基于图表结构的预测方法的能力。Scellato基于地理定位服务设计了一种关系链预测系统，在Gowallar app上通过收集大规模数据以及周期性的快照，来捕获和分析它的时间演变[1]。一系列新的预测功能被定义，它们构建在已经到访过地点的用户属性和那些可以用来预测用户之间潜在未来关系链的功能。由于近年来蜂拥而至的定位社交服务，用户地理定位信息在服务连接上线后是立即可见的,参考文献[3]提出了一项在用户中出现的移动社交网络空间属性的综合性研究，主要是基于三个流行的LBSN应用，Foursquare, Gowalla和Brightkite。幸亏有多维度的数据源，才提供了追踪人类流动性的可能性，所以它给新型移动应用和服务提供了发展机会。有一种方法提出可以通过个人行为的多重属性提供的预测能力，来预测一个手机用户下一次的所在地点[5]。他们提出了一系列整合功能，利用各种位置变换信息，用户在街道间的移动流向，以及用户签到行为模式的时间空间特性，旨在捕获可以掌握用户移动的因素。Cranshaw介绍了一项新的定位功能来分析某一地理区域的社交环境，它可以衡量某一街道内独立用户的多样性。基于那些功能，他们提供了一种模型，通过分析他们的位置轨迹，来预测两个个体间的朋友关系[7]。Lichtenwalter指出一个有效基于人群流向的预测方法，随后他们提供了关于关系链预测不平衡性的正式界限，以及利用一种评估算法来观察稀疏网络中的不平衡性[10]。一种建立在特定用户兴趣本体上的方法被提出，用来解决关系链预测的问题。他们指出一种主题模型方法，基于共同兴趣和现有朋友关系来预测新的朋友关系链[29]。
3.探测在移动社交网络内的社群
一般来说，在很多领域和学科内，网络间的社群结构调查其实才是一个真正重要的课题。主要问题涉及到社交网络分析人物，生理需求以及科技问题，持续性的问题比如，互联网上用户关系的目标分析，代谢和蛋白质网络的功能研究，或者是大型基础设施的优化。一些社交网络具有一些包括社群结构的基本属性。探索某一网络内的社群，是使用某种方式将节点划分为多个组，从而发现每个组内的顶点将稀疏网络外部与内部紧密联结。
在这一部分，我们会给出一些符号，模块化的目标函数以及用来代表一个社交网络其它定义，这些会在论文内贯穿始终。
3.1 定义和符号
（符号）假设的基础上，社交网络可以由一个无向无权图G=（V，E）表示，其中包括eta;个节点和kappa;个链接。此外，任何子集S属于V，顶点S的总度，S内边的数量，和从S内一个点u到所有顶点的边数，分别意味着符号, 和 .
假设集合不相交的群体是由zeta;= { ，，..， }表示，在Ciisin;是图G的一部分，对任意一个顶点u，让du，（u）和lt;ugt;做他的度，这个集合包含了顶点u和一系列与他相邻的集合。
（动态社交网络）假设一个依赖网络的很短的时间tau;可以由图=（，）表示，让∆和∆作为节点和边将会在时间tau;被更新，并且由∆=（∆，∆）代表在整个网络更新的信息。在接下来的快照时间tau; 1，网络是由当前图更新，即 =cap;∆。动态网络G是一系列网络小时间随着时间的推移而发展：G =（，，...，）
定义1模块化：分析和评估网络结构，我们利用[ 30 ]提出的最广泛的权威测试，即模块化Q的定义是
（1）
基本上，前者代表连接到集合中的顶点的边缘的分数，后者表示图中有相同的权重的，在图中的顶点有相同的度，但连接分布随机的预测值。根据方程，模块化值越高表示在网络的集合结构中图有一个更好的结果。因此，我们的目标是在网络中找到一个集合分配给每个顶点使Q是最大的。
定义2结点的影响：让我们考虑一个节点u在原有的网络来连接一个或多个已有的集合，每个顶点u被两个因素影响，即和，参考文献[ 25 ]定义如下：
（2）
（3）
表示这样一个因素，这个因素来自集合，中有一个顶点，并且使u在中，表示对立的因素，这个因素起源于所有相邻模块lt;ugt;除了集合并且把这个顶点加紧它候选目标集合中，或者从cI中去除结点。
基于上面的方程（2）和（3），一个节点可以主动决定哪个是最合适的集合去保持关系，通过计算两
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29955]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
