基于信息传播的有向社会网络简化

《基于信息传播的有向社会网络简化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文图书分类号：TP311密级：公开UDC：620学校代码：10005工程硕士学位论文M.E.DISSERTATION论文题目：基于信息传播的有向社会网络简化论文作者：赵建炜领域：软件工程指导教师：奥顿论文提交日期：2016年4月UDC：620学校代码：10005中文图书分类号：TP311学号：G2013202268密级：公开北京工业大学硕士专业学位论文（非全日制）题目：基于信息传播的有向社会网络简化英文题目：DirectedSocialNetworkSimplificationBasedonInformationSpread论文作者：赵建炜领域：软件

2、工程研究方向：企业管理信息化申请学位：工程硕士专业学位指导教师：奥顿所在单位：电子信息与控制工程学院答辩日期：2016年5月授予学位单位：北京工业大学独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：赵建炜日期：2016年6月21日关于论文使用授权的说明本人完全了解北京工业大学有

3、关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵守此规定）签名：赵建炜日期：2016年6月21日导师签名：奥顿日期：2016年6月21日摘要社会网络是WEB2.0时代的重要特征。它不仅扩展了传统互联网的功能，还大大提高了互联网用户使用网络，建设网络的积极性。它在网络维度提供的新型的用户交互手段，已经深深的影响了全世界人民的日常行为习惯。Twitter是一个典型的社会网络。Twitter中最重要的特征是信息的传

4、播非常迅速，这个特征更多的要归功于Twitter提供的转推机制。转推机制的基本原理是，每个Twitter用户可以对任何一条推文进行转推，然后这条推文就可以立即被这个Twitter用户的所有粉丝（follower）接收到。如此以来，一旦有几个用户对某条推文进行了转推行为，那么这条推文就能以非常快的速度传播到网络的非常大的范围。Twitter对于转推行为设置了非常巧妙的实现方式，它既能保证用户一定会收到关注用户转推的所有推文，又对那些重复的推文做了系统级别的过滤。这个机制使得用户体验更加简洁，然而也对网络分析带来了许多隐蔽的问题。其中一个较为重要的问题是用

5、户排序。目前，社会网络领域的大多用户排序工作都依赖于PageRank算法以及其变种，这些算法会建立一个基于用户关注关系的网络结构，并且假设推文在网络中的任何一条边都可以流动，这与事实上的Twitter转发机制是违背的。我们暂未见到相关文献，而此问题对于Twitter是值得研究的。本文第一次正式研究了Twitter中的转推机制，并分析了其特点，提出网络简化问题，给出可行的算法，并分析了简化问题对其他网络分析工作的影响，进一步推动了为社会网络领域的分析工作。文章从Twitter的转发机制出发，定义了网络简化问题，提出了基于传播三角形模型的算法，并进行了多种

6、优化。为了提高算法的应用范围，还提出了在无向图上的网络简化算法。在实验部分，我们在实际的Twitter数据集上运行了简化算法，验证了算法的可行性；并在数据集上对用户进行了排序，分析了简化算法对于排序结果的影响，验证了算法的有效性。最后实现了一个原型系统，使得简化工作的效果更加直观。关键词：社会网络；Twitter；有向图；网络简化AbstractAbstractSocialNetworkisoneofthemostimportantfeaturesofWEB2.0era.Ononehand,itexpandsthefunctionoftradition

7、alworldwideweb.Ontheotherhand,itimprovestheenthusiasmofuserstoparticipateandconstructtheweb.Itprovidesnovelwaysforuserstointeractwitheachotherandhasdeeplyinfluencethehabitofpeopleallovertheworld.Twitterisatypicalsocialnetwork.ThemostimportantfeatureinTwitteristhattheinformations

8、preadsveryfastandthefeatureowestothemechanismof