基于改進凝聚算法與鐵路網(wǎng)的社團劃分

李勤敏 郭進利

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

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

DOI：10. 11907/rjdk. 181573

中圖分類號：TP319文獻標識碼：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 引言

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

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

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

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

1 簡單鐵路網(wǎng)絡構造

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

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

2 改進的凝聚算法

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

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

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

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

3 算法結果

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

3.2 迭代步驟分析

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

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

在上一步分析以后，社團的劃分情況開始跨越南北，最終社團呈現(xiàn)如圖6所示的節(jié)點54、51、40、49。鐵路網(wǎng)絡聯(lián)系的緊密程度能夠影響并且?guī)又苓叧鞘邪l(fā)展[15]，將社團合并的先后順序與經(jīng)濟發(fā)展相結合，得出推論：對于節(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)合效應帶動了區(qū)域發(fā)展;對于節(jié)點54（以北京、天津、河北為首的中國北部及西北部分），其中北京、天津、河北的連接發(fā)揮了主要作用。這符合區(qū)域經(jīng)濟發(fā)展中，小部分城市帶動整個區(qū)域發(fā)展的情況，稱為經(jīng)濟作用的火車頭[16]。由此可見，社團劃分過程通常以一個hub點為基礎，成為周邊聯(lián)系的紐帶。

4 結語

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

參考文獻：

[1] 汪小帆，李翔，陳關榮. 復雜網(wǎng)絡理論及其應用[M]. 北京：清華大學出版社，2006.

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

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

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

[5] 王秀鳳，馬英紅. 基于加權網(wǎng)絡模塊強度的社團劃分[J].? 計算機應用研究，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霞，秦勇，王莉. 高速鐵路加權復雜網(wǎng)絡特性分析[J]. 鐵道科學與工程學報，2016，13（2）：201-209.

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

[11] 汪小帆，李翔，陳關榮. 網(wǎng)絡科學導論[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] 司守奎，孫璽菁.? 復雜網(wǎng)絡算法與應用[M]. 北京：國防工業(yè)出版社，2015.

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

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

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

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

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

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

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

（責任編輯：黃 ?。?/p>