论文部分内容阅读
社交网络正在成为人类社会关系维系及信息传播的重要渠道和载体,有关社交网络理论和关键技术的研究,对于社会发展以及商业服务应用都有着实际的应用价值。用户影响力分析作为社交网络分析的关键内容之一,在诸多领域有着广泛的应用,如推荐系统、广告投放、链路预测和实时事件异常检测等。微博作为社交网络的一种重要媒介,凭借其即时发布、实时传播、简便易用的特点逐渐成为最为主流的社交网络平台。用户影响力评价是微博社交网络中基本而又重要的问题,它对于优化与推动社会信息传播来说有着重要意义。面对大规模的微博用户群体,微博用户的影响力作为其基本特征吸引了广大学者对此进行研究。在社交网络中,个性化排名是指基于网络链接结构以及用户的个性化偏好对网络节点进行重要性排名。社交网络中的个性化排名技术对于垃圾链接检测、朋友推荐、精准营销、社区发现等都有重要的研究意义。同时,在现实生活中,在线社交媒体FaceBook、Twitter等这些网络结构不仅规模巨大,而且持续地动态更新。因此,对于具有实时性的个性化排名技术需要有效地应对不断变化的网络结构,设计出弹性可扩展的动态更新算法。本文主要围绕社交网络中用户影响力与个性化排名两个问题展开分析与研究,主要贡献如下:(1)本文首先分析了微博网络中用户质量存在差异,针对PageRank算法在迭代过程中平均分配权值不够合理的问题,引入用户相对质量概念。同时,综合考虑用户微博评论率、转发率、是否微博认证等用户特征。(2)面对大规模的用户数据,合理有效的并行化处理显得尤为重要。本文结合MapReduce并行编程环境,设计基于PageRank的用户影响力排名算法。在Hadoop平台下,对比实验结果表明本文提出的QRank算法具有良好的可扩展性,能够有效结合微博用户关系网络与行为特性,从而更加真实与充分地反映用户的实际影响力。(3)对于个性化排名技术,本文首先分析个性化PageRank算法的本地更新方法。为了分析动态网络结构下算法的复杂度问题,引入随机边有序到达动态模型。基于本地更新的思想,本文先给出加入残余概率优先级队列的PriorityPush算法,并提出适用于动态网络结构的DynamicPriorityPush算法。基于随机边有序到达动态模型,给出了该算法详细的复杂度分析,并通过实验验证该算法的有效性与准确性。(4)实验结果表明,DynamicPriorityPush算法1秒钟可以实时追踪近400条边变化,在WikiTalk数据集上追踪单条边删除变化,该算法的更新时间仅需390us。实验结果验证了当插入的边的规模不断增长时,算法总的运行时间与边的规模基本成线性关系,对于k条变化的边,算法的平均时间复杂度为O(d/ε+k+k/(nε)),摊还分析可知对于每一条边变化,该算法的分摊时间复杂度为O(1/ε)。同时,实验结果验证了该动态算法能够在保证正确性的同时,运行效率均优于其余两种方法:对比每次边插入后重新运行的PriorityPush from scratch方法,本文算法具有23-114倍的加速,对比蒙特卡洛方法,在所有数据集上算法均达到上百倍的加速,最高可达455倍。