李勤敏 郭進利

摘 要：為了更好地分析鐵路網(wǎng)劃分過程及其與周邊經(jīng)濟發(fā)展?fàn)顩r的聯(lián)系，以省為單位建立加權(quán)無向復(fù)雜網(wǎng)絡(luò)，其中節(jié)點為省，兩省之間的鐵路連線為網(wǎng)絡(luò)連邊。提出改進的凝聚算法，進一步對網(wǎng)絡(luò)社團劃分的迭代過程展開分析，最后得出明顯的南北社團劃分分界線。將社團劃分過程與經(jīng)濟發(fā)展情況相聯(lián)系，分析得出鐵路發(fā)達情況與區(qū)域間經(jīng)濟發(fā)展息息相關(guān)，從而得出結(jié)論：鐵路間聯(lián)系越緊密，區(qū)域經(jīng)濟帶動作用越強，并證實了國家近年來大力發(fā)展鐵路建設(shè)的重要性。

關(guān)鍵詞：改進Newman快速算法;社團劃分;鐵路網(wǎng)

DOI：10. 11907/rjdk. 181573

中圖分類號：TP319文獻標(biāo)識碼：A文章編號：1672-7800（2019）001-0132-04

Abstract：In order to analyse the process of community identifity and the relation of community identifity and economic development， we create weighted network through taking Privoce as node and the railway between Privoces as weighted edge. An improved Newman fast algorithm is used to analyse the process of iteration and we can get a clear divide between south and north in the graph.Contacting the process of community identifity and economic development，we get the conclusion that they are interrelated with each other and railway development drives the development of economy and area.In this way，we can find the importance of national support of the development of railway construction.

0 引言

在對復(fù)雜網(wǎng)絡(luò)的研究中，由于大部分網(wǎng)絡(luò)都是加權(quán)復(fù)雜網(wǎng)絡(luò)，有必要對復(fù)雜網(wǎng)絡(luò)的拓撲性質(zhì)及社團劃分等方面更多地引入加權(quán)情況。復(fù)雜網(wǎng)絡(luò)的社團性質(zhì)能夠更好地將社團根據(jù)相互間的聯(lián)系程度與相似程度對整個網(wǎng)絡(luò)節(jié)點進行分類。通過社團的劃分，社團內(nèi)部節(jié)點之間的聯(lián)系緊密程度比社團之間的聯(lián)系緊密程度更高，即各個社團之間的聯(lián)系更加稀疏。

早前對復(fù)雜網(wǎng)絡(luò)的研究主要集中在無權(quán)網(wǎng)絡(luò)圖上，如Kernighan-Lin算法是1970年Lin & Kernighan[1]提出的基于試探性優(yōu)化的貪婪算法，通過多次交換不同社區(qū)節(jié)點計算網(wǎng)絡(luò)模塊度Q，不斷搜尋可使Q增大的社團劃分方式，利用貪婪算法找出最大Q，從而得到最佳社團劃分方法。該算法的缺陷是每次只能將網(wǎng)絡(luò)分成兩個大小已知的社團;GN算法是一種最常見的分裂算法，于2002年由Girvan & Newman提出，其基本步驟為：①找出網(wǎng)絡(luò)所有邊的介數(shù);②移除網(wǎng)絡(luò)中具有最高介數(shù)的邊;③重復(fù)上一步，直到每單個節(jié)點都分別退化成一個社團為止。該算法具有較高精度，但其復(fù)雜度也很高。與分裂算法相對應(yīng)的是凝聚算法，凝聚算法包括Newman快速算法、利用堆結(jié)構(gòu)的CNM算法與結(jié)合譜分析的貪婪算法，其簡化了算法復(fù)雜度，使社團劃分方法能夠更好地運用于當(dāng)今的Internet等復(fù)雜大數(shù)據(jù)網(wǎng)絡(luò)。

近年對加權(quán)網(wǎng)絡(luò)的研究也越來越多，對于加權(quán)復(fù)雜網(wǎng)絡(luò)社團劃分研究進展如下：2008年宣照國等[2]對Newman快速凝聚算法作加權(quán)改造，根據(jù)兩節(jié)點的相似程度將節(jié)點與社團進行合并;2010年韓華等[3]提出對CNM算法進行加權(quán)算法改進，將CNM算法中的[eij]與[ai]引入邊權(quán)、點權(quán)概念，拓展了CNM的應(yīng)用范圍;2013年鹿靜等[4]提出基于加權(quán)網(wǎng)絡(luò)的節(jié)點相似度劃分算法，構(gòu)造節(jié)點相似度矩陣，將相似度大的優(yōu)先合并;2013年王秀鳳等[5]以社交關(guān)系網(wǎng)絡(luò)為例研究并設(shè)計了加權(quán)關(guān)系網(wǎng)絡(luò)算法;2016年Xiaoming Liu[6]等對節(jié)點的隨機游走進行研究，得出邊緣更加緊密的連通子圖具有較大權(quán)重，周圍節(jié)點更容易聚合為一個社團結(jié)構(gòu)，但對大型網(wǎng)絡(luò)進行社團劃分的方法未考慮節(jié)點連邊權(quán)重對游走的影響;2016年Fang Hu等[7]結(jié)合PageRank算法與CNM算法，基于節(jié)點重要性對社團劃分算法進行改進，增加了算法的可靠性，但未考慮網(wǎng)絡(luò)連邊是加權(quán)網(wǎng)絡(luò)的情況;2017年DONG MIN等[8]提出k-權(quán)關(guān)系矩陣，k為無圈情況下i與j之間存在節(jié)點的個數(shù)，同時考慮了加權(quán)情況的k，基于加權(quán)模塊度矩陣設(shè)計迭代算法，使其應(yīng)用于大型加權(quán)網(wǎng)絡(luò)的社團劃分。

本文通過對Newman快速算法進行簡單改進，將網(wǎng)絡(luò)節(jié)點之間的連邊權(quán)重引入算法中，使社團劃分算法更易于理解，且接近實際情況。與此同時，本文應(yīng)用改進的Nenman快速算法對通過三橫五縱簡化的各省之間鐵路主干線復(fù)雜網(wǎng)絡(luò)圖進行社團劃分，并結(jié)合實際情況展開分析，并將劃分過程與經(jīng)濟發(fā)展結(jié)合起來。

1 簡單鐵路網(wǎng)絡(luò)構(gòu)造

結(jié)合三橫五縱所經(jīng)過的省構(gòu)造簡化鐵路網(wǎng)絡(luò)的加權(quán)無向網(wǎng)絡(luò)，首先將鐵路經(jīng)過的省份作為網(wǎng)絡(luò)圖的節(jié)點V，若在簡化的鐵路網(wǎng)上兩省之間存在鐵路連線，則可看作兩省之間存在連邊E。為方便計算，取各省的省會城市作為計算點，將兩省會之間每天往返兩地列車的總班次數(shù)量記為兩省節(jié)點連邊權(quán)重[9]，每天的往返列車班次可通過12306官網(wǎng)進行查詢，然后作出統(tǒng)計并取平均。對各省代表的節(jié)點進行標(biāo)號，如4-北京、5-天津、6-河北，對三橫五縱鐵路主干線網(wǎng)經(jīng)過的省份進行網(wǎng)絡(luò)圖繪制，并且通過Pajek[10]畫出對應(yīng)網(wǎng)絡(luò)，如圖1所示（數(shù)據(jù)統(tǒng)計時間為2017年12月，忽略時間因素導(dǎo)致的不精確情況）。

Pajek繪制結(jié)果顯示圖中參與省份一共有29個節(jié)點、69條連邊，整個網(wǎng)絡(luò)的平均度為2.62。

2 改進的凝聚算法

Newman快速算法是由Newman在GN算法基礎(chǔ)上提出的另一種快速凝聚算法，算法主要基于貪婪算法思想，從一開始即將單個節(jié)點看成一個社團，假設(shè)合并社團并求出各個模塊增量，根據(jù)模塊度增加最大的方向?qū)ι鐖F進行合并，并不斷更新網(wǎng)絡(luò)的社團模塊度，從而得到最大模塊度的步驟。這里將復(fù)雜網(wǎng)絡(luò)社團節(jié)點之間連邊的權(quán)重引入算法中，以期更加準(zhǔn)確地劃分社團，并且降低社團劃分算法的復(fù)雜度。

對于網(wǎng)絡(luò)圖G（V，E）（表示具有V個節(jié)點、E條連邊的網(wǎng)絡(luò)圖）的網(wǎng)絡(luò)社團劃分算法過程，其中[eij]是指社團i與社團j之間連邊權(quán)重占整個網(wǎng)絡(luò)邊數(shù)總權(quán)重和的比例，[ai]為一端與社團i中節(jié)點相連邊的權(quán)重占網(wǎng)絡(luò)總權(quán)重的比例，W指整個網(wǎng)絡(luò)所有邊的權(quán)重之和，[ωij]指社團i與社團j之間連邊的權(quán)重和[11]。算法具體步驟描述如下：

（1）初始化：一開始將每個節(jié)點分別看成互相獨立的社團，初始模塊度值記為[Q=0]，[eij]、[ai]計算方法如式（1）、式（2）所示，其中[ωij]即為節(jié)點i與j之間連邊的權(quán)重。

（2）按照順序依次對有邊相連的社團進行合并，計算合并后的模塊度增量，再根據(jù)貪婪算法原理，社團朝著模塊度增加速度最快的方向合并，[ΔQ]迭代公式如下：

3 算法結(jié)果

3.1 合并次數(shù)與Q關(guān)系分析

3.2 迭代步驟分析

迭代第1步，mdq=0.214 5（這里mdq為貪婪算法中挑選的最大值）。合并點11（江蘇）與點13（上海）為n+k=30，將合并后的點重新標(biāo)號為30;第2步，mdq=0.128 3，合并點30（江蘇上海）與點14（浙江）為n+k=31，將合并后的點重新標(biāo)號為31;依次繼續(xù)迭代，到第13次迭代，mdq=0.046 7，合并點41（河北，北京，天津，陜西，河南）與9（山西）為n+k=42。此時即社團合并前13次迭代，得到如圖4、圖5所示結(jié)果。

按照優(yōu)先選擇[？Q]最大的貪婪算法合并原則，將網(wǎng)絡(luò)分成東西兩部分，因為聯(lián)系緊密的優(yōu)先合并，所以相較于西邊，東邊省份之間聯(lián)系更為緊密。由于鐵路的發(fā)達程度可以對各省市之間的經(jīng)濟發(fā)展起到一定帶動作用[14]，城市之間鐵路的連接有利于提升可達性，與區(qū)域經(jīng)濟成正比關(guān)系。社團網(wǎng)絡(luò)劃分過程形成了東西分界線，與實際相符合。合并到第25次時，mdq=0.002 0，合并節(jié)點53與節(jié)點50，n+k=54，Q=1.498 7，此時網(wǎng)絡(luò)的模塊度Q達到最大值，得到4個社團，結(jié)果如圖6所示。

在上一步分析以后，社團的劃分情況開始跨越南北，最終社團呈現(xiàn)如圖6所示的節(jié)點54、51、40、49。鐵路網(wǎng)絡(luò)聯(lián)系的緊密程度能夠影響并且?guī)又苓叧鞘邪l(fā)展[15]，將社團合并的先后順序與經(jīng)濟發(fā)展相結(jié)合，得出推論：對于節(jié)點51（黑龍江，吉林，哈爾濱），跨省經(jīng)濟主要由節(jié)點2（吉林）-3（遼寧）帶動，根據(jù)2016年東北三省的GDP排名，遼寧省居第一;節(jié)點40經(jīng)濟帶（上海、江蘇、浙江、山東、安徽）中，11-13-14（江蘇、上海、浙江）為聯(lián)系最緊密的部分，顯然上海、江蘇帶動了該經(jīng)濟帶連線之間的經(jīng)濟發(fā)展;與節(jié)點49（西南一部分省）聯(lián)系最緊密的是首先合并的社團16（湖北）-17（湖南），兩省經(jīng)濟產(chǎn)生的聯(lián)合效應(yīng)帶動了區(qū)域發(fā)展;對于節(jié)點54（以北京、天津、河北為首的中國北部及西北部分），其中北京、天津、河北的連接發(fā)揮了主要作用。這符合區(qū)域經(jīng)濟發(fā)展中，小部分城市帶動整個區(qū)域發(fā)展的情況，稱為經(jīng)濟作用的火車頭[16]。由此可見，社團劃分過程通常以一個hub點為基礎(chǔ)，成為周邊聯(lián)系的紐帶。

4 結(jié)語

將鐵路網(wǎng)連邊權(quán)重引入Newman快速算法，對該算法進行簡單改進，引入節(jié)點之間的權(quán)重，從而使算法作用的社團劃分更加符合實際情況。本文通過對k-Q圖像進行分析，再結(jié)合貪婪算法思想對算法過程進行剖析，發(fā)現(xiàn)在基于三橫五縱的鐵路網(wǎng)中，我國的東邊鐵路之間聯(lián)系更加緊密，而西邊相對稀疏，根據(jù)貪婪算法的加權(quán)Newman快速算法，先合并的是東邊省份。我國經(jīng)濟東西分界線也是鐵路主干線的東西分界線。網(wǎng)絡(luò)最后分為4個社團，各個社團內(nèi)部又由聯(lián)系相對緊密的經(jīng)濟帶所帶動。對原有的Newman快速算法進行改進，根據(jù)改進算法對鐵路發(fā)展與對應(yīng)地區(qū)經(jīng)濟進行分析，分析結(jié)果符合我國鐵路連線發(fā)展情況以及對經(jīng)濟帶動作用的實際情況，可明顯看出鐵路網(wǎng)東西發(fā)展不平衡的現(xiàn)狀?；阼F路與經(jīng)濟的緊密聯(lián)系，我國為進一步發(fā)展鐵路建設(shè)，與此同時帶動國家經(jīng)濟發(fā)展，國務(wù)院常務(wù)會議于2016年6月29通過了《中長期鐵路網(wǎng)規(guī)劃》，提出了打造高速鐵路“八橫八縱”的主干線。本文對社團劃分過程進行了分析，以期用復(fù)雜網(wǎng)絡(luò)理論證明鐵路網(wǎng)絡(luò)與經(jīng)濟發(fā)展各方面息息相關(guān)，最后建議以核心經(jīng)濟帶為中心，進一步優(yōu)化高速鐵路網(wǎng)絡(luò)布局，實現(xiàn)高鐵站與城市交通的無縫對接，促進不同地區(qū)的經(jīng)濟交流，打造經(jīng)濟一體化環(huán)境[17]。

參考文獻：

[1] 汪小帆，李翔，陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：清華大學(xué)出版社，2006.

[2] 宣照國，苗靜，黨延忠，等. 科研領(lǐng)域關(guān)聯(lián)網(wǎng)絡(luò)的社團結(jié)構(gòu)分析[J].? 上海理工大學(xué)學(xué)報，2008，30（3）：249-252.

[3] 韓華，王娟，王慧. 改進的CNM算法對加權(quán)網(wǎng)絡(luò)社團結(jié)構(gòu)的劃分[J]. 計算機工程與應(yīng)用，2010，46（35）：86-89.

[4] 鹿靜，徐勇，安麗平. 基于節(jié)點相似度的加權(quán)網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法[J]. 信息與控 制，2012，41（4）：504-508.

[5] 王秀鳳，馬英紅. 基于加權(quán)網(wǎng)絡(luò)模塊強度的社團劃分[J].? 計算機應(yīng)用研究，2013，30（3）：695-698.

[6] LIU X，ZHOU Y，HU C， et al. Miracle：a multiple independent random walks community parallel detection algorithm for big graphs[J].? Journal of Network & Computer Applications，2016，70：89-101.

[7] HU F， LIU Y. A new algorithm CNM-centrality of detecting communities based on node centrality[J]. Physica A：Statistical Mechanics & Its Applications，2016， 446：138-151.

[8] MIN D， YU K， LI H J. Refinement of the community detection performance by weighted relationship coupling[J]. Pramana-Journal of Physics，2017.

[9] 張?zhí)m霞，秦勇，王莉. 高速鐵路加權(quán)復(fù)雜網(wǎng)絡(luò)特性分析[J]. 鐵道科學(xué)與工程學(xué)報，2016，13（2）：201-209.

[10] 李光正，翟龍余，左傳桂. 基于Matlab的小世界網(wǎng)絡(luò)仿真[J]. 科技信息：科學(xué)教研，2008（17）：71-72.

[11] 汪小帆，李翔，陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[M]. 北京：高等教育出版社，2012：37-38.

[12] NEWMAN M E. Fast algorithm for detecting community structure in networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys，2004，69：066133.

[13] 司守奎，孫璽菁.? 復(fù)雜網(wǎng)絡(luò)算法與應(yīng)用[M]. 北京：國防工業(yè)出版社，2015.

[14] 劉莉文，張明. 高速鐵路對中國城市可達性和區(qū)域經(jīng)濟的影響[J]. 國際城市規(guī)劃，2017，32（4）：76-81，89.

[15] 張安民. 淺談高速鐵路建設(shè)對我國區(qū)域經(jīng)濟的帶動作用[J]. 企業(yè)技術(shù)開發(fā)，2014，33（23）：126-127.

[16] 蔡之兵，滿艦遠. 中國超大城市帶動區(qū)域經(jīng)濟增長的效應(yīng)研究[J]. 上海經(jīng)濟研究，2016（11）：3-11，128.

[17] 陳薇薇. 高速鐵路建設(shè)對我國貿(mào)易經(jīng)濟一體化的影響及對策研究[J]. 價格月刊，2016（1）：65-68.

[18] 解， 汪小帆. 復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)分析算法研究綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005（3）：1-12.

[19] 楊澤俊，何柳. 復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法概述[J]. 數(shù)字技術(shù)與應(yīng)用，2013（3）：145.

[20] 王天成，劉真真，李天明，等. 復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分方法及其應(yīng)用[J]. 信息通信，2015（8）：43-45.

（責(zé)任編輯：黃 健）