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

• 作者: 张伟哲 张宏莉 张玥
• 来源期刊: 中文信息学报
• 学科: 工学
• 关键词: 幂律 入度 集合划分 快速排序
• 年，卷（期）: 2012,（4）
• 页码范围: 122-128
• 分类号: TP391
• 字数: 4299字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0077.2012.04.017

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张宏莉	哈尔滨工业大学计算机科学与技术学院	185	2778	29.0	46.0
2	张玥	哈尔滨工业大学计算机科学与技术学院	17	91	5.0	9.0
3	张伟哲	哈尔滨工业大学计算机科学与技术学院	37	798	15.0	28.0