论文部分内容阅读
随着web2.0时代的到来,越来越多的数据呈现在互联网上,更多的体现用户在网络上的互相交互。人们既生产大量网络数据、又同时对其进行消费。人们的生产、生活、学习、娱乐也越来越离不开互联网。社交网络把现实中人与人之间的关系建立在互联网上,加强人们之间的交流和互动,促进信息更快的在世界范围内流动。随着Facebook上市,社交网络也越来越多的受到人们的关注。Facebook是一种强关系的社交网络,用户可以利用其进行朋友之间的关系的促进改善和维护;微博Twitter是一种弱关系的社交网络,在其上容易形成意见领袖和信息快速传播,有利于社交网络的广告推广和营销;Linkedin是专注于商务人士拓展业务,求职招聘等进行商务交流的专业社交平台。国内也有很多社交网络如腾讯微博、嘀咕、9911、随心微博、新浪微博、搜狐微博、Follow5、网易微博、品品米、MySpace聚友网、百度i贴、同学网、饭否等,其中比较知名的新浪微博比较类似于Twitter。截至2012年12月份,国内知名社交网络新浪微博用户规模达到5亿;时至2012年7月国外著名社交网络Twitter用户数量超过5亿;另外一个世界知名社交网站FaceBook用户数量达到10亿以上。据国外知名数据公司PingDorn的数据显示,全球已有几十亿社交网络用户,同时社交网络链接和网页插件已经占据全世界所有网站的四分之一。对社交网络进行分析,发现社交网络中各种社区对于商品推荐、广告推送、朋友推荐以及对社交网络进行划分具有十分重要的意义。本文在调研分析大规模社交网络发展和研究的基础上,主要就如何有效挖掘社交网络中兴趣社区做了深入研究。本文先就其两个子问题社交网络中个性化兴趣的建模和个性化PageRank高效计算进行研究。在完成兴趣建模和个性化PageRank高效计算的基础上,进行大规模社交网络的兴趣社区探测。首先,采用用户好友关系信息、用户发布和转发微博信息作为兴趣信息,针对普通用户和特殊用户的不同,分别提出以关注对象为兴趣的三层模型和以发布微博为兴趣的两层模型的模型表示方法。针对微博内容为兴趣建模,提出基于LDA改进的微博兴趣分类方法。针对用户兴趣改变的问题,提出基于用户微博内容为反馈的贝叶斯方法,同时还提出基于兴趣社区发现为目的的用户兴趣偏好模型。最后通过以用户标签作为参考对模型进行评估,得出模型在标签较充足时能有80%以上的查准率和查全率。其次,个性化PageRank作为信息检索和数据挖掘领域的重要算法,随着数据规模的不断增大,有必要对其进行优化和加速。传统迭代方法比较耗费时间和空间,本文使用基于Monte Carlo随机步方法。MapReduce适合数据密集型计算,不适合大量的迭代,本文提出基于MPI的分布式算法。改进先前的二路合并方法到基于Fibonacci的方法,从理论上性能有30%左右的提高,在大量真实数据的实验上得出该方法相对基础方法性能提高10%到40%。最后,由于社区结构信息包含成员关系连接信息和成员本身的个性化信息,提出考虑结构信息和节点自身属性特征的基于个性化PageRank的社区发现方法。针对日益发展的社交网络的数据大规模性,提出局部的社区分析方法和将算法改进适应在分布式计算架构MapReduce之上。由于大部分社区探测方法不适合用在具有千万级甚至更大用户规模的社区分析,而Metis方法是少有的能处理如此大规模的网络分析工具,本文将所提出的基于个性化PageRank方法与Metis方法进行比较,凸显本文提出方法具有更好的社区探测能力,能找到聚簇性很强的局部社区。另外,本文通过MapReduce扩展实验说明了方法的可扩展性和高效性。