面向復(fù)雜有權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法研究

譚紅葉,吳永科,張 虎，劉全明,李 茹,2

(1. 山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2. 山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室, 山西 太原 030006)

0 引言

隨著以互聯(lián)網(wǎng)為代表的網(wǎng)絡(luò)技術(shù)的快速發(fā)展，人類社會已邁入了復(fù)雜網(wǎng)絡(luò)時(shí)代。當(dāng)前，人們生活在一個(gè)充滿各種類型網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)世界。例如，社會網(wǎng)絡(luò)、電力與交通網(wǎng)絡(luò)、經(jīng)濟(jì)與金融網(wǎng)絡(luò)等，在這些網(wǎng)絡(luò)中充斥著各種不同的關(guān)系和結(jié)構(gòu)。隨著研究人員對網(wǎng)絡(luò)性質(zhì)研究的不斷深入，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都有明顯的社區(qū)結(jié)構(gòu)[1]，每個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)之間的連接相對較為緊密，各個(gè)社區(qū)之間的連接相對比較稀疏?；谶@些特征，人們對不同的社會網(wǎng)絡(luò)探索了很多實(shí)用的社區(qū)發(fā)現(xiàn)算法。典型的算法主要包括: (1)基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法，主要有Pothen 等人[2]在20世紀(jì)90年代提出的基于譜分析方法的社區(qū)結(jié)構(gòu)探測算法和Girvan 等人[3]提出的GN層次聚類算法。(2)基于網(wǎng)絡(luò)動力學(xué)的算法，主要包括Reichardt 和 Bornholdt[4-5]將物理學(xué)中Potts模型運(yùn)用到社區(qū)發(fā)現(xiàn)中的超順磁聚類算法，Wu等人[6]將網(wǎng)絡(luò)類比成電路的電流算法。(3)基于模塊度優(yōu)化的算法主要包括貪婪算法[7]和極值優(yōu)化算法[8-9]等。(4)基于聚類的社區(qū)發(fā)現(xiàn)算法是尋找社會網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的一類傳統(tǒng)方法。它基于各個(gè)節(jié)點(diǎn)之間連接的相似性或者強(qiáng)度，把網(wǎng)絡(luò)自然地劃分為各個(gè)子群，根據(jù)向網(wǎng)絡(luò)中添加邊或者是從網(wǎng)絡(luò)中移除邊，該類算法可以分為兩類: 凝聚方法和分裂方法[10-12]。

顯然，這些典型的社區(qū)發(fā)現(xiàn)方法主要針對無權(quán)網(wǎng)絡(luò)，在這些網(wǎng)絡(luò)中節(jié)點(diǎn)之間的邊只有存在或不存在兩種情況，兩節(jié)點(diǎn)之間存在邊則連接強(qiáng)度為1，不存在則為0。但在很多實(shí)際網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的權(quán)值不同，相互的耦合性不同，這些差異對分析復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)起著至關(guān)重要的作用。如科研合作網(wǎng)絡(luò)中，各個(gè)研究者之間的合作論文數(shù)量是不同的，合作論文數(shù)量多的研究者的緊密性通常更強(qiáng)；復(fù)雜交通網(wǎng)絡(luò)中，一個(gè)周期內(nèi)不同城市間的航班班次和火車車次也相差巨大，來往次數(shù)較多的城市更容易形成一體化的經(jīng)濟(jì)圈。顯然，復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接強(qiáng)度會在很大程度上影響網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，因此利用權(quán)重來刻畫連接強(qiáng)度的差異性，并將其應(yīng)用到社區(qū)發(fā)現(xiàn)研究中具有重要的意義[13-15]。

目前，針對有權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究已經(jīng)成為一個(gè)重要的研究方向。相關(guān)研究主要有: Newman M E J[16]提出了WGN算法，是對GN算法的改進(jìn)，將邊介數(shù)用權(quán)重的邊替換；王坤等人[17]提出了基于相似度的加權(quán)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)；韓華等人[18]基于現(xiàn)有的劃分算法提出改進(jìn)的CNM算法對加權(quán)網(wǎng)絡(luò)進(jìn)行劃分，該方法延續(xù)應(yīng)用了社團(tuán)結(jié)構(gòu)分級聚類，對Newman貪婪算法[19]進(jìn)行了改進(jìn)。

本文結(jié)合節(jié)點(diǎn)的直接連邊權(quán)重和基于共同鄰節(jié)點(diǎn)的連邊權(quán)重提出了一種改進(jìn)的節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則?；谶@種改進(jìn)的節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則和團(tuán)體之間的聚集方法構(gòu)建了面向有權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)模型，分別在有權(quán)值的科學(xué)家合作網(wǎng)絡(luò)、全國列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)?；诹熊囘\(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示出我國不同城市間的列車分布情況，發(fā)現(xiàn)了連接最緊密的城市群、包含較少節(jié)點(diǎn)的社區(qū)和孤立的城市節(jié)點(diǎn)等。

1 加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則

1.1 節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則

在無權(quán)復(fù)雜網(wǎng)絡(luò)中，經(jīng)典三元閉包原則指出，如果兩人A和B擁有一個(gè)共同的朋友C，那么這兩個(gè)人今后也很有可能成為朋友，從而使得三個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)閉包三角形ABC。對于一般的網(wǎng)絡(luò)，可以把這一原則推廣如下: 兩個(gè)節(jié)點(diǎn)的共同鄰居數(shù)量越多，這兩個(gè)節(jié)點(diǎn)越相似。本文將該原則應(yīng)用到無向有權(quán)網(wǎng)絡(luò)中，同時(shí)在此基礎(chǔ)上將連邊權(quán)值引入到兩個(gè)節(jié)點(diǎn)間的相關(guān)度計(jì)算模型，節(jié)點(diǎn)相關(guān)度準(zhǔn)則既考慮了兩個(gè)節(jié)點(diǎn)的共同鄰節(jié)點(diǎn)，同時(shí)又考慮了基于共同鄰節(jié)點(diǎn)的連邊權(quán)重。

對于復(fù)雜網(wǎng)絡(luò)，兩個(gè)節(jié)點(diǎn)間的連接強(qiáng)度除了與基于共同鄰節(jié)點(diǎn)形成的連邊相關(guān)外，還與直接相連的邊有關(guān)，因此計(jì)算兩個(gè)節(jié)點(diǎn)的相關(guān)度需要同時(shí)考慮基于共同鄰節(jié)點(diǎn)的連邊權(quán)重和直接連邊權(quán)重。本文通過設(shè)置參數(shù)α，β來調(diào)節(jié)直接連邊權(quán)重和基于共同鄰接點(diǎn)的連邊權(quán)重的關(guān)系，節(jié)點(diǎn)vi和vj之間的權(quán)重可以通過以下式(1)來表示:

(1)

其中，σij表示節(jié)點(diǎn)vi和vj本身的直接連邊權(quán)重，在復(fù)雜有權(quán)網(wǎng)絡(luò)中都會直接列出；σh表示節(jié)點(diǎn)vi和vj基于共同鄰節(jié)點(diǎn)的連邊權(quán)重，需要針對不同類型的復(fù)雜網(wǎng)絡(luò)構(gòu)造對應(yīng)的計(jì)算模型，針對該問題本文面向復(fù)雜有權(quán)網(wǎng)絡(luò)定義了基于共同鄰節(jié)點(diǎn)的連邊權(quán)重；n表示節(jié)點(diǎn)vi和vj的共同鄰節(jié)點(diǎn)數(shù)；α和β分別為直接連邊權(quán)重和基于共同鄰接點(diǎn)的連邊權(quán)重的調(diào)節(jié)參數(shù)，需通過實(shí)驗(yàn)訓(xùn)練，要求α+β=1。

1.2 基于共同鄰節(jié)點(diǎn)的連邊權(quán)重

假設(shè){v1,v2,…,vn}表示節(jié)點(diǎn)vi和vj的共同鄰節(jié)點(diǎn)，{θi1,θi2,…,θin}表示節(jié)點(diǎn)vi與共同鄰節(jié)點(diǎn)的連邊權(quán)重，{θj1,θj2,…,θjn}表示節(jié)點(diǎn)vj與共同鄰節(jié)點(diǎn)的連邊權(quán)重。通過圖1可以看到節(jié)點(diǎn)vi和vj?？梢曰谒鼈兊墓侧徆?jié)點(diǎn)產(chǎn)生進(jìn)一步的聯(lián)系。那么，對于有權(quán)網(wǎng)絡(luò)該如何通過共同鄰節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)vi和vj的連接強(qiáng)度。基于網(wǎng)絡(luò)流中的最大流理論，每一條路徑最大流的流值等于該路徑上最小容量的那條邊所能承受的流量。圖2中節(jié)點(diǎn)vi和vj通過公共鄰節(jié)點(diǎn)v相連，可以看到節(jié)點(diǎn)vi到節(jié)點(diǎn)v的容量為10，節(jié)點(diǎn)v到節(jié)點(diǎn)vj的容量為2。那么，按照最大流理論可以得到節(jié)點(diǎn)vi和vj間的最大流為2。

圖1 兩個(gè)節(jié)點(diǎn)的公共鄰節(jié)點(diǎn)

圖2 兩個(gè)節(jié)點(diǎn)間的最大流

因此，對于基于公共鄰節(jié)點(diǎn)v的連邊權(quán)值計(jì)算問題，依據(jù)最大流理論可以選取兩條邊的最小權(quán)值作為通過該節(jié)點(diǎn)v的連邊的權(quán)重。節(jié)點(diǎn)vi和vj的第h個(gè)公共鄰節(jié)點(diǎn)的連邊權(quán)值計(jì)算如式(2)所示。

σh=min(θih,θjh)

(2)

其中，θih和θjh分別表示節(jié)點(diǎn)vi和vj的第h個(gè)共同鄰節(jié)點(diǎn)的連邊權(quán)值, 且0≤h≤n。

1.3 基于兩種權(quán)值的統(tǒng)一表示框架

復(fù)雜網(wǎng)絡(luò)中的加權(quán)方式通常有兩種: 相異權(quán)和相似權(quán)。相異權(quán)是指權(quán)值越大，節(jié)點(diǎn)間的相關(guān)度越小，關(guān)系越疏遠(yuǎn)；相似權(quán)是指權(quán)值越大，節(jié)點(diǎn)間的相關(guān)度越大，關(guān)系越緊密。本文研究的復(fù)雜有權(quán)網(wǎng)絡(luò)包括科學(xué)合作網(wǎng)絡(luò)和列車運(yùn)行網(wǎng)絡(luò)，兩種復(fù)雜網(wǎng)絡(luò)只考慮無向情況。其中科學(xué)合作網(wǎng)絡(luò)的邊權(quán)賦予采用相似權(quán)的方式，列車運(yùn)行網(wǎng)絡(luò)的邊權(quán)賦予采用相異權(quán)和相似權(quán)的組合方式。由于相異權(quán)考慮了節(jié)點(diǎn)間的距離，相似權(quán)考慮了節(jié)點(diǎn)間的關(guān)系緊密度，因此在列車運(yùn)行網(wǎng)絡(luò)中通過這兩種權(quán)值的組合可以更準(zhǔn)確地反應(yīng)節(jié)點(diǎn)劃分的實(shí)際情況。本文將這兩種權(quán)值表示到統(tǒng)一的節(jié)點(diǎn)權(quán)重度量框架，具體表現(xiàn)形式如式(3)所示。

(3)

其中，σij和ζij分別表示節(jié)點(diǎn)vi和vj的相異權(quán)和相似權(quán)；x，y表示相異權(quán)和相似權(quán)的權(quán)重調(diào)節(jié)參數(shù)，且x+y=1。同時(shí)，式(3)分別對相異權(quán)的倒數(shù)和相似權(quán)做了標(biāo)準(zhǔn)化處理，使不同量綱的兩個(gè)變量都介于0到1之間，一定程度上保證了兩個(gè)參數(shù)的可調(diào)節(jié)性。式(3)可進(jìn)一步寫成式(4):

σ(vi,vj)=x*min(σij)/σij+y*ζij/max(ζij)

(4)

在本文的實(shí)驗(yàn)中，針對科學(xué)合作網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)令相異權(quán)的調(diào)節(jié)參數(shù)x=0，相似權(quán)的調(diào)節(jié)參數(shù)y=1。對列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)通過不斷調(diào)整x和y的取值分析兩個(gè)權(quán)對結(jié)果的影響。

2 面向有權(quán)網(wǎng)絡(luò)的社區(qū)劃分模型

2.1 團(tuán)體間的連接強(qiáng)度度量準(zhǔn)則

通過式(4)可以將單個(gè)節(jié)點(diǎn)合并成一個(gè)個(gè)小團(tuán)體。然后需將這些小團(tuán)體合并成大的團(tuán)體直到形成一個(gè)個(gè)社區(qū)。如何合并這些小團(tuán)體是社區(qū)劃分研究需要解決的一個(gè)關(guān)鍵問題。按照同一社區(qū)通常有較強(qiáng)凝聚性的原則，本文研究通過定義團(tuán)體間的權(quán)值來刻畫團(tuán)體間的連接強(qiáng)度。然后，依照權(quán)重值的大小來合并各個(gè)小團(tuán)體直到形成合適的社區(qū)。兩個(gè)團(tuán)體之間的權(quán)值基于任意兩個(gè)不在一個(gè)小團(tuán)體內(nèi)的節(jié)點(diǎn)的相關(guān)度的加權(quán)平均來計(jì)算，如式(5)所示。

(5)

其中，weight(Ci,Cj)表示小團(tuán)體Ci和Cj之間的權(quán)值；σij表示小團(tuán)體Ci和Cj之間任意兩個(gè)不在一個(gè)小團(tuán)體內(nèi)的節(jié)點(diǎn)的相關(guān)度。

2.2 算法描述

算法思想: 計(jì)算各個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn)相關(guān)度，按照設(shè)定的閾值合并不同的節(jié)點(diǎn)，形成一個(gè)個(gè)小團(tuán)體；計(jì)算不同團(tuán)體間的連接強(qiáng)度，不斷合并節(jié)點(diǎn)或小團(tuán)體，迭代該過程直到找到合適的社區(qū)為止；通過評價(jià)指標(biāo)對社區(qū)劃分結(jié)果進(jìn)行評價(jià)。

算法流程: 假設(shè)G(V，E，W)是一個(gè)由n個(gè)節(jié)點(diǎn)m條邊組成的復(fù)雜網(wǎng)絡(luò)。其中V是網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E是網(wǎng)絡(luò)邊的集合，W是網(wǎng)絡(luò)邊上權(quán)重的集合。

(1) 計(jì)算各個(gè)節(jié)點(diǎn)間的相關(guān)度，表示為σ。同時(shí)，根據(jù)σ的大小設(shè)定一個(gè)閾值T。

(2) 初始化社區(qū)，對于每個(gè)節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)的社區(qū)分別表示為L{i}。

(3) 找到節(jié)點(diǎn)間相關(guān)度最大且其值大于閾值T的節(jié)點(diǎn)對，將其合并為小團(tuán)體。如果節(jié)點(diǎn)vi和vj滿足條件，則將節(jié)點(diǎn)vj對應(yīng)社區(qū)中節(jié)點(diǎn)移到vi對應(yīng)的社區(qū)中，即L{i}=L{i,j}，并將L{j}清空，其相應(yīng)的連接強(qiáng)度全部歸為0。

(4) 重復(fù)步驟(3)直到?jīng)]有找到滿足相關(guān)度(連接強(qiáng)度)最大和相關(guān)度(連接強(qiáng)度)大于閾值T的節(jié)點(diǎn)對為止。

(5) 計(jì)算由步驟(4)得到的團(tuán)體L之間的連接強(qiáng)度W，找到最大W值所對應(yīng)的團(tuán)體進(jìn)行合并。

(6) 重復(fù)步驟(5)，直到團(tuán)體社區(qū)L的個(gè)數(shù)等于k時(shí)迭代終止，并計(jì)算相應(yīng)的社區(qū)劃分的評價(jià)指標(biāo)。

(7) 對不同類型的復(fù)雜網(wǎng)絡(luò)分別設(shè)定不同的k值，評價(jià)不同k值對應(yīng)的社區(qū)劃分結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析3.1 評價(jià)指標(biāo)

為了評價(jià)該方法的社區(qū)劃分效果，本文實(shí)驗(yàn)使用了2004年Newman[20]提出的Q函數(shù)概念，當(dāng)模塊性Q函數(shù)最大時(shí)表示網(wǎng)絡(luò)劃分最好。在加權(quán)網(wǎng)絡(luò)中，Q函數(shù)通常按式(6)的形式計(jì)算。

(6)

其中，aij為網(wǎng)絡(luò)鄰接矩陣的元素，如果vi和vj兩節(jié)點(diǎn)相連，則aij為邊的權(quán)重，否則等于0；δ為隸屬函數(shù)， 當(dāng)節(jié)點(diǎn)vi和vj屬于同一個(gè)社團(tuán)時(shí)， 隸屬函數(shù)

為1，否則等于0；M=0.5*∑aij為網(wǎng)絡(luò)中邊的權(quán)重之和。在網(wǎng)絡(luò)劃分結(jié)構(gòu)固定，兩節(jié)點(diǎn)的邊隨機(jī)連接時(shí)，節(jié)點(diǎn)間存在邊的可能性為kikj/(2M)，ki為節(jié)點(diǎn)vi的點(diǎn)權(quán)，計(jì)算方法為對鄰接矩陣的第i行求和。

3.2 實(shí)驗(yàn)數(shù)據(jù)

本文使用兩個(gè)數(shù)據(jù)集驗(yàn)證所提出的方法，包括: 科學(xué)家合作網(wǎng)絡(luò)和全國列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集。實(shí)驗(yàn)所用的科學(xué)家合作網(wǎng)絡(luò)[21]是由Mark Newman于2006年編寫的有權(quán)網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)表示網(wǎng)絡(luò)科學(xué)領(lǐng)域的科學(xué)家，邊表示科學(xué)家之間的論文合作關(guān)系，權(quán)值為作者間的直接合作數(shù)量。該版本的科學(xué)家合作網(wǎng)絡(luò)共有1 589名科學(xué)家，其中包括由379位科學(xué)家組成的最大社區(qū)。全國列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)收集了我國全部的列車數(shù)據(jù)和任意車次的途徑車站數(shù)據(jù)，為了消除部分特殊點(diǎn)本文的實(shí)驗(yàn)中采用的列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)僅保留了五線城市以上的站點(diǎn)，并對一個(gè)城市中的所有站點(diǎn)進(jìn)行了合并，構(gòu)成了一個(gè)由273個(gè)節(jié)點(diǎn)和12 925條邊的加權(quán)復(fù)雜網(wǎng)絡(luò)，其中不同城市間的連邊權(quán)值由來往車次數(shù)和實(shí)際距離確定。兩組實(shí)驗(yàn)數(shù)據(jù)的基本信息如表1所示。

表1 兩種實(shí)驗(yàn)數(shù)據(jù)信息

3.3 基于科學(xué)家合作網(wǎng)絡(luò)的社區(qū)劃分

針對科學(xué)合作網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行的實(shí)驗(yàn)使用作者間的合作數(shù)據(jù)作為相似權(quán)，實(shí)驗(yàn)表明當(dāng)參數(shù)α，β分布選取0.6和0.4，且閾值T為2時(shí)得到最好的社區(qū)劃分結(jié)果，將整個(gè)網(wǎng)絡(luò)劃分為397個(gè)社區(qū)。此時(shí)各個(gè)子社區(qū)之間沒有連邊，模塊度達(dá)到0.81，最大的子社區(qū)包含節(jié)點(diǎn)數(shù)為379，表2顯示了該實(shí)驗(yàn)的社區(qū)劃分結(jié)果。

表2結(jié)果顯示科學(xué)家合作網(wǎng)絡(luò)中存在很多零散的小社區(qū)。本文方法有效的將社區(qū)中由379位科學(xué)家組成的最大的子社區(qū)部分精確的找出來，并將其余的節(jié)點(diǎn)也很好的進(jìn)行了社區(qū)劃分。其中，節(jié)點(diǎn)數(shù)在5以下的子社區(qū)數(shù)量占所有子社區(qū)數(shù)量的85.6%。該實(shí)驗(yàn)表明本文提出的方法在科學(xué)家合作網(wǎng)絡(luò)數(shù)據(jù)集上會取得模塊度較大的社區(qū)劃分結(jié)果。

表2 基于科學(xué)家合作網(wǎng)絡(luò)數(shù)據(jù)集的社區(qū)劃分結(jié)果統(tǒng)計(jì)

3.4 基于列車運(yùn)行網(wǎng)絡(luò)的社區(qū)劃分

(1) 社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)

在列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)中本文分別將站點(diǎn)的來往次數(shù)作為相似權(quán)，站點(diǎn)間的距離作為相異權(quán)，并基于相異權(quán)和相似權(quán)的不同調(diào)節(jié)參數(shù)分別進(jìn)行了社區(qū)劃分實(shí)驗(yàn)。α，β采用了科學(xué)合作網(wǎng)絡(luò)實(shí)驗(yàn)中結(jié)果最好的參數(shù)作為初始值，同時(shí)使用了其他參數(shù)值進(jìn)行了同類實(shí)驗(yàn)，并選擇了結(jié)果最好的參數(shù)值作為后續(xù)比較實(shí)驗(yàn)的參數(shù)。各組實(shí)驗(yàn)都選取α=0.6，β=0.4，并在T為0.035時(shí)取得較好的實(shí)驗(yàn)結(jié)果。圖3～圖6展示了在不同的社區(qū)數(shù)，不同的x和y時(shí)對應(yīng)的不同效果圖。由于節(jié)點(diǎn)較多實(shí)驗(yàn)選出至少包括10個(gè)節(jié)點(diǎn)的較大的社區(qū)來展示劃分結(jié)果，并將各個(gè)較大社區(qū)包含的不同站點(diǎn)按照經(jīng)緯度在圖中顯示出來。每個(gè)社區(qū)用不同的顏色來區(qū)分，橫坐標(biāo)表示經(jīng)度，縱坐標(biāo)表示緯度。

實(shí)驗(yàn)一7個(gè)較大社區(qū)時(shí)，不同相異權(quán)和相似權(quán)對應(yīng)的社區(qū)劃分結(jié)果如圖3a～3c所示:

圖3a 只考慮站點(diǎn)間距離的社區(qū)劃分

圖3b x=0.9 y=0.1

圖3c x=0.8 y=0.2

實(shí)驗(yàn)中在x=0.7和y=0.3時(shí)未找見7個(gè)較大社區(qū)。

實(shí)驗(yàn)二6個(gè)較大社區(qū)時(shí)，不同相異權(quán)和相似權(quán)對應(yīng)的社區(qū)劃分結(jié)果如圖4a～4d所示。

圖4a 只考慮站點(diǎn)間距離的社區(qū)劃分

圖4b x=0.9 y=0.1

圖4c x=0.8 y=0.2

圖4d x=0.7 y=0.3

實(shí)驗(yàn)中，在x=0.6和y=0.4時(shí)，未找見6個(gè)較大社區(qū)。

實(shí)驗(yàn)三5個(gè)較大社區(qū)時(shí)，不同相異權(quán)和相似權(quán)對應(yīng)的社區(qū)劃分結(jié)果如圖5a～5e所示:

圖5a 只考慮站點(diǎn)間距離的社區(qū)劃分

圖5b x=0.9 y=0.1

圖5c x=0.8 y=0.2

圖5d x=0.7 y=0.3

圖5e x=0.6 y=0.4

實(shí)驗(yàn)中，在x=0.5和y=0.5時(shí)，未找到5個(gè)較大社區(qū)。

實(shí)驗(yàn)四4個(gè)較大社區(qū)時(shí)，不同相異權(quán)和相似權(quán)對應(yīng)的社區(qū)劃分結(jié)果如圖6a～6e所示:

圖6a 只考慮站點(diǎn)間距離的社區(qū)劃分

圖6b x=0.9 y=0.1

圖6c x=0.8 y=0.2

圖6d x=0.7 y=0.3

圖6e x=0.6 y=0.4

實(shí)驗(yàn)中，在x=0.5和y=0.5時(shí)，未找到4個(gè)較大社區(qū)。

(2) 實(shí)驗(yàn)結(jié)果分析

圖3～圖6顯示出不同城市之間形成了較明顯的社區(qū)結(jié)構(gòu)。對于只考慮站點(diǎn)間距離的社區(qū)劃分形成的圖3～圖6中的a圖，盡管形成了社區(qū)，但部分社區(qū)將離得較遠(yuǎn)的節(jié)點(diǎn)劃分到一起了，出現(xiàn)這種現(xiàn)象的主要有兩個(gè)原因: ①部分節(jié)點(diǎn)只與較遠(yuǎn)的節(jié)點(diǎn)有連邊； ②兩個(gè)節(jié)點(diǎn)之間的連邊權(quán)值，既考慮了直接連邊也考慮了共同鄰居節(jié)點(diǎn)的連邊。

對于圖3～圖6中的b、c、d、e圖，針對不同的社區(qū)數(shù)的社區(qū)劃分結(jié)構(gòu)都有明顯的變化，但從圖中可以看出越到后邊的圖節(jié)點(diǎn)越稀疏，社區(qū)越清晰，越能看出列車運(yùn)行網(wǎng)絡(luò)的骨干線路。出現(xiàn)這種現(xiàn)象主要是因?yàn)殡S著連邊權(quán)值的調(diào)節(jié)參數(shù)不斷加大，節(jié)點(diǎn)之間的連邊數(shù)在社區(qū)劃分中起的作用越大，而相應(yīng)的節(jié)點(diǎn)距離起的作用就會變小。這將會導(dǎo)致部分地理位置上比較緊密的點(diǎn)，可能由于來往次數(shù)比較少而成為了孤立節(jié)點(diǎn)或者較小的社區(qū)。

圖4a中6個(gè)大社區(qū)時(shí)的社區(qū)劃分對應(yīng)的部分城市如表3所示，表4為考慮距離與來往次數(shù)比值為 7∶3時(shí)的社區(qū)劃分結(jié)果對應(yīng)的城市列表，表5是兩者的交集結(jié)果。通過對這些數(shù)據(jù)的分析可以發(fā)現(xiàn)三類城市: ①部分城市距離較近，但他們之間的列車運(yùn)行趟數(shù)較少，這些城市會隨著連邊次數(shù)的權(quán)值占比加大而逐漸分散； ②部分城市距離較遠(yuǎn)，會隨著連邊次數(shù)的權(quán)值占比加大而逐漸聚合； ③部分城市不僅距離較近，他們之間的列車運(yùn)行趟數(shù)也較多，屬于比較穩(wěn)定的經(jīng)濟(jì)體，如表5所示。同時(shí)，基于完整的社區(qū)發(fā)現(xiàn)數(shù)據(jù)還可進(jìn)一步發(fā)現(xiàn)較小的社區(qū)和孤立點(diǎn)。

表3 只考慮距離的社區(qū)劃分結(jié)果對應(yīng)的城市列表

表4 考慮距離與來往次數(shù)比值為7∶3時(shí)的社區(qū)劃分結(jié)果對應(yīng)的城市列表

表5 表3和表4相交的城市列表

針對不同類型數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的面向復(fù)雜有權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法具有較好的社區(qū)劃分效果。面向全國列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)分析了全國列車城市站點(diǎn)的不同類別，挖掘了穩(wěn)定的經(jīng)濟(jì)體、節(jié)點(diǎn)較少的社區(qū)和孤立點(diǎn)等，可進(jìn)一步為較大的經(jīng)濟(jì)體的建設(shè)提供重要的依據(jù)。

4 結(jié)論

本文結(jié)合節(jié)點(diǎn)的直接連邊權(quán)重和基于共同鄰居節(jié)點(diǎn)的連邊權(quán)重提出了一種改進(jìn)的節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則?；谶@種改進(jìn)的節(jié)點(diǎn)相關(guān)度度量準(zhǔn)則和團(tuán)體之間的聚集方法構(gòu)建了面向有權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)模型。在有權(quán)值的科學(xué)家合作網(wǎng)絡(luò)和全國列車運(yùn)行網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)，驗(yàn)證了本文提出的方法在有權(quán)網(wǎng)絡(luò)的社區(qū)劃分上的有效性，分析了該方法在全國列車運(yùn)行城市類別研究中的重要意義。接下來將在本文實(shí)驗(yàn)的基礎(chǔ)上進(jìn)一步面向復(fù)雜交通網(wǎng)絡(luò)研究最有影響力的城市節(jié)點(diǎn)發(fā)現(xiàn)方法和社區(qū)的“結(jié)構(gòu)洞”挖掘模型。