基于關鍵節點積極效應模型的快遞物流網絡點集挖掘

摘要：針對快遞物流網絡中點集挖掘問題，基于關鍵節點積極效應模型構建DW-KPP-Pos模型，并設計一種啟發式算法提升模型運算效率。對中國快遞物流網絡的實證分析表明：融合啟發式算法的DW-KPP-Pos模型可高效挖掘快遞物流網絡中的“最大傳播點集”，該集合成員包括上海市、重慶市、廣州市、北京市、金華市和香港特別行政區；計量結果對比顯示，DW-KPP-Pos模型所挖掘的點集K，相對點度數點集K_deg、PageRank點集K_pag和中介中心性點集K_bet，傳播效率分別高出0.59%、0.88%和6.19%。

關鍵詞：復雜網絡；點集挖掘方法；DW-KPP-Pos模型；快遞物流；啟發式算法

中圖分類號： K909;C94文獻標識碼： A

收稿日期：2023-05-29；修回日期：2023-08-07

基金項目：國家自然科學基金（42071165）

第一作者：吳旗韜（1982- ），男，河南平頂山人，博士，研究員，主要研究方向為交通復雜網絡分析。

Nodes-set Mining of Express Logistics Network Based on the Key Player Problem-positive Model

WU Qitao¹， LI Yuanting^1，2， WU Hailing^1，3， YANG Yunhao^1，2， WU Junqiang⁴

（1. Guangzhou Institute of Geography， Guangdong Academy of Sciences， Guangzhou 510070， China; 2. School of Geosciences， South China Normal University， Guangzhou 510631， China; 3. Guangdong University of Technology， Guangzhou 510090， China; 4. Nationalchip（Guangzhou）， Inc， Guangzhou 510700， China）

Abstract：Aiming at the problem of nodes-set mining in express logistics network， this paper constructs DW-KPP-Pos （Directed Weighted-Key Players Problem-Positive） model based on KPP-Pos （Key Player Problem-Positive） and designs a heuristic algorithm to improve the efficiency of the model. The empirical analysis of China’s urban express logistics network shows that： The DW-KPP-Pos model with heuristic algorithm can efficiently mine “Maximum spread seeds group” in express logistics network. Including Shanghai， Chongqing， Guangzhou， Beijing， Jinhua and Hong Kong; The comparison of measurement results suggest that the propagation efficiency of nodes-set K mined by DW-KPP-Pos model is 0.59%， 0.88% and 6.19% higher than that of degree nodes-set K_deg， PageRank nodes-set K_pag and betweenness centrality nodes-set K_bet respectively. In this paper， a new method of nodes-set mining considering maximum spread effect is proposed， which can provide technical support for the layout of express logistics infrastructure.

Keywords： complex network; nodes-set mining method; DW-KPP-Pos model; express logistics; heuristic algorithm

0 引言

挖掘網絡中對信息傳播、要素擴散等過程影響較大的關鍵節點，是有效干預、優化控制網絡的重要手段^[1]。在交通運輸領域，網絡關鍵節點挖掘對于鐵路運輸組織優化^[2]、公路通行效率提升^[3]、軌道交通網絡脆弱性和可靠性評估^[4]等均具有重要意義，也逐漸成為學科研究的前沿方向。快遞物流多服務于電子商務產業，是融合運輸業、倉儲業、信息業的現代物流產業^[5]，快遞物流網絡是網商交易發展到一定階段的產物，網絡以發貨地城市為起點，以收貨地城市為終點，多通過公路等組織系統經由特定路徑完成快遞的運輸和派送。挖掘快遞物流網絡中具備最大傳播效應的節點城市，對于提升快遞物流運輸效率和網絡通達性、優化物流基礎設施布局等具有實際意義。

梳理相關研究發現，對節點在網絡中傳播能力的評估主要基于網絡的局部屬性、全局屬性、位置和隨機游走4種視角^[6]。節點度是基于網絡局部屬性的典型指標，主要考慮節點與其臨近節點的直連關系，度值高的節點可以直接傳播更多的鄰點^[6]。基于網絡全局屬性的典型指標為中介中心性，以網絡中經過某節點的最短路徑條數，衡量節點在傳播過程中的重要性^[6]。基于位置和隨機游走的指標，如K-core分解算法和PageRank節點排序算法等，多以節點度為基礎，對節點傳播能力的衡量分別基于節點是否處于網絡中的核心位置、節點與鄰點的相互影響關系^[7]。上述指標為物流網絡關鍵節點挖掘鋪墊了方法基礎，但尚存在以下問題：1）多關注網絡中單個節點的傳播能力對比，忽略了節點對于網絡實現整體最大傳播的作用。在復雜網絡中，節點規模較大，節點間聯系路徑、方向均呈現多元化特征，這意味著網絡整體最大傳播效應的實現往往不能依托單一節點而是一組節點集。2）即使關注到了節點集合，傳統研究也多基于節點度等量化結果，順次拾取最優節點形成點集。這是一種“個體最優”的選擇標準，帶來的顯著問題就是“富人俱樂部”效應，即個體中心度較高的節點抱團形成特定社區，使最緊密的聯系路徑局限在社區內，無法實現傳播最大化^[8]。

為解決此類問題，社會科學專家Stephen P. Borgatti提出關鍵節點積極效應模型Key Player Problem-Positive（KPP-Pos）以挖掘一組能最大程度連接到其它節點的關鍵節點集合（Nodes-set）^[9]。這是一種集成目標導向的組合優化模型，目前國內關于KPP-Pos模型的研究較少^[10]，在國外已被應用于交通擁堵治理^[11]、網頁信息精確檢索^[12]、重點專利技術資助^[13]等領域。鑒于原始KPP-Pos方法基于無向無權網絡提出，為滿足復雜加權網絡分析，有關學者針對KPP方法的節點選擇和求解效率、節點權重和連邊權重等問題進行優化，如王新棟等^[10]構建IP-KPP-POS整數線性規劃模型，并設計局部搜索啟發式算法提升模型的求解效率；McGuire和Deckro^[14]認為關鍵節點挖掘要考慮聯系強度的差異性，因此在連邊權重上擴展了KPP方法并提出WKPP-Pos模型。現有研究仍存在一些問題：對有向網絡的節點挖掘模型較少，忽視了節點聯系的雙向特征；對加權網絡的節點挖掘模型仍在探索之中，缺乏相關實證研究，無法評估模型有效性；算法復雜程度較高，尤其在大規模節點網絡中，出于運算量級限制而缺乏實操可行性。

綜上，本研究將改進KPP-Pos關鍵節點積極效應模型，針對典型大規模復雜網絡——快遞物流網絡的最大傳播點集挖掘問題，構建DW-KPP-Pos（Directed Weighted-Key Players Problem-Positive）模型，并設計了一種啟發式算法提升模型運算效率，同時通過對比DW-KPP-Pos模型和中心度、PageRank算法、中介中心性的節點分析結果，檢驗模型對于物流網絡節點挖掘的有效性。

1 數據與方法

1.1 數據來源

本研究建模快遞物流網絡的數據來源于中國智能物流骨干網（China Smart Logistics Network，CSN， https：//56.1688.com）。CSN網絡包含起止點城市、數目等快遞物流運輸線路信息，在其官方網站商家工作臺的發貨線路查詢入口，檢索中國各地市之間的有向物流線路數目，最終實際獲取城市之間111 366對起止點（O-D）組合，共計21 430 731條有向線路。

1.2 研究方法

1.2.1 DW-KPP-Pos節點挖掘模型

在本研究中，有向加權的快遞物流網絡構建、PageRank算法和點度數計量均參考前人研究方法^[5]，在此不贅述。KPP-Pos方法用于挖掘一組能以最小距離連接所有節點的節點集。即給定一個無權無向的網絡G，找到一組k個節點，組成節點集K，使其以最小距離連接剩余節點，也可理解為沿最大傳播路徑連接剩余節點。基于無權無向網絡，Borgatti提出的KPP-Pos原始公式^[9]為

其中，K為k個被選節點組成的關鍵節點集；j為剩余節點集中的任意節點；d_Kj為K的任意成員到節點j的最小距離，取倒數以標準化度量指標，使得D_R∈[0，1]；D_R為目標值，可以看做集合到達所有節點的加權比例，D_R值越大，表明在節點數量約束值為k的條件下，當前K集到剩余所有節點的距離最小，傳播效能最大。KPP-Pos原始公式關鍵節點與自身的距離為1（即d_ii=1，i∈K），這與圖論中節點到自身的距離等于0相悖，而本研究網絡的構建基于圖論原理，取d_ii=0，即去掉K集中節點自身的聯系，式（1）分母由n變為n-k（n＞k）。此外，鑒于中國快遞物流網絡為有向加權網絡，在式（1）的基礎上考慮i和j節點之間聯系的方向性，并增加w權重。

第1步：考慮節點之間的方向性，即K集中節點起始發往j節點的快遞物流與從j節點起始發往K集中節點的快遞物流是兩種不同的快遞流向，由此形成了雙向對稱矩陣。此外，本研究對于KPP-Pos模型的改進將基于一步連通性，當城市之間存在兩步及以上連通性時，則d_Kj=∞，式（3）中取距離倒數以標準化度量的原則在此可簡化：

其中，r_Kj為K集中的節點到節點j之間的距離；r_jK為節點j到K集中的節點之間的距離。

第2步：增加權重w，以科學衡量K集中節點與節點j之間的緊密度，也可理解為距離接近度，以替代0/1指向節點連接與否的簡單設定。加權后的算子WD_R：

其中，w_Kj為K集中節點與節點j之間的距離接近度，以標準化之后的兩點之間快遞物流線路數目表示，以確保WD_R∈[0，1]；w_jK同理。

1.2.2 節點挖掘的啟發式算法

上述DW-KPP-Pos節點挖掘模型的原理相對簡單，即找到一組和剩余所有節點通過最小距離路徑連接，進而實現最大傳播效應的節點集，但在實際操作過程中要多次進行節點的重組、節點間關系的重構，計算難度較高，在進行復雜網絡的關鍵點集挖掘時可行性較低。因此本研究設計一種啟發式算法降低WD_R求解復雜度。具體思路如圖1所示：1）首先計算網絡中所有n個節點的點度數，借鑒相關研究^[10]選擇點度數最大的節點作為K集中首位成員。點度數最大節點假設為圖1中的節點1。2）選擇第2個節點的思路為：在剩余（n-1）節點中順次選擇節點加入K集，計算WD_R值，取最高值對應的節點填充K集。即選擇下圖中節點1和剩余節點分別組成K集二元組（1，2）、（1，3）、（1，4）……（1，9），若二元組合為（1，3）時WD_R值最大，則節點3成為K集的第2個成員。3）K集中其他節點挖掘方式同理，直至形成能以最小距離連接所有節點的“最大傳播節點集”。啟發式算法流程圖如圖2所示。2 結果分析

2.1 最大傳播節點集（K集）的挖掘結果

通過啟發式算法探索“最大傳播節點集”（K集）時可提升運算效率和方案實施可行性。在中國快遞物流網絡中，城市節點n=345，假設K=10，K集的排列組合有C¹⁰₃₄₅=A¹⁰₃₄₅/A¹⁰₁₀=345×344×343×……×336/10×9×8×…×2×1=5.771×10¹⁸個，WD_R值迭代次數相同。以Matlab工具為例，其內置求全組合的函數nchoosek，算法約束下集合內元素數量不得超過15。當k=10時，基于啟發式算法的D_R值迭代次數為345+344+…+336=3 405輪，運算復雜度將由10¹⁸量級降低至10³量級。

基于DW-KPP-Pos分析結果（見表1），在利用啟發式算法填充K集時，選定第6個節點北京市后，K₆集（包括上海市，重慶市，廣州市，北京市，金華市和香港特別行政區6個節點的K集，以下簡稱K₆集）成員為上海市，重慶市，廣東省廣州市，北京市，浙江省金華市和香港特別行政區。這6個節點的組合對外最大傳播節點數為339，全面連接K₆集外所有節點，同時形成覆蓋范圍為100%的最大傳播網絡結構，表明中國快遞物流網絡的“最大傳播節點集”為上述K₆集內城市。其中上海市是基于啟發式算法—首位點度數原則挖掘的第1個K集成員。剩余344個節點中，重慶市與上海市的二元組K₂，其DW-KPP-Pos值為0.149 5，數值高于任意節點與上海市的二元組，因此重慶市成為第2個加入K集的成員。組合6個節點后，再進行節點遍歷時，選擇剩余任意節點計算出的DW-KPP-Pos特征值均保持不變，表明剩余任意節點的加入對K集傳播能力不具備實質性提升。比如再進一步尋找第7個加入K集的成員時，選擇安徽省安慶市加入K集的方案K_7a和選擇安徽省蚌埠市加入K集的方案K_7b具有相同的DW-KPP-Pos特征值，也同樣全面連接了K₆集外100%節點，和K₆集的網絡傳播效能等同。

2.2 K集節點對快遞物流網絡的傳播范圍影響

基于K₆集節點刻畫中國快遞物流最大傳播網絡，可視化結果如圖3所示。借鑒兩級傳播理論，以K集節點作為“領袖節點”；與某K集節點形成最小距離連接的K集外節點作為“受眾節點”。K集6個領袖節點連接起中國所有城市之間的最大傳播路徑。基于首位點度數原則挖掘的第1個K集節點：上海市以最小距離連接了中國約70%的節點城市；其傳播受眾節點除長三角地區外，廣泛覆蓋中國東北地區、西北地區和西南地區等。而此時網絡中剩余約30%的節點未與K集建立起連接關系。重慶市作為第2個K集節點，以最小距離連接了中國中部地區、東南沿海地區和北方地區的部分節點，對上海的傳播網絡進行了補充，此時網絡中剩余受眾節點已低于20%。廣州市作為第3個K集節點，以最小距離連接了中國中部、南方地區（尤其是廣東省）的部分城市和新疆自治區的少數城市。第4個K集節點北京市主要從西南，尤其青藏高原連接方向上對網絡進行了補充。由上述4個“多受眾領袖節點”傳播路徑交錯形成的最大傳播網絡，其結構完整度已超過99%。剩余受眾節點為海南省三沙市和臺灣省，分別與“單受眾領袖節點”香港特別行政區和浙江省金華市連接，由此形成100%全連接的最大傳播網絡。

2.3 K集與中心度、中介中心性和PageRank點集的傳播效率對比

以“找到一組最大傳播節點”為核心目標，對比點度數、中介中心性和PageRank三大指標，檢驗DW-KPP-Pos模型進行點集挖掘的有效性。以K集成員數量為約束條件，順次選擇點度數Top6節點、PageRank值Top6節點、中介中心性Top6節點，組成點集K_deg，K_pag和K_bet。各點集傳播效率如表2所示。

如圖4，在6個節點的約束條件下，K集傳播效率最高，其對外最大傳播節點數為339，最大傳播網絡范圍為100%；K_deg集傳播效率次之，其對外最大傳播節點數為337，最大傳播網絡范圍為99.41%；K_pag集傳播效率居中；K_bet傳播范圍最小，其對外最大傳播節點數僅有318，最大傳播網絡范圍為93.81%，集外仍有21個節點未和K_bet集建立起最小距離連接。可知在同樣的節點數量約束下，基于DW-KPP-Pos模型挖掘的K集具有最高的傳播效率，較之基于“個體最優原則”順次拾取節點形成的K_deg集、K_pag集和K_bet集，傳播效率分別高出0.59%、0.88%和6.19%。

3 結論

針對復雜網絡的點集挖掘問題，本研究構建DW-KPP-Pos模型，并設計啟發式算法提升模型運行效率，以中國城市快遞物流網絡為例得出實證分析結果：1）基于啟發式算法的DW-KPP-Pos模型可提升復雜網絡中節點挖掘的效率。中國快遞物流網絡的“最大傳播點集”包括上海市、重慶市、廣州市、北京市、浙江省金華市和香港特別行政區。上述6個城市組成的點集K以最小距離、最全范圍連接了外部100%的節點。此外，中國快遞物流具有明顯的等級擴散效應，K集節點多是中國人口和經濟規模較大的城市，物流輻射力較強，吸引K集外部城市克服距離摩擦形成最大傳播鏈路。2）基于“集體最優原則”的DW-KPP-Pos模型所挖掘的點集K傳播效率最高，在同樣的節點數量約束下，點集K相對基于“個體最優原則”的點度數點集K_deg、PageRank點集K_pag和中介中心性點集K_bet，傳播效率分別高出0.59%、0.88%和6.19%。

本研究構建的DW-KPP-Pos模型適用于大規模、有向加權物流網絡中最大傳播點集的挖掘，可為快遞物流基礎設施布局等提供方法參考。未來將不斷提升復雜網絡數學建模和網絡拓撲結構分析等技能，以期在多功能節點與點集挖掘、物流最優路徑探查等復雜網絡科學領域取得新的突破。

參考文獻：

[1]DABAGHI-ZARANDI F， KAMALIPOUR P. Community detection in complex network based on an improved random algorithm using local and global network information[DB/OL].[2023-05-06]. http：//dx.chinadoi.cn/10.1016/j.jnca.2022.103492

[2]馮芬玲，蔡明旭，賈俊杰.基于多層復雜網絡的中歐班列運輸網絡關鍵節點識別研究[J].交通運輸系統工程與信息，2022， 22（6）：191-200.

FENG F L， CAI M X， JIA J J. Research on key node identification of China railway express transportation network based on multi-layer complex network[J]. Journal of Transportation Systems Engineering and Information Technology， 2022， 22（6）：191-200.

[3]王靈麗，黃敏，高亮.基于聚類算法的交通網絡節點重要性評價方法研究[J].交通信息與安全， 2020，38（2）：80-88.

WANG L L， WANG M， GAO L. Methods of importance evaluation of traffic network node based on clustering algorithms[J]. Journal of Transport Information and Safety，2020， 38（2）： 80-88.

[4]王亭，張永，周明妮，等.融合網絡拓撲結構特征與客流量的城市軌道交通關鍵節點識別研究[J].交通運輸系統工程與信息， 2022，22（6）：201-211.

WANG T， ZHANG Y， ZHOU M N， et al. Identification of key nodes of urban rail transit integrating network topology characteristics and passenger flow[J]. Journal of Transportation Systems Engineering and Information Technology， 2022，22（6）：201-211.

[5]李苑君，吳旗韜，李苑庭，等.“流空間”視角下中國電子商務快遞物流網絡結構與機理[J].熱帶地理， 2023，43（4）：657-668.

LI Y J， WU Q T， LI Y T， et al. Exploring the structure and mechanism of China′s E-commerce express logistics network： based on space of flows[J]. Tropical Geography，2023，43（4）：657-668.

[6]趙之瀅，于海，朱志良，等.基于網絡社團結構的節點傳播影響力分析[J].計算機學報， 2014，37（4）：753-766.

ZHAO Z Y， YU H， ZHU Z L， et al. Identifying influential spreaders based on network community structure[J]. Chinese Journal of Computers，2014，37（4）：753-766.

[7]KITSAK M， GALLOS L K， HAVLIN S， et al. Identification of influential spreaders in complex networks[J]. Nature Physics，2010，6（11）：888-893.

[8]MATTEO C， GIOVANNA F， ANTONIO I. Resilience of core-periphery networks in the case of rich-club[DB/OL].[2023-02-02]. https：//doi.org/10.48550/arXiv.1708.07329.

[9]BORGATTI S P. Identifying sets of key players in a social network[J]. Computational amp; Mathematical Organization Theory，2006，12（1）：21-34.

[10] 王新棟，于華，江成.社交網絡關鍵節點檢測的積極效應問題[J].中國科學院大學學報， 2019，36（3）：425-432.

WANG X D， YU H， JIANG C. Positive effect of key player detection in social networks[J]. Journal of University of Chinese Academy of Sciences，2019，36（3）：425-432.

[11] JAIN A， YADAV S， VIJ S， et al. A Novel self-organizing approach to automatic traffic light management system for road traffic network[J]. Wireless Personal Communications，2020， 110（2）：1303-1321.

[12] JAIN A， MITTAL K， TAYAL D K. Automatically incorporating context meaning for query expansion using graph connectivity measures[J]. Progress in Artificial Intelligence，2014， 2（2/3）：129-139.

[13] CHO Y， KIM W. Technology-industry networks in technology commercialization： evidence from Korean university patents[J]. Scientometrics，2014， 98（3）：1785-1810.

[14] MCGUIRER M， DECKRO R F. The weighted key player problem for social network analysis[J]. Military Operations Research，2015，20（2）： 35-53.

（責任編輯 李 進）