文档库

最新最全的文档下载
当前位置:文档库 > 基于Agent和CPN的Web信息传播系统建模研究

基于Agent和CPN的Web信息传播系统建模研究

第22卷第3期

系统仿真学报?V ol. 22 No. 3 2010年3月Journal of System Simulation Mar., 2010 基于Agent和CPN的Web信息传播系统建模研究

贺筱媛,胡晓峰,罗批

(国防大学信息作战与指挥训练教研部, 北京 100091)

摘要:Web信息传播问题的复杂性是系统宏观结构和微观个体行为两方面因素共同作用的结果。

在分析Web信息传播建模难点及解决思路的基础上,研究了将基于Agent的仿真方法和Petri网的

描述机制相结合,利用Petri 网擅长描述系统的整体逻辑结构和动态特性的优长,将Agent对系统

个体特性和交互规则的仿真溶入到着色Petri网(CPN)描述的系统动态行为之中,使仿真分析和

逻辑结构分析结合起来,对解决类似的复杂社会系统仿真提供一种新的思路。

关键词:复杂网络;信息传播;建模方法;CPN;Agent建模

中图分类号:TP391.9 文献标识码:A 文章编号:1004-731X (2010) 03-0715-05 Modeling Method Research of Web Information Diffusion Based on Petri Net

HE Xiao-yuan, HU Xiao-feng, LUO Pi

(The Department of Information Operation & Command Training, NDU of PLA, Beijing 100091, China) Abstract: The complexity of Web information diffusion problem is the result of two aspects of factors: both macro systematic structure and micro individual behavior. Based on the analyzing of the key point and solution of Web information diffusion modeling, the method was studied which combined the Agent-based simulation and Petri Net description mechanism. The total logic architecture and dynamic properties of the system were constructed by Petri Net. Simultaneously, the Agent method was employed to make the simulation of the individual characteristic and interaction rules of the system elements dissolved into the systematic dynamic behaviors of the CPN (Colored Petri Nets), so that the simulation analysis and logic structure analysis could be combined, and a new approach was provided to the solving of similar complex society system simulation.

Key words: complex network; information diffusion; modeling method; CPN; Agent

引言

Web网的本质功能是信息传播,基于Web的信息传播存在大量不确定的、复杂的交互因素的影响,具有群体涌现性、自适应性等典型复杂系统特征。基于Web的行为建模与仿真是研究危机条件下网络信息传播及影响的重要内容。

目前的复杂网络传播问题研究大多是以经典的传染病传播模型(SIS和SIR)为基础进行的,且大多属于泊松模型(Poisson model)或临界值模型(Threshold model),未考虑各传染个体相互之间暴露的相关性[1,2]。而基于Web网的信息传播归根结底是人的行为,既有传播模式、传播结构的复杂性,又有传播参与者行为的多样不确定性及历史行为相关性,单纯地采用自底向上或是自顶向下的分析建模方法,都只能是管中窥豹,缺乏足够的可信性。

迅速发展的复杂系统、复杂网络研究成果为理解和研究基于Web的信息传播行为提供了新的视野和有力的工具。其中,基于Agent的建模仿真方法通过多Agent及交互来描述系统的复杂性,非常适用于解决经济系统、生物系统等社会系统中的演化、涌现、自组织等复杂性问题,但基于Agent

收稿日期:2008-04-15 修回日期:2008-08-30

基金项目:国家863项目(2006AA01Z337)和国家自然科学基金 (60774035,60874086)

作者简介:贺筱媛(1968-), 女, 陕西人, 博士生, 研究方向为战争模拟系统与环境。的方法在分析系统整体结构,尤其是逻辑和动力学特性方面略显不足。Petri 网是一种对离散事件动态系统进行逻辑层次建模的有效方法,很适于分析系统的动态特性及因果依赖等关系,但Petri 网的缺陷是对系统的仿真模拟能力不足。因此,如能将Agent 和Petri 网结合起来构建离散事件动态系统模型,从而将仿真分析和逻辑结构分析结合起来,将对解决类似的复杂性问题建模提供一条可行的思路。

近年来,不少学者对Agent和Petri网相结合的建模方法进行了研究。如Jin等[3]采用非再生随机Petri 网建立和分析多Agent 系统中Agent 的概率行为;Xu 等[4]扩展面向对象Petri网,侧重于利用Petri 网构建Agent,在此基础上利用Petri 网表示Agent 之间的消息交互,并利用Petri 网的理论分析整个系统的性能;Hiraishi[5]基于P/T 网,以Agent 构造令牌,Agent 本身也由

基于Agent和CPN的Web信息传播系统建模研究

P/T网构造,形成网中网;Abouaissa 等[6]用Agent 表示系统元模型中的角色,体现Agent 的行为,Agent 的相互关系遵循角色间的关系,将Agent 作为着色Petri 网中的变迁,构建系统的着色Petri 网模型分析系统的性能。

本文第1节首先分析了Web网信息传播特点及建模难点,在此基础上确定了将Agent和Petri网相结合的建模思路。第2节采用自底向上的Agent方法定义系统个体及相互作用,然后在第3节自顶向下将Agent的行为与CPN构造系统网模型溶合起来。

2010年3月系统仿真学报 Mar., 2010

1 Web网信息传播模型建模思路

1.1 Web网信息传播的复杂性原因

Web网信息传播与以往的复杂网络传播问题相比,主要有两点不同:

宏观上,传播结构具有复杂多层交互性。Web网信息传播系统是一个具有三网一体结构的动力学系统,涉及三个不同层次的复杂网络(如图1所示)。Web网是目前规模最大的复杂网络系统[7],其节点是网页,边是网页间的超链接;网民关系网中的节点是网民,边是网民之间在现实或虚拟社会中的关系;当网民在虚拟或现实信息环境刺激下,以Web 网为媒介发生信息传播行为时,才生成信息传播网。信息传播网的节点是Web网的各类信息发布平台(网站),边是平台之间的传播关系。这三张网把传播系统行为划分成三个相互关联的阶段,每个阶段的作用对象、影响因素等各不相同;

图1 Web网信息传播系统结构

微观上,个体传播行为具有自主不确定性。网民行为的个性化、Web网丰富的传播和反馈模式,使Web网传播系统具有典型的动力学系统的历史性和路径依赖的特点,以往一概而论以假设的传播概率为前提建立数学模型的方法显然难以成立,故合理的“传播概率”必须要体现时间、网民个体属性、传播系统的动力学反馈,以及个体行为的自适应性、随机性等因素的影响。

1.2 建模思路分析

上述分析可知,基于Web网的信息传播过程涉及分布的、复杂动态、不同种类和层次的网络及个体,既有宏观层次系统结构和传播机制层面上的复杂性,又有微观层次系统元素的个体状态和交互作用带来的不确定性。

为此,本文采用基于Petri网的动态体系结构建模框架构造传播系统的内部结构和系统动态演化行为,以基于Agent的复杂系统建模仿真方法描述传播系统各类个体元素之间的复杂多样的交互模式和行为特征。即:在宏观层次上,将依据复杂网络和系统动力学理论,使用Petri网搭建系统框架结构和系统行为,侧重于描述Web网信息传播系统三网一体的传播结构和传播系统的动力学行为;微观层次则借鉴传播学、社会学等领域的研究成果,在Petri网系统框架之上,把网民、网站等系统元素作为Agent个体,使用Agent 的方法描述系统内部元素各自的个体特性和行为特征,着重描述个体属性和交互与传播行为的关系,使独立的微观个体行为与宏观系统的演化机制有机结合起来。

2 基于Agent的系统元素描述

2.1 Agent的分类及属性

Web信息传播过程主要包括两类Agent个体:网民Agent和网站平台Agent,其个体特性及交互规则分别定义如下:

定义2.1:网站Agent的主要属性定义

Site-Attributes = (Id, type, trust, influence, num_login, num_ read, num_ comment, status)

其中Id:网站Agent的唯一标识号,类型为整数;

type:网站类型,type=1为商业门户类网站,type=2为传统媒体类网站,type=3为政府类网站,type=4为其他类型的网站;

influence:网站的影响力,类型为[0,1]区间上的实数,代表了网站的日常访问量、在网民中的知名度,与该网站在Web网中的节点度成正比;

trust:网站的公信力,即个体对网站的信任程度,类型为[0,10]区间上的整数,可依据类型和影响力共同确定;

num_login:登录网民数,类型为整数;

num_read:网民浏览数,类型为整数;

num_comment:网民评论数,类型为整数;

status:status=0为“易感态”(信息尚未在该网站发布),status=1为“感染态”(信息已发布)。

定义2.2:网民Agent的属性定义

Netizen-Attributes= (Id,tpye,Pri_behavior,type_behavior ,status) 其中Id:网民Agent的唯一标识号,类型为整数;

type:网民类型(按上网动机和行为特点区分)。normal_type=1为普通型(上网的主要目的是获取信息),active_type=2为活跃型(有较强的表达和交流愿望),professional_type=3为职业型(代表媒体,或从事与传播职业的人,以发掘、制造、引导信息焦点或热点为职业,其传播能量大于前两类);

Pri_behavior:网民的信息偏好。重点关注三类:新闻、论坛和博客,可利用CNNIC的统计数据建立信息偏好与网民类型的关联;

type_behavior:网民的传播行为类型。Read_type=1为浏览模式,指标题或内容吸引网民点击浏览的兴趣;comment_type =2为交流讨论模式,指以发表评论、跟帖等形式与他人交流讨论;copy_type =3为转发复制模式,指以新闻、博客、论坛主帖等形式表达自己的见解或态度,是对源信息的变形、衍生、加工;ignor_type =4为忽略模式,即对信息不感兴趣,无任何传播行为。

status:status=0为“易感态”(尚未获悉信息),status=1为“感染态”(已获悉)。

传播反馈

访问万维网

网民关系网

信息传播网

2010年3月 贺筱媛,等:基于Agent 和CPN 的Web 信息传播系统建模研究 Mar., 2010

2.2 Agent 的交互规则

Agent 是基于规则的刺激-反应实体,但网民兴趣爱好、传播习惯、思维过程等是一个难以准确描述的问题,只能通过假设对此作出可能的简化处理。

假设一:信息内容是有关政治、外交、经济、军事等的重大或危机事件,按相应事件的重要度,将信息价值info_value 用[0,10]上的数值表示。对这类引发大众关注焦点或将产生重大影响的事件,假设网民将采取理性客观、普遍关注的态度,对信息的关注程度将由信息价值info_value 决定;

假设二:网民的传播行为偏好虽然不同,但依据不同类型网民的上网目的、各种传播方式从本质上所体现的不同的Web 信息传播机制,可假设每类网民将都有一种“主传播方式”(Pri_mode)。“主传播方式”与网民类型type 的对应关系为:normal_type=1时,Pri_mode=1; active_type=2时 Pri_ mode =2,professional_type=3时,Pri_mode =3。

此外,Web 信息传播模型中的“信息”,是特指作为建模要素的目标信息,其余的海量信息只能看作环境的有机组成部分。

基于以上假设,当网民访问网站时,决定其对目标信息“传不传”、“如何传”的交互定义如下:

规则2.1:网民传播行为规则定义

1、设S i 为某网站 Agent (Id, type, trust, influence, num_ login, num_read, num_comment ,status),N i 为网民Agent (ID, Tpye ,Pri_behavior ,Type_behavior ,status),其发布的信息价值为info_value;

2、网民N i 登录S i 的概率为P 1,

1()i

i

i

d P f influenc

e d ==

∑ 其中,influence 是网站S i 的影响力,d i 为网站S i 在Web 网中的节点度,d i 服从Power-Law 分布;

3、N i 浏览该新闻的概率P 2=P 1*g (info_value ),g (info_value )是信息的时效性函数:

()t -g info_value e info value ?=×λ

4、N i 以概率P 3选择该类型网民的主传播方式进行传播,P 3=P 2*SIF(S i ), 选择ignore_mode 的概率为1-P 3,其中:

()t

t

i t

num_read num_comment

SIF S num_login

αβ×+×=

∑∑∑

SIF(S i )为网站S i 的传播强度(具体定义另文详述),α、β为网民N i 的随机从众系数,Num_login,Num_read, Num_ comment 为网站S i 的动态属性值;

5、N i 选择相邻节点进行人际传播的概率为P 4[0∈,1],接受其它传播方式的概率为P 5[0∈,1]

以上规定定义了网民对传播方式的选择,但不同传播方式从本质上反映了不同的传播机制,将对传播网的演化产生

不同的作用。其中,浏览只是增加了网民中信息的知晓范围;交流讨论会促使平台意见气候的形成,从而吸引更多网民的关注和参与;而转发复制是跨越平台的传播行为,会真正增加“已感染节点”的数量。因此,还需定义传播网的演化规则。以下规则中涉及的网站都是目标信息

规则2.2:传播网演化规则定义

1、设网民N i 与网站S i 交互时按规则3.1所选择的传播模式由网民的type_behavior 属性来标识,网民N i 对目标信息的获悉状态由网民Agent 的status 属性来标识, 目标信息在各网站的分布情况由网站Agent 的 status 属性来标识;

2、当网民N i 与网站S i 交互时的传播模式type_behavior =1时,网站S i num_read= num_read+1,网民N i 的status=1;

3、当网民N i 与网站S i 交互时的传播模式type_behavior =2时,S i num_read= num_read+1,num_comment = num_ comment+1,网民N i status=1;

4、当网民N i 与网站S i 交互时的传播模式type_behavior =3时,网民将以随机概率P 5选择网站S g :=(Max(influence(g )) with status(g )=1) ∨ (Max (influence(g ) with status(g )=0)作为传播的目标网站,以概率1-P 5选择任一网站S g ’作为目标网站,并令目标网站status(g )=1或status(g ’)=1,网民N i status=1。

此处仅对网民传播行为规则和传播网演化规则进行了简单的定义,实际的系统要素之间还存在更丰富、更复杂的交互行为,将另文详述。

3 基于CPN 的传播系统分析

3.1 Petri 网简介

Petri 网是一种适用于多种系统的图形化、数学化建模工具,既可以用于静态的结构分析,又可用于动态的行为分析,特别适合于描述系统内部的组织结构和系统状态的改变。作为一种图形化的工具,Petri 网可表达数据流程图和网络图相似的概念;作为一种数学化的工具,它可以用来建立状态方程、代数方程和其它描述系统行为的数学模型[8]。

Petri 网有四种系统元素:库所(Place)、变迁(Transition)、弧(Arc)和令牌(Token)。它用库所、变迁、弧的连接标识系统的静态结构,通过变迁的激发和令牌的移动描述系统的动态行为。Petri 网的元素具有二元性。库所代表发生条件、地点、资源等被动元素,变迁代表事件、动作、消息的发送/接收等主动元素,这两类元素组成的集合互不相交;Petri 网还具有局部确定性。一个变迁的行为仅仅取决于它的局部环境,这由变迁的输入和输出集合以及变迁本身来定义。

着色Petri 网(Colored Petri Nets,CPN)作为一种高级的Petri 网模型,进一步扩展了Petri 网的令牌机制,使它具有颜色(Color)和类型(Type),可用于描述复杂的数据对象,并对变迁和弧加上发生条件约束,大大增强了Petri 网的建模功能。

2010年3月 系

统 仿 真 学 报 Mar., 2010

Petri 网的图形表示特征:用圆形表示库所,用矩形或粗杠表示变迁,作为高级网的特性,变迁上可以有铭记(Inscription ),以表示这个变迁实施的进一步条件,以及进行必要的计算,还可以调用外部方法完成较复杂的计算。

选择高级Petri 网作为建模工具,考虑的主要需求有: 1.能反映信息传播过程中各阶段不同的动力学机制和算法,以及算法的控制语义与数据流;

2.能同时进行静态结构与动态行为的建模,并反映系统元素的并发、随机、行为条件和约束等特性;

3.便于运用相关的统计信息,分析算法的合理性和可信性;

3.2 面向Agent 的Petri 网构模

传播系统的宏观行为、结构等特征来源于各Agent 个体及相互作用,而宏观特征又能反馈回来进一步刺激或约束Agent 个体及行为,因此,Petri 网模型的构建应体现这种微观和宏观关联的双向性,在反映Web 信息传播系统的宏观静态结构基础上,其动态行为须以网民个体行为的建模一致起来。

首先,以某网民N i 访问网站S i 为例,其行为过程可用图2(a)所示的Petri 网模型表示其Web 信息的传播过程。库所S 1和S 2分别代表网民N i 和网站S i ,其token 类型分别为两种不同类型的Agent ;T 1表示N i 选择并登录网站的行为(双向弧代表网民重新选择目标网站);S 3代表N i 对S i 的访问状

态;T 2表示N i 在此浏览、发现感兴趣的信息、并自主选择传播方式的行为(符号“ ”表示AND/OR-Split );S 4、S 5、S 6、S 7可看作是由不同的传播行为所“构造”的信息传播网元素(见图1);当T 3发生时,表示N i 退出S i 。S 3及S 4、S 5、S 6、S 7为网民与网站的交互库所,其token 类型由两类Agent 共同确定。

其次,将图2(a)的S 1细化为图2(b)的多个网民库所,同理,T 1细化为对应的多个变迁,则S 1和T 1可分别看作是网民库所及对应变迁的折叠(folding),即cd(S 1)={N i │i = 0,1,2,3,…}(N i 为网民Agent 的实例),cd(T 1)? Bag(cd(S 1))× Bag(cd(S 2)),图2(a)即为图2(b)的抽象结果。由于在Agent 的描述机制中用可利用个体属性来区别不同的系统要素,用规则来定义系统要素之间的交互行为,因此,图2(b)在遵从个体属性和交互规则的约束下,与图2(a)所示的动态行为是一致的,图2(a)可以看作是图2(b)的更自然、更紧凑的表现方式,抽象后库所的token 类型不变,其颜色集由各Agent 的属性值确定,token 的数量为其中包含的Agent 个体数量。变迁的作用依然是依据其输入库所的token ,来确定其输出库所的token 分布,只不过各变迁的建模已由个体的原子动作扩展为建立在基于统计的Agent 行为概率之上的宏观行为模型,用事件发生的概率分布函数来定义,并由Agent 之间的交互规则来约束。对图2(a)的网站库所S 2可同理进行折叠操作。

基于Agent和CPN的Web信息传播系统建模研究

基于Agent和CPN的Web信息传播系统建模研究

基于Agent和CPN的Web信息传播系统建模研究

基于Agent和CPN的Web信息传播系统建模研究

基于Agent和CPN的Web信息传播系统建模研究

图2 基于CPN 的Web 信息传播系统模型

2010年3月 贺筱媛,等:基于Agent 和CPN 的Web 信息传播系统建模研究 Mar., 2010

进一步地,对图2(a)扩展其它影响网络传播的系统行为(见图1的Web 信息传播系统结构中的“反馈”流),则得到图2(c)的Web 信息传播系统Petri 网模型。其中,事件①~③分别与图2(a)的T 1~T 3等价,

图2(c)的T 2~T 5可以并发发生;S 8表示处于现实社会信息环境中的网民,其token 类型为网民,颜色集为网民Agent 的属性;T 7表示网民接受传统的大众传播、人际传播等的影响;各种传播模式S 4、S 5、S 6、S 7汇集起来形成信息传播网S 9;T 8表示S 9通过网站的自动更新和网络服务(如排行榜、热帖推荐)等与网站S i 溶合,完成Web 系统的反馈。S 3、S 4、S 5、S 6、S 7为网民与网站的交互库所,其token 由两类Agent 共同决定。

形式化的,对面向Agent 的CPN 模型的定义如下(各库所及变迁的描述见表1)。

表1 库所及变迁定义

类别 名称 含义 状态或算法描述

S 1 Web 网,

Cd(S 1)= netizens ,无尺度网络

S 2 网民关系网, Cd(S 2)= sites,小世界网络 S 3 网民登录网站 Cd(S 3)= cd(S 1×S 2)= login S 4 浏览态 Cd(S 4)=diffuse_net ,见规则3.1 S 5 讨论态 Cd(S 5)=diffuse_net ,见规则3.1 S 6 复制传播态 Cd(S 6)=diffuse_net ,见规则3.1 S 7 忽略态 Cd(S 7)= diffuse_net ,见规则3.1 S 8 现实态 Cd(S 8)=logout

库 所

S 9 传播网 Cd(S 9)= diffuse_net, 节点为感染态

网站, 边为传播关系

T 1 网民选择并登录网站 1()j

i

i

d P f influenc

e d

==∑

T 2 浏览信息 21(10)t

P P e

info value ??=××÷λ

T 3

参与交流讨论

P 3=P 2*SIF(S i ), SIF(S i )定义见规则3.1, T 4 创建新的信息源

同上

T 5 对信息不感兴趣 1-P 3

T 6

退出

T 7 其它传播(人际传播、大众传播)

P 4、P 5,见规则3.1

变 迁

T 8

网站更新传播态势 见规则3.2 定义3.1:基于CPN 的Web 信息传播系统网模型WIDM (Web Information diffuse model)是一个六元组,WIDM = (S,T ,Pre, Post, C ,cd)

其中:S ={S l ,S 2,…S 8},为库所集合;T = {T 1,T 2,…T 8},由含有为变迁集合;Pre, Post 分别是向前和向后的关联矩阵,定义相关变迁所消耗和产生的token 的颜色之间的对应关系;C ={netizens,sites ,logon, diffuse_net}为颜色类集合,代表了所有系统要素对象,Netizens={N 1,N 2,…N |I |},

|Netizens|=I , WebSites={S 1,S 2,…S |J |},|WebSites|=J ;cd:S ∪T →C 是颜色域的映射, cd(S i )=Agent_objects, cd(T i )由对应的连接弧(S i ,T i )∈S ×T ,通过计算cd(S i )来得到。

由面向Agent 的CPN 模型的构模过程可知,WIDM 是在基本的Petri 网模型基础上,通过“折叠”和“扩展”得到的。“折叠”是将各Agent 的建模重叠为着色Petri 网中的库所,各库所的颜色由其所容纳的Agent 对象建模,颜色值代表了Agent 的属性值,token 个数由Agent 的数量来确定,。变迁参数化为多Agent 的各种交互行为所定义的发生概率的分布函数,各分布函数的变量是与之相连的库所的颜色集(如:T1的变量集合是{N i ,S i ,L i },各变量的类型分别是:dom(N i )= netizens, dom(S i )= sites, dom(L i )= logon )

,连接弧替换为弧向量,弧向量的每一维对应于Agent 属性值或交互规则约束下的行为发生概率;“扩展”是在Agent 个体行为的基础上,增加系统宏观行为,以体现微观和宏观的关联是双向性。

4 结论

采用Agent 和Petri 网相结合的方法,既能利用Petri 网建模简单直观、逻辑性强、便于分析系统整体的动态特性等优点,又能发挥Agent 便于描述个体相互作用、便于人类行为社会性、适应性、随机性的仿真等特性,从而在仿真机制上将个体行为与系统行为有机结合,在分析机制上将个体仿真分析和系统逻辑结构分析有机结合起来。

参考文献:

[1] 郭雷, 许晓鸣. 复杂网络[M]. 上海: 上海科技教育出版社, 2006. [2] Dodds P S, Watts D J. Universal behavior in a generalized model of contagion [J]. Phys. Rev. Lett. (S0031-9007), 2004, 92(21): 218-701. [3]

Jin Q, Yano Y , Sugasawa Y . Modeling and Analysis of Agents’ Probabilistic Behavior by a Non-Regenerative Stochastic [C]// IEEE International Conference on SMC, 1996. USA: IEEE, 1996.

[4]

Haiping Xu, Sol M Shatz. An Agent-based Petri Net Model with Application to Seller/Buyer Design in Electronic Commerce [C]// Proceedings of 5th IEEE International Symposium on Autonomous Decentralized Systems, 2001. USA: IEEE, 2001: 11-18.

[5] Hiraishi K. A Petri-net-based Model for the Mathematical Analysis of Multi-agent Systems [C]// Proceedings of SMC, 2000. USA: IEEE, 2000: 3009-3014.

[6] Abouaissa H, Nicolas J C, Czesnalowicz E. Formal Specification of Multi-Agent Systems :Approach based on Meta-Nets-Case Study of a Transportation System [C]// Proceedings of IEEE International Conference on SMC, 2002. USA: IEEE, 2002.

[7] Albert R, Jeong H, Barabási A L. Diameter of the World-Wide Web [J]. Nature (S0028-0836), 1999, 401: 130-31.

[8]

范玉顺. 工作流管理技术及其应用[M]. 北京: 清华大学出版社, 2001.