异质边多重图网络模型研究

2017-12-22王娜娜高红刘巍

智能系统学报 2017年4期

关键词：物元异质关联

王娜娜，高红，刘巍,

(1. 大连海事大学交通运输管理学院，辽宁大连116026； 2. 大连海事大学数学系，辽宁大连 116026)

异质边多重图网络模型研究

王娜娜1，高红2，刘巍1,2

(1. 大连海事大学交通运输管理学院，辽宁大连116026； 2. 大连海事大学数学系，辽宁大连 116026)

在物流网络中，为实现物流节点之间的异质边的统一性度量，运用可拓学中的基元理论构建了一种基于物元特征的异质边多重完全图网络模型，该网络模型适用于物流中心和物流配送中心共同具有的功能，其功能有运输功能、储存功能、包装功能、流通加工功能、信息处理功能,功能特征之间是异质，每一个功能特征决定了两物流节点间相连接的一条边。在每个功能特征建立一个关联函数，关联函数值作为边权，实现了物流网络的统一性度量，同时也为物流网络优化提供便利。

复杂网络；多重边；多重图网络；异质边；可拓学；物元；二维可拓距；二维位值

复杂网络的研究在复杂系统中有重要的应用[1-3]。在复杂网络中，物流多重图网络的突出特点是节点间可以有多种运输方式可以选择，可以选择铁路运输、公路运输、航空运输等。

在应用图论工具研究复杂网络时，通常是针对无多重边的网络研究，但是多重边复杂网络比通常的单边复杂网络在拓扑结构、节点动态特性等性质方面有着更为复杂的形态，从而需要更合适的模型表达方式和更实用的解决方案。

马啸来[4]建立了同一位置有多个物流节点和物流路径可供选择的、以多重图作为拓扑形式的物流链选择决策模型，并讨论了将其转化为简单图的求解算法。高洋等[5]根据网络中边的不同性质提出了网络拆分的思想, 通过引入时滞进行拆分, 从而建立了多重边复杂网络的动力学模型；安新磊等[6]在通常公交网络模型的基础上,建立了一种新的多重边公交线路网络模型；Acosta-Mendoza等[7]提出一种用于多重图集合中的近似模式挖掘的新算法；Suil[8]提出在一般多重图中特征值边缘连通性的新方法；Haxella[9]提出没有小密集子集的边缘着色多重图，给出多重图色度指数的推论结果；Yang[10]提出通过多重图排名的鲁棒视觉跟踪原创研究文章来探讨图的排名和多个组合方法；Chakareski[11]给出多重图分析选择顶点的方法;文献[12]针对SF和ER网络，研究了随机攻击条件下层级网络间的依存强度对系统的作用效果；Stippinger[13]提出交织型层级复杂网络，它是用于描述子网络交织关系的密切程度。

本文依托物流网络的应用背景，试图引入可拓学的基元理论[14-15]，构建一种多重图网络的新模型，这种新型多重图网络模型的特点是其重边具有异质性，并且依据可拓论的思想能够进一步研究这种网络模型的优化问题。

1 基本概念

经典图论中关于图是这样定义的。

定义1 一个有序二元组V,E称为一个图, 记为G=V,E,其中V称为G的顶点集,V≠∅,其元素称为顶点或结点,一般可记为V=v1,v2,…，vm；E称为G的边集,一般可记为E=e1,e2,…,en，其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边, 相应G称为无向图；否则, 称为有向边，相应G称为有向图。

定义2 在图G=V,E中，如果允许有多重边，也就是有至少二个边的二个顶点完全相同，至少有二个顶点可以由二个边相连接，则称G为多重图。图1表示了一个一般性的多重图的示意图。

图1 多重图示意图Fig.1 Multigraph

定义3 若将图G的每一条边e都对应一个实数we,称we为该边的权,并称图G为赋权图(网络),记为G=V,E,w。

定义4 在多重图G中的每一条边e都对应一个实数we,称we为该边的权,并称图G为多重图网络。

定义5 如果多重图G的任何两个不同的顶点之间都有r重边，则称G为r-多重完全图。图2表示3-多重图的示意图。

图2 复杂物流网络示意图Fig.2 Complex logistics network

在经典的多重图网络研究中，一般是将多重边看成是同一性质的连接，每一边e上权we也都是一致的可公度的度量，即要么都是费用，要么都是距离。但是在复杂的物流网络以及更为复杂的社会网络中，多重边的性质往往是不一致的，或者说是异质性的。那么怎么样标度多重图中边的异质性，怎样研究这种复杂网络的性质，怎样实现这种复杂网络的优化，带着这些问题，我们引入可拓学中的基元概念及其可拓性,将其应用到具有异质边的多重图网络模型的构建。

可拓学是研究解决矛盾问题的规律和方法的学科，可拓学理论的逻辑细胞是基元[4]，基元包括物元、事元、关系元。

定义6 以物Om为对象，n个特征Cm1,Cm2,…,Cmn及Om关于Cmii=1,2,…,n对应的量值Vmii=1,2,…,n所构成的n维阵列：

称为n维物元[15]，其中

定义7 设A0是平面上的一个凸区域，Γ0是A0的边界，Px1,x2为平面上的一点，则点Px1,x2与区域A0的二维可拓距[16-17]规定为

式中：P1为区域A0的边界Γ0上的一点。

定义8 二维位值。设A0和A是平面上的矩形区域，且A0⊂A，Γ是A的边界，Px1,x2为平面上的一点，则Px1,x2关于区域A0和A组成的区域套的位值规定为

DP,A0,A=ρP,A-ρP,A0

为二维位值[18]，其中

P2为区域A的边界Γ上的一点。DP,A0,A就描述了点Px1,x2与区域A0和A组成的区域套的位置关系。

基元是有序三元组，是现实世界中“物”、“事”、“关系”的形式化表示，是“质”与“量”的统一体。为了描述多重图中边的异质性，我们将基元概念引入多重图网络中，构造一种新型网络模型。

2 模型构建

针对每个节点之间有r个边的r-多重完全图网络来研究,将模型称之为基于物元特征的r-异质边多重完全图网络模型。

记所构造的网络为G=V,E,F，在G中，顶点集合V中的元素为r维物元M,即V={M1,M2,…,Mn}

式中：cm1,cm2,…,cmr是所有物元M共有的r个特征，任何两个顶点Mi和Mj之间有r重边相连，r个边是不同质的，分别对应特征cm1,cm2,…,cmr，连接示意图见图3。

图3 r重边连接示意图Fig.3 r-Multi-links

可以将该网络边的集合记为E={ei,j,1,ei,j,2,…,ei,j,r|i,j=1,2,…,n}，其中各边上的权的集合记为F,

F=fijcmh|h=1,2,…r;i,j=1,2,…,n

这样构成的网络属于r-多重完全图网络。但是与普通r-多重完全图网络的不同点在于任何两顶点间的r条边是异质的，其异质性由r个特征cm1,cm2,…,cmr所决定，而网络中所有节点(顶点)是同质的。为了描述两个顶点间的关系,还需要引入两个论域上关系的概念。

定义9 可拓关系。设U、V是任意两个集合，且k是U×V到是实数域R的一个映射，称

由于需要描述的是网络两个节点间在某一指定特征上的关系，故此将上面定义的可拓关系再扩充为如下定义的概念。

定义10 基于特征的可拓关系。设V={M1,M2,…,Mn}是前面在描述基于物元特征的r-异质边多重完全图网络中定义的n维物元集，V中物元的r个特征为cm1,cm2,…,cmr针对其中某一cmh,定义

kcmh(u,v)∈(-,+)

称为物元集V上关于特征cmh的可拓关系。其中kcmh(u,v)称为该可拓关系的关联函数。这里，二维关联函数kcmh(u,v)是一个物元集合笛卡儿积V×V到实数域I的映射。本文根据实际应用问题设置其的具体构造。构造思想借鉴文献[19-20]，建立二维简单关联函数。

正域为有限区域A=〈a,b〉×〈c,d〉，且最大值点Mx0,y0∈A，对于不同的有限区域和最大值点的取值不同，建立的关联函数也是不同的，但是对于物流节点的各个功能关联函数构造方法是相同的，关联函数的形状相似，都是锥形的，如图4所示。对于任意一点px,y的二维关联函数构造为

式中：

则kp满足如下性质：

1)kp在p=M处达到最大值，且kM=1;

2)px,y∈D,且x≠a,b,y≠c,d⟺kp>0；

3)px,y∉D,且x≠a,b,y≠c,d⟺kp<0;

4)x=aorb,y=cord⟺kp=0。

图4 关联函数示意图Fig.4 Dependent function

网络权F可以根据可拓关系确定：

根据可拓学的基元理论，采用物元表示网络节点，所有网络节点都具有r个相同特征，特征之间是不同质的，而每一个特征决定了两个相邻节点间相连接的一条边，用不同特征下的关联函数值表示边权，实现异质边的统一性度量，这就为异质边多重边物流网络的处理带来便利。

3 实例

我们提出的这种r-多重完全图网络模型是建立在物元特征基础之上的，对于物流网络的应用背景来说，物流节点的功能特征可以作为网络节点物元的特征。比如物流中心一般具有如下功能：运输功能、储存功能、装卸搬运功能、包装功能、流通加工功能、信息处理功能、结算功能、需求预测功能、设计咨询功能、教育与培训功能等。而对于物流配送中心来说，一般其功能特征主要是配送功能、储存功能、配组功能、分拣功能、衔接功能、集散功能、包装功能、流通加工功能、运输功能、信息处理与提供功能理功能等。物流中心和物流配送中心的共有的功能有运输功能、储存功能、包装功能、流通加工功能、信息处理功能。对于物流中心和物流配送中心的功能量化如下：运输功能、储存功能、包装功能、流通加工功能、信息处理功能分别对应着运输能力、仓库储存量、流通加工量、信息处理能力。本文以图3为例给出Mi和Mj的物元表示。

最大值点在中点取得，根据式(1)构造的二维关联函数构造方法，计算出节点Mi与Mj之间5个功能的5个关联函数，每个特征的关联函数的正域取值及功能特征的取值是根据物流网络的实际情况来定值。

1)计算运输功能的关联度，其中正域为有限区域A1=〈a1,b1〉×〈c1,d1〉，其中，〈a1,b1〉=〈50%,80%〉，〈c1,d1〉=〈70%,95%〉且最大值点M165%,82.5%∈A1，将p145%,85%代入建立二维关联函数构造k(p1):

2)计算储存功能的关联度，其中正域为有限区域A2=〈a2,b2〉×〈c2,d2〉，其中，〈a2,b2〉=〈40,300〉，〈c2,d2〉=〈40,250〉且最大值点M2(170，145)∈A2。

3)将p2100,90代入建立二维关联函数构造k(p2):

3)计算包装功能的关联度，其中正域为有限区域A3=〈a3,b3〉×〈c3,d3〉，其中〈a3,b3〉=〈100,500〉，〈c3,d3〉=〈100,500〉且最大值点M3(300,300)∈A3，将p3350,400代入建立二维关联函数构造k(p3):

4)计算加工功能的关联度，其中正域为有限区域A4=〈a4,b4〉×〈c4,d4〉，其中〈a4,b4〉=〈200,400〉，〈c4,d4〉=〈200,450〉且最大值点M4(300,325)∈A4将p4(300,350)代入建立二维关联函数构造k(p4):

5)计算信息功能的关联度，其中正域为有限区域A5=〈a5,b5〉×〈c5,d5〉,其中〈a5,b5〉=〈60%,80%〉，〈c5,d5〉=〈60%,90%〉且最大值点，M570%，75%∈A5，将p575%,80%代入建立二维关联函数构造k(p):

4 结束语

本文根据可拓学的基元理论构建了一种异质边多重图网络模型——基于物元特征的r-异质边多重图网络模型。这种模型适用于所有网络节点都具有r个相同特征，特征之间是不同质的，而每一个特征决定了两个相邻节点间相连接的一条边，从而形成r-异质多重完全图网络。对于物流网络背景来说，这种模型适用于物流网络各节点的功能特征基本相同或者所关注的若干功能特征相同的情况，这些功能特征是异质的，并且对应每个功能特征能够建立起物流节点间的可拓关系。

物流网络的运行是由许多运动过程和许多相对停顿过程组成的。因此，物流网络结构也是由执行运动使命的线路和执行停顿使命的节点两种基本元素所组成，全部物流活动是在线路和结点进行的物流网络水平高低、功能强弱则取决于网络中这两个基本元素的配置和两个基本元素本身。

提高物流网络的效能就应该从变换网络节点的功能特征和节点间的连接关系入手。这就体现在物流节点的物元变换和关联函数的变换。配置和关系的改变是网络结构的演变，节点功能的改变则是节点本身的功能性改变。由于我们采用物元表示网络节点，用基于特征的关联函数表示边权，这就为异质多重边物流网络的处理带来便利。同时，这种异质多重边网络的优化可以通过网络中节点特征间的联合相关度作为评价指标来指导网络的优化演变。

[1]WANG Z, SOLNOKI A. Self-organization towards optimally interdependent networks by means of coevolution[J]. New journal of physics， 2016, 16: 33-41.

[2]WANG N N, MI Y Y, LIU W, et al. Logistics network model based on matter element node[J]. Procedia compute science， 2016, 91: 351-356.

[3]王娜娜，高红，李珊珊，等. 基于异质超边的超图[J].广东工业大学学报， 2017, 34(1): 6-10.

WANG Nana, GAO Hang, LI Shanshan, et al. A research on hypergraph of heterogeneous edge[J]. Journal of guangdong university of technology, 2017, 34(1): 6-10.

[4]马啸来. 基于多重图的物流链选择决策模型及算法研究[J]. 铁道运输与经济， 2012, 34(1): 56-61.

MA Xiaolai. Study on decision-making model and calculation method of logistics chain selection based on multigraph[J]. Railway transport and economy， 2012, 34(1)： 56-61.

[5]高洋，李丽香,彭海朋，等. 多重边复杂网络系统的稳定性分析[J]. 物理学报， 2008, 57(3): 1444-1452.

GAO Yang, LI Lixiang, PENG Haipeng， et al. Adaptive Synchronization in united complex dynamical network with multi-links[J]. Acta physica sinica, 2008, 57(3)： 144-1452.

[6]安新磊，李引珍,马昌喜. 一种新的多重边复杂公交网络模型[J].交通运输系统工程与信息， 2014, 14(3): 154-161.

AN Xinlei, LI Yinzhen, MA Changxi. Public traffic network modeling withmulti-links[J]. Journal of transportation systems engineering and information technology, 2014, 14(3)： 154-161.

[7]NIUSVEL A M, ANDRES G A. A new algorithm for approximate pattern mining in multigraphs collections[J]. Knowledge based systems, 2016(109): 198-207.

[8]SUIL.Edge-connectivity in regular multigraphs from eigenvalues[J]. Linear algebra and its applications， 2016, 491(15): 4-14.

[9]HAXELLA P E, KIESTEAD H A. Edge coloring multi-gra phs without small dense subsets[J].Original researc article， 2015, 338(12): 2502-2506.

[10]XUN Y, WANG M. Robust visual tracking via multi-graph ranking[J]. Neurocomputing， 2015, 159: 35-43.

[11]CHAKARESKI J. Vertex selection via a multi-graph analysis[J]. Original research article， 2014, 102: 139-150.

[12]JIANG J, LI W. The effect of interdependence on the percolation of interdependent network[J]. Physica: a statistical mechanics and its applications， 2014， 41: 573-581.

[13]STIPPINGER M. Enhancing resilience of interdependent networks by healing[J]. Physica: a statistical mechanics and its applications， 2014， 416: 481-487.

[14]蔡文,杨春燕,何斌. 可拓学的基础理论与方法体系[J]. 科学通报, 2013, 58(13): 1190-1199.

CAI Wen, YANG Chunyan, HE Bin. Basic theory and methodology on extenics[J]. Chinese science bulletin， 2013, 58(13): 1190-1199.

[15]蔡文.可拓集合和不相容问题[J]. 科学探索学报， 1983(1): 83-97.

CAI Wen. Extension set and non-compatible problems[J]. Journal of scientific exploration, 1983(1): 83-97.

[16]LI Q X, LIU S F. The general elementary dependent function based on the side distance[C]//Proceedings of the 7 th World Congresson Intelligence Control and Automation. Piscataway， 2008: 1325-1328.

[17]LI Q X. The interval elementary dependent function based on interval side-distance[C]//Proceedings of IEEE 2008 ISECS International Colloquium on Computing, Communication, Control, and Management. Piscataway, 2008: 674-678.

[18]蔡文.物元模型及其应用[M]. 北京：科学技术文献出版社，1994.

[19]李志明,杨春燕. 三个区域套下二维初等关联函数的构造方法[J]. 辽宁工程技术大学学报, 2015， 2： 267-272.

LI Zhiming, YANG Chunyan. Construction method of two-dimensional elementary dependent function in three nested regions[J]. Journal of liaoning technical university, 2015， 2： 267-272.

[20]YANG Chunyan, CAI Wen. Extenics: theory method and application[M]. Beijing: Science Press, 2013.

Researchonaheterogeneousedgemulti-graphnetworkmodel

WANG Nana1， GAO Hong2, LIU Wei1,2

(1.College of Transportation Management， Dalian Maritime University, Dalian 116026, China; 2. Department of Mathematics, Dalian Maritime University, Dalian 116026, China)

In a logistics network, in order to achieve unity of the logistics node between heterogeneous edge measurements, we use the primitive Extenics theory to build a type of heterogeneity and multiple complete graph network models based on matter-element characteristics. This network model is suitable for the common functions of the logistics center and the logistics distribution center. Its functions include transportation, storage, packaging, circulation processing, and information processing. There is heterogeneity among the characteristics of these functions.The characteristics of every function exhibit one connected edge between two logistics nodes. We established a connection function for each function characteristic and the function value was used as the right edge. This achieved unity in the logistics network measurements and is appropriate for logistics network optimization.

complex network; multi-links; multi-graph network; heterogeneous edge; extenics; matter-element; two-dimensional extension distance; two-dimensional place value

2016-10-14.网络出版日期2017-04-07.

辽宁省自然科学基金项目(2015020033).

刘巍. E-mail：liuwei09@aliyun.com.

10.11992/tis.201610011

http://kns.cnki.net/kcms/detail/23.1538.tp.20170407.1758.018.html

TP182

1673-4785(2017)04-0475-07

中文引用格式：王娜娜，高红，刘巍.异质边多重图网络模型研究J.智能系统学报， 2017, 12(4): 475-481.

英文引用格式：WANGNana，GAOHong,LIUWei.Researchonaheterogeneousedgemulti-graphnetworkmodelJ.CAAItransactionsonintelligentSystems, 2017, 12(4): 475-481.