基于多功能網的最短路徑查詢算法

袁敏 孫更新 賓晟

摘要：在單一網絡功能下節點間最短路徑的研究基礎上，提出基于多功能網的最短路徑查詢問題，給出一種基于貪心策略的查詢算法來查詢節點間在不同網絡功能下的最短路徑。利用多功能網對山東半島城市群進行建模，分別查詢城市群網絡實現經濟和信息兩種不同功能時城市間的最短路徑，并計算分析。研究結果表明，查詢節點間在不同網絡功能下的最短路徑對于挖掘復雜系統不同功能間的潛在聯系具有一定的現實意義。

關鍵詞：多功能網;最短路徑查詢算法;中心性;山東半島城市群

中圖分類號：N95

文獻標志碼：A

收稿日期：2020-11-02

基金項目：

教育部人文社會科學研究青年項目（批準號：15YJC860001）資助;山東省自然基金面上項目（批準號：ZR2017MG011）資助;山東省社會科學規劃項目（批準號：17CHLJ16）資助。

通信作者：

孫更新，男，博士，副教授，主要研究方向為大數據分析、數據挖掘、復雜網絡。E-mail：sungengxin@qdu.edu.cn

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

1 多功能網

多功能網認為實體間的相互作用與實體的特征屬性有關，利用節點來表示復雜系統中的實體，節點以特征屬性向量的形式表示，通過動態地選擇特征屬性集，依據相應的特征屬性集映射函數來確定節點間的關聯，進而實現特定的網絡功能。該模型使用三元組MFCN=V，P，F來表示：

（1）V=∪|V|i=1vi是多功能網的節點集合;

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

（3）Fvi，vj=ξ（f1，f2，…，fh，…，ft）是多功能網基于所選擇的特征屬性集P*（P*P）的特征屬性集映射函數，節點vi，vj間基于特征屬性集P*建立的關聯通過其實現，其中t≤P，fh是特征屬性Ph對應的特征屬性映射函數。

節點數量為V，具有P個特征屬性的多功能網，可用V×P的矩陣描述：

2 基于多功能網的最短路徑查詢

2.1 基本概念

定義1 基于特征屬性集映射函數F的路徑。對多功能網MFCN=V，P，F，選擇不同的特征屬性集，其映射函數不同，節點間的相互作用不同，進而使得節點間的路徑不同。給定起始節點vs和目標節點vt（vt≠vs），若有節點序列l=vs，…，vk，vk+1，…，vt，其中vk，vk+1∈l在特征屬性集映射函數F下均存在關聯，則稱l為由節點vs到vt的基于特征屬性集映射函數F的路徑，簡記為基于F的路徑。

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

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

其中，σ為函數，在特征屬性集映射函數F下，當節點vi和vj存在關聯時，有σFvi，vj=1，否則σFvi，vj=0。

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

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

2.2 查詢算法

基于多功能網的最短路徑查詢的形式定義為Q=（vs，vt），其中vs為起始節點，vt為目標節點，則多功能網上基于特征屬性集映射函數最短路徑查詢問題（MFCNSPQ）定義如下：

輸入：多功能網MFCN，最短路徑查詢Q;

輸出：節點vs到vt的基于F的全部最短物理路徑。

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

Step 1 利用特征屬性集映射函數F對節點vs和vt進行運算，得到返回值Fvs，vt，判斷Fvs，vt是否滿足映射規則，若滿足，則l=vs，vt為vs到vt的基于F的最短物理路徑，算法結束，否則執行Step 2;

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

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

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

P1P2P3P4P5P6

v1v2v3v4v5v6v7100000

110000

101100

011010

000101

000011

000000

查詢節點v1到v6的基于F的最短物理路徑，其中F為特征屬性集P*=P對應的特征屬性集映射函數，利用特征屬性集映射函數F對節點vi和vj進行運算，Fvi，vj=pi·pj，返回值Fvi，vj1時，滿足映射規則，節點vi和vj在特征屬性集映射函數F下存在關聯。具體步驟如下：

Step 1 利用特征屬性集映射函數F對節點v1和v6進行運算，得到返回值Fv1，v6=0，不滿足映射規則，執行Step 2;

Step 2 利用特征屬性集映射函數用F對節點v1和節點v2，v3，v4，v5，v7逐一運算，有Fv1，v2和Fv1，v3滿足映射規則，于是集合S={v2，v3}，更新節點v2和v3的前置節點信息為v1，利用特征屬性集映射函數F對節點v2、v3和節點v6逐一運算，Fv2，v6和Fv3，v6均不滿足映射規則，執行Step 3;

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

3 實驗

3.1 建模

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

以城市為節點，基于多功能網的山東半島城市群網絡可用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）

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

通常認為城市間的聯系密切程度與城市間的相互吸引力有關，根據引力模型及其改進模型，城市間的引力強度與其質量水平呈正相關，與其距離呈負相關。利用城市年末人口數和生產總值表示城市經濟質量水平，城市間的最短公路里程表示城市間的距離，選擇特征屬性集P*=P1，P2，P3，相應的特征屬性集映射函數為

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

通過FEco（vi，vj）可建立城市vi和vj間的經濟聯系，其中，kij=pi2/（pi2+pj2）為城市vi在城市vi與vj經濟發展聯系中的貢獻率，Dij=ej·pi3，ej為第j個分量值為1的1×17階的單位向量。

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

FInforvi，vj=ej·pi4（3）

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

3.2 分析

從算法的適用場景對基于多功能網的最短路經查詢算法與其他最短路徑查詢算法進行對比分析，如表1，其中靜態網絡指網絡結構固定，動態網絡指根據用戶的不同功能需求，網絡結構不同。MFCNSPQ算法通過改變特征屬性集映射函數來改變網絡結構，進而實現動態網絡上的最短路經查詢，相較于其他算法適用場景更廣。

緊密中心性和介數中心性是復雜網絡分析中與節點間最短路徑相關的兩個重要的中心性度量指標。多功能網中節點基于特征屬性集映射函數F的物理緊密中心性（簡記為基于F的物理緊密中心性）

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

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

多功能網中節點基于特征屬性集映射函數F的物理介數中心性（簡記為基于F的物理介數中心性）定義為

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

其中，δFvs，vt為節點vs與vt間基于F的最短物理路徑的條數，δFvs，vt（vi）為節點vs與vt間基于F的最短物理路徑經過節點vi的條數。節點間基于F的最短物理路徑中經過節點vi的條數越多，BCFvi越大，節點vi基于F的物理介數中心性越高。

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

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

綜上，山東半島城市群的經濟和信息空間基本呈現一致性且均表現為多中心格局，濟南、青島、濰坊和臨沂是帶動城市群經濟和信息發展的重要力量，淄博、煙臺、濟寧和泰安在中心城市的輻射帶動下也表現出了一定的發展潛力，而棗莊和日照等城市在經濟和信息空間中則處于邊緣地位。建議未來充分利用經濟和信息建設的相互促進作用，在繼續發展和擴大中心城市輻射能力的基礎上，重點培育潛力城市，對邊緣城市產生新的帶動作用，從而實現山東半島城市群的協調發展。

4 結論

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

參考文獻

[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]吳亞晶，張鵬，狄增如，等. 二分網絡研究[J]. 復雜系統與復雜性科學，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]邵峰晶，孫仁誠，李淑靜，等. 多子網復合復雜網絡及其運算研究[J]. 復雜系統與復雜性科學，2012， 9（4）：20-25.

[7]隋毅，邵峰晶，孫仁誠，等. 基于向量空間的多子網復合復雜網絡模型動態組網運算的形式描述[J]. 軟件學報， 2015， 26（8）：2007-2019.

[8]鐘麗君，賓晟，袁敏，等. 多功能復雜網絡模型及其應用[J]. 復雜系統與復雜性科學， 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] 李忠飛，楊雅君，王鑫.基于規則的最短路徑查詢算法[J].軟件學報，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算法中的多鄰接點與多條最短路徑問題[J].計算機科學，2014，41（6）：217-224.

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

[15] 盧立果，劉立越，魯鐵定，等.一種改進的Floyd算法[J].東華理工大學學報（自然科學版），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] 馬學廣，唐承輝. 基于功能性聯系的山東半島城市群空間范圍劃定實證研究[J]. 經濟地理， 2020， 40（5）：106-117.

[20] 劉曉明，孫毅，秦夢. 山東經濟增長中的結構調整效應分解與路徑分析—基于新舊動能轉換的視角[J]. 青島大學學報（自然科學版）， 2020， 33（1）：91-98.

[21] 王振波，楊勵雅，梁龍武，等.山東半島城市群交通網絡載流能力評估與優化研究[J]. 地球信息科學學報， 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