重疊社區(qū)與強(qiáng)弱邊關(guān)系研究

楊紅培 劉 萍 王 威

1(許昌電氣職業(yè)學(xué)院 河南 許昌 461000) 2(河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453000)

重疊社區(qū)與強(qiáng)弱邊關(guān)系研究

楊紅培1劉 萍2王 威2

1(許昌電氣職業(yè)學(xué)院 河南 許昌 461000)2(河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453000)

近年來(lái)重疊區(qū)域結(jié)構(gòu)的發(fā)現(xiàn)使得相對(duì)獨(dú)立的社區(qū)關(guān)系變得日趨復(fù)雜化。對(duì)于社區(qū)內(nèi)部以及社區(qū)之間的用戶關(guān)系也變得更加多樣性，評(píng)估用戶關(guān)系的緊密程度以及用戶關(guān)系對(duì)信息交流和傳播的促進(jìn)作用已成為目前研究的熱點(diǎn)。重疊節(jié)點(diǎn)由于自身的特殊性，重疊節(jié)點(diǎn)之間以及它們與非重疊節(jié)點(diǎn)之間的關(guān)系很難用傳統(tǒng)的強(qiáng)弱關(guān)系進(jìn)行刻畫。針對(duì)此問(wèn)題提出重疊系數(shù)指標(biāo)，以數(shù)值形式量化節(jié)點(diǎn)之間的強(qiáng)弱關(guān)系。在此基礎(chǔ)上，對(duì)節(jié)點(diǎn)度進(jìn)行重新定義并分析重疊節(jié)點(diǎn)與強(qiáng)弱邊之間的關(guān)系。同時(shí)對(duì)重疊與非重疊社區(qū)結(jié)構(gòu)中強(qiáng)弱邊的數(shù)量進(jìn)行了比較分析，發(fā)現(xiàn)在重疊社區(qū)結(jié)構(gòu)中節(jié)點(diǎn)之間隱藏著豐富的隱性關(guān)系。最后在對(duì)重疊社區(qū)結(jié)構(gòu)中弱關(guān)系的深入研究發(fā)現(xiàn)，移除弱邊的過(guò)程也是重疊社區(qū)結(jié)構(gòu)向非重疊社區(qū)結(jié)構(gòu)轉(zhuǎn)化的過(guò)程。結(jié)果表明重疊結(jié)構(gòu)與非重疊結(jié)構(gòu)并不是相互獨(dú)立，而是存在著密切聯(lián)系的，即非重疊社區(qū)結(jié)構(gòu)是重疊社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)中的一個(gè)特例。

重疊社區(qū)結(jié)構(gòu) 重疊節(jié)點(diǎn) 重疊系數(shù)指標(biāo) 強(qiáng)弱關(guān)系

0 引 言

社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)有助于人們了解網(wǎng)絡(luò)中的人際關(guān)系，探索網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)的變化情況和預(yù)測(cè)未來(lái)社交網(wǎng)絡(luò)的發(fā)展趨勢(shì)。社交網(wǎng)絡(luò)中是強(qiáng)關(guān)系重要還是弱關(guān)系重要一直是研究的熱點(diǎn)。關(guān)于強(qiáng)弱關(guān)系的評(píng)價(jià)方法也不斷被提出，學(xué)者們分別從社交網(wǎng)絡(luò)結(jié)構(gòu)的不同方面對(duì)強(qiáng)弱關(guān)系進(jìn)行了研究，認(rèn)為弱關(guān)系在社交網(wǎng)絡(luò)中占據(jù)著重要的作用[1]。

隨著社區(qū)發(fā)現(xiàn)算法的日益成熟，社交網(wǎng)絡(luò)中備受關(guān)注的問(wèn)題已經(jīng)從如何發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)轉(zhuǎn)變?yōu)樵鯓雍侠碛行У卦u(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)系的重要性[2-4]。在社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的基礎(chǔ)上，對(duì)用戶節(jié)點(diǎn)之間強(qiáng)弱關(guān)系進(jìn)行判別，并研究他們?cè)谛畔U(kuò)散中的作用，具有理論與現(xiàn)實(shí)意義[5]。Pasquale等[6]認(rèn)為弱關(guān)系是遠(yuǎn)距離傳遞信息的有效手段，強(qiáng)調(diào)了弱關(guān)系的作用和重要性。在以社區(qū)結(jié)構(gòu)為基礎(chǔ)的社交網(wǎng)絡(luò)，人們普遍認(rèn)為強(qiáng)關(guān)系維持了社區(qū)內(nèi)部節(jié)點(diǎn)之間的信息交流，弱關(guān)系對(duì)社區(qū)之間節(jié)點(diǎn)交流提供了保障。

重疊社區(qū)的發(fā)現(xiàn)是對(duì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的進(jìn)一步延伸，它在一定層次上打破了社區(qū)個(gè)體的封閉性，使得網(wǎng)絡(luò)中的社區(qū)不再孤立，保證了社區(qū)之間信息交流的暢通。重疊社區(qū)中的節(jié)點(diǎn)從屬于兩個(gè)或兩個(gè)以上的社區(qū)，因其自身的特殊性，重疊節(jié)點(diǎn)之間、重疊節(jié)點(diǎn)與非重疊節(jié)點(diǎn)之間的關(guān)系很難用強(qiáng)和弱去定義。如圖1所示，節(jié)點(diǎn)4和節(jié)點(diǎn)7屬于重疊節(jié)點(diǎn)，根據(jù)重疊節(jié)點(diǎn)歸屬社區(qū)的不同，有以下兩種情況：(1) 當(dāng)把節(jié)點(diǎn)4歸屬于社區(qū)1時(shí)，那么節(jié)點(diǎn)4與節(jié)點(diǎn)2、3的關(guān)系為強(qiáng)關(guān)系，與節(jié)點(diǎn)5、7的關(guān)系變?yōu)槿蹶P(guān)系；同理，當(dāng)把節(jié)點(diǎn)4歸屬于社區(qū)2時(shí)，那么節(jié)點(diǎn)4與節(jié)點(diǎn)2、3的關(guān)系為弱關(guān)系，與節(jié)點(diǎn)5、7的關(guān)系變?yōu)閺?qiáng)關(guān)系。當(dāng)節(jié)點(diǎn)4為重疊節(jié)點(diǎn)時(shí)(既屬于社區(qū)1又屬于社區(qū)2)，很難用傳統(tǒng)的強(qiáng)弱邊關(guān)系的定義來(lái)刻畫它與節(jié)點(diǎn)2、3、5的關(guān)系。(2) 如果只針對(duì)重疊社區(qū)而言，基于節(jié)點(diǎn)4與節(jié)點(diǎn)7的關(guān)系又可以分為兩種情況，即①同為重疊社區(qū)，當(dāng)兩個(gè)節(jié)點(diǎn)同屬于一個(gè)社區(qū)時(shí)，它們之間的關(guān)系為強(qiáng)關(guān)系；②雖然同在重疊社區(qū)中，但兩個(gè)節(jié)點(diǎn)又屬于兩個(gè)不同社區(qū)，使得它們之間的強(qiáng)弱關(guān)系也很難下定論。

圖1 重疊社區(qū)結(jié)構(gòu)圖

針對(duì)該問(wèn)題，本文提出了重疊系數(shù)指標(biāo)，在重疊社區(qū)結(jié)構(gòu)的基礎(chǔ)上，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)關(guān)系以權(quán)值的形式重新定義，使得強(qiáng)弱關(guān)系可量化。本文的主要貢獻(xiàn)如下：

(1) 基于四個(gè)數(shù)據(jù)集，在劃分重疊社區(qū)結(jié)構(gòu)的基礎(chǔ)上，提出了重疊系數(shù)指標(biāo)，以此為基準(zhǔn)，判斷重疊社區(qū)結(jié)構(gòu)下節(jié)點(diǎn)之間的強(qiáng)弱關(guān)系。

(2) 對(duì)節(jié)點(diǎn)度進(jìn)行了重新定義。在具有重疊區(qū)域結(jié)構(gòu)的網(wǎng)絡(luò)中，根據(jù)重疊社區(qū)系數(shù)指標(biāo)，對(duì)節(jié)點(diǎn)之間的權(quán)值進(jìn)行重新定義，構(gòu)建重疊社區(qū)結(jié)構(gòu)關(guān)系網(wǎng)絡(luò)，挖掘節(jié)點(diǎn)之間隱藏的社會(huì)關(guān)系。

(3) 分析了重疊節(jié)點(diǎn)與強(qiáng)弱邊之間的關(guān)系，發(fā)現(xiàn)重疊節(jié)點(diǎn)是連接社區(qū)內(nèi)部與外部進(jìn)行通信的橋梁。

(4) 對(duì)重疊與非重疊兩種網(wǎng)絡(luò)結(jié)構(gòu)下的強(qiáng)弱邊數(shù)量進(jìn)行對(duì)比，發(fā)現(xiàn)在重疊社區(qū)結(jié)構(gòu)中強(qiáng)弱邊數(shù)量要明顯高于非重疊社區(qū)結(jié)構(gòu)下，進(jìn)一步闡述了重疊社區(qū)結(jié)構(gòu)下隱藏的節(jié)點(diǎn)關(guān)系。

1 相關(guān)工作

隨著網(wǎng)絡(luò)技術(shù)的進(jìn)步，網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的研究成為越來(lái)越重要的一個(gè)熱點(diǎn)問(wèn)題，社區(qū)發(fā)現(xiàn)和檢測(cè)算法獲得較快發(fā)展并且日益成熟。

2002年，Girvan等提出了GN算法，是一種經(jīng)典的社區(qū)發(fā)現(xiàn)算法。該算法屬于分裂型，在算法執(zhí)行過(guò)程中計(jì)算所有邊的邊介數(shù)，并依次刪除邊介數(shù)最大的邊，最終實(shí)現(xiàn)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的劃分，同時(shí)這種方法啟發(fā)了人們對(duì)網(wǎng)絡(luò)社區(qū)研究的思路[7]。2004年，他們又提出了網(wǎng)絡(luò)劃分指標(biāo)函數(shù)——模塊度Q，模塊度值的大小主要取決于網(wǎng)絡(luò)中節(jié)點(diǎn)所屬社區(qū)的分配情況，對(duì)于衡量社區(qū)劃分的精確度是一個(gè)重要參考指標(biāo)[8]。2007年，Zhang等[9]以特征矩陣作為原始輸入，提出了NMF算法，檢測(cè)到網(wǎng)絡(luò)中存在著一個(gè)節(jié)點(diǎn)可能同時(shí)屬于多個(gè)社區(qū)的情況。2011年，Psorakis等[10]在NMF算法的基礎(chǔ)上，提出了基于貝葉斯的NMF算法。從網(wǎng)絡(luò)中提取出具有重疊區(qū)域的模塊，并且通過(guò)利用模塊度量化指標(biāo)對(duì)所劃分的社區(qū)精確程度進(jìn)行合理性評(píng)價(jià)，最終實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)社區(qū)中重疊結(jié)構(gòu)的劃分。2014年，李玉翔等[11]在BNMF算法的基礎(chǔ)上進(jìn)一步改進(jìn)，通過(guò)對(duì)NMF算法的研究分析，對(duì)原始輸入的特征矩陣進(jìn)行相關(guān)擴(kuò)展性處理，可以有效地統(tǒng)計(jì)出網(wǎng)絡(luò)中社區(qū)數(shù)目。并在此基礎(chǔ)上利用節(jié)點(diǎn)與社區(qū)之間的所屬關(guān)系，實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的劃分。2006年，Shi等深入研究了關(guān)系網(wǎng)絡(luò)的連通性，并在此基礎(chǔ)上，發(fā)現(xiàn)在健壯的社交網(wǎng)絡(luò)中存在著薄弱環(huán)節(jié)。這些薄弱環(huán)節(jié)的存在延長(zhǎng)了網(wǎng)絡(luò)中的平均最短路徑，通過(guò)對(duì)網(wǎng)絡(luò)中信息傳遞關(guān)系的研究，發(fā)現(xiàn)刪除網(wǎng)絡(luò)中的弱連接會(huì)隔離網(wǎng)絡(luò)中絕大多數(shù)的節(jié)點(diǎn)[1]。2007年，Onnela等[12]提出了網(wǎng)絡(luò)結(jié)構(gòu)的概念，深入研究了移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)關(guān)系強(qiáng)度之間的聯(lián)系，認(rèn)為網(wǎng)絡(luò)完整性的保持需要以牢固的關(guān)系為基礎(chǔ)，提出在通信網(wǎng)絡(luò)中移除弱關(guān)系的結(jié)果可能會(huì)導(dǎo)致在一個(gè)階段上的網(wǎng)絡(luò)崩潰。雖然緊密聯(lián)系的強(qiáng)關(guān)系被去除對(duì)于網(wǎng)絡(luò)信息傳輸影響不大，但是會(huì)影響到網(wǎng)絡(luò)信息傳輸?shù)恼w完整性。Yang等在2012年-2013年提出一個(gè)基于集群關(guān)系模型的社區(qū)檢測(cè)算法用于檢測(cè)重疊社區(qū)的密度，較為精確地發(fā)現(xiàn)網(wǎng)絡(luò)中真實(shí)的重疊社區(qū)結(jié)構(gòu)。對(duì)網(wǎng)絡(luò)重疊社區(qū)內(nèi)外部節(jié)點(diǎn)之間的緊密關(guān)系進(jìn)行了研究，根據(jù)重疊社區(qū)中節(jié)點(diǎn)關(guān)系的密集程度，重疊社區(qū)可進(jìn)一步劃分為稀疏和稠密重疊社區(qū)兩種類型[13-14]。2014年，Pasquale等[6]提出了一種只依賴于社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的強(qiáng)弱關(guān)系定義方法，找到適用于Facebook的全新弱關(guān)系定義。通過(guò)研究強(qiáng)弱關(guān)系對(duì)信息傳播過(guò)程的影響，強(qiáng)調(diào)了弱關(guān)系的作用和重要性。在社區(qū)發(fā)現(xiàn)的基礎(chǔ)上，關(guān)于強(qiáng)弱關(guān)系在整個(gè)大型網(wǎng)絡(luò)中所起到的作用一直是研究人員重點(diǎn)關(guān)注的一個(gè)問(wèn)題。

隨著重疊區(qū)域結(jié)構(gòu)的發(fā)現(xiàn)[15]使得相對(duì)獨(dú)立的社區(qū)關(guān)系復(fù)雜化，對(duì)于社區(qū)內(nèi)部以及社區(qū)之間的用戶關(guān)系也變得更加多樣性，用戶之間的強(qiáng)弱關(guān)系也變得愈加不確定。人們?cè)趶?fù)雜網(wǎng)絡(luò)中判斷強(qiáng)弱關(guān)系時(shí)，沒(méi)有更多地考慮到重疊社區(qū)結(jié)構(gòu)的特性，由于重疊社區(qū)的普遍存在，重疊社區(qū)與非重疊社區(qū)中節(jié)點(diǎn)之間的強(qiáng)弱關(guān)系情況難以定義。針對(duì)該問(wèn)題，本文在發(fā)現(xiàn)重疊社區(qū)的基礎(chǔ)上提出了重疊社區(qū)指數(shù)作為劃分節(jié)點(diǎn)關(guān)系的一個(gè)參考指標(biāo)。

2 重疊系數(shù)指標(biāo)

本節(jié)中提出了重疊系數(shù)指標(biāo)作為評(píng)價(jià)節(jié)點(diǎn)強(qiáng)弱關(guān)系的一個(gè)參考指標(biāo)，即從社區(qū)與重疊社區(qū)相結(jié)合的角度來(lái)觀察節(jié)點(diǎn)之間的關(guān)系，以關(guān)系權(quán)值的方式表示節(jié)點(diǎn)之間的關(guān)系強(qiáng)度，可以使得復(fù)雜的網(wǎng)絡(luò)關(guān)系簡(jiǎn)單化。重疊系數(shù)如下式：

(1)

式中：Ei和Ej表示節(jié)點(diǎn)i和節(jié)點(diǎn)j所歸屬的社區(qū)，Ei∩Ej表示節(jié)點(diǎn)i、j共同擁有的社區(qū)數(shù)量，Ei∪Ej表示節(jié)點(diǎn)i、j所屬社區(qū)的并集。Oij表示節(jié)點(diǎn)i與j之間的關(guān)系權(quán)值。

圖2 重疊系數(shù)指標(biāo)計(jì)算圖例

重疊系數(shù)指標(biāo)的提出，以權(quán)值的方式解釋了網(wǎng)絡(luò)中的復(fù)雜關(guān)系，使其關(guān)系可量化。同時(shí)以關(guān)系權(quán)值的表示形式解決了第1節(jié)提到的2種難以界定的節(jié)點(diǎn)關(guān)系。通過(guò)對(duì)節(jié)點(diǎn)關(guān)系的數(shù)值化處理有利于把復(fù)雜的網(wǎng)絡(luò)關(guān)系歸一化，在一定程度上簡(jiǎn)化了網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜度，以數(shù)據(jù)標(biāo)識(shí)的方式增加了人們的認(rèn)知度。

圖3展示了4個(gè)數(shù)據(jù)集以重疊系數(shù)賦予節(jié)點(diǎn)之間新的權(quán)值所生成的鄰接矩陣(這里截取部分行、列)。從圖中可以看到，節(jié)點(diǎn)之間的關(guān)系權(quán)值由0到1，同時(shí)也由簡(jiǎn)單到復(fù)雜再回歸到簡(jiǎn)單的一個(gè)過(guò)程。

圖3 四個(gè)數(shù)據(jù)集新的權(quán)值鄰接矩陣圖

3 節(jié)點(diǎn)度

在圖論中，節(jié)點(diǎn)度是指和當(dāng)前節(jié)點(diǎn)相連接邊的總條數(shù)，節(jié)點(diǎn)度的大小可以直接反應(yīng)出當(dāng)前的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的重要程度，便于對(duì)節(jié)點(diǎn)的重要性做出一個(gè)初步的評(píng)斷。根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接情況，建立相應(yīng)的鄰接矩陣，可以快速地統(tǒng)計(jì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度。

(2)

式中：xij表示鄰接矩陣W的第i行第j列的元素權(quán)值，Di表示當(dāng)前節(jié)點(diǎn)i的節(jié)點(diǎn)度。由于在圖論中，節(jié)點(diǎn)圖可以劃分有向圖和無(wú)向圖，對(duì)于有向圖來(lái)說(shuō)，節(jié)點(diǎn)度又可以劃分為入度(表示網(wǎng)絡(luò)圖中指向該節(jié)點(diǎn)的邊的集合)和出度(表示從該節(jié)點(diǎn)出發(fā)的邊的集合)。

圖4展示是6個(gè)節(jié)點(diǎn)形成的有向拓?fù)鋱D，以節(jié)點(diǎn)5為例，來(lái)計(jì)算出節(jié)點(diǎn)5的出度和入度如下：

(3)

(4)

圖4 有向拓?fù)鋱D

圖4中以節(jié)點(diǎn)5為出發(fā)點(diǎn)，因?yàn)榘l(fā)出的邊分別與節(jié)點(diǎn)1、2、4相連，所以節(jié)點(diǎn)5的出度為3，相應(yīng)計(jì)算得到它的入度為2。

對(duì)于無(wú)向圖來(lái)說(shuō)，節(jié)點(diǎn)度的統(tǒng)計(jì)要簡(jiǎn)單得多，以當(dāng)前節(jié)點(diǎn)是否有連接邊為標(biāo)準(zhǔn)，在統(tǒng)計(jì)過(guò)程中進(jìn)行累加，最后得到無(wú)向圖中節(jié)點(diǎn)度，運(yùn)算如式(1)。

無(wú)論是有向圖還是無(wú)向圖，如果節(jié)點(diǎn)的節(jié)點(diǎn)度越大，就表明該節(jié)點(diǎn)周圍密度較大，同時(shí)也說(shuō)明了該節(jié)點(diǎn)在網(wǎng)絡(luò)局部中所起的作用越重要[15]。對(duì)于網(wǎng)絡(luò)中信息流動(dòng)來(lái)說(shuō)，節(jié)點(diǎn)之間如果有連接邊，表明信息在這兩個(gè)節(jié)點(diǎn)之間是可以傳輸信息，連接邊越多，信息傳遞時(shí)穩(wěn)定性越好，也可以說(shuō)明當(dāng)前節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中的信息擴(kuò)散影響就越大，對(duì)網(wǎng)絡(luò)信息傳輸?shù)臅惩ㄐ跃驮接斜Ｕ稀?/p>

從關(guān)系權(quán)值的角度進(jìn)一步分析發(fā)現(xiàn)，在原始的大型網(wǎng)絡(luò)中，根據(jù)4個(gè)數(shù)據(jù)集中節(jié)點(diǎn)的原始關(guān)系生成由0和1組成的鄰接矩陣，0、1表示節(jié)點(diǎn)之間關(guān)系的權(quán)值。這種權(quán)值的表示方法具有“二分性”，鄰接矩陣展示出了節(jié)點(diǎn)之間的絕對(duì)關(guān)系，把用戶分為絕對(duì)的聯(lián)系和無(wú)聯(lián)系。然而在真實(shí)的世界中絕對(duì)的事情大多是不存在的，因?yàn)樵诂F(xiàn)實(shí)世界中很多事物之間看似沒(méi)有任何關(guān)系，但其中卻總是隱藏著或多或少的聯(lián)系。隨著重疊社區(qū)結(jié)構(gòu)的出現(xiàn)，網(wǎng)絡(luò)中所隱藏的關(guān)系逐漸被暴露出來(lái)，網(wǎng)絡(luò)結(jié)構(gòu)變得越來(lái)越復(fù)雜。

第2節(jié)提出的重疊系數(shù)指標(biāo)，就是在基于重疊結(jié)構(gòu)的社區(qū)中，根據(jù)重疊社區(qū)的特殊性，在社區(qū)的層次上重新定義節(jié)點(diǎn)之間的關(guān)系權(quán)值。本節(jié)以統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度為基礎(chǔ)，對(duì)非重疊和重疊社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)進(jìn)行比較。

(5)

式中：xij表示節(jié)點(diǎn)之間的關(guān)系權(quán)值。

圖5、圖6為基于PCA算法和NMF算法的兩種數(shù)值比較。其中橫坐標(biāo)表示節(jié)點(diǎn)ID，首先對(duì)非重疊社區(qū)結(jié)構(gòu)中所有節(jié)點(diǎn)度進(jìn)行升序排列，并以此序列作為橫坐標(biāo)；縱坐標(biāo)表示節(jié)點(diǎn)度。

圖5 基于PCA算法節(jié)點(diǎn)度對(duì)比圖

圖6 基于NMF算法節(jié)點(diǎn)度對(duì)比圖

在具有重疊區(qū)域結(jié)構(gòu)的網(wǎng)絡(luò)中，根據(jù)重疊社區(qū)系數(shù)指標(biāo)，對(duì)節(jié)點(diǎn)之間的權(quán)值進(jìn)行重新定義。構(gòu)建重疊社區(qū)結(jié)構(gòu)關(guān)系網(wǎng)絡(luò)，按照節(jié)點(diǎn)度的統(tǒng)計(jì)方式計(jì)算出在重疊社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的數(shù)值。

初始網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系權(quán)重為0或1，根據(jù)節(jié)點(diǎn)關(guān)系建立的0、1鄰接矩陣，每一行元素值之和就是與當(dāng)前節(jié)點(diǎn)相連接的所有節(jié)點(diǎn)的邊權(quán)值總和，據(jù)此得到當(dāng)前節(jié)點(diǎn)i節(jié)點(diǎn)度。根據(jù)節(jié)點(diǎn)度的大小對(duì)當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行升序排列，如圖5和圖6中逐漸上升的曲線展示了對(duì)原始網(wǎng)絡(luò)節(jié)點(diǎn)的權(quán)值排序結(jié)果。

在原始網(wǎng)絡(luò)中本來(lái)沒(méi)有直接關(guān)系的兩個(gè)節(jié)點(diǎn)，根據(jù)重疊系數(shù)指標(biāo)重新給節(jié)點(diǎn)關(guān)系賦以權(quán)值使得節(jié)點(diǎn)之間所隱藏的關(guān)系顯露出來(lái)。此時(shí)部分節(jié)點(diǎn)之間邊的權(quán)值已不再是0，說(shuō)明這些節(jié)點(diǎn)之間建立起來(lái)了或多或少的聯(lián)系。根據(jù)兩種權(quán)值情況下的實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在重疊社區(qū)結(jié)構(gòu)情況下節(jié)點(diǎn)的數(shù)值普遍較高，這是因?yàn)樵诰哂兄丿B社區(qū)的社交網(wǎng)絡(luò)中，使得節(jié)點(diǎn)之間的潛在聯(lián)系顯現(xiàn)出來(lái)。此時(shí)節(jié)點(diǎn)之間的關(guān)系不在具有絕對(duì)的二分性，而更多地體現(xiàn)了現(xiàn)實(shí)世界中關(guān)系的普遍性。

從圖5與圖6中的波折曲線可以看到，在具有重疊區(qū)域結(jié)構(gòu)的網(wǎng)絡(luò)中，絕大多數(shù)節(jié)點(diǎn)度要大于原始網(wǎng)絡(luò)節(jié)點(diǎn)度。實(shí)驗(yàn)結(jié)果表明：① 重疊社區(qū)的存在明顯地改變了節(jié)點(diǎn)關(guān)系的判斷標(biāo)準(zhǔn)；② 重疊結(jié)構(gòu)的存在挖掘出了節(jié)點(diǎn)之間隱藏的關(guān)系，加強(qiáng)了節(jié)點(diǎn)之間的聯(lián)系，完善了復(fù)雜網(wǎng)絡(luò)的關(guān)系結(jié)構(gòu)，同時(shí)也使得節(jié)點(diǎn)之間所構(gòu)成的無(wú)向圖更加緊密。

4 重疊節(jié)點(diǎn)與強(qiáng)弱邊之間的關(guān)系

重疊節(jié)點(diǎn)的發(fā)現(xiàn)與存在有著它獨(dú)特的一面，它處于多個(gè)社區(qū)相互重疊的區(qū)域，構(gòu)成了社區(qū)之間信息傳輸?shù)臉蛄骸Ｖ丿B社區(qū)的形成是由屬于多個(gè)社區(qū)的節(jié)點(diǎn)所組成的一片區(qū)域，使得在非重疊社區(qū)結(jié)構(gòu)中只能依靠弱連接維持信息傳遞的關(guān)系多了一層保護(hù)，確保了社區(qū)之間信息交流的暢通。

本節(jié)以重疊社區(qū)為基礎(chǔ)，以重疊節(jié)點(diǎn)為研究對(duì)象，按照一定比例依次把重疊節(jié)點(diǎn)移到非重疊社區(qū)中。同時(shí)應(yīng)用PCA和NMF兩種算法分別對(duì)相關(guān)節(jié)點(diǎn)的強(qiáng)弱邊進(jìn)行統(tǒng)計(jì)，并觀察網(wǎng)絡(luò)中的強(qiáng)弱邊數(shù)量的變化情況。

由PCA和NMF兩種算法統(tǒng)計(jì)結(jié)果得知，隨著重疊節(jié)點(diǎn)逐漸被移到非重疊社區(qū)，網(wǎng)絡(luò)中強(qiáng)弱邊的數(shù)量都在快速的增加，并最終隨著重疊社區(qū)中節(jié)點(diǎn)完全被移出，強(qiáng)弱邊的數(shù)量也達(dá)到峰值。同時(shí)也可以看到重疊節(jié)點(diǎn)逐漸被移出的過(guò)程，就是重疊社區(qū)結(jié)構(gòu)向非重疊社區(qū)結(jié)構(gòu)轉(zhuǎn)變的過(guò)程。當(dāng)重疊節(jié)點(diǎn)完全被移出時(shí)，非重疊社區(qū)結(jié)構(gòu)則正式形成，網(wǎng)絡(luò)中出現(xiàn)信息孤島現(xiàn)象。

進(jìn)一步分析可知，在開始階段，隨著重疊節(jié)點(diǎn)的遞減，強(qiáng)弱邊數(shù)量出現(xiàn)了一個(gè)明顯的上升趨勢(shì)，這說(shuō)明了重疊社區(qū)中的節(jié)點(diǎn)在強(qiáng)弱連接中起著一個(gè)非常大的支撐作用，重疊社區(qū)的出現(xiàn)為信息擴(kuò)散起到了巨大的保證作用。在后半段，弱邊數(shù)量的增長(zhǎng)速度要顯著高于強(qiáng)邊的數(shù)量，這說(shuō)明了隨著重疊節(jié)點(diǎn)的不斷減少，弱連接成為網(wǎng)絡(luò)關(guān)系中的主體，弱關(guān)系逐漸發(fā)揮出在信息傳輸方面的優(yōu)勢(shì)。

實(shí)驗(yàn)結(jié)果表明，重疊社區(qū)的出現(xiàn)削弱了社區(qū)內(nèi)部節(jié)點(diǎn)之間的強(qiáng)聯(lián)系，重疊部分構(gòu)成了社區(qū)內(nèi)外連接的橋梁，在社區(qū)內(nèi)部與外部之間起到一個(gè)過(guò)渡的作用。重疊區(qū)域結(jié)構(gòu)的存在使得社區(qū)內(nèi)部與外部的區(qū)分不是非常明顯，讓信息的傳輸交流不至于因?yàn)閺?qiáng)邊或弱邊的消失而導(dǎo)致中斷，在整個(gè)網(wǎng)絡(luò)社區(qū)的信息傳輸中起著重要的作用，有助于保證信息的暢通性。

5 兩種網(wǎng)絡(luò)拓?fù)渲袕?qiáng)弱邊數(shù)量比較

考慮到重疊社區(qū)結(jié)構(gòu)在社交網(wǎng)絡(luò)中的廣泛存在性，在討論強(qiáng)邊和弱邊時(shí)，就不能拋開重疊社區(qū)來(lái)主觀地區(qū)分強(qiáng)弱關(guān)系。針對(duì)該問(wèn)題，根據(jù)第2節(jié)提出的重疊系數(shù)指標(biāo)Oij，對(duì)重疊社區(qū)結(jié)構(gòu)中節(jié)點(diǎn)之間的復(fù)雜關(guān)系以權(quán)值的形式進(jìn)行定義，以數(shù)字的形式把復(fù)雜關(guān)系簡(jiǎn)單化。

考慮到節(jié)點(diǎn)之間關(guān)系的強(qiáng)弱由邊的權(quán)值來(lái)決定，定義閾值μ，把μ=0.5作為強(qiáng)弱關(guān)系變化的一個(gè)分界線，當(dāng)Oij>0.5時(shí)表示節(jié)點(diǎn)i和j之間為強(qiáng)連接，當(dāng)Oij≤0.5時(shí)表示節(jié)點(diǎn)i和j之間為弱連接。

基于PCA算法和NMF算法對(duì)重疊社區(qū)結(jié)構(gòu)和非重疊社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)中的強(qiáng)弱邊數(shù)量進(jìn)行統(tǒng)計(jì)，在重疊社區(qū)結(jié)構(gòu)中根據(jù)重疊系數(shù)指標(biāo)統(tǒng)計(jì)出的強(qiáng)弱邊數(shù)量要明顯高于非重疊社區(qū)結(jié)構(gòu)中的強(qiáng)弱邊數(shù)量。該現(xiàn)象充分說(shuō)明重疊系數(shù)指標(biāo)充分挖掘出了節(jié)點(diǎn)之間的潛在聯(lián)系，更深層地反映了真實(shí)世界網(wǎng)絡(luò)的內(nèi)部特征。

6 結(jié) 語(yǔ)

為解決重疊社區(qū)結(jié)構(gòu)下節(jié)點(diǎn)之間強(qiáng)弱關(guān)系的不確定性，本文提出了重疊系數(shù)指標(biāo)，給節(jié)點(diǎn)之間定義新的關(guān)系權(quán)值，并從節(jié)點(diǎn)度的角度對(duì)重疊社區(qū)結(jié)構(gòu)和非重疊社區(qū)結(jié)構(gòu)進(jìn)行實(shí)驗(yàn)對(duì)比。接著通過(guò)改變重疊社區(qū)中重疊節(jié)點(diǎn)的比例，觀察網(wǎng)絡(luò)中強(qiáng)弱邊的變化情況，來(lái)進(jìn)一步驗(yàn)證重疊社區(qū)的重要性。同時(shí)發(fā)現(xiàn)移除弱邊的過(guò)程也是重疊社區(qū)結(jié)構(gòu)向非重疊社區(qū)結(jié)構(gòu)轉(zhuǎn)化的過(guò)程。最后對(duì)兩種社區(qū)結(jié)構(gòu)中強(qiáng)弱邊數(shù)量進(jìn)行統(tǒng)計(jì)比較，發(fā)現(xiàn)在重疊社區(qū)結(jié)構(gòu)中節(jié)點(diǎn)之間隱藏著大量的關(guān)系，這些隱藏的關(guān)系對(duì)網(wǎng)絡(luò)信息交流的暢通起到了有力的保障。

[1] Shi X,Adamic L A,Strauss M J.Networks of strong ties[J].Physica A Statistical Mechanics & Its Applications,2006,378(1):33-47.

[2] Xie J,Kelley S,Szymanski B K.Overlapping community detection in networks:The state-of-the-art and comparative study[J].Acm computing surveys,2013,45(4):43.

[3] Yang J,Leskovec J.Overlapping Communities Explain Core-Periphery Organization of Networks[J].Proceedings of the IEEE,2014,102(12):1892-1902.

[4] Meligy A,Samak A H,Saad M E.A new Pre-processing Strategy for Improving Community Detection Algorithms[J].International Journal of Computer Applications,2015,119(16).

[5] Zhao J,Wu J,Xu K.Weak ties:Subtle role of information diffusion in online social networks[J].Physical Review E,2010,82(1):016105.

[6] Meo P D,Ferrara E,Fiumara G,et al.On Facebook,most ties are weak[J].Communications of the Acm,2012,57(11):78-84.

[7] Girvan M,Newman M E J.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.

[8] Newman M E J.Analysis of weighted networks[J].Physical Review E,2004,70(5):056131.

[9] Zhang S,Wang R S,Zhang X S.Uncovering fuzzy community structure in complex networks[J].Physical Review E,2007,76(4):70-80.

[10] Psorakis I,Roberts S,Ebden M,et al.Overlapping community detection using Bayesian non-negative matrix factorization[J].Physical Review E,2011,83(6):1509-1520.

[11] 李玉翔,李弼程,郭志剛.基于非負(fù)矩陣分解的網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)研究[J].系統(tǒng)仿真學(xué)報(bào),2014,26(3):643-649.

[12] Onnela J P,Saram?ki J, Hyv?nen J,et al.Structure and tie strengths in mobile communication networks[J].Proceedings of the National Academy of Sciences,2007,104(18):7332-7336.

[13] Yang J,Leskovec J.Community-Affiliation Graph Model for Overlapping Network Community Detection[C]//IEEE,International Conference on Data Mining.IEEE Computer Society,2012:1170-1175.

[14] Yang J,Leskovec J.Overlapping community detection at scale:a nonnegative matrix factorization approach[C]//Proceedings of the 6th ACM international conference on Web search and data mining,2013:587-596.

[15] 胡麗瑩,郭躬德,馬昌鳳.基于對(duì)稱非負(fù)矩陣分解的重疊社區(qū)發(fā)現(xiàn)方法[J].計(jì)算機(jī)應(yīng)用,2015,35(10):2742-2746.

RESEARCHONTHERELATIONSHIPBETWEENOVERLAPPINGAREAANDSTRONG-WEAKEDGES

Yang Hongpei1Liu Ping2Wang Wei2

1(XuchangElectricalVocationalCollege,Xuchang461000,Henan,China)2(CollegeofComputerandInformationEngineering,HenanNormalUniversity,Xinxiang453000,Henan,China)

In recent years, the discovery of overlapping regional structures has made the relatively independent community relations become more and more complicated and the user relationship between the community and the users also have been more diversity. It is a hot research to evaluate the tightness of user relations and the promotion of user relations to information exchange and communication. Overlapping nodes the overlap between the nodes and their relations with non-overlapping between nodes is hard to be described by using the traditional strength of the relationship, because of its particularity. In this thesis, we proposed overlap coefficient index between nodes in the strength of the relationship between the quantitative numerical forms to solve this problem. On this basis, we redefined the nodes and analysis of the relationship between the overlapping nodes and the strength of the edge, the number of overlapping and non-overlapping community structure of strong and weak edge. We found a hidden relationship between the hidden nodes in the rich overlapping community structure; finally found there are plentiful weak relationships in deep research of the overlapping community structure, in the process of remove the weak edge and overlapping community structure to process non overlapping community structure transformation. The results showed that the overlapping structure and non-overlapping structure were not mutually independent, but closely related, namely non overlapping community structure is a special case of overlapping community structure in the network.

Overlapping area structure Overlapping nodes Overlapping coefficient index Strong-weak relationship

2017-02-13。國(guó)家自然科學(xué)基金項(xiàng)目(U1404602)。楊紅培，講師，主研領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)通信，軟件教學(xué)及研究。劉萍，工程師。王威，碩士生。

TP3 TP393.0

A

10.3969/j.issn.1000-386x.2017.11.028