李勤敏 郭進(jìn)利

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

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

DOI：10. 11907/rjdk. 181573

中圖分類號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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ò)的拓?fù)湫再|(zhì)及社團(tuán)劃分等方面更多地引入加權(quán)情況。復(fù)雜網(wǎng)絡(luò)的社團(tuán)性質(zhì)能夠更好地將社團(tuán)根據(jù)相互間的聯(lián)系程度與相似程度對整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類。通過社團(tuán)的劃分，社團(tuán)內(nèi)部節(jié)點(diǎn)之間的聯(lián)系緊密程度比社團(tuán)之間的聯(lián)系緊密程度更高，即各個(gè)社團(tuán)之間的聯(lián)系更加稀疏。

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

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

本文通過對Newman快速算法進(jìn)行簡單改進(jìn)，將網(wǎng)絡(luò)節(jié)點(diǎn)之間的連邊權(quán)重引入算法中，使社團(tuán)劃分算法更易于理解，且接近實(shí)際情況。與此同時(shí)，本文應(yīng)用改進(jìn)的Nenman快速算法對通過三橫五縱簡化的各省之間鐵路主干線復(fù)雜網(wǎng)絡(luò)圖進(jìn)行社團(tuán)劃分，并結(jié)合實(shí)際情況展開分析，并將劃分過程與經(jīng)濟(jì)發(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é)點(diǎn)V，若在簡化的鐵路網(wǎng)上兩省之間存在鐵路連線，則可看作兩省之間存在連邊E。為方便計(jì)算，取各省的省會(huì)城市作為計(jì)算點(diǎn)，將兩省會(huì)之間每天往返兩地列車的總班次數(shù)量記為兩省節(jié)點(diǎn)連邊權(quán)重[9]，每天的往返列車班次可通過12306官網(wǎng)進(jìn)行查詢，然后作出統(tǒng)計(jì)并取平均。對各省代表的節(jié)點(diǎn)進(jìn)行標(biāo)號(hào)，如4-北京、5-天津、6-河北，對三橫五縱鐵路主干線網(wǎng)經(jīng)過的省份進(jìn)行網(wǎng)絡(luò)圖繪制，并且通過Pajek[10]畫出對應(yīng)網(wǎng)絡(luò)，如圖1所示（數(shù)據(jù)統(tǒng)計(jì)時(shí)間為2017年12月，忽略時(shí)間因素導(dǎo)致的不精確情況）。

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

2 改進(jìn)的凝聚算法

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

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

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

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

3 算法結(jié)果

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

3.2 迭代步驟分析

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

[5] 王秀鳳，馬英紅. 基于加權(quán)網(wǎng)絡(luò)模塊強(qiáng)度的社團(tuán)劃分[J].? 計(jì)算機(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é)報(bào)，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] 劉莉文，張明. 高速鐵路對中國城市可達(dá)性和區(qū)域經(jīng)濟(jì)的影響[J]. 國際城市規(guī)劃，2017，32（4）：76-81，89.

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

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

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

[18] 解， 汪小帆. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(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ò)社團(tuán)結(jié)構(gòu)劃分方法及其應(yīng)用[J]. 信息通信，2015（8）：43-45.

（責(zé)任編輯：黃 ?。?/p>