基于多功能網(wǎng)的最短路徑查詢算法

袁敏 孫更新 賓晟

摘要：在單一網(wǎng)絡(luò)功能下節(jié)點(diǎn)間最短路徑的研究基礎(chǔ)上，提出基于多功能網(wǎng)的最短路徑查詢問題，給出一種基于貪心策略的查詢算法來查詢節(jié)點(diǎn)間在不同網(wǎng)絡(luò)功能下的最短路徑。利用多功能網(wǎng)對山東半島城市群進(jìn)行建模，分別查詢城市群網(wǎng)絡(luò)實(shí)現(xiàn)經(jīng)濟(jì)和信息兩種不同功能時(shí)城市間的最短路徑，并計(jì)算分析。研究結(jié)果表明，查詢節(jié)點(diǎn)間在不同網(wǎng)絡(luò)功能下的最短路徑對于挖掘復(fù)雜系統(tǒng)不同功能間的潛在聯(lián)系具有一定的現(xiàn)實(shí)意義。

關(guān)鍵詞：多功能網(wǎng);最短路徑查詢算法;中心性;山東半島城市群

中圖分類號：N95

文獻(xiàn)標(biāo)志碼：A

收稿日期：2020-11-02

基金項(xiàng)目：

教育部人文社會科學(xué)研究青年項(xiàng)目（批準(zhǔn)號：15YJC860001）資助;山東省自然基金面上項(xiàng)目（批準(zhǔn)號：ZR2017MG011）資助;山東省社會科學(xué)規(guī)劃項(xiàng)目（批準(zhǔn)號：17CHLJ16）資助。

通信作者：

孫更新，男，博士，副教授，主要研究方向?yàn)榇髷?shù)據(jù)分析、數(shù)據(jù)挖掘、復(fù)雜網(wǎng)絡(luò)。E-mail：sungengxin@qdu.edu.cn

挖掘復(fù)雜系統(tǒng)不同功能間的潛在聯(lián)系，實(shí)現(xiàn)系統(tǒng)各種功能間的優(yōu)勢互補(bǔ)，對于優(yōu)化系統(tǒng)結(jié)構(gòu)，促進(jìn)系統(tǒng)發(fā)展具有重要意義。復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的重要工具之一，但以往的復(fù)雜網(wǎng)絡(luò)模型如隨機(jī)圖[1]、二分圖[2-3]、層次網(wǎng)絡(luò)[4-5]和多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型[6-7]等均將系統(tǒng)中的實(shí)體表示為節(jié)點(diǎn)，將實(shí)體間的相互作用表示為連邊，拓?fù)浣Y(jié)構(gòu)相對固定，功能相對單一，而多功能網(wǎng)[8]可以充分利用并動態(tài)地選擇節(jié)點(diǎn)的屬性，依據(jù)映射規(guī)則來確定節(jié)點(diǎn)間的相互作用，實(shí)現(xiàn)不同的網(wǎng)絡(luò)結(jié)構(gòu)和功能。最短路徑查詢[9-11]是圖論中的一個(gè)經(jīng)典問題，旨在尋找圖中兩個(gè)節(jié)點(diǎn)間的最短路徑，其在復(fù)雜網(wǎng)絡(luò)領(lǐng)域有重要的應(yīng)用，如網(wǎng)絡(luò)直徑、平均最短路徑長度、緊密中心性和介數(shù)中心性等復(fù)雜網(wǎng)絡(luò)分析中重要的特征度量，均可以在最短路徑查詢的基礎(chǔ)上進(jìn)一步計(jì)算獲得。圖論中回答最短路徑查詢的方法主要有兩類，第一類方法不對原始數(shù)據(jù)圖進(jìn)行任何的預(yù)處理操作，此類方法的代表性算法有BFS算法、Dijstra算法[12-13]、Floyd算法[14-15]和A*算法[16]。第二類方法首先對原始數(shù)據(jù)圖構(gòu)建相應(yīng)的索引，然后在相應(yīng)的索引上進(jìn)行最短路徑查詢操作，此類方法的代表性算法有IS_LABEL算法[17]和PLL算法[18]。但這些方法均無法查詢節(jié)點(diǎn)間在不同網(wǎng)絡(luò)功能下的最短路徑。綜上，本文提出基于多功能網(wǎng)的最短路徑查詢，給出MFCNSPQ算法來查詢節(jié)點(diǎn)間在不同網(wǎng)絡(luò)功能下的最短路徑，并參考文獻(xiàn)[19-21]，對山東半島城市群進(jìn)行建模、查詢與分析。

1 多功能網(wǎng)

多功能網(wǎng)認(rèn)為實(shí)體間的相互作用與實(shí)體的特征屬性有關(guān)，利用節(jié)點(diǎn)來表示復(fù)雜系統(tǒng)中的實(shí)體，節(jié)點(diǎn)以特征屬性向量的形式表示，通過動態(tài)地選擇特征屬性集，依據(jù)相應(yīng)的特征屬性集映射函數(shù)來確定節(jié)點(diǎn)間的關(guān)聯(lián)，進(jìn)而實(shí)現(xiàn)特定的網(wǎng)絡(luò)功能。該模型使用三元組MFCN=V，P，F(xiàn)來表示：

（1）V=∪|V|i=1vi是多功能網(wǎng)的節(jié)點(diǎn)集合;

（2）P=∪|P|h=1Ph是多功能網(wǎng)的特征屬性集合，domP=∪Ph∈Pdom（Ph）是特征屬性集P的值域集合，節(jié)點(diǎn)vi在Ph下的取值為pih∈domPh，pi=（pi1，pi2，…，pih，…，piP）是節(jié)點(diǎn)vi的在特征屬性集P下的向量表示形式;

（3）Fvi，vj=ξ（f1，f2，…，fh，…，ft）是多功能網(wǎng)基于所選擇的特征屬性集P*（P*P）的特征屬性集映射函數(shù)，節(jié)點(diǎn)vi，vj間基于特征屬性集P*建立的關(guān)聯(lián)通過其實(shí)現(xiàn)，其中t≤P，fh是特征屬性Ph對應(yīng)的特征屬性映射函數(shù)。

節(jié)點(diǎn)數(shù)量為V，具有P個(gè)特征屬性的多功能網(wǎng)，可用V×P的矩陣描述：

2 基于多功能網(wǎng)的最短路徑查詢

2.1 基本概念

定義1 基于特征屬性集映射函數(shù)F的路徑。對多功能網(wǎng)MFCN=V，P，F(xiàn)，選擇不同的特征屬性集，其映射函數(shù)不同，節(jié)點(diǎn)間的相互作用不同，進(jìn)而使得節(jié)點(diǎn)間的路徑不同。給定起始節(jié)點(diǎn)vs和目標(biāo)節(jié)點(diǎn)vt（vt≠vs），若有節(jié)點(diǎn)序列l(wèi)=vs，…，vk，vk+1，…，vt，其中vk，vk+1∈l在特征屬性集映射函數(shù)F下均存在關(guān)聯(lián)，則稱l為由節(jié)點(diǎn)vs到vt的基于特征屬性集映射函數(shù)F的路徑，簡記為基于F的路徑。

定義2 基于特征屬性集映射函數(shù)F的物理路徑長度。若l為由節(jié)點(diǎn)vs到vt的基于F的路徑，那么節(jié)點(diǎn)vs到vt的基于特征屬性集映射函數(shù)F的物理路徑長度，簡記為基于F的物理路徑長度為

lFvs，vt=∑vk，vk+1∈lσ（Fvk，vk+1）（1）

其中，σ為函數(shù)，在特征屬性集映射函數(shù)F下，當(dāng)節(jié)點(diǎn)vi和vj存在關(guān)聯(lián)時(shí)，有σFvi，vj=1，否則σFvi，vj=0。

定義3 基于特征屬性集映射函數(shù)F的最短物理路徑。設(shè)l為由節(jié)點(diǎn)vs到vt的基于F的路徑，若多功能網(wǎng)中找不到一條由節(jié)點(diǎn)vs到vt的基于F的路徑w使得wFvs，vt<lFvs，vt，那么稱l為由節(jié)點(diǎn)vs到vt的基于特征屬性集映射函數(shù)F的最短物理路徑，簡記為基于F的最短物理路徑。

定義4 基于特征屬性集映射函數(shù)F的物理距離。若l為由節(jié)點(diǎn)vs到vt的基于F的最短物理路徑，那么lFvs，vt為節(jié)點(diǎn)vs到vt的基于特征屬性集映射函數(shù)F的物理距離，簡記為基于F的物理距離。

2.2 查詢算法

基于多功能網(wǎng)的最短路徑查詢的形式定義為Q=（vs，vt），其中vs為起始節(jié)點(diǎn)，vt為目標(biāo)節(jié)點(diǎn)，則多功能網(wǎng)上基于特征屬性集映射函數(shù)最短路徑查詢問題（MFCNSPQ）定義如下：

輸入：多功能網(wǎng)MFCN，最短路徑查詢Q;

輸出：節(jié)點(diǎn)vs到vt的基于F的全部最短物理路徑。

采用貪心的思想解決MFCNSPQ問題，算法具體步驟如下：

Step 1 利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)vs和vt進(jìn)行運(yùn)算，得到返回值Fvs，vt，判斷Fvs，vt是否滿足映射規(guī)則，若滿足，則l=vs，vt為vs到vt的基于F的最短物理路徑，算法結(jié)束，否則執(zhí)行Step 2;

Step 2 利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)vs和多功能網(wǎng)中除節(jié)點(diǎn)vt外的其他節(jié)點(diǎn)逐一運(yùn)算，返回值滿足映射規(guī)則的節(jié)點(diǎn)組成集合S，更新集合S中節(jié)點(diǎn)的前置節(jié)點(diǎn)為vs，利用特征屬性集映射函數(shù)F對集合S中節(jié)點(diǎn)和節(jié)點(diǎn)vt逐一運(yùn)算，返回值滿足映射規(guī)則的節(jié)點(diǎn)為節(jié)點(diǎn)vt的前置節(jié)點(diǎn)，若節(jié)點(diǎn)vt的前置節(jié)點(diǎn)信息不為空，則根據(jù)節(jié)點(diǎn)的前置節(jié)點(diǎn)信息得到節(jié)點(diǎn)vs到vt的基于F的全部最短物理路徑，算法結(jié)束，否則執(zhí)行Step 3;

Step 3 利用特征屬性集映射函數(shù)F對集合S中節(jié)點(diǎn)和多功能網(wǎng)中除節(jié)點(diǎn)vs和vt外還未加入過集合S節(jié)點(diǎn)逐一運(yùn)算，返回值滿足映射規(guī)則的節(jié)點(diǎn)組成新的集合S，更新集合S中節(jié)點(diǎn)的前置節(jié)點(diǎn)信息，利用特征屬性集映射函數(shù)F對集合S中節(jié)點(diǎn)和節(jié)點(diǎn)vt逐一運(yùn)算，返回值滿足映射規(guī)則的節(jié)點(diǎn)為節(jié)點(diǎn)vt的前置節(jié)點(diǎn)，若節(jié)點(diǎn)vt的前置節(jié)點(diǎn)信息不為空，則根據(jù)節(jié)點(diǎn)的前置節(jié)點(diǎn)信息得到節(jié)點(diǎn)vs到vt的基于F的最短物理路徑，算法結(jié)束，否則重復(fù)執(zhí)行Step 3，直到節(jié)點(diǎn)vt的前置節(jié)點(diǎn)信息不為空，找到節(jié)點(diǎn)vs到vt的基于F的全部最短物理路徑。

由于MFCNSPQ算法總是先尋找距離起始節(jié)點(diǎn)vs為k的所有節(jié)點(diǎn)，再尋找距離vs為k+1的所有節(jié)點(diǎn)，并記錄查詢過程中節(jié)點(diǎn)的全部前置節(jié)點(diǎn)信息，因此通過MFCNSPQ算法一定能找到節(jié)點(diǎn)vs到vt的基于F的全部最短物理路徑。通過多功能網(wǎng)一個(gè)實(shí)例對MFCNSPQ算法過程進(jìn)行解釋。實(shí)例節(jié)點(diǎn)集V=∑7i=1vi，特征屬性集P=P1，P2，P3，P4，P5，P6，節(jié)點(diǎn)vi的特征屬性向量形式pi=（pi1，pi2，pi3，pi4，pi5，pi6）。該實(shí)例被描述為一個(gè)7×6階的矩陣：

P1P2P3P4P5P6

v1v2v3v4v5v6v7100000

110000

101100

011010

000101

000011

000000

查詢節(jié)點(diǎn)v1到v6的基于F的最短物理路徑，其中F為特征屬性集P*=P對應(yīng)的特征屬性集映射函數(shù)，利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)vi和vj進(jìn)行運(yùn)算，F(xiàn)vi，vj=pi·pj，返回值Fvi，vj1時(shí)，滿足映射規(guī)則，節(jié)點(diǎn)vi和vj在特征屬性集映射函數(shù)F下存在關(guān)聯(lián)。具體步驟如下：

Step 1 利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)v1和v6進(jìn)行運(yùn)算，得到返回值Fv1，v6=0，不滿足映射規(guī)則，執(zhí)行Step 2;

Step 2 利用特征屬性集映射函數(shù)用F對節(jié)點(diǎn)v1和節(jié)點(diǎn)v2，v3，v4，v5，v7逐一運(yùn)算，有Fv1，v2和Fv1，v3滿足映射規(guī)則，于是集合S={v2，v3}，更新節(jié)點(diǎn)v2和v3的前置節(jié)點(diǎn)信息為v1，利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)v2、v3和節(jié)點(diǎn)v6逐一運(yùn)算，F(xiàn)v2，v6和Fv3，v6均不滿足映射規(guī)則，執(zhí)行Step 3;

Step 3 利用特征屬性集映射函數(shù)用F對節(jié)點(diǎn)v2、v3和節(jié)點(diǎn)v4、v5、v7逐一運(yùn)算，有Fv2，v4、Fv3，v4和Fv3，v5滿足映射規(guī)則，于是S={v4，v5}，更新節(jié)點(diǎn)v4的前置節(jié)點(diǎn)信息為v2和v3，節(jié)點(diǎn)v5的前置節(jié)點(diǎn)信息為v3，利用特征屬性集映射函數(shù)F對節(jié)點(diǎn)v4、v5和節(jié)點(diǎn)v6逐一運(yùn)算，F(xiàn)v4，v6和Fv5，v6均滿足映射規(guī)則，更新節(jié)點(diǎn)v6的前置節(jié)點(diǎn)信息為v4和v5，此時(shí)v6的前置節(jié)點(diǎn)信息不為空，根據(jù)所記錄的前置節(jié)點(diǎn)信息，得到節(jié)點(diǎn)v1到v6的基于F的最短物理路徑為l1=v1，v2，v4，v6，l2=v1，v3，v4，v6和l3=v1，v3，v5，v6。

3 實(shí)驗(yàn)

3.1 建模

在《山東半島城市群發(fā)展規(guī)劃（2016—2030年）》中提出以17個(gè)地級市：濟(jì)南、青島、淄博、棗莊、東營、煙臺、濰坊、濟(jì)寧、泰安、威海、日照、萊蕪（2019年1月正式撤銷）、臨沂、德州、聊城、濱州、菏澤共同組成山東半島城市群?？紤]本文從經(jīng)濟(jì)和信息角度出發(fā)討論的山東半島城市群網(wǎng)絡(luò)所需數(shù)據(jù)信息以及數(shù)據(jù)的時(shí)效性和完整性，收集并處理了山東半島城市群中各城市的2018年的年末人口數(shù)、地區(qū)生產(chǎn)總值、里程和信息關(guān)注度的信息，數(shù)據(jù)來源于《山東統(tǒng)計(jì)年鑒2019》、百度指數(shù)20180101—20181231和百度地圖。

以城市為節(jié)點(diǎn)，基于多功能網(wǎng)的山東半島城市群網(wǎng)絡(luò)可用17×4階的矩陣描述：

P1 P2 P3P4

v1v2v17

655.97856.6（0，352，…，243）（0，691，…，452）

817.812 001.5（325，0，…，529）（547，0，…，303）

1 025.43078.8（243，529，…，0）（235，210，…，0）

其中，節(jié)點(diǎn)集V=∑17i=1vi，特征屬性集P={P1，P2，P3，P4}，P1為城市年末人口數(shù)，P2為城市生產(chǎn)總值，P3為城市群中某城市與其他城市間的最短公路里程，P4為基于百度指數(shù)整體日均值的城市群中某城市對其他城市的搜索指數(shù)。城市節(jié)點(diǎn)vi的特征屬性向量形式pi=（pi1，pi2，pi3，pi4），pi1為城市vi的年末人口數(shù)，pi2為城市vi的生產(chǎn)總值，pi3=（li1，li2，…，lij，…，li17），lij為城市vi的與城市vj間的最短公路里程，j=i時(shí)，lij=0，pi4=（qi1，qi2，…，qij，…，qi17），qij為基于百度指數(shù)整體日均值的城市vi對城市vj的搜索指數(shù)，在此不考慮城市對自身的搜索指數(shù)，即j=i時(shí)，qij=0。

通常認(rèn)為城市間的聯(lián)系密切程度與城市間的相互吸引力有關(guān)，根據(jù)引力模型及其改進(jìn)模型，城市間的引力強(qiáng)度與其質(zhì)量水平呈正相關(guān)，與其距離呈負(fù)相關(guān)。利用城市年末人口數(shù)和生產(chǎn)總值表示城市經(jīng)濟(jì)質(zhì)量水平，城市間的最短公路里程表示城市間的距離，選擇特征屬性集P*=P1，P2，P3，相應(yīng)的特征屬性集映射函數(shù)為

FEcovi，vj=kij× pi1pi2×pj1pj2D2ij（2）

通過FEco（vi，vj）可建立城市vi和vj間的經(jīng)濟(jì)聯(lián)系，其中，kij=pi2/（pi2+pj2）為城市vi在城市vi與vj經(jīng)濟(jì)發(fā)展聯(lián)系中的貢獻(xiàn)率，Dij=ej·pi3，ej為第j個(gè)分量值為1的1×17階的單位向量。

由于基于百度指數(shù)獲取的關(guān)注度數(shù)據(jù)覆蓋面廣泛，可以作為一種較為可信的數(shù)據(jù)用以表征城市間的信息流特征，選擇特征屬性集P*={P4}，相應(yīng)的特征屬性集映射函數(shù)為

FInforvi，vj=ej·pi4（3）

通過FInforvi，vj可建立城市vi和vj間的信息聯(lián)系，其中，ej同上。

3.2 分析

從算法的適用場景對基于多功能網(wǎng)的最短路經(jīng)查詢算法與其他最短路徑查詢算法進(jìn)行對比分析，如表1，其中靜態(tài)網(wǎng)絡(luò)指網(wǎng)絡(luò)結(jié)構(gòu)固定，動態(tài)網(wǎng)絡(luò)指根據(jù)用戶的不同功能需求，網(wǎng)絡(luò)結(jié)構(gòu)不同。MFCNSPQ算法通過改變特征屬性集映射函數(shù)來改變網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)而實(shí)現(xiàn)動態(tài)網(wǎng)絡(luò)上的最短路經(jīng)查詢，相較于其他算法適用場景更廣。

緊密中心性和介數(shù)中心性是復(fù)雜網(wǎng)絡(luò)分析中與節(jié)點(diǎn)間最短路徑相關(guān)的兩個(gè)重要的中心性度量指標(biāo)。多功能網(wǎng)中節(jié)點(diǎn)基于特征屬性集映射函數(shù)F的物理緊密中心性（簡記為基于F的物理緊密中心性）

CCFvi=minvk∈V∑vj∈VlFvk，vj/∑vj∈VlFvi，vj（4）

其中，minvk∈V∑vj∈VlFvk，vj為多功能網(wǎng)中所有節(jié)點(diǎn)與其他節(jié)點(diǎn)間基于F的物理距離之和中的最小值，∑vj∈VlFvi，vj為節(jié)點(diǎn)vi與其他節(jié)點(diǎn)間基于F的物理距離之和。當(dāng)任意一對節(jié)點(diǎn)間不存在基于F的最短物理路徑時(shí)，節(jié)點(diǎn)間基于F的物理距離記為SymboleB@，若分子或分母為SymboleB@，令CCFvi=0，則0≤CCFvi≤ 1。節(jié)點(diǎn)vi與其他節(jié)點(diǎn)間基于F的物理距離越近，CCFvi越接近1，節(jié)點(diǎn)vi基于F的物理緊密中心性越高。節(jié)點(diǎn)vi與vj間基于F的最短物理路徑存在方向時(shí)，可以分為基于F的出物理緊密中心性和基于F的入物理緊密中心性。

多功能網(wǎng)中節(jié)點(diǎn)基于特征屬性集映射函數(shù)F的物理介數(shù)中心性（簡記為基于F的物理介數(shù)中心性）定義為

BCFvi=∑vs≠vi≠vt∈VδFvs，vt（vi）/δFvs，vt（5）

其中，δFvs，vt為節(jié)點(diǎn)vs與vt間基于F的最短物理路徑的條數(shù)，δFvs，vt（vi）為節(jié)點(diǎn)vs與vt間基于F的最短物理路徑經(jīng)過節(jié)點(diǎn)vi的條數(shù)。節(jié)點(diǎn)間基于F的最短物理路徑中經(jīng)過節(jié)點(diǎn)vi的條數(shù)越多，BCFvi越大，節(jié)點(diǎn)vi基于F的物理介數(shù)中心性越高。

利用MFCNSPQ算法查詢山東半島城市群網(wǎng)絡(luò)中所有城市節(jié)點(diǎn)間基于FEco和FInfor的最短物理路徑，根據(jù)式（4）對各城市節(jié)點(diǎn)基于FEco和FInfor的出物理緊密中心性進(jìn)行計(jì)算，結(jié)果如圖1。從出物理緊密中心性來看，濟(jì)南、青島、濰坊和臨沂基于FEco和FInfor的物理緊密中心性均明顯高于其他城市，能與其他城市更快的主動產(chǎn)生經(jīng)濟(jì)和信息聯(lián)系，具有很強(qiáng)經(jīng)濟(jì)和信息輻射能力。從入物理緊密中心性來看，淄博、泰安和臨沂基于FEco的入物理緊密中心性較高，其次為濟(jì)南、濰坊、濟(jì)寧和德州，這些城市更容易受到其他城市的影響，具有較強(qiáng)的經(jīng)濟(jì)資源整合能力;濟(jì)南和青島基于FInfor的入物理緊密中心性遠(yuǎn)高于其他城市，是城市群中信息集聚的中心。

根據(jù)式（5）對各城市節(jié)點(diǎn)基于FEco和FInfor的物理介數(shù)中心性進(jìn)行計(jì)算，結(jié)果如圖2。山東半島城市群網(wǎng)絡(luò)中城市節(jié)點(diǎn)基于FEco和FInfor的物理介數(shù)中心性兩極分化明顯?；贔Eco的物理介數(shù)中心性均值為911，高于這一均值的城市有濰坊、泰安、濟(jì)南、臨沂、青島、煙臺、淄博和濟(jì)寧，其中，濰坊位于城市群中部作為重要的交通樞紐，其基于FEco的物理介數(shù)中心性遠(yuǎn)高于其他城市，是城市群城市間經(jīng)濟(jì)聯(lián)系中的重要紐帶;基于FInfor的物理介數(shù)中心性均值為789，高于這一均值的城市有濟(jì)南、青島、濰坊和臨沂，其中，濟(jì)南和青島基于FInfor的物理介數(shù)中心性遠(yuǎn)高于其他城市，對城市群城市間信息流動具有很強(qiáng)控制能力。

綜上，山東半島城市群的經(jīng)濟(jì)和信息空間基本呈現(xiàn)一致性且均表現(xiàn)為多中心格局，濟(jì)南、青島、濰坊和臨沂是帶動城市群經(jīng)濟(jì)和信息發(fā)展的重要力量，淄博、煙臺、濟(jì)寧和泰安在中心城市的輻射帶動下也表現(xiàn)出了一定的發(fā)展?jié)摿Γ鴹椙f和日照等城市在經(jīng)濟(jì)和信息空間中則處于邊緣地位。建議未來充分利用經(jīng)濟(jì)和信息建設(shè)的相互促進(jìn)作用，在繼續(xù)發(fā)展和擴(kuò)大中心城市輻射能力的基礎(chǔ)上，重點(diǎn)培育潛力城市，對邊緣城市產(chǎn)生新的帶動作用，從而實(shí)現(xiàn)山東半島城市群的協(xié)調(diào)發(fā)展。

4 結(jié)論

本文研究了基于多功能網(wǎng)的最短路徑查詢問題。利用節(jié)點(diǎn)在不同特征屬性集下的相互作用，查詢節(jié)點(diǎn)間基于不同特征屬性集映射函數(shù)的全部最短物理路徑。提出了MFCNSPQ算法并分析了其有效性，相較于其他最短路徑查詢算法，MFCNSPQ算法具有更廣的適用場景。結(jié)合社會科學(xué)領(lǐng)域知識，從經(jīng)濟(jì)和信息角度對山東半島城市群網(wǎng)絡(luò)進(jìn)行了查詢與中心性分析，結(jié)合分析結(jié)果為區(qū)域規(guī)劃和政策部署提供了建議。由于本文在進(jìn)行查詢時(shí)，并未考慮節(jié)點(diǎn)間的關(guān)聯(lián)權(quán)值，這可能會導(dǎo)致部分網(wǎng)絡(luò)信息的損失，因此在以后的研究中基于多功能網(wǎng)的考慮節(jié)點(diǎn)間關(guān)聯(lián)權(quán)值的最短路徑查詢問題是重要的方向。

參考文獻(xiàn)

[1]LEIFELD P，CRANMER S J. A theoretical and empirical comparison of the temporal exponential random graph model and the stochastic actor-oriented model[J]. Radiochimica Acta， 2015，94（2）：679-682.

[2]吳亞晶，張鵬，狄增如，等. 二分網(wǎng)絡(luò)研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2010，7（1）：1-12.

[3]MATTHIEU L，CLEMENCE M，NATHALIE D V. Basic notions for the analysis of large two-mode networks[J]. Social Networks， 2008，30（1）：31-48.

[4]KURANT M，THIRAN P. Layered complex networks[J]. Physical Review Letters，2006，96（13）：138701.

[5]KURANT M， THIRAN P， HAGMANN P. Error and attack tolerance of layered complex networks[J]. Physical Review E， 2007，76（2）：026103.

[6]邵峰晶，孫仁誠，李淑靜，等. 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)及其運(yùn)算研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2012， 9（4）：20-25.

[7]隋毅，邵峰晶，孫仁誠，等. 基于向量空間的多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型動態(tài)組網(wǎng)運(yùn)算的形式描述[J]. 軟件學(xué)報(bào)， 2015， 26（8）：2007-2019.

[8]鐘麗君，賓晟，袁敏，等. 多功能復(fù)雜網(wǎng)絡(luò)模型及其應(yīng)用[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2019，16（2）：31-40.

[9]XIAO Y， WU W， PEI J， et al. Efficiently indexing shortest paths by exploiting symmetry in graphs[C]// International Conference on Extending Database Technology. New York，2009：439-504.

[10] TREYTAKOV K， ARMAS-CERVANTES A， VILO J， et al. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs[C]// Acm Conference on Information & Knowledge Management. New York， 2011：1785-1794.

[11] 李忠飛，楊雅君，王鑫.基于規(guī)則的最短路徑查詢算法[J].軟件學(xué)報(bào)，2019，30（3）：515-536.

[12] PHILANI B， RANDHIR R. Development of an optimal state transition graph for trajectory optimisation of dynamic systems by application of Dijkstra's algorithm[J]. Computers & Chemical Engineering， 2019， 125：569-586.

[13] 王樹西，李安渝.Dijkstra算法中的多鄰接點(diǎn)與多條最短路徑問題[J].計(jì)算機(jī)科學(xué)，2014，41（6）：217-224.

[14] 左秀峰，沈萬杰.基于Floyd算法的多重最短路問題的改進(jìn)算法[J].計(jì)算機(jī)科學(xué)，2017，44（5）：232-234+267.

[15] 盧立果，劉立越，魯鐵定，等.一種改進(jìn)的Floyd算法[J].東華理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，42（1）：78-81.

[16] KANG N K， SON H J， LEE S H. Modified A-star algorithm for modular plant land transportation[J]. Journal of Mechanical Science and Technology， 2018， 32（12）：5563-5571.

[17] FU W C， WU H， CHENG J， et al. IS-LABEL： An independent-set based labeling scheme for point-to-point distance querying on large graphs[J]. Proceedings of the Vldb Endowment， 2012， 6（6）. doi：10.14778/2536336.2536346

[18] TAKUYA A，YOICHI I，YUICHI Y. Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C].//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data，NewYork，2013：349-360.

[19] 馬學(xué)廣，唐承輝. 基于功能性聯(lián)系的山東半島城市群空間范圍劃定實(shí)證研究[J]. 經(jīng)濟(jì)地理， 2020， 40（5）：106-117.

[20] 劉曉明，孫毅，秦夢. 山東經(jīng)濟(jì)增長中的結(jié)構(gòu)調(diào)整效應(yīng)分解與路徑分析—基于新舊動能轉(zhuǎn)換的視角[J]. 青島大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2020， 33（1）：91-98.

[21] 王振波，楊勵(lì)雅，梁龍武，等.山東半島城市群交通網(wǎng)絡(luò)載流能力評估與優(yōu)化研究[J]. 地球信息科學(xué)學(xué)報(bào)， 2017， 19（6）：808-817.

Shortest Path Query Algorithm Based on Multi-functional Network Model

YUAN Min， SUN Geng-xin， BIN Sheng

（School of Data Science and Software Engineering， Qingdao University， Qingdao 266071， China）

Abstract：

The shortest path between nodes under single network function has been widely concerned in the existing research. On this basis， the shortest path query problem based on multi-functional network model is proposed， and a query algorithm based on greedy strategy is proposed to query the shortest path between nodes under different network functions. In the experiment， the multi-functional network model is used to model the urban agglomeration of Shandong Peninsula， and the shortest paths between cities when the urban agglomeration network realizes two different functions of economy and information are queried and calculated and analyzed. The result shows that querying the shortest paths between nodes under different network functions has certain practical significance for mining the potential connections between different functions of complex systems.

Keywords：

multi-functional complex network model; shortest path query algorithm; centrality; Shandong Peninsula urban agglomeration