计算机科学 ›› 2014, Vol. 41 ›› Issue (4): 233-238.

• 人工智能 • 上一篇    下一篇

ELPS:一种高效的微博信息传播轨迹提取算法

王悦,黄威靖   

  1. 中央财经大学信息学院计算机系 北京100081;北京大学信息科学技术学院 北京100871
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金(60970143,8),北京市教委共建项目,中央财经大学研究生教育改革项目资助

ELPS:An Efficient Information Trajectory Extracting Algorithm in Microblog

WANG Yue and HUANG Wei-jing   

  • Online:2018-11-14 Published:2018-11-14

摘要: 近年来,随着社会性网络服务应用(SNS)的流行与发展,SNS已成为人与人之间重要的交流渠道。SNS中大量用户产生的数据内容包含了社会网络中信息传播的客观知识,由此SNS可用于研究社会网络中公众舆论的变化趋势及信息传播的相关规律。由于SNS服务中节点规模大、其用户间的信息传播通常出现离散而稀疏的情况,需要高效的信息 传播观察手段。为解决该问题,提出信息传播轨迹用于研究社会网络中信息传播的基本规律,具体的方法为:(1)提出信息传播轨迹(info-trajectory)模型以记录社会网络中信息传播的具体路径;(2)针对微博社会网络,提出几个高效的信息传播轨迹抽取算法;(3)根据已获取的信息传播轨迹研究用户间转发信息行为的时序规律;(4)提出算法K-advocators-discover用于发现社会网络中促进信息传播的top-k名用户;(5)提供充分的实验测试来将所提方法用于抽取新浪微博上热点话题信息 的 传播轨迹,并采用K-advocators-discover算法分析新浪微博中促进信息传播的用户。实验结果验证,所提方法能高效地提取微博中信息传播轨迹,挖掘其中促进信息传播的用户。

关键词: 社会网络,图挖掘,信息传播轨迹

Abstract: With the development of the Social Networking Services (SNS),SNS has become an important tool for people to communicate with each other.The rich user generated contents (UCG) of SNS have contained useful knowledge about information propagation rules.Thus SNS can be used to study public opinion and information propagation rules in the social networks.As information propagation happens in the online social networks discretely and sparsely,it is hard to directly observe and study the propagation process of information in an online social network with over 10million nodes.To meet the challenges,the paper (1) provided a model “info-trajectory” to capture the information propagation pathways in the online social network,(2) proposed several algorithms to extract info-trajectory from some practical microblog social networks efficiently by employing repost timeline (a kind of public available repost notification data of microblog),(3) studied the temporal relations of the repost actions for the users on the obtained info-trajectories, (4) proposed algorithm K-advocators to discover the advocators from the information propagation trajectories and information propagation patterns in the microblog,and (5) in the experiment section,provided the sufficient experiments to study info-trajectories for several topics on Sinamicroblog(a prevalent microblog application in China),and several po-pular SNSs.The results show that the proposed methods are efficient to extract the info-trajectories,and useful to disco-ver advocators for specific topics in the microblogs.

Key words: Social network,Graph mining,Information trajectory

[1] Granovetter M.The strength of weak ties[J].American Journal of Sociology,1973,8(6):1360-1380
[2] Huberman B A,Adamic L A.Information Dynamics in the Networked World [J].Lect.Notes Phys.,2004,0:371-398
[3] Kossinets G,Kleinberg J M,Watts D J.The structure of information pathways in a social communication network[C]∥Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2008:435-443
[4] Kossinets G.Effects of missing data in social networks[J].Social Networks,2006,8:247-268
[5] Laumann E,Marsden P,Prensky D.The boundary specification problem in network analysis[J].Applied Network Analysis,1983(10):18-34
[6] Leskovec J,Adamic L A,Huberman B A.The dynamics of viral marketing[J].ACM Transactions on the Web (TWEB),2007,1(1)
[7] Liben-Nowell D,Kleinberg J.Tracing information flow on aglobal scale using Internet chain-letter data[J].Proc.Natl.Acad.Sci.USA,2008,5(12):4633-4638
[8] Bakshy E,Rosenn I,Marlow C,et al.The role of social networks in information diffusion[C]∥WWW.2012:519-528
[9] 樊鹏翼,王晖,姜志宏,等.微博网络测量研究[J].计算机研究与发展,2012(4):691-699
[10] Qin L,Yu J X,Chang L.Keyword search in databases:the powerof RDBMS[C]∥SIGMOD Conference.2009:681-694
[11] Illenberger J,Kowald M,Axhausen K W,et al.Insights into a spatially embedded social network from a large-scale snowball sample[C]∥The European Physical Journal B-Condensed Matter and Complex Systems.2011:1-13
[12] Song Xiao-dan,Chi Yun,Hino K,et al.Identifying opinion lea-ders in the blogosphere[C]∥CIKM 200.72007:971-974
[13] Zafarani R,Liu H.Social Computing Data Repository at ASU.http://socialcomputing.asu.edu.Tempe,AZ:Arizona State University,School of Computing,Informatics and Decision Systems Engineering,2009
[14] http://jung.sourceforge.net/

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!