在线社交网络下基于信任度的消息传播模型

本论文是一篇个体相关新闻传播毕业论文范文,关于在线社交网络下基于信任度的消息传播模型相关硕士学位毕业论文范文。免费优秀的关于个体及消息及社交方面论文范文资料,适合个体论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

摘 要：

社交网络作为一种新兴的媒体具有广泛的社会影响力,且基于社交网络的营销方式逐渐成为一种新的发展趋势,因此研究社交网络中消息的传播具有重大的现实和经济意义.通过借鉴日常生活中人与人之间的信任原理,提出了一种基于信任度的消息传播模型.该模型首先利用个体的公开信息,使用数据挖掘的算法对个体进行分类；然后,根据同类和不同类个体之间的关系计算个体之间的信任度；最后,使用消息与个体的属性相似性以及信任度来计算消息可能传播范围.给出了相应的计算方法,并与两种基准方法对比,结果表明,该模型在准确度上提升15%左右,而所用时间降低50%以上.与数据集统计结果对比,该实验的结果与统计结果相差5%左右,充分表明该模型在实际应用中有比较好的效果.

关 键 词 ：

社交网络；数据挖掘；分类算法；信任度；网络的结构聚类算法；消息传播模型

中图分类号：

TP393.4

文献标志码：A

Trust-based information propagation model in online social works

Abstract：

As a new media, social work gains a wide range of social influence, and the social work based e-merce bees more and more popular, which make the study of information propagation of great significance. A trust based information propagation model was presented in this paper according to the trust relationship between people in daily life. First, the algorithm of data mining was employed on personal information to make the classification of the users. And then the value of trust between the users was calculated according to their relationships. At last, this paper predicted the range of information propagation by using the trust value between the users and messages. Compared with two basic methods, the final experiment shows that the results generated by the model are enhanced by 15% in precision, while the time used decreases more than 50%. The results differ with the statistic results on the dataset at 5%, which shows that the model preforms well in practice.

Key words：

social work； data mining； classification algorithm； trust； Structural Clustering Algorithm for Networks （SCAN）； information propagation model

0 引言

近年来社交网络得到了迅猛的发展,信息化革命让人们越来越依赖网络获取资讯,大批的社会性网络服务（Social Networking Service, SNS）网站受到越来越多用户的欢迎,如国外的Twitter,以及国内的新浪微博等.用户通过社交网络分享新闻、日志、视频等,维持和开拓人际关系,正是由于社交网络的开放性,人与人之间很容易建立起关系且这种关系不受时间、空间的限制.与传统的社交网络相比,社交网络上的消息传播有其随意性、不可控性以及其前所未有的传播优势和巨大的影响力,使其成为拥有强大舆论动员力的传播工具.同时由于电子商务的发展,基于SNS的网络营销越来越受到人们的重视,而SNS上的消息受众的多少也直接影响营销的效果,了解消息的受众范围往往可以收到事半功倍的效果.因此,对社交网络上的消息传播的研究具有非常重要的社会意义和经济意义.

在现实生活中,熟人之间的通信是消息传播的重要方式,而社交网络是现实中人际关系的反映,因此在消息传播模型中加入信任度的概念,不仅能有效地了解消息在社交网络中的传播,同时大大降低了研究消息传播的用户的规模.

在之前对信任度的研究中,很多优秀的模型和算法被提出来,文献[1]提出了P2P网络中节点之间的通过信任度建立下载关系；针对P2P网络中信任计算方法,文献[2]提出了基于名誉度的计算模型,文献[3]通过P2P网络中节点之间的交互记录来计算节点之间传递的信任度.文献[4]总结了对等网络环境下信任机制的体系结构,并对信任模型进行了相关总结.虽然这些信任模型在P2P对等网络中有非常显著的作用,然则社交网络并不完全等同于P2P网络,因此需要对信任模型加以修改.文献[5]将信任模型引入到社交网络中,提出了二度信任模型来解决社交网络中人与人之间的关系；文献[6]将拍卖中审计的机制引入社交网络的信任模型,防止了用户之间信任度的欺骗行为,然而在信任度的计算过程中,却仅仅使用粉丝数的多少来确定个人的原始信任度；文献[7]通过用户之间的熟悉性和相似性计算用户之间的信任度,但是没有考虑到社交网络中用户数量的庞大,因此只能计算部分用户的信任度,达不到预期的目的.纵观这些方法,其缺陷在于这些模型是基于最基本的统计模型.基于统计得来的结果往往能达到比较好的效果,然而随着数据的爆炸式增长,大量的伪数据可能会给这些统计结果带来偏差.据统计分析,Twitter用户的人均粉丝数为51人,人均推文数高达307条,且该数量以每月20%的速度增长[8].面对大量数据,依靠统计模型已经不能充分说明消息传播的途径和范围. 本文通过借鉴之前的研究成果,结合当前社交网络中的具体情况,提出了基于数据挖掘的信任度计算方法,然后使用该方法来模拟消息在社交网络中的传播.本文中的信任与心理学中人与人的信任的概念稍有不同,在本文中信任是指消息接收者对于消息发布者发布或者转发的消息,相信并转发该消息的可能性.在本模型中,首先利用数据挖掘中的分类方法对群体进行分类,然后通过消息发布者与消息接收者之间的历史交互记录,计算个体之间的信任度,通过这种方式来评估消息在社交网络群体中的传播途径和传播范围.

1.社交网络的消息传播机制

1.1 社交网络中的信任关系

本文用图论中的加权有向图G（N,E,W）来表示社交网络.其中：节点N表示群体中的个体,有向边E表示两个个体的关系,权重W表示两个体之间的信任关系.社交网络在逻辑形式上表现如图1所示.

在现实生活中,人们之间存在很多关系,其中部分关系是由兴趣相同而产生的.根据常识,一般兴趣相同的人的话更容易被接受,也就是说他们更信任与自己有相同爱好的人.因此,可以将每个人的爱好等这类内部属性总结出来,如果两个人之间的属性更加相近,则他们之间的信任度会更高.当这些属性确定之后,就可以根据个体的这些属性以及在群体中的社交关系将社交网络中的个体划分类别,之后可以计算个体在所在类别中的信任度；当群体中的个体对其所有邻居的信任值都确定之后,就可以通过信任度来预测消息可能的传播范围.

1.2 基于数据挖掘的群体类别划分算法

由于在社交网络上,个体之间建立关系,最终形成一个巨大的关系网,且每个个体都会发布消息,因此这个关系网的信息量巨大.根据文献[9]研究成果,且有20/80法则[10],可以得到社交网络中80%的消息是由20%的个体产生的,且社交网络中的数据非常庞大,直接对这些数据进行处理几乎是不可能完成的任务,因此要为群体划分类别首先需要对社交网络中的数据进行预处理.

1.2.1 社交网络中数据的预处理

虽然社交网络中的数据是半结构化的,但是其中有很多数据的质量是非常低的.数据质量[11]涉及许多因素,包括准确性、完整性、一致性、时效性、可信性以及可解释性.由于社交网络中充斥着大量的不真实数据,此类数据的存在对研究消息传播不仅没有帮助,反而浪费大量的处理时间,因此必须对这些数据进行预处理.数据挖掘的预处理方法有很多种,在这里使用了其中的三种：数据清理、数据集成和数据归约.

数据清理 数据清理主要是将那些不重要的数据精简,以实现数据的准确性和时效性.在社交网络中可以发现有很多长期不活动或者很少活动的个体,此类个体的邻居个数较少或者没有,且在社交网络中很少发布或转发消息,在社交网络中构成一个“信息孤岛”,此类个体在消息传播过程中基本上没有影响,在数据预处理时可以将此类个体删除.

图1经过数据清理之后,社交网络变成如图2所示.

数据集成 在社交网络中,由于个体的性格特点等,存在着用不同的名字代表同一属性而导致的不一致和冗余,需要对这些数据进行数据集成以简化数据.通过数据集成,将个体的某个属性集成到有限数量的值上,简化个体的类别判定.

数据归约 数据归约可以得到数据集的归约表示,归约后的数据集小得多,但是仍然能保持原始数据的完整性.在本文中,数据归约主要是将个体发布的历史消息用一些关 键 词 来表示,这些关 键 词 主要概括了该消息的类型、领域等主要信息.

分析个体的属性为计算个体之间的信任值有非常重要的作用,接下来将介绍通过个体的历史信息发掘个体属性的方法.

1.2.2 基于Apriori算法[12]的个体属性发现算法

社交网络中个体发布的消息大部分与其属性有某种关联,所以每条消息可以使用其若干个属性来概括该消息.对于其发布的消息的接收个体而言,如果该接收个体对此消息感兴趣,会以比较大的可能性转发该消息；反之,对此消息不感兴趣的个体以比较小的可能性转发该消息.

Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成向下封闭检测两个阶段来挖掘频繁项集.Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索（k+1）项集.

个体内部属性的挖掘算法如下：首先通过扫描用户的历史消息记录,累计每个关 键 词 的计数,并收集满足最小支持度的关 键 词 ,找出频繁1项集,该集合记为L1,然后使用L1找出频繁2项集的集合L2,使用L2找到L3.具体算法过程如下：

算法1 使用逐层迭代方法给予候选产生找出频繁项集.

输入 个体历史消息记录集合D；最小支持度阈值min_sup；

输出 L, D中的频繁项集,即个体潜在的内部属性.

在连接步中,为了找出Lk,通过将Lk-1与自身连接产生候选k项集的集合.记号li[j]表示li的第j项.为了有效地实现上述算法,Apriori算法设定每个消息中的关 键 词 按字典序排序,连接li和lj产生的结果项集是{li[1],li[2],等,li[k-1],lj[k-1]}.

在剪枝步中,Ck是Lk的超集,Ck中的关 键 词 可能不是频繁出现的,但是所有频繁的k项集都包含在Lk中,扫描个体所有历史消息记录,确定Ck中每个候选的计数,从而确定Lk.

1.2.3 社交网络中群体类别划分算法

经过之前的属性挖掘,就很容易进行分类工作.本文采用了拓展数据挖掘中的网络的结构聚类算法（Structural Clustering Algorithm for Networks,SCAN）[13]进行类别划分. 通过上述算法,可以将具有不同属性的个体划分成多个类别,由于每个个体具有多个属性,因此每个个体可能属于多个类别.需要指出的是,由于社交网络中个体的数量很多,上述分类算法需要消耗大量时间,因此只有对特定消息类型传播预测时才使用特定属性对社交网络进行分类.

1.3 社交网络中的信任度计算

根据之前的群体类别划分算法,整个社交网络被划分成多个相对独立的类别.对于类别内部而言,消息从一个个体传播到另一个个体；对于类别之间的消息传播,是通过两个群体之间多个个体之间的交互从一个类别传播到另外一个类别中.这两种消息传播模式不同,因此其信任度的计算方法也不同.

1）社交网络中个体类别内部信任度的计算.

由于前面已经将社交网络中群体根据个体之间的属性相似性进行分类,所以在这里只需要考虑个体之间的熟悉性.如图3所示的交互记录,连接线上的数字表示两个个体之间的交互次数.

根据常识,回复消息越多的个体则说明其对个体A越信任,对它的信任度也就越高,因此,该群体中其他个体对个体F的信任度可以通过式（2）计算,式中引入了一个层的概念,如消息传播路径为F→E→A,个体F为第0层,个体E为第1层,个体A为第2层.

其中：m表示个体A与个体E之间的层数；N（Lj-1,Lj）表示第j-1层个体和第j层个体交互的次数；T（j-1, j）表示第j-1层和第j层的交互的总次数；n表示个体A与个体E之间的链路的个数；为了表示不同个体相对于消息发布个体之间的远近层次关系,用λi表示第j层在整个传播链路中的权重.由于离消息发布个体越近的个体,两个人的熟悉程度更高,因此,λi值也就越大,权重计算如式（3）所示：

其中：Trust（A,Cstr）表示个体A在类别Cstr中的信任度；V（Cstr）表示类别Cstr中个体集合；σ（j,A）表示个体j和个体A之间的属性相似度,如果j和A之间没有交互,则σ（j,A）等于0.

如果Cstr中有n个个体,因此有n个类似于式（4）的方程,其中Trust（A,Clstr）、Trust（j,Clstr）为未知数,求解这个问题是一个n元方程组,可以轻松解出这些值.

1.4 社交网络中群体类别之间信任度的计算

在上一节中介绍了如何计算群体类别内部的信任度,通过前面的介绍,一个群体类别和&

本论文是一篇个体相关新闻传播毕业论文范文,关于在线社交网络下基于信任度的消息传播模型相关硕士学位毕业论文范文。免费优秀的关于个体及消息及社交方面论文范文资料,适合个体论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

对于类别C1中个体和类别C2中个体有直接交互,则C1和C2有一对直接交互个体,如果C1和C2中有直接交互的节点数量越多,则两个类别之间的信任度也就越高.同时,一个个体可能同时属于两个类别.在这里,先考虑类别C1与个体k之间的信任度,其中kC1,借鉴式（3）的信任度计算方法,k与C1之间的信任度为个体k与类别C1中有直接交互的个体之间的信任度的加权平均值,其权重为k与C1中有直接交互个体的属性相似度.因此个体k与类别C1的信任度计算公式为

Trust（k,C1）等于

对于每条消息Msg,数据规约之后的向量应该选取特定数量的选项,既要考虑到计算的复杂性,同时还要考虑到预测的准确性.当Msg规约的选项越多,计算复杂性越高,同时预测的准确度越高；反之,计算复杂性越低,同时预测的准确度越低.

2.实验结果验证与分析

本文使用新浪微博API来采集微博数据,数据为新浪微博在2013年04月01日到2013年05月01日内一个月内的数据.其中采集的微博数量为84423条,涉及用户6734个（本数据由中国科学院软件研究所提供）.在这里使用该数据集来验证本模型的正确性和合理性.对于上述数据特征,经过统计如表1、2所示.

根据第1.3节中描述的方法,对数据进行预处理.

首先对这些数据进行数据清理,该数据规模不是很大,为了保证数据的有效性,将一个月发布微博数在0～30的用户且粉丝数少于20人的用户删除,经过上述处理之后剩余的用户为5455个,剩余微博数量为76920条.

在数据集成阶段,选取用户的如下属性：用户所在地、教育背景、职业信息、兴趣爱好.用户的外部属性可以直接从用户的个人信息设置可以得出.对于用户的内部信息,用户自己标出来的是一部分,但是大部分内部属性需要通过对过去该用户发布的微博的内容来总结挖掘.

在数据归约的过程中使用了如下算法,先对微博进行分词,本文使用ICTCLAS[14]对微博进行分词,从中提取可用的关 键 词 ,当关 键 词 在微博中出现的次数超过一定数量之后就把这个词作为用户可能的内部属性.

通过使用Apriori算法挖掘出用户微博中的所有关 键 词 之后,将提取这些关 键 词 的共同属性,总结成一些内部属性.经过上述过程,在本实验数据上总结了17个内部属性：计算机、电子消费、音乐、幽默笑话、金融投资、医药健康、女装购物、电影影视、游戏娱乐、汽车、文学小说、交友婚介、股票基金、旅游美食、科技、体育、校园生活.

在对微博中用户的类别进行划分时,首先将微博用户以其原有的关注者组织成一个用户关系网络.由于之前对于每个用户使用Apriori算法挖掘出用户的属性,因此每个用户可以用一个向量表示,如果用户有该属性,则用1表示,否则用0表示,因此可以使用SCAN算法进行分类,最终可以将整个实验数据中的人数分成17类,每个类别的用户数分布如图4所示.

在开始计算微博中信任度时,需要对式（6）和（8）中的λL和λG的值进行训练,因此在本轮训练过程中选取了来自用户“上海发布”的10条消息分别涉及：1）电子消费；2）音乐；3）金融投资；4）医药健康；5）电影影视；6）汽车；7）股票基金；8）旅游美食；9）科技；10）体育.通过统计,这10条消息传播的范围如图5所示（本文只统计了转发消息的用户,其他接收但是未转发的用户并不再统计之内）. 在图5中,local表示该消息在所在类别中传播的用户数,global表示该消息在全部用户中的传播数.通过上述10组数据,可以计算得到的λL和λG的值如表3所示.

由于该数据在整个新浪微博中只是非常小的一部分,因此需要通过多组数据来对两个参数进行训练才能让预测结构更加符合这个数据集,通常取上面10组数据的平均值.通过计算就可以预测消息可能的传播范围.

在验证阶段本文选用了基于用户上下文的信任度计算方法以及文献[7]中提出的基于用户之间熟悉性和相似性的计算方法作为基准方法,与本文方法作对比.本文选用了用户“上海发布”发布其他10条消息,经过之前的预处理阶段,这10条消息的具体信息如表4（由于两种基准计算方法在计算用户之间的信任度与本文中提到的方法不同,因此三者的计算的信任值不具有可比性,在此不再列举出来）.

通过表5的结果可以看出,三种方法的计算值和实际统计值的浮动为5%左右,这是因为这个数据集不完整,因此在两个因子的计算上出现偏差；而且,该数值计算非常复杂,中间进行了大量的舍入操作,而这些值经过层层放大,直接导致计算值与统计值偏差较大,但在估算中可以容忍一定的差别.通过对比实验,可以看出方法2和方法3预测的结果差别比本文方法差别大.

三种方法消耗的时间如表6所示（以消息类型为校园为例）.

由于方法2和方法3并没有对数据集进行数据清理,因此计算时间比较长.通过上述对比实验可以发现本文方法在预测的准确度上有较大的提升,并且计算时间大大降低.

3.结语

本文通过数据挖掘算法对个体过去发布的所有消息进行处理,挖掘出个体最关心的话题,然后将这些话题总结成个体的属性,因此每个个体都有多个属性.然后按属性将社交群体划分成若干个类别,之后再计算个体与个体之间、个体与类别的相似度,计算出个体与各自之间的信任度.当需要预测某个个体发布的某条消息的传播范围时,就可以先计算该消息与个体及其所在类别的相似度,结合用户在该类别中的信任度,计算可能的传播范围.这种通过数据挖掘的方法得出来的结果比单纯的依靠个体的已知信息来计算信任度,可靠性更高,预测的结果更加可信.然而该模型的缺点在于需要大量的计算,因为在数据挖掘的过程中,由于没有合适的词典库,因此在数据规约阶段花费了大量的时间,未来需要利用机器学习的方法对这部分进行改进.