基于幂律分布的网络用户快速排序算法

摘要：

随着网络论坛、博客、微博的发展,引出社会网络中的用户排序问题.将在线网络论坛中用户映射为节点,用户评论过程中形成的回复关系映射为有向关联图,其节点度符合幂律分布.且论坛中用户的主题发布行为和回复关系符合Pagerank算法的互增强和随机游走特性,因此选用Pagerank算法排序用户影响力.该文提出的研究问题:如何提高用户排序应用中数据的存储和运行效率.天涯网络论坛中80％以上用户入度为0,据此,根据入度是否为0划分为两个集合,对入度为0集合按出度构造链接表,设计了基于集合划分的高效排序算法SD-Rank.SD-Rank时空复杂性为O(V'),V'为入度非0节点集.对天涯网络论坛真实用户数据的实验结果表明:SD-Rank算法时空复杂性优于Pagerank算法.

关键词：幂律、入度、集合划分、快速排序

所属期刊栏目：26

分类号：TP391(计算技术、计算机技术)

资助基金：国家863自然科学基金2010AA012504;国家973重点基础研究发展规划项目基金G2011CB302605;国家自然科学基金61173145

在线出版日期：2012-11-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：122-128