﻿ 异质边多重图网络模型研究
«上一篇
 文章快速检索 高级检索

 智能系统学报  2017, Vol. 12 Issue (4): 475-481  DOI: 10.11992/tis.201610011 0

### 引用本文

WANG Nana, GAO Hong, LIU Wei. Research on a heterogeneous edge multi-graph network model[J]. CAAI Transactions on Intelligent Systems, 2017, 12(4): 475-481. DOI: 10.11992/tis.201610011.

### 文章历史

1. 大连海事大学 交通运输管理学院, 辽宁 大连 116026;
2. 大连海事大学 数学系, 辽宁 大连 116026

Research on a heterogeneous edge multi-graph network model
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
Abstract: 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.
Key words: complex network    multi-links    multi-graph network    heterogeneous edge    extenics    matter-element    two-dimensional extension distance    two-dimensional place value

1 基本概念

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

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

 $M = \left[ {\begin{array}{*{20}{c}} {{O_{m'}},}&{{O_{m1'}},}&{{O_{m2'}}}\\ {}&{{c_{m2'}},}&{{v_{m2}}}\\ {}& \vdots & \vdots \\ {}&{{c_{mn'}},}&{{v_{mn}}} \end{array}} \right] = \left( {{O_{m'}},{C_m},{V_m}} \right)$

 ${C_m} = \left[ {\begin{array}{*{20}{c}} {{c_{m1}}}\\ {{c_{m2}}}\\ \vdots \\ {{c_{mn}}} \end{array}} \right],\;\;\;\;\;{V_m} = \left[ {\begin{array}{*{20}{c}} {{v_{m1}}}\\ {{v_{m2}}}\\ \vdots \\ {{v_{mn}}} \end{array}} \right]$

 $\rho \left( {P,{A_0}} \right) = \left\{ \begin{array}{l} \mathop {\inf }\limits_{{P_1} \in {\mathit{\Gamma }_0}} \rho \left( {P,{A_0}} \right),\;\;\;\;P \notin {A_0}\\ - \mathop {\inf }\limits_{{P_1} \in {\mathit{\Gamma }_0}} \rho \left( {P,{A_0}} \right),\;\;P \in {A_0} \end{array} \right.$

 $D\left( {P,{A_0},A} \right) = \rho \left( {P,A} \right) - \rho \left( {P,{A_0}} \right)$

 $\rho \left( {P,{A_0}} \right) = \left\{ \begin{array}{l} \mathop {\inf }\limits_{{P_2} \in \mathit{\Gamma }} \rho \left( {P,{P_2}} \right),\;\;\;\;P \notin A\\ - \mathop {\inf }\limits_{{P_2} \in \mathit{\Gamma }} \rho \left( {P,{P_2}} \right),\;\;P \in A \end{array} \right.$

P2为区域A的边界Γ上的一点。D(P, A0, A)就描述了点P(x1, x2)与区域A0A组成的区域套的位置关系。

2 模型构建

 ${M_i} = \left[ {\begin{array}{*{20}{c}} {{O_{mi}},}&{{c_{m1}},}&{{v_{m1}}}\\ {}&{{c_{m2}},}&{{v_{m1}}}\\ {}& \vdots & \vdots \\ {}&{{c_{mr}},}&{{v_{mr}}} \end{array}} \right]$

 $F = \left\{ {{f_{ij}}\left( {{c_{mh}}} \right)\left| {h = 1,2, \cdots r;i,j = 1,2, \cdots ,n} \right.} \right\}$

 $\tilde r = \left\{ {\left( {u,v,y} \right)\left| {\left( {u,v} \right)} \right. \in U \times V,y = k\left( {u,v} \right)} \right\}$

UV之间的一个二元可拓关系[18]。所有UV二元可拓关系的全体记为￡(U×V):称$\tilde r$={(u, v, y)|(u, v)∈U×V, y=k(u, v)≥0}为$\tilde r$的正域；$\tilde r$={(u, v, y)(u, v)∈U×V, y=k(u, v)≤0}为$\tilde r$的负域；J0($\tilde r$)={(u, v)|(u, v)∈U×V, k(u, v)}=0为$\tilde r$的零界；这里的关联函数y=k(u, v)是二维的, 在文献[19-20]中给出了一种构造二维关联函数的方法。

 $\begin{array}{*{20}{c}} {{{\tilde r}_{{c_{mh}}}} = \left\{ {\left( {u,v,y} \right)\left| {\left( {u,v} \right)} \right. \in V \times V,y = } \right.}\\ {\left. {{k_{{c_{mh}}}}\left( {u,v} \right) \in \left( { - \infty , + \infty } \right)} \right\}} \end{array}$

 图 4 关联函数示意图 Fig.4 Dependent function
 $k\left( p \right) = \left\{ \begin{array}{l} \left( {y - c} \right)/\left( {{y_0} - c} \right),\;\;\;\;y \le {y_0},{x_1} \le x \le {x_4}\\ \left( {x - a} \right)/\left( {{x_0} - a} \right),\;\;\;\;x \le {x_0},{y_1} \le y \le {y_2}\\ \left( {y - d} \right)/\left( {{y_0} - d} \right),\;\;\;\;y \ge {y_0},{x_2} \le x \le {x_3}\\ \left( {x - b} \right)/\left( {{x_0} - b} \right),\;\;\;\;\;x \ge {x_0},{y_3} \le y \le {y_4} \end{array} \right.$ (1)

 $\left\{ \begin{array}{l} {x_1} = \frac{{{x_0} - a}}{{{y_0} - c}}y + \frac{{a{y_o} - c{x_0}}}{{{y_0} - c}}\\ {x_2} = \frac{{{x_0} - a}}{{{y_0} - d}}y + \frac{{a{y_o} - d{x_0}}}{{{y_0} - d}}\\ {x_3} = \frac{{{x_0} - b}}{{{y_o} - d}}y + \frac{{b{y_o} - d{x_0}}}{{{y_0} - d}}\\ {x_4} = \frac{{{x_0} - b}}{{{y_0} - c}}y + \frac{{b{y_o} - c{x_0}}}{{{y_0} - c}} \end{array} \right.$
 $\left\{ \begin{array}{l} {y_1} = \frac{{{y_0} - c}}{{{x_0} - a}}x + \frac{{c{x_0} - a{y_o}}}{{{x_0} - a}}\\ {y_2} = \frac{{{y_0} - d}}{{{x_0} - a}}x + \frac{{d{x_0} - a{y_o}}}{{{x_0} - a}}\\ {y_3} = \frac{{{y_0} - d}}{{{x_o} - b}}x + \frac{{d{x_0} - b{y_o}}}{{{x_0} - b}}\\ {y_4} = \frac{{{y_0} - c}}{{{x_0} - b}}x + \frac{{c{x_0} - b{y_o}}}{{{x_0} - b}} \end{array} \right.$

k(p)满足如下性质：

1)k(p)在p=M处达到最大值，且k(M)=1;

2)p(x, y)∈D, 且xa, b, yc, dkp）>0；

3)p(x, y)∉D, 且xa, b, yc, dk(p)＜0;

4)x=a or b, y=c or dk(p)=0。

 ${f_{ij}}\left( {{c_{mh}}} \right) = {k_{{c_{mh}}}}\left( {{M_i},{M_j}} \right),h = 1,2, \cdots ,r,i,j = 1,2, \cdots ,n$ (2)

3 实例

 ${M_i} = \left[ {\begin{array}{*{20}{c}} {物流节点\;{D_i},}&{运输功能\;{c_{m1}},}&{45\% }\\ {}&{储存功能\;{c_{m2}},}&{100}\\ {}&{包装功能\;{c_{m3}},}&{350}\\ {}&{加工功能\;{c_{m4}},}&{300}\\ {}&{信息功能\;{c_{m5}},}&{75\% } \end{array}} \right]$
 ${M_j} = \left[ {\begin{array}{*{20}{c}} {物流节点\;{D_i},}&{运输功能\;{c_{m1}},}&{85\% }\\ {}&{储存功能\;{c_{m2}},}&{90}\\ {}&{包装功能\;{c_{m3}},}&{400}\\ {}&{加工功能\;{c_{m4}},}&{350}\\ {}&{信息功能\;{c_{m5}},}&{80\% } \end{array}} \right]$

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

 $k\left( {{p_1}} \right) = \left\{ \begin{array}{l} \left( {y - 70\% } \right)/\left( {82.5\% - 70\% } \right),\;\;y \le 82.5\% ,\frac{4}{3}y - \frac{{13}}{{30}} \le x \le - \frac{6}{5}y + \frac{{41}}{{25}}\\ \left( {y - 50\% } \right)/\left( {65\% - 50\% } \right),\;\;\;\;\;x \le 65\% \frac{3}{4}x + \frac{{13}}{{40}} \le y \le - \frac{5}{6}x + \frac{{41}}{{30}}\\ \left( {y - 95\% } \right)/\left( {82.5\% - 95\% } \right),\;\;\;y \le 82.5\% , - \frac{6}{5}y + \frac{{41}}{{25}} \le x \le \frac{4}{3}y - \frac{{13}}{{30}}\\ \left( {x - 80\% } \right)/\left( {65\% - 80\% } \right),\;\;\;\;\;\;x \ge 65\% , - \frac{5}{6}x + \frac{{41}}{{30}} \ge y \le \frac{3}{4}x + \frac{{13}}{{40}} \end{array} \right.$

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

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

 $k\left( {{p_2}} \right) = \left\{ \begin{array}{l} \left( {y - 40} \right)/\left( {145 - 40} \right),\;\;\;\;\;\;y \le 145,\frac{{26}}{{21}}y - \frac{{200}}{{21}} \le x \le - \frac{{26}}{{21}}y + \frac{{1340}}{{21}}\\ \left( {x - 40} \right)/\left( {170 - 40} \right),\;\;\;\;\;\;x \le 170,\frac{{21}}{{26}}x + \frac{{100}}{{13}} \le y \le - \frac{{21}}{{26}}x + \frac{{3670}}{{13}}\\ \left( {y - 250} \right)/\left( {145 - 250} \right),\;\;\;\;\;\;y \ge 145, - \frac{{26}}{{21}}y + \frac{{1340}}{{21}} \le x \le \frac{{26}}{{21}}y + \frac{{200}}{{21}}\\ \left( {x - 300} \right)/\left( {170 - 300} \right),\;\;\;\;\;\;x \ge 170, - \frac{{21}}{{26}}x + \frac{{3670}}{{13}} \le y \le \frac{{21}}{{26}}x + \frac{{100}}{{13}} \end{array} \right.$

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

 $k\left( {{p_3}} \right) = \left\{ \begin{array}{l} \left( {y - 100} \right)/\left( {300 - 100} \right),\;\;\;y \le 300,y \le x \le - y + 400\\ \left( {x - 100} \right)/\left( {300 - 100} \right),\;\;\;x \le 300, \le y \le - x + 400\\ \left( {y - 500} \right)/\left( {300 - 500} \right),\;\;\;y \ge 300, - y + 400 \le x \le y\\ \left( {x - 500} \right)/\left( {300 - 500} \right),\;\;\;x \ge 300, - x + 400 \le y \le x \end{array} \right.$

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

 $k\left( {{p_4}} \right) = \left\{ \begin{array}{l} \left( {y - 200} \right)/\left( {325 - 200} \right),\;\;\;\;y \le 325,\frac{4}{5}y + 40 \le x \le - \frac{4}{5}y + 640\\ \left( {x - 200} \right)/\left( {300 - 200} \right),\;\;\;\;x \le 300,\frac{5}{4}x - 50 \le y \le - \frac{5}{4}x + 800\\ \left( {y - 450} \right)/\left( {325 - 450} \right),\;\;\;\;y \ge 325, - \frac{4}{5}y + 640 \le x \le \frac{4}{5}y + 40\\ \left( {x - 400} \right)/\left( {300 - 400} \right),\;\;\;\;x \ge 300, - \frac{5}{4}x + 800 \le y \le \frac{5}{4}x - 50 \end{array} \right.$

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

 $k\left( p \right) = \left\{ \begin{array}{l} \left( {y - 60\% } \right)/\left( {75\% - 60\% } \right),\;\;\;\;y \le 75\% ,\frac{2}{3}y + \frac{1}{5} \le x \le - \frac{2}{3}y + \frac{6}{5}\\ \left( {x - 60\% } \right)/\left( {70\% - 60\% } \right),\;\;\;\;x \le 70\% ,\frac{3}{2}x - \frac{3}{{10}} \le y \le - \frac{3}{2}x - \frac{9}{5}\\ \left( {y - 90\% } \right)/\left( {75\% - 90\% } \right),\;\;\;\;y \ge 75\% , - \frac{2}{3}y + \frac{6}{5} \le x \le \frac{2}{3}y + \frac{1}{5}\\ \left( {x - 80\% } \right)/\left( {70\% - 80\% } \right),\;\;\;\;x \ge 70\% , - \frac{3}{2}x - \frac{9}{5} \le y \le \frac{3}{2}x - \frac{3}{{10}} \end{array} \right.$

4 结束语

 [1] WANG Z, SOLNOKI A. Self-organization towards optimally interdependent networks by means of coevolution[J]. New journal of physics, 2016, 16: 33-41. (0) [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. DOI:10.1016/j.procs.2016.07.093 (0) [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. (0) [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. (0) [5] 高洋, 李丽香, 彭海朋, 等. 多重边复杂网络系统的稳定性分析[J]. 物理学报, 2008, 57(3): 144-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. (0) [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. (0) [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. (0) [8] SU IL. Edge-connectivity in regular multigraphs from eigenvalues[J]. Linear algebra and its applications, 2016, 491(15): 4-14. (0) [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. (0) [10] XUN Y, WANG M. Robust visual tracking via multi-graph ranking[J]. Neurocomputing, 2015, 159: 35-43. DOI:10.1016/j.neucom.2015.02.046 (0) [11] CHAKARESKI J. Vertex selection via a multi-graph analysis[J]. Original research article, 2014, 102: 139-150. (0) [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. (0) [13] STIPPINGER M. Enhancing resilience of interdependent networks by healing[J]. Physica:a statistical mechanics and its applications, 2014, 416: 481-487. DOI:10.1016/j.physa.2014.08.069 (0) [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. (0) [15] 蔡文. 可拓集合和不相容问题[J]. 科学探索学报, 1983(1): 83-97. CAI Wen. Extension set and non-compatible problems[J]. Journal of scientific exploration, 1983(1): 83-97. (0) [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. (0) [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. (0) [18] 蔡文. 物元模型及其应用[M]. 北京: 科学技术文献出版社, 1994. (0) [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. DOI:10.11956/j.issn.1008-0562.2015.02.025 (0) [20] YANG Chunyan, CAI Wen. Extenics:theory method and application[M]. Beijing: Science Press, 2013. (0)