摘 要:為提高航線網(wǎng)絡(luò)魯棒性,對航線網(wǎng)絡(luò)的節(jié)點(diǎn)重要性辨識進(jìn)行研究.基于航空公司執(zhí)飛數(shù)據(jù)構(gòu)建航線網(wǎng)絡(luò)拓?fù)淠P?,依托航線網(wǎng)絡(luò)節(jié)點(diǎn)間交互階數(shù)與網(wǎng)絡(luò)平均路徑差值集結(jié)鄰域多階異質(zhì)性信息,利用航線網(wǎng)絡(luò)鄰域節(jié)點(diǎn)的圈結(jié)構(gòu)表征節(jié)點(diǎn)在網(wǎng)絡(luò)中的緊密性特征集結(jié).構(gòu)建基于航線網(wǎng)絡(luò)的節(jié)點(diǎn)多階鄰域信息與結(jié)構(gòu)信息融合模型并提出基于多階鄰域貢獻(xiàn)度的節(jié)點(diǎn)中心性算法.實(shí)驗(yàn)選取投入攻擊資源R=0.3和R=0.5進(jìn)行分析,分別最大提升39.62%和49.69%的攻擊效用值,表明該算法對航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識準(zhǔn)確有效,可給航線網(wǎng)絡(luò)連通性優(yōu)化設(shè)計(jì)提供理論參考.
關(guān)鍵詞:
航線網(wǎng)絡(luò);節(jié)點(diǎn)多階鄰域;鄰域貢獻(xiàn)度;圈結(jié)構(gòu)貢獻(xiàn)度
中圖分類號:
TP39"" 文獻(xiàn)標(biāo)志碼:
A"" 文章編號:
1000-1565(2024)03-0329-08
Node importance identification in airline networkbased on multi-order neighborhood contribution degree
HU Gang1,2, WANG Lemeng1, LU Zhiyu1, HU Junjie1, KANG Kai1
(1.School of Management Science and Engineering, Anhui University of Technology, Maanshan243032, China; 2.Key Laboratory of Multidisciplinary Management and Control of Complex Systems of Anhui Higher Education Institutes, Maanshan 243032, China)
Abstract: In order to improve the robustness of airline network, the node importance identification of airline network is studied. A airline network topology model is constructed based on airline flight data, and multi-order heterogeneity information of the neighborhood is gathered by means of interaction order and average path difference between the nodes of the airline network. The circle structure of the neighborhood nodes of the airline network is used to characterize the closeness of the nodes in the network. A fusion model of multi-order neighborhood information and structural information of nodes is constructed based on airline network and a node centrality algorithm is proposed based on multi-order neighborhood contribution. The attack resources R=0.3 and R=0.5 are selected for the analysis, which maximally improve the attack utility value by 39.62% and 49.69%, respectively, indicating that the algorithm is accurate and effective in identifying the importance of nodes in the airline network, and it can provide theoretical references for the optimal design of the connectivity of the airline network.
Key words: airline network; multi-order neighborhood of nodes; neighborhood contribution degree; circle structure contribution degree
隨著社會發(fā)展和科技進(jìn)步,空中交通[1]成為人民生活的重要出行途徑之一.有效識別航空線路網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)、鏈路,針對性優(yōu)化航空線路網(wǎng)絡(luò),使其具有更高的魯棒性是當(dāng)今社會亟需解決的關(guān)鍵問題.航線網(wǎng)絡(luò)分析研究多以網(wǎng)絡(luò)魯棒性[2]、節(jié)點(diǎn)重要性[3]、航線效用[4]等角度開展.在系統(tǒng)控制科學(xué)研究領(lǐng)域,諸多學(xué)者以“魯棒性”表述系統(tǒng)的健康程度,以魯棒性指代系統(tǒng)不受特性或參數(shù)變化的影響.復(fù)雜網(wǎng)絡(luò)的魯棒性即為網(wǎng)絡(luò)遭受破壞時(shí)的網(wǎng)絡(luò)信息傳輸及網(wǎng)絡(luò)最大連通組件維持連通性等能力的保持性[5];廣義節(jié)點(diǎn)重要性反映復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的大小或?qū)蛹壍母叩停骄€效用反映該航線對網(wǎng)絡(luò)連通性維持的貢獻(xiàn).異常天氣[6]、突發(fā)公共事件[7]、航材備品損壞、應(yīng)急管控干擾等諸多因素都會導(dǎo)致其網(wǎng)絡(luò)節(jié)點(diǎn)或連邊部分失效,進(jìn)而影響整個(gè)航線網(wǎng)絡(luò)的連通性.
目前,度中心性[8]、介數(shù)中心性[9]、k-shell[10]、接近中心性[11]等經(jīng)典指標(biāo)已在航線網(wǎng)絡(luò)節(jié)點(diǎn)辨識中取得廣泛發(fā)展和應(yīng)用.如何更有效和高效地識別航線網(wǎng)絡(luò)重要節(jié)點(diǎn)方面仍有更多的工作要做.王興隆等[12]根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)流量,提出改進(jìn)的復(fù)雜度矩陣和節(jié)點(diǎn)效率指標(biāo)來評估網(wǎng)絡(luò)性能.楊泳等[13]和杜方葉等[14]分別從國內(nèi)和國際航線分析中國航空網(wǎng)絡(luò)的空間格局演變特征.胡鋼等[15]提出以鄰域熵信息異質(zhì)性為基礎(chǔ)的多階鄰域信息集結(jié)模型,辨識航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性序結(jié)構(gòu).張培文等[16]以復(fù)雜網(wǎng)絡(luò)相關(guān)指標(biāo)與標(biāo)準(zhǔn)差橢圓進(jìn)行反距離權(quán)重法插值,分析國內(nèi)客運(yùn)航空網(wǎng)絡(luò)空間結(jié)構(gòu)演化特征.馮霞等[17]提出節(jié)點(diǎn)失效和邊失效的航線網(wǎng)絡(luò)魯棒性系統(tǒng)分析方法.在國外研究中參與系數(shù)(PC)[18]、模塊化生命力中心性(MVC)[19]、度聚類系數(shù)(DCC)[20]等指標(biāo)對航線網(wǎng)絡(luò)重要節(jié)點(diǎn)辨識的研究受到廣泛關(guān)注.Guimera等[18]強(qiáng)化節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)塊內(nèi)度和參與系數(shù),指定節(jié)點(diǎn)在自己的區(qū)塊內(nèi)和與其他區(qū)塊內(nèi)的關(guān)系.Magelinski等[19]根據(jù)節(jié)點(diǎn)移除后模塊化變化活力提出局部結(jié)構(gòu)活躍性指標(biāo)作為集群質(zhì)量活力的度量衡量.Yang等[20]考慮目標(biāo)節(jié)點(diǎn)及其鄰居度和目標(biāo)節(jié)點(diǎn)及其二級鄰居的聚類系數(shù)提出半局部中心性測度.對于航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識,單一中心性測度存在局限性.例如,度中心性只考慮節(jié)點(diǎn)的局部信息;當(dāng)2個(gè)節(jié)點(diǎn)屬于不同的連通切片時(shí),接近中心性難以科學(xué)確定節(jié)點(diǎn)影響力;介數(shù)中心性考慮網(wǎng)絡(luò)的全局結(jié)構(gòu),但在實(shí)際航線網(wǎng)絡(luò)中節(jié)點(diǎn)大多處于網(wǎng)絡(luò)邊緣位置,不處于網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑上,介數(shù)中心性無法有效區(qū)分邊緣節(jié)點(diǎn)的重要性差異.如何進(jìn)一步準(zhǔn)確辨識航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性信息亟待進(jìn)一步研究驗(yàn)證.
本文以辨識航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性為基礎(chǔ),給出基于網(wǎng)絡(luò)平均路徑長度與節(jié)點(diǎn)間交互階數(shù)差異的多階鄰域貢獻(xiàn)度定義;通過航線網(wǎng)絡(luò)節(jié)點(diǎn)鄰域內(nèi)圈結(jié)構(gòu)形成的概率集定義節(jié)點(diǎn)圈結(jié)構(gòu)貢獻(xiàn)度;最后,集結(jié)節(jié)點(diǎn)鄰域的層級信息和圈結(jié)構(gòu)表征航線網(wǎng)絡(luò)節(jié)點(diǎn)的可替代性,形成航線網(wǎng)絡(luò)節(jié)點(diǎn)中心性(airlines network node neighborhood centrality,ANC).該中心性相比其他算法,通過以網(wǎng)絡(luò)平均路徑長度為多階信息集結(jié)能力測度基準(zhǔn),自適應(yīng)不同類型的網(wǎng)絡(luò)信息集結(jié),并融合節(jié)點(diǎn)鄰域異質(zhì)性層級信息和結(jié)構(gòu)信息辨識節(jié)點(diǎn)在網(wǎng)絡(luò)連通性維護(hù)中的重要作用,綜合節(jié)點(diǎn)局部和全局信息的動態(tài)性平衡,其中心性的定量計(jì)算不僅體現(xiàn)節(jié)點(diǎn)在各自鄰域結(jié)構(gòu)內(nèi)的屬性表達(dá),也體現(xiàn)間接相連節(jié)點(diǎn)在鄰域結(jié)構(gòu)外所形成的特殊結(jié)構(gòu)屬性信息表達(dá).
1 航線拓?fù)渚W(wǎng)絡(luò)節(jié)點(diǎn)辨識理論基礎(chǔ)
1.1 航線網(wǎng)絡(luò)特點(diǎn)
航空運(yùn)輸需要航空站、航線、航空器、服務(wù)提供商、終端設(shè)施等共同作用.本文構(gòu)建航線拓?fù)渚W(wǎng)絡(luò),其復(fù)雜性特點(diǎn)如下:1)航線網(wǎng)絡(luò)節(jié)點(diǎn)復(fù)雜.隨著人民生活需求的日益增長,諸多地級市均已經(jīng)擁有執(zhí)飛機(jī)場.這些機(jī)場分布于不同的地區(qū),委托管理于不同的服務(wù)提供商,呈現(xiàn)出多主體、多區(qū)塊的耦合架構(gòu).2)航線網(wǎng)絡(luò)線路復(fù)雜.機(jī)場間航線數(shù)量倍增,傳統(tǒng)的稀疏性航線網(wǎng)絡(luò)逐步消失,取而代之的是呈現(xiàn)出以核心機(jī)場為網(wǎng)絡(luò)連接中心,邊緣機(jī)場隨機(jī)連接的錯綜航線網(wǎng)絡(luò).3)航線網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜.以往單核心或雙核心的區(qū)域性航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)逐漸被多中心、組塊化的區(qū)域性航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)替代.網(wǎng)絡(luò)中效用相同的結(jié)構(gòu)大幅度增多,維持航線網(wǎng)絡(luò)連通性,保持高連通性網(wǎng)絡(luò)運(yùn)行效率的研究場景日趨復(fù)雜化.
1.2 航線網(wǎng)絡(luò)拓?fù)錅?zhǔn)則
基于東方航空公司2023年3月的國內(nèi)航線數(shù)據(jù)建立航線系統(tǒng)研究的拓?fù)淠P?該拓?fù)淠P偷臉?gòu)建準(zhǔn)則如下:1)將東方航空公司執(zhí)飛航線涉及機(jī)場抽象為復(fù)雜航線網(wǎng)絡(luò)中的節(jié)點(diǎn);2)將東方航空公司國內(nèi)執(zhí)飛航線抽象為復(fù)雜航線網(wǎng)絡(luò)中的節(jié)點(diǎn)間連邊;3)定義節(jié)點(diǎn)間連邊均是雙向信息傳輸,即為無向連邊;4)定義節(jié)點(diǎn)間航線存在通航能力即滿足信息傳輸,不考慮航線涉及點(diǎn)的規(guī)模和等級影響.
1.3 航線網(wǎng)絡(luò)模型構(gòu)建
復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)及節(jié)點(diǎn)間信息多以邊表格、鄰接表及鄰接矩陣等形式保存.依托中國航空網(wǎng)以及VariFlight Map提供的國內(nèi)航線為拓?fù)湫畔碓?根據(jù)機(jī)場節(jié)點(diǎn)間連邊均是雙向信息傳輸準(zhǔn)則,刪去重復(fù)性航線信息,得到最終有效航線信息邊表格,如表1所示.
根據(jù)表1的編號對應(yīng)規(guī)則,將機(jī)場連邊轉(zhuǎn)化為節(jié)點(diǎn)間連邊,形成復(fù)雜網(wǎng)絡(luò)“MU-3”,網(wǎng)絡(luò)基本統(tǒng)計(jì)數(shù)據(jù)信息如表2所示.
其中,n表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù),m表示網(wǎng)絡(luò)的邊數(shù),MU-3航線網(wǎng)絡(luò)共有159個(gè)節(jié)點(diǎn)、829條邊,〈k〉表示網(wǎng)絡(luò)節(jié)點(diǎn)平均度值,〈l〉表示網(wǎng)絡(luò)平均路徑長度;c表示網(wǎng)絡(luò)集聚系數(shù)數(shù)值,ksmax表示網(wǎng)絡(luò)層級位置的最高層級數(shù)值.
1.4 航線拓?fù)渚W(wǎng)絡(luò)統(tǒng)計(jì)指標(biāo)分析
1.4.1 度中心性分布及可視化
依托節(jié)點(diǎn)度中心性對MU-3航線網(wǎng)絡(luò)進(jìn)行基礎(chǔ)統(tǒng)計(jì)信息具體分析,度分布可視化如圖1.
基于表2,對MU-3航線網(wǎng)絡(luò)的聚集系數(shù)和平均路徑程度與同等節(jié)點(diǎn)數(shù)量和同等平均度的隨機(jī)網(wǎng)絡(luò)的聚集系數(shù)和平均路徑長度進(jìn)行對比(表3).crandom表示隨機(jī)網(wǎng)絡(luò)的集聚系數(shù);〈l〉random表示隨機(jī)網(wǎng)絡(luò)的平均路徑長度;c表示航線網(wǎng)絡(luò)的集聚系數(shù);〈l〉表示航線網(wǎng)絡(luò)的平均路徑長度.
根據(jù)表3可知MU-3航線網(wǎng)絡(luò)模型符合小世界網(wǎng)絡(luò)模型特性,因?yàn)樵摼W(wǎng)絡(luò)聚集系數(shù)和平均路徑長度均高于隨機(jī)網(wǎng)絡(luò)的相關(guān)指標(biāo)數(shù)值,MU-3航線網(wǎng)絡(luò)模型具有一定的小世界特性.通過圖1可發(fā)現(xiàn),MU-3網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的度數(shù)較低,只有少數(shù)節(jié)點(diǎn)的度值較高,同時(shí)圖1表明該網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)分布具有冪律特性,體現(xiàn)典型的無標(biāo)度網(wǎng)絡(luò)特性.因此MU-3航線網(wǎng)絡(luò)既具有小世界網(wǎng)絡(luò)模型特性同時(shí)又具有無標(biāo)度網(wǎng)絡(luò)模型特性.
1.4.2 介數(shù)中心性分布及可視化
節(jié)點(diǎn)的介數(shù)中心性是網(wǎng)絡(luò)任意2點(diǎn)之間最短路徑通過該節(jié)點(diǎn)比例的歸一化值.該值有效衡量節(jié)點(diǎn)在網(wǎng)絡(luò)信息傳播過程中基于路徑的控制能力.
圖2表征MU-3航線網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的介數(shù)中心性均較低,僅有極少數(shù)節(jié)點(diǎn)的介數(shù)中心性較高,說明在該網(wǎng)絡(luò)中存在部分核心介數(shù)中心性較強(qiáng)節(jié)點(diǎn),這些節(jié)點(diǎn)之間的連邊控制著網(wǎng)絡(luò)的連通性穩(wěn)定.以上信息表明,航線網(wǎng)絡(luò)因?yàn)楣?jié)點(diǎn)自身等級化特性,大量節(jié)點(diǎn)處于同一節(jié)點(diǎn)重要性指標(biāo)分布層級,故用該類指標(biāo)對航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識.基于該類指標(biāo)所辨識節(jié)點(diǎn)序列對航線網(wǎng)絡(luò)進(jìn)行破壞性仿真,其連通性穩(wěn)定性都不能取得較為科學(xué)的結(jié)果,必須集結(jié)更多維度節(jié)點(diǎn)信息才能有效識別航線網(wǎng)絡(luò)節(jié)點(diǎn)連通性的重要程度.
2 航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識模型構(gòu)建
2.1 航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識模型構(gòu)建
本文給出航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識方法.首先,基于網(wǎng)絡(luò)平均路徑長度與節(jié)點(diǎn)間交互階數(shù)差異給出多階鄰域貢獻(xiàn)度定義;其次,基于航線網(wǎng)絡(luò)節(jié)點(diǎn)鄰域內(nèi)特殊結(jié)構(gòu)形成概率集定義節(jié)點(diǎn)圈結(jié)構(gòu)貢獻(xiàn)度;最后,集結(jié)鄰域節(jié)點(diǎn)層級信息,結(jié)合圈結(jié)構(gòu)表征的航線網(wǎng)絡(luò)節(jié)點(diǎn)的可替代性信息,形成航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識指標(biāo),該指標(biāo)綜合節(jié)點(diǎn)鄰域異質(zhì)性層級信息和鄰域異質(zhì)性結(jié)構(gòu)信息辨識節(jié)點(diǎn)在網(wǎng)絡(luò)連通性維護(hù)中的重要作用.
定義1
航線網(wǎng)絡(luò)平均路徑長度
航線網(wǎng)絡(luò)平均路徑長度是指航線網(wǎng)絡(luò)中的任意2點(diǎn)間距離的平均值,用〈l〉表示,如果航線網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為N,則航線網(wǎng)絡(luò)的平均路徑長度計(jì)算即如式(1)所示.
〈l〉=2∑i≠jdijN(N-1),(1)
式(1)中,dij表示航線網(wǎng)絡(luò)中節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離.
定義2
航線網(wǎng)絡(luò)多階鄰域貢獻(xiàn)度
研究表明,網(wǎng)絡(luò)中節(jié)點(diǎn)間的交互傳遞效用定量化描述與網(wǎng)絡(luò)節(jié)點(diǎn)各階交互數(shù)量的概率分布密切相關(guān)[21],但過高階信息集結(jié)會對節(jié)點(diǎn)重要性辨識準(zhǔn)確性產(chǎn)生一定負(fù)向效用.本文拓展節(jié)點(diǎn)間交互傳遞作用測度的基準(zhǔn),依托網(wǎng)絡(luò)平均路徑長度與節(jié)點(diǎn)交互階數(shù)差值定義航線網(wǎng)絡(luò)多階鄰域貢獻(xiàn)度.研究表明,依托網(wǎng)絡(luò)平均路徑長度進(jìn)行節(jié)點(diǎn)間信息交互,其信息傳遞效用最高,故航線網(wǎng)絡(luò)節(jié)點(diǎn)各階鄰域貢獻(xiàn)度計(jì)算如式(2).
wτ=1-|τ-〈l〉|〈l〉,τ≤2〈l〉
0,τ>2〈l〉
,(2)
式(2)中,τ表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互階數(shù),〈l〉表示網(wǎng)絡(luò)平均路徑長度.該定義表明當(dāng)節(jié)點(diǎn)間交互信息的索引階數(shù)τ高于網(wǎng)絡(luò)平均路徑長度的2倍時(shí),即不考慮其帶來的信息貢獻(xiàn).網(wǎng)絡(luò)節(jié)點(diǎn)的多階鄰域貢獻(xiàn)度即為Wτ=(wτ)=[w1,w2,…,wmaxτ]T.
定義3
航線網(wǎng)絡(luò)圈結(jié)構(gòu)貢獻(xiàn)度
節(jié)點(diǎn)與鄰域節(jié)點(diǎn)交互形成的圈結(jié)構(gòu)數(shù)量可表征目標(biāo)節(jié)點(diǎn)在不同階交互網(wǎng)絡(luò)中的局部緊密性,同時(shí)也可表明多階交互關(guān)聯(lián)關(guān)系中目標(biāo)節(jié)點(diǎn)與網(wǎng)絡(luò)中其余節(jié)點(diǎn)的同質(zhì)程度.在航線網(wǎng)絡(luò)連通性研究中,受限于節(jié)點(diǎn)間產(chǎn)生交互關(guān)聯(lián)關(guān)系時(shí)的資源耗費(fèi)限制,若以二階圈結(jié)構(gòu)及以上多階圈結(jié)構(gòu)進(jìn)行航線節(jié)點(diǎn)連通性可替代程度描述不符合客運(yùn)航線轉(zhuǎn)駁的實(shí)際情況,一階最小圈結(jié)構(gòu)則符合真實(shí)客運(yùn)航線轉(zhuǎn)駁情況,故本文僅定義一階圈結(jié)構(gòu)貢獻(xiàn)度,給出航線網(wǎng)絡(luò)節(jié)點(diǎn)圈結(jié)構(gòu)貢獻(xiàn)度定義計(jì)算如式(3).
Ti=∑ni=1PTilog2PTi,
(3)
其中,Ti表示節(jié)點(diǎn)i因自身交互形成的圈結(jié)構(gòu)屬性特征信息對節(jié)點(diǎn)全局重要性指標(biāo)形成的貢獻(xiàn),PTi表示節(jié)點(diǎn)i組成的圈結(jié)構(gòu)與全網(wǎng)絡(luò)圈結(jié)構(gòu)的數(shù)量之比.網(wǎng)絡(luò)節(jié)點(diǎn)的圈結(jié)構(gòu)貢獻(xiàn)度即為T=(Ti)=[T1,T2,…,Tn]T.
2.2 航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識模型
基于節(jié)點(diǎn)多階鄰域空間位置信息和結(jié)構(gòu)信息貢獻(xiàn),可有效識別節(jié)點(diǎn)網(wǎng)絡(luò)重要程度,故本文定義航線網(wǎng)絡(luò)節(jié)點(diǎn)鄰域多屬性中心性,融合節(jié)點(diǎn)鄰域?qū)蛹墝傩孕畔ⅲ瑫r(shí)辨識節(jié)點(diǎn)在網(wǎng)絡(luò)連通性維持中的可替代性,給出航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識中心性,其計(jì)算方式如下:
ANCi=(1-Ti)2+∑j∈naτijwτijksj/bτi∑i∈n∑j∈naτijwτijksj/bτi,
(4)
式(4)中,Ti表示節(jié)點(diǎn)的一階鄰域內(nèi)可替代程度,該值越高,說明節(jié)點(diǎn)的網(wǎng)絡(luò)效用獨(dú)特性越低;ksj表示節(jié)點(diǎn)j的層級位置屬性信息,該信息依托k-shell方法獲取;bτi表示節(jié)點(diǎn)i對鄰域節(jié)點(diǎn)層級信息集結(jié)時(shí)的標(biāo)準(zhǔn)化處理.
3 航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識算法應(yīng)用
3.1 航線網(wǎng)絡(luò)連通性分析評價(jià)指標(biāo)
為便于對比航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識算法的準(zhǔn)確性和有效性,選取以下復(fù)雜網(wǎng)絡(luò)指標(biāo)的變化趨勢表征各算法針對MU-3網(wǎng)絡(luò)連通性核心節(jié)點(diǎn)辨識的科學(xué)性.
3.1.1 網(wǎng)絡(luò)連通性
無向網(wǎng)絡(luò)中節(jié)點(diǎn)若兩兩之間均擁有至少1條路徑則說明該網(wǎng)絡(luò)是連通的,若存在節(jié)點(diǎn)間無路徑則說明該網(wǎng)絡(luò)是不連通的;不連通的網(wǎng)絡(luò)是由多個(gè)連通子網(wǎng)組合而成,而擁有節(jié)點(diǎn)數(shù)最多的連通子網(wǎng)即是最大連通子圖.基于此,本文定義在依次刪除節(jié)點(diǎn)間連邊時(shí)所得網(wǎng)絡(luò)子圖數(shù)目與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比值和網(wǎng)絡(luò)最大連通子圖規(guī)模變化均可有效表征網(wǎng)絡(luò)在攻擊性仿真實(shí)驗(yàn)時(shí)的連通性變化.
3.1.2 攻擊效用指數(shù)
假設(shè)航線網(wǎng)絡(luò)完全崩潰為攻擊效用理想值,此時(shí)航線網(wǎng)絡(luò)子圖數(shù)目與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比值為最大值1.依據(jù)不同算法識別節(jié)點(diǎn)序列進(jìn)行蓄意仿真攻擊,網(wǎng)絡(luò)崩潰一般均呈現(xiàn)逐步擴(kuò)大趨勢,此時(shí)等梯度投入不同規(guī)模資源進(jìn)行節(jié)點(diǎn)間連邊攻擊,均有一個(gè)網(wǎng)絡(luò)子圖數(shù)目與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比值與其對應(yīng),此值可表示該規(guī)模資源投入造成的攻擊效用.此值除以攻擊效用理想值即為攻擊效用指數(shù),其定量描述公式為
AUIR=SRSmax,
(5)
式(5)中R表示投入攻擊資源數(shù),其范圍為R∈(0,1].SR表示R規(guī)模資源投入航線網(wǎng)絡(luò)攻擊獲得的航線網(wǎng)絡(luò)子圖數(shù)目與航線網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比值;Smax為攻擊效用理想值,AUIR為R規(guī)模資源投入攻擊的攻擊效用指數(shù).
3.2 航線網(wǎng)絡(luò)節(jié)點(diǎn)ANC中心性應(yīng)用
使用ANC中心性辨識MU-3航線網(wǎng)絡(luò)連通性重要節(jié)點(diǎn),同時(shí)因?yàn)樵摼W(wǎng)絡(luò)是國內(nèi)航線網(wǎng)絡(luò)拓?fù)?,考慮資源耗費(fèi)帶來的航線轉(zhuǎn)駁實(shí)情,在應(yīng)用中索引節(jié)點(diǎn)三階鄰域節(jié)點(diǎn)間交互關(guān)系信息.其算法應(yīng)用實(shí)現(xiàn)過程如下:
Step 1 計(jì)算MU-3網(wǎng)絡(luò)平均路徑長度.
將MU-3網(wǎng)絡(luò)邊表格導(dǎo)入程序,形成網(wǎng)絡(luò)MU-3,再計(jì)算網(wǎng)絡(luò)平均路徑長度:〈l〉 = 2.236.
Step 2 計(jì)算航線網(wǎng)絡(luò)多階鄰域貢獻(xiàn)度.
基于式(2)的網(wǎng)絡(luò)MU-3的多階鄰域貢獻(xiàn)度:W3=[0.447,0.894,0.658].
Step 3 航線網(wǎng)絡(luò)圈結(jié)構(gòu)貢獻(xiàn)度.
基于式(3)的網(wǎng)絡(luò)節(jié)點(diǎn)的圈結(jié)構(gòu)貢獻(xiàn)度列表:T=[0.001,0.160 7,…,0.002].
Step 4 航線網(wǎng)絡(luò)節(jié)點(diǎn)層級位置信息.
定義函數(shù)k-shell(),得網(wǎng)絡(luò)節(jié)點(diǎn)層級位置屬性信息列表:Ks=[1,14,…,2].
Step 5 航線網(wǎng)絡(luò)節(jié)點(diǎn)鄰域中心性.
基于式(4),得各節(jié)點(diǎn)鄰域中心性指標(biāo):ANC=[0.999,0.839,…,0.998].
Step 6 航線網(wǎng)絡(luò)節(jié)點(diǎn)鄰域中心性排序.
依據(jù)各節(jié)點(diǎn)ANC中心性依次排序,并輸出節(jié)點(diǎn)序列:list_node=[152,144,…,17].
為進(jìn)一步驗(yàn)證ANC中心性的有效性,選取本文算法和DC[8]、BC[9]、k-shell[10]、CC[11]及文獻(xiàn)[22]的算法進(jìn)行節(jié)點(diǎn)辨識率、連通性破壞及攻擊效用指數(shù)對比實(shí)驗(yàn),連通性破壞實(shí)驗(yàn)中依次等梯度刪除重要節(jié)點(diǎn)間連邊,統(tǒng)計(jì)依次刪除后連邊網(wǎng)絡(luò)子圖與節(jié)點(diǎn)數(shù)目的比值變化和網(wǎng)絡(luò)最大連通子圖規(guī)模變化.表4表明針對MU-3航線網(wǎng)絡(luò),本文算法對航線網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識擁有更高的區(qū)分度.
圖3表明,ANC中心性針對航空網(wǎng)絡(luò)節(jié)點(diǎn)重要性序列結(jié)構(gòu)的辨識相較于其余對比算法更加準(zhǔn)確.在等梯度刪除網(wǎng)絡(luò)連邊時(shí),依托ANC中心性辨識所得節(jié)點(diǎn)序列間連邊順序破壞性仿真,航線網(wǎng)絡(luò)的連通子圖數(shù)目比值上升最快,說明依據(jù)ANC中心性破壞仿真能更快達(dá)到網(wǎng)絡(luò)分解效果;其最大連通子圖規(guī)模下降最快,說明依據(jù)ANC中心性的破壞仿真能更快地將網(wǎng)絡(luò)中最大的連通集團(tuán)或連通區(qū)域消減至較小范圍.這2個(gè)指標(biāo)的變化趨勢表明該算法辨識的重要性節(jié)點(diǎn)對網(wǎng)絡(luò)連通性的影響程度要遠(yuǎn)大于其余算法.
為定量化描述基于不同算法的網(wǎng)絡(luò)攻擊效用差異,仿真實(shí)驗(yàn)中用等梯度資源投入量對MU-3網(wǎng)絡(luò)進(jìn)行攻擊,對比各算法所得攻擊效用指數(shù)(表5所示),結(jié)果表明基于ANC中心性的不同梯度資源投入網(wǎng)絡(luò)攻擊效用指數(shù)均高于對比算法.選取R=0.3和R=0.5進(jìn)行分析,分別最大提升39.62%和49.69%的攻擊效用值,表明依托本算法結(jié)果對航線網(wǎng)絡(luò)進(jìn)行破壞,可在同等資源投入下,提升網(wǎng)絡(luò)連通性破壞效果,達(dá)到少量航線停飛致使航線網(wǎng)絡(luò)癱瘓的局面.
依托ANC中心性識別所得重要節(jié)點(diǎn)信息,可在其節(jié)點(diǎn)間增加航線,以達(dá)到增加網(wǎng)絡(luò)中連通性關(guān)鍵節(jié)點(diǎn)的可替代節(jié)點(diǎn)數(shù)量,提升因天氣、政策或設(shè)備等因素造成的航線網(wǎng)絡(luò)中部分航線失效時(shí)的同進(jìn)出港航線轉(zhuǎn)駁規(guī)劃設(shè)計(jì)多樣性;同時(shí),表明航空公司應(yīng)注重該部分航線網(wǎng)絡(luò)節(jié)點(diǎn)的效用保持,在航線運(yùn)行資源保障分配中,應(yīng)對該部分節(jié)點(diǎn)間的航線所涉及的機(jī)組、地勤及配套設(shè)備等提供能面對異常干擾時(shí)的航線執(zhí)飛保障,從而優(yōu)化航線網(wǎng)絡(luò)節(jié)點(diǎn)連通穩(wěn)定性.
4 結(jié)論
依托航線交互關(guān)聯(lián)階數(shù)量化航線網(wǎng)絡(luò)多階鄰域貢獻(xiàn)度,體現(xiàn)多階交互關(guān)聯(lián)關(guān)系在網(wǎng)絡(luò)連通性保持的異質(zhì)性效用,表明航線網(wǎng)絡(luò)節(jié)點(diǎn)多階鄰域內(nèi)節(jié)點(diǎn)連通性效用貢獻(xiàn)量化受網(wǎng)絡(luò)全局結(jié)構(gòu)影響,而非依托最近鄰最大化原則.鄰域圈結(jié)構(gòu)貢獻(xiàn)的定量化描述幫助辨識航線網(wǎng)絡(luò)節(jié)點(diǎn)連通性時(shí)更準(zhǔn)確識別不可替代節(jié)點(diǎn),為航線網(wǎng)絡(luò)針對性優(yōu)化抗毀性提供理論指導(dǎo).本文僅從航線網(wǎng)絡(luò)線路設(shè)計(jì)層面進(jìn)行模型構(gòu)建和理論驗(yàn)證,受限于航線網(wǎng)絡(luò)實(shí)務(wù)性優(yōu)化操作影響因素紛繁復(fù)雜,未來研究將結(jié)合基礎(chǔ)設(shè)施建設(shè)、出行密度等層面進(jìn)一步精細(xì)化辨識多航司跨地區(qū)航線網(wǎng)絡(luò)連通性核心節(jié)點(diǎn),并有針對性地給出優(yōu)化模型.
參 考 文 獻(xiàn):
[1] HAMDAN S, JOUINI O, CHEAITOU A, et al. Air traffic flow management under emission policies: Analyzing the impact of sustainable aviation fuel and different carbon prices[J]. Transportation Research Part A, 2022, 166: 14-40. DOI: 10.1016/j.tra.2022.09.013.
[2] YONG Y, KAIJUN X, HONG H X, et al. Analysis on Chinese airline network invulnerability[J]. Journal of Systems Science and Information, 2019, 7(4): 359-372. DOI: 10.21078/JSSI-2019-359-14.
[3] 任廣建,張明,郭宇帥.基于拉普拉斯能量相對熵的航路網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估分析[J].北京交通大學(xué)學(xué)報(bào), 2023, 47(2): 76-85. DOI: 10.11860/j.issn.1673-0291.20220034.
[4] LALITHA S, SUNDARARAJAN M, KARTHIK B, et al. Reliable multi-path route selection strategy based on evidence theory for internet of things enabled networks[J]. Measurement: Sensors, 2023, 27: 100795. DOI: 10.1016/j.measen.2023.100795.
[5] 李亞飛,梁琛.基于TOPSIS融合法的航路網(wǎng)關(guān)鍵節(jié)點(diǎn)識別及抗毀性研究[J].飛行力學(xué),2022,40(6):83-87. DOI: 10.13645/j.cnki.f.d.20220930.001.
[6] 丁建立,孫玥.基于LightGBM的航班延誤多分類預(yù)測[J].南京航空航天大學(xué)學(xué)報(bào), 2021, 53(6): 847-854. DOI: 10.16356/j.1005-2615.2021.06.003.
[7] MUELLER F. Link and edge weight prediction in air transport networks:an RNN approach[J]. Physica A: Statistical Mechanics and its Applications. 2023, 613: 128490. DOI: 10.1016/j.physa.2023.128490.
[8] ALBERT R, JEONG H, BARABASI. The diameter of the world wide web [J]. Nature, 1999, 401(6): 130-131. DOI:10.1038/43601.
[9] STEPHENSON K, ZELEN M. Rethinking centrality: Methods and examples[J]. Social Networks. 1989, 11(1): 1-37. DOI: 10.1016/0378-8733(89)90016-6.
[10] KITSAK M, GALLOSL K, HAVLIN S, et al. Identification of influential spreaders in complex networks [J]. Nature Physics, 2010, 6(11): 888-893. DOI: 10.48550/arXiv.1001.5285.
[11] BORGATTI S P, EVERETT M G. A Graph-theoretic perspective on centrality [J]. Social Networks, 2006, 28(4): 466-484. DOI: 10.1016/j.socnet.2005.11.005.
[12] 王興隆,張淑婷.航空網(wǎng)絡(luò)影響力節(jié)點(diǎn)識別與魯棒性分析[J].科學(xué)技術(shù)與工程, 2019, 19(8): 297-302.
[13] 楊泳,徐開俊,李珊珊,等.春運(yùn)期間中國航空網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)實(shí)征分析[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 2019, 43(3): 410-413. DOI: 10.3963/j.issn.2095-3844.2019.03.007.
[14] 杜方葉,王姣娥,謝家昊,等.“一帶一路”背景下中國國際航空網(wǎng)絡(luò)的空間格局及演變[J].地理科學(xué)進(jìn)展, 2019, 38(7): 963-972. DOI: 10.18306/dlkxjz.2019.07.002.
[15] 胡鋼,盧志宇,王樂萌,等.基于復(fù)雜網(wǎng)絡(luò)多階鄰域貢獻(xiàn)度的節(jié)點(diǎn)重要性序結(jié)構(gòu)辨識[J].電子學(xué)報(bào), 2023, 51(7): 1956-1963. DOI: 10.12263/DZXB.20221109.
[16] 張培文,杜福民,王雪,等.近十年中國客運(yùn)航空網(wǎng)絡(luò)空間結(jié)構(gòu)演化及分析研究[J].世界地理研究, 2021, 30(6): 1253-1264. DOI: 10.3969/j.issn.1004-9479.2021.06.
[17] 馮霞,賈宏璨.考慮節(jié)點(diǎn)失效和邊失效的航空網(wǎng)絡(luò)魯棒性[J].北京交通大學(xué)學(xué)報(bào), 2021, 45(5): 84-92. DOI: 10.11860/j.issn.1673-0291.20200137.
[18] GUIMERA R, NUNES AMARAL LA. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895-900. DOI: 10.1038/nature03288.
[19] MAGELINSKI T, BARTULOVIC M, CARLEY KM. Measuring node contribution to community structure with modularity vitality[J]. IEEE Transactions on Network Science and Engineering, 2021, 8(1): 707-723. DOI: 10.1109/TNSE.2020.3049068.
[20] YANG Y, WANG X, CHEN Y, et al. A novel centrality of influential nodes identification in complex networks[J]. IEEE Access, 2020, 8: 58742-58751. DOI: 10.1109/ACCESS.2020.2983053.
[21] 李阿明,侯谷庾,王龍.時(shí)序網(wǎng)絡(luò)構(gòu)建的理論和方法[J].控制與決策, 2023, 38(6): 1473-1490. DOI: 10.13195/j.kzyjc.2022.1797.
[22] 胡鋼,高浩,徐翔,等.基于重要度傳輸矩陣的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識方法[J].電子學(xué)報(bào), 2020, 48(12): 2402-2408. DOI: 10.3969/j.issn.0372-2112.
(責(zé)任編輯:孟素蘭)
收稿日期:2023-06-21;修回日期:2024-01-16
基金項(xiàng)目:
國家自然科學(xué)基金資助項(xiàng)目(62072249); 國家社會科學(xué)基金一般項(xiàng)目(19BGL254); 安徽省自然科學(xué)基金資助項(xiàng)目(2108085MC236); 安徽省高校自然科學(xué)研究項(xiàng)目(KJ2021A0385)
第一作者:胡鋼(1970—),男,安徽工業(yè)大學(xué)教授,博士,主要從事復(fù)雜網(wǎng)絡(luò)建模與分析方向研究.E-mail: hug_2004@126.com