異質邊多重圖網絡模型研究

王娜娜，高紅，劉巍,

(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

A

1673-4785(2017)04-0475-07

中文引用格式：王娜娜，高紅，劉巍.異質邊多重圖網絡模型研究J.智能系統學報， 2017, 12(4): 475-481.

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

王娜娜，女，1989年生，碩士研究生，主要研究方向為優化運籌優化。

高紅，女，1976年生，副教授，博士，主要研究方向為現代算法及其在管理學中的和圖論及其應用。主持國家自然科學基金青年基金項目、省級自然科學基金項目、深圳市交通局項目多項，發表學術論文20余篇。

劉巍，男，1955年生 ，教授，博士生導師，主要研究方向為優化管理。主持國家自然科學基金、深圳市交通局項目多項，發表學術論文30余篇。