曹黎侠
(西安工业大学理学院,陕西西安 710032)
近年来,科学界发现大量的真实网络具有与规则网络和随机网络都不相同的特征,并将这种无规律的网络称为复杂网络[1-4].钱学森认为,具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络.复杂网络虽然已经众所周知,但目前还没有一个严格的定义[5-6].那么怎么判断一个网络是否是复杂网络呢?文献[7-10]指出,复杂网络一般具有结构复杂、网络进化、连接多样性、动力学复杂性、节点多样性和多重复杂性融合等特征.近几年来,大量关于复杂网络的文章发表在Science,Nature,PRL,PNAS等国际一流刊物上,说明复杂网络已经成为一个新兴的研究热点[11-17].
目前国内外关于复杂网络的研究主要集中在复杂网络建模、同步、控制、博弈、传播、节点重要性指标、传播动力学和鲁棒性分析等方面[18-21].但是,所有这些研究成果都是针对节点具有确定性和边的连接信息具有完全性的确定性复杂网络的.一些现实网络往往节点具有不确定性,边的连接具有不可分辨性.如在电影演员合作网络中,默认电影演员是确定的,研究其相互之间合作的一个复杂网络;而实际上某一个演员他都会与哪些演员合作,与他合作的这些演员又与谁合作,事先都是不确定的;另外,一个演员是否与另一个演员合作或成为潜在的合作者,这些信息也是不可分辨的,这样的复杂网络定义为粗糙复杂网络,这样的电影演员合作网络称为粗糙电影演员合作网络.
遗憾的是,到目前为止还很少有基于粗糙集[19]的不完全信息复杂网络的相关研究成果.文献[20]将粗糙集和传统图论相结合,给出基于粗糙集思想的粗糙图的定义,但是并没有把粗糙图与现实的复杂网络相对应;文献[21]给出粗糙属性图的概念,并对粗糙属性图的粗糙特性进行分析,得出粗糙属性图的精度与顶点和边集属性划分程度有关的结论,但这也只是对粗糙属性图所做的一些研究成果,不能完全解决不完全信息复杂网络上的问题.因此,文中提出了粗糙复杂网络的概念,实现该类复杂网络的概念和性质研究;通过构建实际的粗糙复杂网络并研究其静态几何特征,表明本文的概念设计能够满足一些实际问题的需求.
粗糙集理论的主要思想就是在保持分类能力不变的前提下,通过知识约简导出问题的决策或分类规则.所谓知识约简,就是在保持知识库分类能力不变的条件下,删除其中不相关或不重要的知识.令X是U的一个子集,R为U上的一个等价关系,当X能表示成某些R基本范畴之并时,称X是R可定义的;否则称为不可定义的.R的可定义集称为R的精确集,而不可定义集称为R的粗糙集.粗糙集的下近似和正域是由那些根据知识R判断肯定属于X的U中的元素构成的集合;上近似是那些根据知识R判断可能属于X的U中的元素组成的集合;边界域是根据知识R既不能判断肯定属于X又不能肯定判断属于~X的U中元素构成的集合;负域是那些根据知识R判断肯定不属于X的U中元素组成的集合.
文献[6]指出,刻画一个复杂网络最基本的三个特征量是度分布、集聚系数和平均距离.在复杂网络中,节点Vi的邻边数目ki称为节点Vi的度;对网络中所有节点的度求平均,得网络的平均度:
k
定义P(k)为度为k的节点在网络中所占的比率,称之为网络的度分布,一般用直方图描述度分布性质.节点Vi到Vj所要经历的边的最小数目称为这两个节点之间的距离;网络中所有节点对之间距离的平均值称为网络平均距离,即
平均集聚系数是指在网络中与同一节点连接的两节点之间也相互连接的平均概率.
作为无向网络的静态特征,比较重要的概念还有介数,它反映了节点和边在整个网络中的作用和影响力,设Njl是节点Vj和Vl之间的最短路径条数,Njl(i)表示节点Vj和Vl之间的最短路径路过节点Vi的条数,则Vi的介数为
Vi的介数就是网络中所有最短路径中经过该节点的数量的比例.类似地,边的介数Bij定义为网络中所有最短路径经过边eij的比例.
在电影演员关系网络中,某个演员与哪些演员合作,以及合作者的合作者是谁,都是不确定的.如果把当前收视排行榜在前十的影片的所有演员和剧务人员看作论域U,其中的电影演员组成了X;设网络中节点的关系可以在邻居之间传递,则R为U的一个等价关系,R={合作关系,朋友关系,同学关系},由于有些具有朋友关系的人同时也是合作关系或是同学关系,因此X不能表示为R基本范畴之并,即X是R的粗糙集.电影演员关系网络的顶点具有粗糙集的特点,所以被认为是粗糙顶点复杂网络.
在第三方支付平台交易中,以商品和商家为节点,顾客随机浏览、收藏和购买商品,以顾客浏览点击为连接边,构成了第三方支付平台交易的复杂网络.由于顾客浏览具有很大的随机性,浏览的商品是否收藏和购买具有信息不完全性.设平台中的商品和商家的链接构成了论域U,网站上销售的某些品牌的手机及其销售商的链接组成了X;设网络中边的连接关系可以相邻传递,则R是顾客行为的选择,R={收藏,购买}.通常情况下,顾客浏览过的商品,先收藏,再从收藏品中择优购买,因此R是U上的一个等价关系,且X不能表示为R的基本范畴之并,所以第三方支付平台交易复杂网络的边集具有粗糙集的特性,是一个粗糙边复杂网络.
定义3粗糙顶点复杂网络RCNV和粗糙边复杂网络RCNE通称为粗糙复杂网络;如果一个复杂网络既是粗糙顶点复杂网络RCNV,又是粗糙边复杂网络RCNE,记为RCN=(RCNV,RCNE).
定理1给定复杂网络CN,则对任意的等价关系RV,RE,有
(1)CN为精确复杂网络,当且仅当
(2)CN为粗糙复杂网络,当且仅当
类似于电影演员关系网络和第三方支付平台交易网络,如果一个复杂网络的顶点集具有不确定性,边集具有信息不完全性,都认为是粗糙复杂网络.和粗糙集一样,复杂网络的不确定性和信息不完全性,是由其顶点集和边集的边界域的存在而引起的,其边界域越大,精确度越低.为了更准确地表达这一点,引入粗糙复杂网络精确度的概念.
显然,精确复杂网络的精确度为1.
定义5粗糙复杂网络RCN的精确度为粗糙顶点复杂网络RCNV的精确度和粗糙边复杂网络RCNE精确度的乘积,即
α(RCN)=αV(RCNV)×αE(RCNE).
定义6称ρ(RCN)=1-α(RCN)为粗糙复杂网络的粗糙度.
定理2(1) 给定粗糙复杂网络RCN,对任意的等价关系R及X⊆U,都有
0≤α(RCN)≤1,0≤ρ(RCN)≤1;
(2)粗糙复杂网络RCN为精确复杂网络当且仅当α(RCN)=1,ρ(RCN)=0.
证明(1) 由粗糙复杂网络的定义1和定义2可知,
从而0≤α(RCN)≤1.根据定义6可得
0≤ρ(PCN)≤1.
α(RCN)=1,ρ(RCN)=0. 】
描述一个复杂网络的静态几何特征,常用的指标有平均距离、集聚系数和度分布.在实际网络中,网络节点都具有一定的实际价值和地位,如第三方支付平台交易的粗糙复杂网络中,度相同的节点价格不同,带给商家的效益是不同.为了解决实际问题的需要,引入粗糙复杂网络的平均距离区间、粗集聚系数和加权度的概念.
定义9网络加权平均度为
其中,N1为下近似网络的节点数;ωi为节点权重;ki为节点的度.
其中N2为下近似网络的节点数.
定理3粗糙复杂网络的下近似粗糙复杂网络与上近似粗糙复杂网络的度分布函数类型相同.
故粗糙复杂网络的下近似粗糙复杂网络与上近似粗糙复杂网络的度分布函数类型相同. 】
在实际网络中,网络加权度可以作为衡量一个节点重要性的指标,但是网络中也存在一些节点,虽然它的加权度很小,但它可能是两个社团的中间联系人,没有了它,整个网络的信息会中断.因此,引出粗糙复杂网络中的另一个重要的全局几何量——粗介数.
分别为粗糙复杂网络RCN的节点i和边eij的粗介数.
光谱衍射效率可以根据图的纵坐标的光强衍射强度与基准光强度的相对比值,可得到在特定波长下的光谱衍射效率,其计算公式为其中I0为原始光谱的总强度,I(为经衍射后的光谱强度,Imin为噪声强度[8]。运用MATLAB对衍射强度信息编程计算,最终得到光谱衍射效率,其部分光谱衍射效率如图9所示。
显然,在粗糙复杂网络中,节点或边的粗介数是网络所有最短路径中路过节点i(或边eij)的比例.粗介数越大,节点(边)在网络中的地位越高.
在第三方支付平台交易网络中,由商品和顾客浏览信息的特点构造第三方支付复杂网络,对应了粗糙集的论域U;如果规定,顾客购买商品前先收藏再在收藏品中择优购买,则顾客收藏的商品及其链接形成了上近似复杂网络,购买商品及其链接形成了下近似复杂网络,从而构建出第三方支付粗糙复杂网络.在该网络中,浏览而未收藏的商品及其链接为粗糙复杂网络的负域,收藏而未购买的商品为粗糙复杂网络的边界域,如图1所示,其中双粗白线及其链接节点为下近似网络,白线及其链接节点为边界域,黑线及其链接节点为网络负域.
图1 第三方支付粗糙复杂网
在第三方支付平台交易中,人们更多关心的是网络的局部特性,这些性质往往和复杂网络的静态几何特征相关.以2016-12-10 9:00~12:00淘宝支付平台“天猫商城”4个品牌的商品共176款手机及其相互连接的复杂网络作为研究对象,收集上近似复杂网络节点和下近似复杂网络节点的属性集,其中有效的上近似网络节点有91个,下近似网络节点52个.该粗糙复杂网络的精确度
图2 第三方支付粗糙网络的下近似网络
图2是它的下近似复杂网络.据定义11得到下近似网络图的加权度及其概率分布如表1所示.
表1 下近似度的概率分布表
由定义1~12可得该粗糙复杂网络的静态几何特征如下:
2)粗集聚系数.定义8指出,粗集聚系数是衡量网络集团化程度的参数.利用Gephi软件,可以得到整个网络的聚类系数为0.183.即第三方支付网络聚类系数较小,说明该粗糙网络结构比较松散,商品之间发生信息交流关系并不活跃,反映了网络销售的竞争性和商业机密性.
3)粗介数.定义12指出,粗介数越大,说明该节点在网络中的地位越高.在图2中,运用Dijkstra算法和介数的概念,可得图2介数最大的是节点37,即
在整个粗糙复杂网络RCN中,粗介数
说明节点37在粗糙复杂网络中的地位比较高.
将不完全信息网络命名为粗糙复杂网络,设计出一种比较完整的理论体系,为粗糙复杂网络的舆情传播、搜索、网络博弈等问题的研究奠定了理论基础.
1)基于粗糙集理论在不确定性问题处理中的优势,从数学的角度定义了不完全信息复杂网络——粗糙复杂网络,研究了它的几何特征.与以往的研究相比,本文的研究更系统、更精确,形成了比较完备的理论体系.
2)构建了一个实际的粗糙复杂网络,研究了该粗糙网络的度分布,得出了该网络具有无标度网络的特性;计算了实际粗糙复杂网络的平均距离区间、粗集聚系数、粗介数,实现了本文所给概念的实际应用,说明了本文概念的有效性和合理性,也有助于加深对概念的理解.