基于二分圖的寶雞公交線路-站點(diǎn)網(wǎng)絡(luò)建模及分析

王歡, 胡靜波

(寶雞文理學(xué)院 a.計(jì)算機(jī)學(xué)院；b. 電子電氣工程學(xué)院，陜西 寶雞 721016)

?

基于二分圖的寶雞公交線路-站點(diǎn)網(wǎng)絡(luò)建模及分析

王歡a, 胡靜波b

(寶雞文理學(xué)院 a.計(jì)算機(jī)學(xué)院；b. 電子電氣工程學(xué)院，陜西 寶雞 721016)

復(fù)雜網(wǎng)絡(luò)理論已成為研究交通系統(tǒng)的有效工具。以陜西省寶雞市的43個(gè)公交線路及344個(gè)公交站點(diǎn)數(shù)據(jù)為基礎(chǔ)，基于二分圖理論，構(gòu)建了站點(diǎn)-線路公交網(wǎng)絡(luò)模型，并對該網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)進(jìn)行了分析。研究結(jié)果表明，網(wǎng)絡(luò)中的線路節(jié)點(diǎn)度分布呈現(xiàn)泊松分布，大部分線路度值集中在平均值附近；而站點(diǎn)節(jié)點(diǎn)度分布呈現(xiàn)冪律分布，其中的少數(shù)節(jié)點(diǎn)高度連接，為網(wǎng)絡(luò)中的關(guān)鍵樞紐節(jié)點(diǎn)。這些高度連接的線路和站點(diǎn)可被篩選為寶雞市交通網(wǎng)絡(luò)研究中的重點(diǎn)規(guī)劃對象。

復(fù)雜網(wǎng)絡(luò)；二分圖；公交網(wǎng)絡(luò)；度分布；樞紐節(jié)點(diǎn)

0 引 言

自然界和人類社會中存在的大量復(fù)雜系統(tǒng)都可以被抽象為網(wǎng)絡(luò)，通過研究個(gè)體之間的相互關(guān)系及探索系統(tǒng)整體呈現(xiàn)出的性質(zhì)，找出其中的規(guī)律性及共性[1-2]。復(fù)雜網(wǎng)絡(luò)理論是研究這種復(fù)雜系統(tǒng)的有力工具，現(xiàn)已被大量應(yīng)用在生物、經(jīng)濟(jì)、社會、交通和管理等各個(gè)領(lǐng)域[3-5]。

交通系統(tǒng)是一種最為典型的復(fù)雜系統(tǒng)，而公交系統(tǒng)則是城市的交通命脈，研究公交系統(tǒng)網(wǎng)絡(luò)對于城市的交通發(fā)展和交通優(yōu)化具有重大的意義[6-7]。公交系統(tǒng)包含有公交線路和公交站點(diǎn)兩個(gè)方面，已有的國內(nèi)公交網(wǎng)絡(luò)的研究基本都是針對單獨(dú)的公交線路或者公交站點(diǎn)，而將公交線路與公交站點(diǎn)結(jié)合起來研究城市公交系統(tǒng)則更具有實(shí)際的指導(dǎo)意義。

本文以陜西省寶雞市43條公交線路和344個(gè)公交站點(diǎn)為基礎(chǔ)，構(gòu)建了公交系統(tǒng)線路-站點(diǎn)二分網(wǎng)絡(luò)模型，計(jì)算并分析了網(wǎng)絡(luò)中不同類節(jié)點(diǎn)的度值及其分布特征，并結(jié)合城市公交系統(tǒng)的實(shí)際情況，研究了寶雞市公交網(wǎng)絡(luò)中線路與站點(diǎn)的關(guān)聯(lián)信息，為公交系統(tǒng)的優(yōu)化提供理論依據(jù)。

1 寶雞公交二分網(wǎng)絡(luò)的構(gòu)建

在復(fù)雜網(wǎng)絡(luò)的研究中，如果希望得到兩種不同的事物之間存在的某種關(guān)聯(lián)性，可通過構(gòu)建兩種不同類型節(jié)點(diǎn)的網(wǎng)絡(luò)以便研究節(jié)點(diǎn)之間的從屬關(guān)系，這種網(wǎng)絡(luò)就稱為二分圖(bipartite graph)[8]。

定義一個(gè)二分圖G=(V,E)，其中V={V1,V2}代表網(wǎng)絡(luò)中的節(jié)點(diǎn)的集合，節(jié)點(diǎn)集合V被劃分為兩個(gè)不相交的子集V1和V2，分別代表兩種不同類型的節(jié)點(diǎn)；E={V1i,V2j}是連接兩個(gè)不同子集中的節(jié)點(diǎn)之間的所有邊的集合，而同一子集中的節(jié)點(diǎn)之間沒有連線，其中i=1,2,…,N1，j=1,2,…,N2，N1和N2分別為兩個(gè)不同子集中的節(jié)點(diǎn)個(gè)數(shù)。

寶雞市公交公司目前一共擁有43條線路，共經(jīng)過344個(gè)不同的站點(diǎn)，考慮公交線路和公交站點(diǎn)兩個(gè)方面之間的聯(lián)系，我們構(gòu)建線路-站點(diǎn)二分網(wǎng)絡(luò)。網(wǎng)絡(luò)中共包含387個(gè)節(jié)點(diǎn)，被分為兩類：N1=43條線路作為一類節(jié)點(diǎn)，記為V1；N2=344個(gè)站點(diǎn)作為另一類節(jié)點(diǎn)，記為V2。當(dāng)V1中的線路i經(jīng)過了V2中的站點(diǎn)j，則節(jié)點(diǎn)i與j之間存在一條邊；反之，則兩個(gè)節(jié)點(diǎn)之間不存在連邊。表1列出了一些隨機(jī)選擇的線路節(jié)點(diǎn)與站點(diǎn)節(jié)點(diǎn)之間的對應(yīng)關(guān)系。其中，如果兩個(gè)節(jié)點(diǎn)間有對應(yīng)關(guān)系，則用1表示；反之，則用0表示。

表1 線路節(jié)點(diǎn)與站點(diǎn)節(jié)點(diǎn)之間的關(guān)系示意表

圖1 寶雞公交線路-站點(diǎn)二分圖

將表1所列舉的這種網(wǎng)絡(luò)節(jié)點(diǎn)之間的對應(yīng)關(guān)系用圖的形式表示出來，即為線路-站點(diǎn)二分圖，如圖1所示。從圖中可以直觀地顯示出線路節(jié)點(diǎn)與站點(diǎn)節(jié)點(diǎn)之間的對應(yīng)關(guān)系，而同種類的節(jié)點(diǎn)之間并沒有連邊存在。

2 寶雞公交二分網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)

復(fù)雜網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)的度定義為該節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間相互連接的邊的數(shù)目。一般情況下，度值越大的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所起的作用就越大，該節(jié)點(diǎn)則越重要。因此，可以用度ki來衡量節(jié)點(diǎn)i在網(wǎng)絡(luò)中的重要程度：

(1)

其中當(dāng)路徑l包含節(jié)點(diǎn)i，即有邊相連接時(shí)，δl為1；否則，δl為0。

而度分布則體現(xiàn)出網(wǎng)絡(luò)中一種重要的幾何性質(zhì)，用分布函數(shù)P(k)來表示，代表網(wǎng)絡(luò)中一個(gè)任意選擇的節(jié)點(diǎn)正好有k條邊的概率，即度為k的節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的比例。下面我們從兩類不同節(jié)點(diǎn)的角度研究網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)。

2.1 線路節(jié)點(diǎn)的統(tǒng)計(jì)性質(zhì)

我們首先考慮寶雞公交線路節(jié)點(diǎn)，由于每條公交線路都經(jīng)過了多個(gè)公交站點(diǎn)，因此，線路節(jié)點(diǎn)的度即代表其經(jīng)過的站點(diǎn)數(shù)目。圖2繪出了每條線路與其經(jīng)過的站點(diǎn)數(shù)的對應(yīng)情況：橫坐標(biāo)n1代表線路的編號(按節(jié)點(diǎn)的度值大小呈降序排列)；縱坐標(biāo)k1則代表該線路節(jié)點(diǎn)的度值，即經(jīng)過的站點(diǎn)數(shù)目。

通過對線路節(jié)點(diǎn)經(jīng)過的公交站點(diǎn)的信息進(jìn)行統(tǒng)計(jì)分析，可以得到以下結(jié)論：

圖2 線路節(jié)點(diǎn)度值(左)及其度分布(右)

(1)線路節(jié)點(diǎn)中具有最大度值的是15路公交線路(k1=45)，占全部公交站點(diǎn)的13.08%,。15路車從寶雞市區(qū)的最東邊虢鎮(zhèn)到寶雞火車站，實(shí)行分段計(jì)價(jià)有人售票模式。橫跨寶雞市三區(qū)中的陳倉區(qū)和金臺區(qū)，途中經(jīng)過火車站、金陵橋西、寶雞石油機(jī)械廠、解放區(qū)第三醫(yī)院、行政中心等45個(gè)站點(diǎn)，這些站點(diǎn)包括寶雞市的樞紐站點(diǎn)、寶雞市的大型廠區(qū)以及寶雞市的繁華地段，是寶雞交通網(wǎng)絡(luò)中不可或缺的一部分。線路節(jié)點(diǎn)中具有最小度值的是19路公交線路(k1=5)，僅占全部公交站點(diǎn)的1.45%，是去大唐秦王陵的一條特定公交線路。

(2)寶雞公交線路的平均度為22，經(jīng)過站點(diǎn)特別多的線路以及特別少的線路僅有少數(shù)，大部分線路經(jīng)過的公交站點(diǎn)數(shù)集中在平均值附近，遠(yuǎn)離平均值的線路數(shù)非常少，度值分布較為均勻，呈現(xiàn)出一種泊松分布狀態(tài)，如圖2(右)所示 。這與交通網(wǎng)絡(luò)的實(shí)情較為符合，大部分線路在規(guī)劃的時(shí)候經(jīng)過的路程遠(yuǎn)近相對均勻，只有少數(shù)線路經(jīng)過最多的站點(diǎn)，覆蓋范圍較大，同時(shí)具有一兩條特定公交線路經(jīng)過的站點(diǎn)最少。

2.2 站點(diǎn)節(jié)點(diǎn)的統(tǒng)計(jì)性質(zhì)

圖3 公交站點(diǎn)的度值(左)、k-P(k)度分布(中)以及l(fā)og-log雙對數(shù)度分布(右)

下面從公交站點(diǎn)的角度研究寶雞公交二分圖的性質(zhì)。每個(gè)站點(diǎn)都有一條或多條線路經(jīng)過，因此，站點(diǎn)節(jié)點(diǎn)的度即代表經(jīng)過其線路的數(shù)目。圖3刻畫了每個(gè)站點(diǎn)節(jié)點(diǎn)與線路數(shù)目的對應(yīng)情況：橫坐標(biāo)n2表示站點(diǎn)節(jié)點(diǎn)的編號(按度值的大小呈降序排列)；縱坐標(biāo)k2為站點(diǎn)節(jié)點(diǎn)的度值，即所經(jīng)過的公交線路的數(shù)目。

通過對公交站點(diǎn)所經(jīng)過的公交線路的信息進(jìn)行分析，我們得到以下結(jié)論：

(1)只有少數(shù)站點(diǎn)具有較高的度值，而大部分站點(diǎn)節(jié)點(diǎn)的度值僅為1或2。這表明大部分站點(diǎn)均只經(jīng)過了一條或兩條公交線路，只有極少數(shù)的站點(diǎn)經(jīng)過較多的公交線路。這些極少數(shù)的公交站點(diǎn)即為寶雞市的樞紐站點(diǎn)或者主要換乘點(diǎn)。

(2)站點(diǎn)節(jié)點(diǎn)中具有最大度值的站點(diǎn)是火車站(k2=13)，表明這個(gè)站點(diǎn)經(jīng)過了最多13條公交線路，即是寶雞市的樞紐中心，又是寶雞市區(qū)的主要換乘點(diǎn)。寶雞火車站是鐵道部所規(guī)定的全國44個(gè)大站之一，是連接西北、西南地區(qū)的交通樞紐，為陜西省的第二大客運(yùn)火車站，客流量密集。因此，在交通規(guī)劃時(shí)這里具有最多的公交線路，以便滿足寶雞市不同去向的客流的需求。

(3)隨著公交線路數(shù)值的減少，站點(diǎn)節(jié)點(diǎn)數(shù)目呈現(xiàn)快速增長，大多數(shù)站點(diǎn)節(jié)點(diǎn)的度值很低，只有少數(shù)站點(diǎn)具有較高的度值，初步判定這種度值分布情況符合冪律度分布的特性。因此，我們對公交站點(diǎn)的度分布進(jìn)行統(tǒng)計(jì)，寶雞公交二分圖中站點(diǎn)節(jié)點(diǎn)的度分布如圖3(中)所示，在雙對數(shù)坐標(biāo)下可以擬合為一條直線，如圖3(右)，其度分布結(jié)果符合冪律分布。

2.3 兩類節(jié)點(diǎn)的對比討論

圖4 寶雞公交二分圖中，線路節(jié)點(diǎn)(圓圈)與站點(diǎn)節(jié)點(diǎn)(三角)度值的對比

圖5 寶雞公交二分圖中，線路節(jié)點(diǎn)(圓圈)與站點(diǎn)節(jié)點(diǎn)(三角)度分布的對比：k-P(k)度分布(左)以及l(fā)og-log雙對數(shù)度分布(右)

寶雞公交二分圖中包含兩類不同的節(jié)點(diǎn)，由網(wǎng)絡(luò)的構(gòu)建規(guī)則可知這兩類節(jié)點(diǎn)的度也代表不同的含義。下面，我們在同一坐標(biāo)系下對比兩類節(jié)點(diǎn)的度值及其分布情況，分別如圖4和圖5所示。圖4中，線路節(jié)點(diǎn)(圓圈)和站點(diǎn)節(jié)點(diǎn)(三角)都是按度值降序排列，兩類節(jié)點(diǎn)的度值變化明顯不同，因此，在圖5的度分布對比圖中，線路節(jié)點(diǎn)呈現(xiàn)出泊松分布，而站點(diǎn)節(jié)點(diǎn)呈現(xiàn)出冪律分布，這種不同的分布情況符合交通網(wǎng)絡(luò)的實(shí)際規(guī)劃。

表2列出了度值排名前5的線路節(jié)點(diǎn)和排名前10的站點(diǎn)節(jié)點(diǎn)的度值及其占最大可能度值的百分比。表中，15路公交線路的度值最高為45，表明其經(jīng)過了總共N2=344個(gè)站點(diǎn)中的45個(gè)站點(diǎn)，比例為13.08%。同理，站點(diǎn)節(jié)點(diǎn)中，火車站的度值最高為13，表明13條公交線路經(jīng)過了火車站，占N1=43條總線路數(shù)的30.23%，這些站點(diǎn)都是寶雞市的主要換乘點(diǎn)、旅游景點(diǎn)或者連接南北東西的樞紐地段。

表2 寶雞公交二分圖中，度值排名前5的線路節(jié)點(diǎn)與排名前10的站點(diǎn)節(jié)點(diǎn)

3 結(jié)束語

本文將寶雞市公交線路信息與公交站點(diǎn)信息結(jié)合在一起，構(gòu)建了寶雞市公交二分網(wǎng)絡(luò)模型，運(yùn)用復(fù)雜網(wǎng)絡(luò)理論進(jìn)行分析，得出以下結(jié)論：

(1) 在寶雞市公交二分網(wǎng)絡(luò)中，包含公交線路與公交站點(diǎn)兩類不同節(jié)點(diǎn)，只有不同類型的節(jié)點(diǎn)之間存在連邊。研究結(jié)果表明，線路節(jié)點(diǎn)度分布呈現(xiàn)泊松分布，度值集中在平均值附近，而站點(diǎn)節(jié)點(diǎn)度分布極為不均，大部分節(jié)點(diǎn)度比較小，極少數(shù)節(jié)點(diǎn)發(fā)揮著重要的作用，度分布均符合冪律分布形式，反映了公交網(wǎng)絡(luò)的復(fù)雜性。

(2) 少數(shù)站點(diǎn)具有較高的度值，這些站點(diǎn)有較多的公交線路經(jīng)過，是寶雞市的樞紐站點(diǎn)、主要換乘點(diǎn)以及重要景區(qū)。這和寶雞市的實(shí)際公交規(guī)劃相符合。

(3) 大部分公交線路經(jīng)過的站點(diǎn)數(shù)多集中在平均度值左右，具有較多站點(diǎn)和較少站點(diǎn)的公交線路都不多，這些線路覆蓋了寶雞市的較大范圍或者是特定旅游線路。

交通系統(tǒng)是一個(gè)非常復(fù)雜的系統(tǒng)，復(fù)雜網(wǎng)絡(luò)理論的發(fā)展為研究交通系統(tǒng)提供了有效的理論工具。我們可通過構(gòu)建交通網(wǎng)絡(luò)模型，與實(shí)際市區(qū)的交通情況相結(jié)合，為寶雞市區(qū)的交通規(guī)劃提供一定的理論指導(dǎo)，綜合考慮客流的分布，運(yùn)行里程的覆蓋范圍等，以優(yōu)化公交線路的規(guī)劃以及公交站點(diǎn)的合理分布。

[1] STROGATZS H. Exploring complex network [J]. Nature, 2001, 410(6825): 268-276.

[3] COSTA L DA F, OLIVEIRA O N JR, TRAVIESO G, et al. Analyzing and modeling real-world phenomena with complex networks: a survey of applications [J]. Advances in Physics，2011, 60(3): 329-412．

[4] M CHORAS,R KOZIK. Real-Time analysis of non-stationary and complex network related data for injection attempts detection[J].Soft Computing in Industrial Applications,2014,(223):257-264.

[5] M NOSRATI,R KARIMI, M Mohammadi,et al. A quick survey on biological networks[J]. World Applied Programming, 2013,3(2):47-51.

[6] 趙金山，狄增如，王大輝．北京市公共汽車交通網(wǎng)絡(luò)兒何性質(zhì)的實(shí)證研究 [J]．復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005，2(2): 45-48．

[7] 汪濤，吳琳麗．基于復(fù)雜網(wǎng)絡(luò)的城市公交網(wǎng)絡(luò)抗毀性分析[J]．計(jì)算機(jī)應(yīng)用研究，2010，27(11): 4084-4086．

[8] DOROGOVTSEV S N, MENDES J F F. Evolution of networks[J]. Advances in Physics, 2002, 51 (4): 1079-1187.

Modeling and Analysis of Baoji Bus Line-station Network Based on the Bipartite Network

Wang Huana, Hu Jingbob

( a. School of Computer, b. School of Electronic and Electrical Engineering of Baoji University of Arts and Sciences, Baoji Shaanxi 721016, China)

Complex network theory has become an effective tool for studying transport systems. Based on the data about 43 bus lines and 344 bus stations in Baoji City, Shaanxi Province, we have constructed a bipartite station-line public transportation network and analyzed the statistical properties of the network. Research results show that the line node degrees of the network are in Poisson distribution and most of them are concentrated near the average value. However, the station node degrees are in power-law distribution, and a small number of nodes are densely connected as key hub nodes of the network. These densely connected lines and stations can be screened out as key planning objects in the course of investigation of the transportation network in Baoji Cit.

complex network； bipartite graph； public transport network； degree distribution； hub node

10.3969/j.issn.1000-3886.2016.03.008

N949

A

1000-3886(2016)03-0023-03

王歡(1981-)，女，陜西人,講師，主要從事復(fù)雜網(wǎng)絡(luò)建模及應(yīng)用研究； 胡靜波(1979-)，男，河南人,講師，主要從事機(jī)器視覺及嵌入式系統(tǒng)研究。

定稿日期: 2015-08-31