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

被引：5

作者：

张玥

张宏莉

张伟哲

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

来源：

中文信息学报 | 2012年 / 26卷 / 04期

关键词：

幂律; 入度; 集合划分; 快速排序;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; TP393.094 [];

学科分类号：

摘要：

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

引用

页码：122 / 128

页数：7

共 27 条

[1]

Maximizing the spread of influence through a social network. Kempe, D,Kleinberg, J,Tardos, E. Proceedings of the 9th International Conference on Knowledge Discovery and Data mining (KDD) . 2003

[2]

Agreeing to disagree:search engines and their public interfaces. F.McCown,M.L.Nelson. Pro-ceedings of the 7th ACM/IEEE-CS joint conferenceon digital libraries . 2007

[3]

Introduction to NumericalAnalysis. Stoer Josef,R Bulirsch. . 2002

[4]

Identifying Topical Au-thorities in Microblogs. Aditya Pai,Scott Counts. Proceedings of the fourthACM international conference on Web search and datamining (WSDM) . 2011

[5]

Randomization Tests for Dis-tinguishing Social Influence and Homophily Effects. T.L.Fond,J.Neville. Proceedings of the 19th international conferenceon World Wide Web . 2010

[6]

Identifying the Influential Bloggers in a Community. Nitin A,Huan L,Lei T. Proceedings of the international conference on Web search and web data mining 2008 . 2008

[7]

Introduction to Algorithms. THOMAS H C,CHARLES E L,RONALD L R, et al. . 2001

[8] Authoritative sources in a hyperlinked environment [J].

Kleinberg, JM .

JOURNAL OF THE ACM, 1999, 46 (05) :604-632

[9]

Comparing Top k Lists. Ronald Fagin,Ravi Kumar,D Sivakumar. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms . 2003

[10]

Yes,there is a correlation:-from social networks to personal behavior on the web. Parag Singla,Matthew Richardson. WWW ‘08:Proceeding of the 17th international conference on World Wide Web . 2008

← 1 2 3 →