基于Hausdorff距離的關(guān)系層次聚類算法

唐四慧，莊 東，劉 瀟

(1.華南理工大學(xué)工商管理學(xué)院，廣州 510640；2.澳大利亞國立大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，澳大利亞，堪培拉 0200；3.暨南大學(xué)管理學(xué)院，廣州 510632)

0 引言

大數(shù)據(jù)的爆炸不全來自于物理世界，其中70%來自于近2年人類的行為包括通訊、社交、購物、互聯(lián)網(wǎng)活動(dòng)等。非常多的應(yīng)用希望利用這種關(guān)系數(shù)據(jù)來了解人類，以期解釋群體社會(huì)行為如席卷伊斯蘭世界(以及一部分西方世界)的宗教原教旨主義，集體經(jīng)濟(jì)安全，全球變暖和我們時(shí)代的大流行[1]。早在過去的60年里，社會(huì)學(xué)家就開始關(guān)注人類的交互行為和群體行為，他們還構(gòu)建了網(wǎng)絡(luò)分析方法來量化這些行為，但是社會(huì)現(xiàn)象不僅包括大量的異質(zhì)個(gè)體而且這些行為還會(huì)在時(shí)間和空間展開?；跇泳淼木W(wǎng)絡(luò)分析方法不再適用于互聯(lián)網(wǎng)環(huán)境下多時(shí)間多空間尺度的群組，這里的個(gè)體行為我們需要考慮1)個(gè)體的經(jīng)歷，2)與其它個(gè)體的競(jìng)爭(zhēng)、合作、比較的關(guān)系，3)他所在的組織和制度，4)以及所有成分之間的相互作用。只有了解這些關(guān)系，我們才能預(yù)測(cè)群體過程。聚類算法是分析群體行為的工具，將傳統(tǒng)的算法應(yīng)用于人類關(guān)系數(shù)據(jù)的研究需要解決以下問題：

2)網(wǎng)絡(luò)的層次結(jié)構(gòu)。異質(zhì)性和斑塊鑲嵌是流動(dòng)發(fā)生的基礎(chǔ)但層級(jí)結(jié)構(gòu)是穩(wěn)定這種結(jié)構(gòu)的機(jī)制[8]，同時(shí)層次結(jié)構(gòu)也使得系統(tǒng)中的流最大化如生態(tài)系統(tǒng)[9]，對(duì)人類群體行為理解后還希望能優(yōu)化它的功能比如控制流動(dòng)[10]。關(guān)系的非對(duì)稱性是建構(gòu)層次結(jié)構(gòu)的基礎(chǔ)。

3)在海量關(guān)系數(shù)據(jù)上有好的速度。

目前的網(wǎng)絡(luò)聚類算法不能同時(shí)將這3個(gè)問題全部解決。在這篇文章中，我們首先運(yùn)用迭代系統(tǒng)隱喻個(gè)體結(jié)構(gòu)的變化，構(gòu)建個(gè)體結(jié)構(gòu)譜，通過結(jié)構(gòu)譜確定節(jié)點(diǎn)結(jié)構(gòu)屬性；再將Hausdorff距離(H氏距離)引入DBSCAN算法，用以解決關(guān)系數(shù)據(jù)非對(duì)稱性的距離測(cè)度，運(yùn)用Hutchinson算子中的加和算子對(duì)同結(jié)構(gòu)節(jié)點(diǎn)進(jìn)行合并，用輸入輸出關(guān)系實(shí)現(xiàn)層次結(jié)構(gòu)的并算子；加和及并算子均為單調(diào)增量方式，處理結(jié)果在時(shí)間和空間維度上可以復(fù)用，從而使得算法在大型關(guān)系數(shù)據(jù)集上有良好的速度。文章的撰寫按以下的方式來組織：第2部分對(duì)已有的層次聚類、劃分算法進(jìn)行特征歸納，得出關(guān)系數(shù)據(jù)層次聚類算法應(yīng)考慮的問題和設(shè)計(jì)標(biāo)準(zhǔn)。第3部分運(yùn)用迭代系統(tǒng)的輸入輸出關(guān)系構(gòu)建關(guān)系數(shù)據(jù)的非對(duì)稱距離測(cè)度。第4部分對(duì)算法進(jìn)行闡述，首先依據(jù)第3部分將節(jié)點(diǎn)進(jìn)行結(jié)構(gòu)標(biāo)識(shí)，然后用結(jié)構(gòu)標(biāo)識(shí)篩選出相關(guān)網(wǎng)絡(luò)數(shù)據(jù)子集并送入DBSCAN算法中。第5部分應(yīng)用中國復(fù)雜網(wǎng)絡(luò)研究群體的數(shù)據(jù)驗(yàn)證算法的有效性及帶來的新發(fā)現(xiàn)。第6部分對(duì)算法進(jìn)行總結(jié)及闡述進(jìn)一步研究的方向。

1 層次聚類算法的設(shè)計(jì)標(biāo)準(zhǔn)

層次聚類算法按處理過程可分為：全局(劃分)和局部(聚集)[11]。全局過程需要知道全局的信息比如決策樹，明確知道類的劃分，然后依據(jù)這個(gè)劃分來優(yōu)化和評(píng)價(jià)聚類過程。網(wǎng)絡(luò)社團(tuán)劃分方法中，GN算法是全局過程，邊的介數(shù)中心性是全局指標(biāo)，要運(yùn)用到網(wǎng)絡(luò)中所有節(jié)點(diǎn)來計(jì)算。局部過程不需要知道全局信息，它是一種啟發(fā)式方法。根據(jù)局部過程對(duì)核心節(jié)點(diǎn)的認(rèn)定大致分為3類：簇中所有節(jié)點(diǎn)均為核心節(jié)點(diǎn)(LPM，Modularity Q)；簇中部分節(jié)點(diǎn)為核心節(jié)點(diǎn)(DBSCAN,CPM)；一個(gè)簇中只有一個(gè)核心節(jié)點(diǎn)(K-means,K-mediods)，DBSCAN和CPM算法會(huì)繼續(xù)在非核心節(jié)點(diǎn)中區(qū)分噪聲節(jié)點(diǎn)，噪聲節(jié)點(diǎn)不參與簇質(zhì)量的計(jì)算。

按是否為層次分類可分為兩類：劃分和層次。劃分算法中無需考慮簇與簇的合并，故不用衡量簇與簇之間的距離而層次聚類需要考慮，故延伸出最小值、最大值、平均值及平均距離等方法[12]。對(duì)于簇與簇的合并，層次算法中會(huì)運(yùn)用加和算子和并算子，加和算子是處理同質(zhì)簇僅為數(shù)量上的增加，在系統(tǒng)組成元素類型上沒變化；并算子不僅在數(shù)量上有增加而且在系統(tǒng)組成元素上也有增加，例如決策樹中如果有風(fēng)和無風(fēng)是并運(yùn)算，那么有風(fēng)天氣時(shí)下雨和不下雨只是加合運(yùn)算。

由此可以得出一個(gè)層次凝聚聚類算法應(yīng)包括核心節(jié)點(diǎn)和噪聲節(jié)點(diǎn)的確定、加和運(yùn)算和并運(yùn)算。首先是核心節(jié)點(diǎn)和噪聲節(jié)點(diǎn)的確定，劃分算法有確定核心節(jié)點(diǎn)的方式而層次聚類則默認(rèn)簇中的節(jié)點(diǎn)就是核心節(jié)點(diǎn)，K-means用虛擬節(jié)點(diǎn)，K-medoid用具體節(jié)點(diǎn)，DBSCAN算法在距離定義的基礎(chǔ)上增加了密度要求(NEps(q)≥MinPts)，CPM算法要求核心節(jié)點(diǎn)位于k-clique中(k-clique為k個(gè)全連接的節(jié)點(diǎn))，節(jié)點(diǎn)度數(shù)為k，且k個(gè)鄰居互為鄰居[13]。所有算法都要求核心節(jié)點(diǎn)能代表群體，在單個(gè)節(jié)點(diǎn)不具有的群體屬性上制定劃分標(biāo)準(zhǔn)。

產(chǎn)生出核心節(jié)點(diǎn)后就可以確定噪聲，式(1)描述了DBSCAN算法的確定方式：

(1)

CPM算法則是根據(jù)與核心節(jié)點(diǎn)是否存在連邊進(jìn)行判斷，這里可以看到劃分節(jié)點(diǎn)類型時(shí)并算子的運(yùn)用

表1 噪聲、邊緣及核心節(jié)點(diǎn)間的并運(yùn)算

流動(dòng)會(huì)發(fā)生在核心節(jié)點(diǎn)與邊緣節(jié)點(diǎn)及核心節(jié)點(diǎn)之間，它們之間有關(guān)系也存在有并算子，非對(duì)稱關(guān)系包含對(duì)稱關(guān)系。

表2 不同節(jié)點(diǎn)間關(guān)系的并運(yùn)算

層次結(jié)構(gòu)除了有同層運(yùn)算還需要處理不同層之間的連接?？臻g層次聚類中相似尺度從高到低體現(xiàn)了空間維度的包含關(guān)系，相似尺度從0.8變化到0.4會(huì)包含小于0.8和不小于0.8，從0.4到0.2包含小于0.4和不小于0.4，決策樹是類別數(shù)據(jù)的包含。在做層與層之間的并運(yùn)算時(shí)，要求不斷添加原有系統(tǒng)中沒有的元素并使得某一系統(tǒng)的全局指標(biāo)單調(diào)變化，空間層次是空間距離，決策樹是熵。在CPM算法中k-clique中的k不斷增大，但這一過程并沒有在系統(tǒng)組成元素中添加新的成份，4-clique可以看成是4個(gè)3-clique，僅為數(shù)量增加；DBSCAN算法要求簇與簇合并時(shí)，簇之間的距離要求小于Eps(任意節(jié)點(diǎn)間的最小距離)，距離從1Eps擴(kuò)展到2Eps；決策樹在作簇與簇的合并時(shí)合并是非關(guān)系。

由此得出一個(gè)關(guān)系凝聚層次聚類算法的設(shè)計(jì)標(biāo)準(zhǔn)：能夠識(shí)別核心和噪聲節(jié)點(diǎn)；定義節(jié)點(diǎn)間的連接關(guān)系；定義簇之間的關(guān)系；所有定義要體現(xiàn)加和及并算子，加和算子僅為同類數(shù)量的增加，并算子要求有類別的變化。

2 關(guān)系數(shù)據(jù)的非對(duì)稱性處理及距離測(cè)度

從社會(huì)學(xué)角度來看，識(shí)別不同簇的原因在于不同的簇具有不同的功能，迭代系統(tǒng)中功能用輸入輸出對(duì)表示，簇間的輸出輸入關(guān)系構(gòu)建了層次，如果一個(gè)簇的輸出作為另一個(gè)簇的輸入，那么后一個(gè)簇就比前一個(gè)簇的層級(jí)結(jié)構(gòu)高，由此形成了更高的功能。找出簇是發(fā)現(xiàn)層次結(jié)構(gòu)的基礎(chǔ)，按照DBSCAN算法的流程，首先需要找出在結(jié)構(gòu)上能代表簇的核心節(jié)點(diǎn)，它要求核心節(jié)點(diǎn)能夠接受簇能接受的所有輸入并產(chǎn)生相同的輸出。不同于簇，節(jié)點(diǎn)不存在非我的空間關(guān)系擴(kuò)展，它的迭代發(fā)生在時(shí)間維度上——上次和這次。

2.1 處理關(guān)系數(shù)據(jù)的非對(duì)稱性

對(duì)于關(guān)系的非對(duì)稱性，2002年Yadohisa基于Jambu擴(kuò)展Lance and Williams對(duì)稱的簇間距離的計(jì)算方法提出非對(duì)稱性關(guān)系的距離計(jì)算方法[6]。

距離dK(IJ)則在參數(shù)上進(jìn)行變化用以度量非對(duì)稱性。非對(duì)稱性主要發(fā)生在層間聚類中，高一層次的簇在包含子集時(shí)，因?yàn)樽蛹臓顟B(tài)存在不同，故高一層的簇與不同子集的距離不同，這時(shí)我們關(guān)注的是高一層次的簇和子簇之間的距離，不用再考慮同層子簇與子簇之間的距離，除非同一層的某個(gè)子簇可以代表高一層的簇?；诳臻g距離測(cè)度的算法，因?yàn)楣?jié)點(diǎn)間的距離與簇間的距離在計(jì)算時(shí)是可壓縮變換所以可以用子簇和子簇距離來表示上一層與子層的距離。關(guān)系數(shù)據(jù)在歐氏距離的測(cè)度下是非壓縮的[14]，本算法中運(yùn)用反饋系統(tǒng)中的迭代關(guān)系來表示層間的距離。

迭代系統(tǒng)可用函數(shù)Xn+1=F(Xn)來表示，比如指數(shù)函數(shù)xn+1=axn、冪律函數(shù)xn+1=xnα。在研究迭代系統(tǒng)的輸入輸出轉(zhuǎn)換關(guān)系時(shí)，有兩點(diǎn)需要關(guān)注一是系統(tǒng)的狀態(tài)已經(jīng)變?yōu)橄到y(tǒng)的輸出，二是系統(tǒng)的輸入也變?yōu)橄到y(tǒng)當(dāng)前的輸出。指數(shù)函數(shù)會(huì)將系統(tǒng)狀態(tài)變?yōu)橄到y(tǒng)輸出但系統(tǒng)的輸入仍然是系統(tǒng)最初的輸入，由公式xn+1=axn=a*axn-1=a*a*axn-2可看出；冪律函數(shù)xn+1=xnα的接受狀態(tài)和輸入都會(huì)變?yōu)橄到y(tǒng)的輸出。為了更具體地解析輸入、狀態(tài)及輸出的關(guān)系，我們將迭代了n次的系統(tǒng)(1+x)n表示為1+a1x+a2x2+…+anxn，當(dāng)下次接收相同的輸入(1+x)時(shí)，系統(tǒng)會(huì)產(chǎn)生新的項(xiàng)an+1xn+1，它是由原系統(tǒng)中anxn項(xiàng)產(chǎn)生(相同的輸入x因個(gè)體的狀態(tài)不同產(chǎn)出也不同)。接著是輸出是輸入的部分，我們將輸出拆分為與上一次迭代系統(tǒng)相同的部分1+a1x+a2x2+…+anxn和原來沒有的部分an+1xn+1，只有最新產(chǎn)生的部分去接收最新產(chǎn)生的輸入才會(huì)得到系統(tǒng)原來絕對(duì)沒有的部分(an+1xn+1接受an+1xn+1一定會(huì)讓系統(tǒng)元素增加)。具有最高等級(jí)結(jié)構(gòu)序列的個(gè)體在時(shí)間維度上包含了所有群體在空間維度上可接受的輸入然后通過接受最新的輸入讓結(jié)構(gòu)單調(diào)遞增變化，因此在算法中我們用具有最高等級(jí)結(jié)構(gòu)序列的個(gè)體來代表群體。我們用表3說明這一事實(shí)并給出關(guān)系輸入輸出的例子來更好的理解狀態(tài)、輸入及輸出的關(guān)系。

表3 狀態(tài)、輸入及輸出對(duì)應(yīng)表

迭代系統(tǒng)中可接受的輸入與狀態(tài)有關(guān)，通過結(jié)合狀態(tài)及輸入可能產(chǎn)生原有系統(tǒng)沒有的新特性。

圖1 不同輸入產(chǎn)生相同輸出

依據(jù)輸入輸出對(duì)的關(guān)系圖1中，a(3)、b(3)的結(jié)構(gòu)是不同的，因?yàn)樗鼈兊妮斎氩煌?，產(chǎn)生出的新特性不同，a(3)產(chǎn)生出不在社團(tuán)中的一條連邊，b(3)產(chǎn)生出一個(gè)社團(tuán)。隨著Ego節(jié)點(diǎn)鄰居數(shù)的不斷增加，可以構(gòu)建一個(gè)以鄰居數(shù)為橫軸，輸出結(jié)構(gòu)為縱軸的二維圖譜，圖2。隨著結(jié)構(gòu)的變化，Ego節(jié)點(diǎn)可接受的輸入數(shù)增多，相應(yīng)的輸出結(jié)構(gòu)數(shù)也增多。算法中只考慮由Ego發(fā)出的變化，所以只研究實(shí)線箭頭不研究虛線箭頭，實(shí)線箭頭中再區(qū)分Ego節(jié)點(diǎn)是否用到最新的狀態(tài)去接受最新的輸入產(chǎn)生出原來系統(tǒng)不存在的結(jié)構(gòu)。圖3中，b(2)比a(2)、b(3)比a(3)的結(jié)構(gòu)等級(jí)高，因?yàn)閎(2)考慮到b(1)有一個(gè)鄰居，新認(rèn)識(shí)的第二個(gè)鄰居要認(rèn)識(shí)已有鄰居，b(3)考慮到現(xiàn)有鄰居都在一個(gè)社團(tuán)中，要求第三個(gè)鄰居不在現(xiàn)有社團(tuán)中；而a(2)、a(3)則一直按a(1)的方式在新增鄰居，沒有用到a(1)的現(xiàn)有狀態(tài)信息。

圖2 Ego節(jié)點(diǎn)鄰居數(shù)與結(jié)構(gòu)變化關(guān)系圖

圖3 結(jié)構(gòu)等級(jí)比較

由此可以得到一個(gè)單調(diào)的關(guān)系迭代序列，這里an+1=f(an)n=0,1,2…

圖4 Ego節(jié)點(diǎn)結(jié)構(gòu)單調(diào)變化圖譜

2.2 關(guān)系功能距離的測(cè)度

圖4采用的算子是并，對(duì)于并運(yùn)算，H氏距離具有壓縮性，所以這里引入功能距離的測(cè)度——H氏距離，運(yùn)用H氏距離來描述系統(tǒng)變化的單調(diào)遞增性。

圖5 H氏距離的定義[13]

圖5中，具有包含關(guān)系時(shí)H(B,A)=0，而不具包含關(guān)系時(shí)需要用最小的包含B的ε-環(huán)來定義，H(A,B)=aε[14]。具體到關(guān)系的功能距離，在圖4中，因?yàn)閍1包含a0，故H(a1,a0)=0而H(a0,a1)=1，直接的輸入輸出關(guān)系定義為1，輸入的輸入則定義為2，依次。H氏距離具有加合性H(a2,a0)=H(a2,a1)+H(a1,a0)=0；H(a0,a2)=H(a0,a1)+H(a1,a2)=2。顯然H氏距離是非對(duì)稱的H(a1,a0)≠H(a0,a1)。序列中用到的H氏距離滿足d(f(x),f(y))≤cd(x,y)0≤c<1。定義了H氏距離后，可以將關(guān)系網(wǎng)絡(luò)中的連接分為兩類：結(jié)構(gòu)連接、功能連接。結(jié)構(gòu)連接表示節(jié)點(diǎn)間有連邊存在如合作關(guān)系、關(guān)注關(guān)系、引用關(guān)系；功能連接是基于結(jié)構(gòu)連接之上的，依據(jù)節(jié)點(diǎn)對(duì)結(jié)構(gòu)上的距離來定義。

3 關(guān)系數(shù)據(jù)的層次聚類

3.1 算法概念

在傳播研究場(chǎng)景下，傳播意味著接受傳播物，擴(kuò)散意味著采納數(shù)量的增多，對(duì)于核心節(jié)點(diǎn)除了能接受傳播物外還要求其有擴(kuò)散意愿和擴(kuò)散能力。對(duì)于一個(gè)傳播物最想傳播它的是當(dāng)次將其轉(zhuǎn)換為輸出的結(jié)構(gòu)，因?yàn)檫@類個(gè)體在采納后獲得了收益。算法先在圖4的結(jié)構(gòu)譜中確定結(jié)構(gòu)進(jìn)而按結(jié)構(gòu)選定備選核心節(jié)點(diǎn)，接著要求核心節(jié)點(diǎn)的鄰居中要有足夠多的點(diǎn)能接受傳播物。首先是同結(jié)構(gòu)和上層的個(gè)體，因?yàn)樗鼈兘邮苓^這樣的輸入，知道這樣輸入的作用。接著就是下一層的結(jié)構(gòu)，它們具有接受傳播物的結(jié)構(gòu)同時(shí)接受后可改變其現(xiàn)有結(jié)構(gòu)。對(duì)于下兩層及之后的結(jié)構(gòu)，因其不具接受傳播物的狀態(tài)故無法采納，將不被計(jì)入可傳播的個(gè)體中。按H氏距離理解，上層個(gè)體與同層個(gè)體因?yàn)槭前P(guān)系所以H氏距離為0，下一層的個(gè)體因?yàn)槭侵苯虞斎腙P(guān)系所以H氏距離為1，下兩層及之后的個(gè)體H氏大于1。傳播中首先要求結(jié)構(gòu)距離必須為1，接著要求功能(H氏)距離小于等于1，這兩種距離之間具有包含關(guān)系。

定義1節(jié)點(diǎn)p的可傳播鄰居數(shù)表示為NEps(P)，其中NEps(P)={q∈D|H(p,q)≤1}。

定義1用于計(jì)算可傳播鄰居數(shù)，相較DBSCAN算法，該定義不僅要求結(jié)構(gòu)可達(dá)S(p,q)=1而且功能可達(dá)H(p,q)≤1。通過規(guī)定MinPts可以將節(jié)點(diǎn)分為核心節(jié)點(diǎn)和非核心節(jié)點(diǎn)，算法中核心節(jié)點(diǎn)和非核心節(jié)點(diǎn)是基于一個(gè)傳播物定義的，同理簇和噪聲也是相對(duì)應(yīng)于一個(gè)傳播物。我們不能要求簇中的所有節(jié)點(diǎn)都是核心節(jié)點(diǎn)，有些節(jié)點(diǎn)可接受傳播物但傳播能力不夠。對(duì)于邊緣節(jié)點(diǎn)用下面的定義來闡述。

定義2直接傳播物可達(dá) 在條件Eps和MinPts下，節(jié)點(diǎn)p從節(jié)點(diǎn)q是直接傳播物可達(dá)的，如果：

1)p∈NEps(q)

2)|NEps(q)|≥MinPts(核心節(jié)點(diǎn)條件)

依定義1，可達(dá)鄰居里分為3類：上層、同結(jié)構(gòu)及下一層。這里雖全部表現(xiàn)為傳播物直接可達(dá)，但采納概率存在差別，因?yàn)樯蠈右呀?jīng)采納過并且已經(jīng)接收了新的輸入，此類輸入對(duì)其結(jié)構(gòu)的改變意義不大，能接受此輸入的目的在于增強(qiáng)未采納者的信心；對(duì)于同結(jié)構(gòu)的雖采納也不會(huì)改變結(jié)構(gòu)，但采納后對(duì)結(jié)構(gòu)的影響感知深切，所以在這里再次采納的可能性最高同時(shí)也愿意推廣；對(duì)于下一層個(gè)體，因?yàn)闊o法知道采納后帶來的益處，所以采納的概率最低但對(duì)于想要傳播的人來講，下一層個(gè)體的采納是最有意義的。就傳播概率來說，簇的空間擴(kuò)展是基于核心節(jié)點(diǎn)的，因?yàn)楹诵墓?jié)點(diǎn)在傳播意愿上達(dá)成共識(shí)使得傳播物的傳播在核心節(jié)點(diǎn)網(wǎng)絡(luò)上是無阻擴(kuò)散的，由此自然得出直接傳播物可達(dá)的規(guī)范擴(kuò)展——傳播物可達(dá)。

定義3傳播物可達(dá) 條件Eps和MinPts下，如果存在一條傳播鏈Pl……Pn,Pl=q,Pn=p，其中Pi+l到Pi是直接傳播物可達(dá)，即節(jié)點(diǎn)p是從節(jié)點(diǎn)q傳播物可達(dá)。

因?yàn)閭鞑ノ镌诤诵墓?jié)點(diǎn)網(wǎng)絡(luò)上的流動(dòng)是無阻的，所以在直接傳播可達(dá)的鏈上加載更多的核心節(jié)點(diǎn)，相當(dāng)于把連接的核心節(jié)點(diǎn)看成是一個(gè)節(jié)點(diǎn)，由此完成簇的加和運(yùn)算實(shí)現(xiàn)同層簇空間的擴(kuò)展。

定義4傳播物相連 條件Eps和MinPts下，如果存在一個(gè)核心節(jié)點(diǎn)o，它對(duì)節(jié)點(diǎn)p和q同時(shí)是傳播物可達(dá)的，那么p和q是傳播物相連。

非核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)是通過關(guān)聯(lián)的核心節(jié)點(diǎn)連接的，由此得到簇在邊緣節(jié)點(diǎn)上的擴(kuò)展?，F(xiàn)在可以定義基于H氏距離的關(guān)系層次聚類算法，簇就是對(duì)傳播物可達(dá)最大擴(kuò)展后得到傳播物相連的節(jié)點(diǎn)的集合，噪聲則是不在所有簇中的節(jié)點(diǎn)。

定義5(簇)假設(shè)D是所有點(diǎn)的集合。在條件Eps和MinPts條件下，C是D中滿足如下條件的子集：

1)?p,q：如果p∈C,q密度可達(dá)pWrt.Eps and MinPts，則q∈c(Maximality)。

2)?p,q:p,q是密度相連的Wrt.Eps and MinPts(Connectivity)。

定義6(噪聲)假設(shè)C1……Ck為數(shù)據(jù)集D在條件Eps和MinPts下的簇i=1,2…k，則不屬于任何簇的節(jié)點(diǎn)就是噪聲。噪聲={p∈D|i:p?Ci}。

同層簇得到劃分后，下一步是層次結(jié)構(gòu)的發(fā)現(xiàn)，前面介紹過如果一個(gè)簇是另一個(gè)簇的輸入那么后一個(gè)簇就在層次上較之前一個(gè)高，在構(gòu)建節(jié)點(diǎn)結(jié)構(gòu)描述時(shí)構(gòu)建了一個(gè)時(shí)間序列，在這個(gè)序列中前一個(gè)結(jié)構(gòu)是后一個(gè)結(jié)構(gòu)的輸入，同時(shí)，也闡述了用具有最高結(jié)構(gòu)序列的節(jié)點(diǎn)來代表簇，所以在構(gòu)建簇的層次結(jié)構(gòu)時(shí)，可以用核心節(jié)點(diǎn)來代表簇的結(jié)構(gòu)層次，沿著圖4譜序列推進(jìn)核心節(jié)點(diǎn)結(jié)構(gòu)時(shí)就是對(duì)簇層次結(jié)構(gòu)的一個(gè)爬升，這與傳統(tǒng)的層次聚類方法一致。

3.2 算法實(shí)現(xiàn)

聚類首先是分層，每層首先在備選節(jié)點(diǎn)中選出核心節(jié)點(diǎn)，然后再通過核心節(jié)點(diǎn)之間的連邊對(duì)核心進(jìn)行擴(kuò)展，最后再加上邊緣節(jié)點(diǎn)形成完整的簇，構(gòu)建結(jié)構(gòu)譜上的所有層，由此構(gòu)成關(guān)系數(shù)據(jù)的層次聚類結(jié)果。

1)Ego節(jié)點(diǎn)的結(jié)構(gòu)標(biāo)識(shí)

以Ego節(jié)點(diǎn)按時(shí)間序列找到子圖，子圖如圖4所列舉由結(jié)構(gòu)最低的開始向上，標(biāo)識(shí)Ego節(jié)點(diǎn)的最高結(jié)構(gòu)StrID。因?yàn)閳D序列中的子圖為輸入輸出關(guān)系，所以如果Ego節(jié)點(diǎn)不屬于低一層次的結(jié)構(gòu)，那么肯定不會(huì)存在高一層次的結(jié)構(gòu)，在程序中可以遞歸的調(diào)用查詢結(jié)果。對(duì)于數(shù)據(jù)集節(jié)點(diǎn)得到的最高結(jié)構(gòu)的最大值，為層次結(jié)構(gòu)的最大值。

2)同層簇的識(shí)別。

標(biāo)識(shí)完所有節(jié)點(diǎn)的最高結(jié)構(gòu)后，基于功能和結(jié)構(gòu)距離做社團(tuán)的識(shí)別，采用的算法同DBSCAN算法，細(xì)節(jié)上有一些差別，闡述如下：

(1)輸入中要求加入核心節(jié)點(diǎn)結(jié)構(gòu)值(Str)，Eps=1，MinPts=3

(2)根據(jù)核心節(jié)點(diǎn)結(jié)構(gòu)值得到備選核心節(jié)點(diǎn)集Ccan={q∈D|StrID=Str}及相關(guān)節(jié)點(diǎn)集Neg={p∈D|H(p,q)≤1，q∈Ccan}

(3)根據(jù)鄰域閾值在備選核心節(jié)點(diǎn)中找到核心節(jié)點(diǎn)Ccore={q∈Ccan||NEps(q)|≥MinPts}

(4)根據(jù)定義3得到最大核心節(jié)點(diǎn)集Cmax_core={p∈Cli|S(p,q)=1;q∈Cli;p,q∈Ccore}

(5)再根據(jù)定義4得到最大傳播物連接集Cconn={s∈Cli|S(s,q)=1;q∈Cli;q∈Ccore}

3)層次的發(fā)現(xiàn)

改變核心節(jié)點(diǎn)結(jié)構(gòu)值(Str)，再次調(diào)用2)，得到對(duì)應(yīng)于結(jié)構(gòu)值(Str)的簇，直到遍歷所有結(jié)構(gòu)值。

4 算法應(yīng)用

數(shù)據(jù)來自于中國復(fù)雜網(wǎng)絡(luò)協(xié)會(huì)，我們首先列出從該學(xué)會(huì)成立(2005)至今所有委員名單及其單位，然后在中國知網(wǎng)找出他們發(fā)表的文章，列出他們的合作者及單位，在知網(wǎng)里找出這些合作者發(fā)表的文章，為消除重名用單位做另一搜索關(guān)鍵字，共獲得15 835位作者、18 205篇文章及36 720個(gè)關(guān)鍵詞?；谝陨蠑?shù)據(jù)可以構(gòu)造一個(gè)科研人員合作網(wǎng)，然后基于科研人員合作網(wǎng)的層級(jí)結(jié)構(gòu)對(duì)層級(jí)結(jié)構(gòu)上的關(guān)鍵詞擴(kuò)散特征進(jìn)行描述，從而找出層次對(duì)關(guān)鍵詞擴(kuò)散的影響。在構(gòu)建人員合作網(wǎng)時(shí)，本文僅將第一作者與其他合作者進(jìn)行連邊，因?yàn)槲覀冋J(rèn)為第一作者可以把關(guān)鍵字推向其他合作者，該網(wǎng)絡(luò)為有向網(wǎng)絡(luò)。

表4 科研人員合作網(wǎng)絡(luò)的層級(jí)特征

NCmax_community為最大社團(tuán)核心節(jié)點(diǎn)數(shù)；NCsec_community為次大社團(tuán)核心節(jié)點(diǎn)數(shù)；Nmax_community為最大社團(tuán)節(jié)點(diǎn)數(shù)

從社團(tuán)結(jié)構(gòu)統(tǒng)計(jì)數(shù)據(jù)可以看出第二層網(wǎng)絡(luò)中出現(xiàn)一個(gè)極大連接社團(tuán)，核心節(jié)點(diǎn)數(shù)為599，社團(tuán)成員數(shù)為2 154占到總?cè)藬?shù)的84%，如果不對(duì)社團(tuán)進(jìn)行分層，無法在一個(gè)均勻大小社團(tuán)結(jié)構(gòu)(層次1)的網(wǎng)絡(luò)中發(fā)現(xiàn)有極大連接的社團(tuán)結(jié)構(gòu)。

接著是在不同層的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)它對(duì)于關(guān)鍵詞傳播的影響，基于關(guān)鍵詞出現(xiàn)頻率及出現(xiàn)的時(shí)間特征對(duì)關(guān)鍵詞進(jìn)行分類：

圖6 關(guān)鍵詞特征劃分

分類標(biāo)準(zhǔn)中跳躍是指關(guān)鍵詞出現(xiàn)的年份不連續(xù)，不連續(xù)的時(shí)間大于3年?；陉P(guān)鍵詞的詞頻選出出現(xiàn)頻率高于20的詞共210個(gè)，然后在谷歌學(xué)術(shù)中找到這些詞出現(xiàn)的次數(shù)。簡(jiǎn)單的對(duì)這210個(gè)詞在不同層關(guān)聯(lián)的作者數(shù)進(jìn)行統(tǒng)計(jì)(關(guān)聯(lián)作者表示作者被該關(guān)鍵詞影響到)，210個(gè)詞中共有162個(gè)詞在層次2的社團(tuán)中出現(xiàn)的次數(shù)大于等于層次1的次數(shù)，占到77%。再按谷歌學(xué)術(shù)出現(xiàn)的次數(shù)找出<100 000的關(guān)鍵詞發(fā)現(xiàn)這一指標(biāo)提高到79%。從這一指標(biāo)我們可以推斷出層次2的社團(tuán)結(jié)構(gòu)對(duì)沒有大眾傳播效果詞的影響效果更大，這與Watts在2012年發(fā)現(xiàn)的在線傳播結(jié)構(gòu)存在不同[15]，在復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)傳播中人際傳播的作用大于大眾媒體。接著找出關(guān)鍵詞中有1次以上跳躍的詞41個(gè)，發(fā)現(xiàn)這一指標(biāo)再次提升到80%。關(guān)鍵詞在我們所選的樣本中沒有年年出現(xiàn)，在一定程度上表示不流行，但在4年后又能在社團(tuán)中出現(xiàn)表示社會(huì)關(guān)系對(duì)這些詞的傳播有非常重要的作用。運(yùn)用層次關(guān)系數(shù)據(jù)聚類算法從實(shí)際數(shù)據(jù)得出的新發(fā)現(xiàn)1)分層后的社團(tuán)結(jié)構(gòu)會(huì)呈現(xiàn)異質(zhì)性，在一個(gè)均勻分布社團(tuán)大小的一層社團(tuán)結(jié)構(gòu)中在分層后可能會(huì)出現(xiàn)不同的社團(tuán)結(jié)構(gòu)；2)分層的社團(tuán)結(jié)構(gòu)在傳播物的擴(kuò)散解釋上要強(qiáng)于不分層的，本文的數(shù)據(jù)集中，層次2對(duì)于關(guān)鍵詞的擴(kuò)散起到重要作用；3)復(fù)雜網(wǎng)絡(luò)研究學(xué)者通過建立互惠關(guān)系來實(shí)現(xiàn)研究工作的擴(kuò)展，更加穩(wěn)定的三角形關(guān)系和差異化關(guān)系在本次研究中的作用不大。

5 結(jié)論

通過對(duì)以往聚類算法的歸納我們發(fā)現(xiàn)了關(guān)系數(shù)據(jù)不同于空間數(shù)據(jù)的非對(duì)稱性特點(diǎn)，就這一特點(diǎn)在距離度量上使得傳統(tǒng)的度量方法變得不可壓縮，為恢復(fù)度量的可壓縮性本文借鑒迭代系統(tǒng)的輸入輸出關(guān)系用H氏距離來描述關(guān)系距離的非對(duì)稱性，通過這種非對(duì)稱的包含關(guān)系來完成聚類算法中尺度上卷，最后通過一個(gè)實(shí)例來描述這一改變的有效性，通過算法的設(shè)計(jì)我們得到以下結(jié)論:

1)對(duì)關(guān)系數(shù)據(jù)的社團(tuán)劃分需要區(qū)分加和算子和并算子，因?yàn)閭鹘y(tǒng)算法是基于距離的，加和與并算子是一致的，但在關(guān)系數(shù)據(jù)中并非如此。

2)不同層次的社團(tuán)結(jié)構(gòu)對(duì)不同傳播物的擴(kuò)散會(huì)產(chǎn)生不同的影響。

3)空間上的并算子與時(shí)間維度上的擴(kuò)展相對(duì)應(yīng)，籍此我們可以通過時(shí)間和空間的對(duì)應(yīng)關(guān)系在時(shí)間維度上對(duì)群體行為做預(yù)測(cè)。

對(duì)于算法的應(yīng)用，本文僅發(fā)現(xiàn)互惠關(guān)系的作用但等級(jí)更高的穩(wěn)定三角形關(guān)系，差異化關(guān)系及雙三角形關(guān)系的作用沒有得到驗(yàn)證，今后可以用更難于傳播的傳播物來驗(yàn)證這些結(jié)構(gòu)的作用。