陳婉杰　盛益強(qiáng)

摘 要：針對(duì)現(xiàn)有的社區(qū)發(fā)現(xiàn)算法難以解決網(wǎng)絡(luò)的多維性問題的現(xiàn)象，提出一種基于網(wǎng)絡(luò)表示學(xué)習(xí)的非單一維度的社區(qū)發(fā)現(xiàn)算法。該算法從節(jié)點(diǎn)屬性特征和網(wǎng)絡(luò)結(jié)構(gòu)特征兩個(gè)維度考慮節(jié)點(diǎn)的差異性，首先根據(jù)節(jié)點(diǎn)屬性相似度計(jì)算得到節(jié)點(diǎn)轉(zhuǎn)移概率，結(jié)合小世界模型的六度分離理論設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)游走路徑的長度。依據(jù)轉(zhuǎn)移概率選擇節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，得到節(jié)點(diǎn)的游走路徑，然后用神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練節(jié)點(diǎn)的游走路徑得到節(jié)點(diǎn)的網(wǎng)絡(luò)特征向量，將節(jié)點(diǎn)網(wǎng)絡(luò)特征向量的相似度重置為節(jié)點(diǎn)連接邊的權(quán)重，在Louvain算法的基礎(chǔ)上完成社區(qū)劃分。最后，在Facebook和Giraffe兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，選用基于初始網(wǎng)絡(luò)結(jié)構(gòu)的Louvain算法和基于單一維度的社區(qū)發(fā)現(xiàn)算法作為對(duì)比算法。實(shí)驗(yàn)結(jié)果表明，在Giraffe數(shù)據(jù)集中，相比于Louvain算法，基于節(jié)點(diǎn)屬性的社區(qū)發(fā)現(xiàn)算法的模塊度指標(biāo)提升了2.7%，基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法的模塊度指標(biāo)提升了3.0%，提出的非單一維度的社區(qū)發(fā)現(xiàn)算法的模塊度指標(biāo)提升了3.7%。所提算法聚焦于網(wǎng)絡(luò)的多維性，有效提升了社區(qū)發(fā)現(xiàn)算法的模塊度。

關(guān)鍵詞：節(jié)點(diǎn)屬性;網(wǎng)絡(luò)結(jié)構(gòu);可擴(kuò)展性;社區(qū)發(fā)現(xiàn);網(wǎng)絡(luò)表示學(xué)習(xí);節(jié)點(diǎn)差異性

中圖分類號(hào)： TP391.4模式識(shí)別與裝置文獻(xiàn)標(biāo)志碼：A

Non-unidimensional community detection algorithm based on network representation learning

CHEN Wanjie1，2， SHENG Yiqiang 1，2*

（1. National Network New Media Engineering Research Center （Institute of Acoustics， Chinese Academy of Sciences）， Beijing 100190， China;

2. University of Chinese Academy of Sciences， Beijing 100049， China）

Abstract： Focusing on the issue that it is difficult for the existing community detection algorithms to solve the multidimensionality problem of the network， a non-unidimensional community detection algorithm based on network representation learning was proposed. The algorithm considered the difference of nodes from the two dimensions of node attribute feature and network structure feature. Firstly， the node transition probability was calculated according to the node attribute similarity. The length of the random walk path of the network node was set according to the six-degree separation theory of the small world model. After obtaining the walking path of the node by selecting its neighbor nodes according to the transition probability， the walking path of the node was trained by the neural network model to achieve the network feature vectors. The similarity of the network feature vectors of the node was reset as the weight of the connected edge， and the community partition was completed based on the Louvain algorithm. Finally， experiments were conducted on two datasets， Facebook and Giraffe with the Louvain algorithm based on the initial network structure and the unidimensional community detection algorithm as comparison algorithms. Experimental results show that on the Giraffe dataset， compared to the Louvain algorithm， the community detection algorithm based on the node attribute has the modularity increased by 2.7%， the community detection algorithm based on the network structure has the modularity increased by 3.0%， and the proposed non-unidimensional community detection algorithm has the modularity increased by 3.7%. The proposed algorithm focuses on the multidimensionality of the network and improves the modularity of the community detection algorithm effectively.

Key words： node attribute; network structure; extensibility; community detection; network representation learning; node difference

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展和移動(dòng)終端的普及應(yīng)用，復(fù)雜網(wǎng)絡(luò)在生活中的很多領(lǐng)域均得到了快速的發(fā)展，如社交媒體領(lǐng)域、學(xué)術(shù)信息領(lǐng)域以及生物學(xué)領(lǐng)域等。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，對(duì)復(fù)雜網(wǎng)絡(luò)的分析也越來越重要，在真實(shí)世界的復(fù)雜網(wǎng)絡(luò)中，通過網(wǎng)絡(luò)中個(gè)體構(gòu)成的社區(qū)來觀察網(wǎng)絡(luò)中節(jié)點(diǎn)的交互行為是清晰的，是全局化的，而通過個(gè)體行為觀察節(jié)點(diǎn)之間的交互則通常是帶有噪聲和片面的。復(fù)雜網(wǎng)絡(luò)中很多行為只能通過社區(qū)去發(fā)現(xiàn)，在個(gè)體層面難以觀察到，這是因?yàn)閭€(gè)體行為往往具有很強(qiáng)的波動(dòng)性，而社區(qū)行為一般相對(duì)穩(wěn)定，不易改變，因此對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)是有必要的。

識(shí)別復(fù)雜網(wǎng)絡(luò)中個(gè)體所在的社區(qū)不僅具有一定的理論價(jià)值，也有著廣泛的應(yīng)用前景。例如電商平臺(tái)通過識(shí)別出相似興趣類別的用戶社區(qū)，可以挖掘出潛在的購買者，當(dāng)社區(qū)內(nèi)成員點(diǎn)擊或者購買了某一件商品后，便可為相同社區(qū)的其他用戶推薦類似商品，從而可以提升商品推薦的準(zhǔn)確率，更好地為用戶服務(wù)。社交網(wǎng)絡(luò)平臺(tái)如微博、知乎、微信和Facebook等，用戶存在點(diǎn)贊、關(guān)注以及評(píng)論等多種類型的互動(dòng)關(guān)系，根據(jù)這些行為，社區(qū)發(fā)現(xiàn)可以獲得網(wǎng)絡(luò)的模塊化結(jié)構(gòu)，從而可以對(duì)具有相似特征的社區(qū)進(jìn)行好友推薦，幫助用戶發(fā)現(xiàn)更多的潛在好友。在信息傳播領(lǐng)域中，發(fā)現(xiàn)社區(qū)的中心節(jié)點(diǎn)，合理地發(fā)揮中心節(jié)點(diǎn)的作用，不僅可以提高節(jié)點(diǎn)傳播的影響力，加速信息傳播，也可以在病毒出現(xiàn)時(shí)及時(shí)抑制病毒的進(jìn)一步擴(kuò)散。

網(wǎng)絡(luò)的發(fā)展帶來了信息的多樣性，如今復(fù)雜網(wǎng)絡(luò)包含的信息已不僅只是網(wǎng)絡(luò)的結(jié)構(gòu)信息，網(wǎng)絡(luò)中的節(jié)點(diǎn)也具有豐富的屬性，如Facebook數(shù)據(jù)集不僅包含網(wǎng)絡(luò)中節(jié)點(diǎn)以及節(jié)點(diǎn)的連接邊信息，還包含節(jié)點(diǎn)的屬性信息，如年齡、性別、公司、生日、姓名等屬性特征。有研究表明，實(shí)際網(wǎng)絡(luò)中有直接連接關(guān)系的節(jié)點(diǎn)，通常其節(jié)點(diǎn)屬性信息的相似度會(huì)更高[1-2]。為了驗(yàn)證該觀點(diǎn)，以Facebook數(shù)據(jù)集和Giraffe數(shù)據(jù)集為例，可以看出，具有連接關(guān)系的節(jié)點(diǎn)屬性相似度大于0.6、0.7和0.8的邊的占比情況，如表1所示。Facebook數(shù)據(jù)集中有61%的連接邊對(duì)應(yīng)節(jié)點(diǎn)的屬性相似度超過60%，Giraffe數(shù)據(jù)集中更有61%的連接邊對(duì)應(yīng)節(jié)點(diǎn)的屬性相似度超過80%，這也論證了結(jié)合節(jié)點(diǎn)屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)的重要意義。

傳統(tǒng)社區(qū)發(fā)現(xiàn)算法大多基于網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)，面對(duì)網(wǎng)絡(luò)的多維性問題，針對(duì)單個(gè)維度的社區(qū)發(fā)現(xiàn)算法研究已到達(dá)一定瓶頸。充分利用網(wǎng)絡(luò)中節(jié)點(diǎn)的多維度特征，實(shí)現(xiàn)不同維度的信息的融合，不僅可以提高社區(qū)發(fā)現(xiàn)對(duì)當(dāng)前網(wǎng)絡(luò)的適應(yīng)性，也可以充分利用網(wǎng)絡(luò)節(jié)點(diǎn)不同維度層面的差異性，更好地挖掘節(jié)點(diǎn)的隱含特征。

隨著信息化程度的提高，復(fù)雜網(wǎng)絡(luò)規(guī)模越來越大。實(shí)際復(fù)雜網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)之間的直接聯(lián)系是非常有限的。選用合理的社區(qū)發(fā)現(xiàn)算法，充分利用節(jié)點(diǎn)屬性與網(wǎng)絡(luò)結(jié)構(gòu)特征，在保證社區(qū)發(fā)現(xiàn)準(zhǔn)確率的前提下，從網(wǎng)絡(luò)中的局部節(jié)點(diǎn)結(jié)構(gòu)便可挖掘出網(wǎng)絡(luò)的隱含的特征信息，將極大地改善傳統(tǒng)社區(qū)發(fā)現(xiàn)算法，從網(wǎng)絡(luò)的全局信息挖掘網(wǎng)絡(luò)潛在特征的低效問題，同時(shí)可以提高社區(qū)發(fā)現(xiàn)算法的可擴(kuò)展性。

近幾十年以來，社區(qū)發(fā)現(xiàn)作為網(wǎng)絡(luò)科學(xué)中的一項(xiàng)基礎(chǔ)研究，很多研究人員對(duì)社區(qū)發(fā)現(xiàn)算法進(jìn)行了深入的探索，取得了很多突破性的成果。但隨著網(wǎng)絡(luò)的發(fā)展，針對(duì)目前社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)中網(wǎng)絡(luò)的特點(diǎn)，社區(qū)發(fā)現(xiàn)的研究面臨著如下問題和挑戰(zhàn)。

1）網(wǎng)絡(luò)的多維性以及網(wǎng)絡(luò)節(jié)點(diǎn)的差異性。

針對(duì)單一維度網(wǎng)絡(luò)結(jié)構(gòu)的傳統(tǒng)社區(qū)發(fā)現(xiàn)算法因?yàn)樾畔⒌娜狈?，在社區(qū)發(fā)現(xiàn)的效率和準(zhǔn)確率上均受到了限制。隨著信息化程度的提高，信息維度的增加使網(wǎng)絡(luò)呈現(xiàn)出多維性，所謂網(wǎng)絡(luò)的多維性是指網(wǎng)絡(luò)中的節(jié)點(diǎn)之間邊的連接關(guān)系有多種類型，而由這些節(jié)點(diǎn)及不同類型的邊所組成的“維度”不同的網(wǎng)絡(luò)就稱為多維度網(wǎng)絡(luò)。在各種復(fù)雜的網(wǎng)絡(luò)尤其是社會(huì)網(wǎng)絡(luò)中，不同節(jié)點(diǎn)之間也是有差異的，而傳統(tǒng)社區(qū)發(fā)現(xiàn)算法，并沒有考慮這一點(diǎn)，大多數(shù)網(wǎng)絡(luò)分析的方法，忽略了節(jié)點(diǎn)之間的差異性，認(rèn)為整個(gè)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)有著相同的地位。實(shí)際的網(wǎng)絡(luò)中，不僅節(jié)點(diǎn)自身的屬性特征有很大的差異性，每一個(gè)節(jié)點(diǎn)的隱含網(wǎng)絡(luò)結(jié)構(gòu)特征也都是不一樣的。因此如何利用網(wǎng)絡(luò)的多維度信息針對(duì)社區(qū)發(fā)現(xiàn)中網(wǎng)絡(luò)節(jié)點(diǎn)的差異性挖掘節(jié)點(diǎn)的隱含特征，從而更好地完成社區(qū)劃分是當(dāng)前社區(qū)發(fā)現(xiàn)的研究面臨的一個(gè)重要問題。

2）可擴(kuò)展性。

當(dāng)今網(wǎng)絡(luò)發(fā)達(dá)，網(wǎng)絡(luò)每時(shí)每刻都有新節(jié)點(diǎn)加入，復(fù)雜網(wǎng)絡(luò)的規(guī)模越來越大，而現(xiàn)有的社區(qū)發(fā)現(xiàn)算法大多都基于全局信息去挖掘網(wǎng)絡(luò)的隱含信息，例如：獲取Girvan-Newman算法中依據(jù)“邊介數(shù)”信息進(jìn)行社區(qū)發(fā)現(xiàn)需要遍歷整個(gè)網(wǎng)絡(luò);Kemighan-Lin算法為了完成社區(qū)劃分必須要提前知道社區(qū)的個(gè)數(shù)或者平均規(guī)模等，在有新節(jié)點(diǎn)加入時(shí)，依然需要遍歷整個(gè)網(wǎng)絡(luò)去挖掘節(jié)點(diǎn)的隱含網(wǎng)絡(luò)結(jié)構(gòu)特征，從而造成算法的低效與浪費(fèi)。而實(shí)際上，復(fù)雜網(wǎng)絡(luò)尤其是社會(huì)網(wǎng)絡(luò)大多是稀疏的，網(wǎng)絡(luò)中的大部分個(gè)體與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)之間的直接聯(lián)系是非常有限的，因此面對(duì)日益增長的節(jié)點(diǎn)規(guī)模，能否通過只依賴網(wǎng)絡(luò)中的局部節(jié)點(diǎn)結(jié)構(gòu)挖掘出網(wǎng)絡(luò)的隱含的特征信息，在有新節(jié)點(diǎn)加入時(shí)，能否只對(duì)新節(jié)點(diǎn)所在的局部網(wǎng)絡(luò)進(jìn)行處理，增強(qiáng)算法的可擴(kuò)展性是當(dāng)前亟需要解決的一個(gè)問題。

針對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)算法難以解決網(wǎng)絡(luò)的多維性問題、節(jié)點(diǎn)的差異性問題以及可擴(kuò)展性問題，本文聚焦于網(wǎng)絡(luò)多維性問題，提出了一種基于網(wǎng)絡(luò)表示學(xué)習(xí)的非單一維度的社區(qū)發(fā)現(xiàn)算法。

該算法將節(jié)點(diǎn)屬性信息作為先驗(yàn)信息，根據(jù)用戶屬性相似度重新計(jì)算節(jié)點(diǎn)之間轉(zhuǎn)移概率，在node2vec算法的基礎(chǔ)上，借助自然語言處理領(lǐng)域的特征學(xué)習(xí)方式，將文本的處理方式遷移至網(wǎng)絡(luò)結(jié)構(gòu)中。同時(shí)，結(jié)合小世界模型的六度分離理論設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)游走路徑的長度，通過對(duì)網(wǎng)絡(luò)的局部結(jié)構(gòu)進(jìn)行分析，從而挖掘出局部網(wǎng)絡(luò)的隱含特征。當(dāng)網(wǎng)絡(luò)中有新節(jié)點(diǎn)加入時(shí)，不需要遍歷整個(gè)網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，只用計(jì)算與新節(jié)點(diǎn)有直接連接關(guān)系的節(jié)點(diǎn)之間的屬性相似度，然后根據(jù)本文提出的算法在新節(jié)點(diǎn)附近按照根據(jù)屬性相似度計(jì)算得到的概率進(jìn)行游走。得到游走路徑后，用神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練得到節(jié)點(diǎn)的隱含特征向量，最后根據(jù)新得到的節(jié)點(diǎn)向量計(jì)算相似度后，使用Louvain社區(qū)發(fā)現(xiàn)算法完成社區(qū)劃分。

本文的主要工作如下：

1）將節(jié)點(diǎn)屬性信息作為先驗(yàn)信息，從節(jié)點(diǎn)屬性和網(wǎng)絡(luò)結(jié)構(gòu)屬性信息兩個(gè)維度考慮了節(jié)點(diǎn)的差異性，改善了傳統(tǒng)社區(qū)發(fā)現(xiàn)算法因?yàn)樾畔⒌娜狈χ会槍?duì)單一維度網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)從而導(dǎo)致效率和準(zhǔn)確率均受到限制的問題。

2）現(xiàn)有社區(qū)發(fā)現(xiàn)算法大多只考慮了邊的連接性，即節(jié)點(diǎn)之間是否有直接連接關(guān)系，本文提出的算法可以計(jì)算出任意兩個(gè)節(jié)點(diǎn)之間的加權(quán)相似度，不再局限只可以計(jì)算有連接關(guān)系的節(jié)點(diǎn)之間的相似度，因此一定程度上解決了社會(huì)網(wǎng)絡(luò)的稀疏性問題。

3）從基于用戶屬性相似度的節(jié)點(diǎn)轉(zhuǎn)移概率和基于六度分離理論設(shè)置的游走路徑長度兩個(gè)方面對(duì)隨機(jī)游走算法進(jìn)行約束，改善了傳統(tǒng)隨機(jī)游走算法在網(wǎng)絡(luò)轉(zhuǎn)移過程中具有較強(qiáng)隨機(jī)性的缺點(diǎn)，提高了社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確率。

4）通過對(duì)網(wǎng)絡(luò)的局部結(jié)構(gòu)進(jìn)行分析，即可挖掘出局部網(wǎng)絡(luò)的隱含特征，提高了算法的可擴(kuò)展性，改善了傳統(tǒng)社區(qū)發(fā)現(xiàn)算法從全局網(wǎng)絡(luò)角度考慮挖掘網(wǎng)絡(luò)隱含特征造成的低效與浪費(fèi)的問題。

實(shí)驗(yàn)結(jié)果表明，在Giraffe數(shù)據(jù)集中，相較于Louvain算法，基于節(jié)點(diǎn)屬性的社區(qū)發(fā)現(xiàn)算法模塊度指標(biāo)提升2.7%，基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法模塊度指標(biāo)提升3.0%，本文提出的非單一維度的社區(qū)發(fā)現(xiàn)算法，模塊度指標(biāo)提升3.7%。

1 相關(guān)工作

隨著復(fù)雜網(wǎng)絡(luò)的發(fā)展，復(fù)雜網(wǎng)絡(luò)分析中的社區(qū)發(fā)現(xiàn)問題成為一大研究熱點(diǎn)，眾多學(xué)者從不同的角度對(duì)該問題進(jìn)行了深入的研究，下面介紹社區(qū)發(fā)現(xiàn)問題相關(guān)的經(jīng)典算法以及當(dāng)前該領(lǐng)域的一些新的研究方法。

Girvan等[3]提出了一種分裂的層次算法GN（Girvan Newman），基于邊介數(shù)的相關(guān)概念對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行劃分。邊介數(shù)的定義是經(jīng)過網(wǎng)絡(luò)中某條邊的任意兩個(gè)點(diǎn)之間最短路徑的數(shù)目，該算法通過迭代地移除網(wǎng)絡(luò)中邊介數(shù)最大的連接，以此完成劃分。該算法優(yōu)點(diǎn)是劃分社區(qū)的結(jié)果很準(zhǔn)確，但是缺點(diǎn)是算法時(shí)間復(fù)雜度在節(jié)點(diǎn)規(guī)模比較大時(shí)過高，因此不太適合處理大規(guī)模的網(wǎng)絡(luò)結(jié)構(gòu)圖。Newman等[4]提出了模塊度的概念，模塊度主要作為評(píng)價(jià)社區(qū)劃分質(zhì)量的指標(biāo)，可以用來衡量社區(qū)結(jié)構(gòu)的強(qiáng)度，模塊度越大，表示社區(qū)劃分的結(jié)果越好，社區(qū)內(nèi)部邊越緊密?，F(xiàn)在模塊度在本身社區(qū)劃分的結(jié)果是未知的情況下已經(jīng)漸漸成為衡量社區(qū)發(fā)現(xiàn)的重要標(biāo)準(zhǔn)。Kernighan和Lin[5]提出了一種貪婪算法，也被稱為Kernighan-Lin法，該算法把網(wǎng)絡(luò)視為圖結(jié)構(gòu)，通過圖分割的相關(guān)算法，不斷迭代和交換不同社區(qū)內(nèi)的節(jié)點(diǎn)，優(yōu)化社區(qū)結(jié)構(gòu)，調(diào)整社區(qū)之間連接邊的數(shù)量，目的就是使社區(qū)內(nèi)連接邊的數(shù)量與社區(qū)之間連接邊的數(shù)量的差值增大，從而獲得社區(qū)劃分的結(jié)果。該算法的缺點(diǎn)是如果劃分社區(qū)之前不了解社區(qū)的實(shí)際規(guī)模，將無法知道使該方法結(jié)束的停止條件。為了改善前面提到的GN算法當(dāng)節(jié)點(diǎn)規(guī)模變大時(shí)算法時(shí)間復(fù)雜度過高的缺陷，Newman[6]提出了一種快速分裂的層次算法FN（Fast Newman），該算法的思想是首先將網(wǎng)絡(luò)的節(jié)點(diǎn)視為單個(gè)的社區(qū)，然后合并社區(qū)，合并的原則就是使模塊度增量達(dá)到最大值時(shí)的兩個(gè)社區(qū)作為新社區(qū)，不斷地迭代調(diào)整直到整個(gè)網(wǎng)絡(luò)被合并為一個(gè)單獨(dú)的社區(qū)。FN算法在模塊度達(dá)到最大時(shí)獲得的劃分結(jié)果成為社區(qū)發(fā)現(xiàn)的最終劃分結(jié)果。該算法在保證社區(qū)劃分質(zhì)量的前提下，降低了算法的時(shí)間復(fù)雜度。 Blondel等[7]提出了Louvain算法，這是一種基于模塊度的算法，該算法主要包括兩個(gè)部分：第一部分是首先將每個(gè)節(jié)點(diǎn)視為單個(gè)的社區(qū)，嘗試將單個(gè)社區(qū)加入可以讓模塊度增加最大的社區(qū)里面，一直遍歷網(wǎng)絡(luò)，直到網(wǎng)絡(luò)中的節(jié)點(diǎn)都穩(wěn)定下來;第二部分是壓縮一個(gè)社區(qū)為一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)權(quán)重為原始社區(qū)內(nèi)部節(jié)點(diǎn)權(quán)重的和，重復(fù)第一個(gè)過程，直到模塊度成為一個(gè)穩(wěn)定值。Louvain算法在網(wǎng)絡(luò)規(guī)模比較大時(shí)依然可以取得很好的劃分效果，而且時(shí)間復(fù)雜度很低，因此常被用于大規(guī)模網(wǎng)絡(luò)中的社區(qū)劃分。

近年來，基于深度學(xué)習(xí)的發(fā)展，結(jié)合神經(jīng)網(wǎng)絡(luò)對(duì)圖結(jié)構(gòu)的分析也取得了很多成果：Deepwalk算法[8]首次將深度學(xué)習(xí)應(yīng)用于圖的網(wǎng)絡(luò)結(jié)構(gòu)分析，在根據(jù)隨機(jī)游走得到節(jié)點(diǎn)的游走序列后，借助自然語言處理中word2vec算法[9-10]的思想，將節(jié)點(diǎn)游走序列類比于文本處理中的句子，將序列中的節(jié)點(diǎn)類比于文本處理中的單詞，使用skip-gram模型[10]學(xué)習(xí)得到網(wǎng)絡(luò)中節(jié)點(diǎn)的向量表示;node2vec算法[11]在Deepwalk的基礎(chǔ)上進(jìn)行了改進(jìn)，Deepwalk算法在得到節(jié)點(diǎn)序列時(shí)就是普通的隨機(jī)游走，而node2vec算法借助參數(shù)可以控制隨機(jī)游走時(shí)更偏向于深度優(yōu)先搜索還是廣度優(yōu)先搜索;大網(wǎng)絡(luò)內(nèi)聚集模型（CLuster Affiliation Model for BIGNetworks， BIGCLAM）算法[12]用一個(gè)非負(fù)向量作為一個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)表示，該算法認(rèn)為兩個(gè)節(jié)點(diǎn)向量表示的內(nèi)積越大，兩個(gè)節(jié)點(diǎn)產(chǎn)生直接連接關(guān)系的可能性也就越大;結(jié)構(gòu)化深度網(wǎng)絡(luò)嵌入（Structural Deep Network Embedding， SDNE）算法[13]首次將深層神經(jīng)網(wǎng)絡(luò)模型用于節(jié)點(diǎn)的網(wǎng)絡(luò)表示學(xué)習(xí)，模型的第一個(gè)模塊是有監(jiān)督的自編碼神經(jīng)網(wǎng)絡(luò)對(duì)一階鄰居關(guān)系的建模，第二個(gè)模塊是無監(jiān)督的自編碼神經(jīng)網(wǎng)絡(luò)對(duì)二階鄰居關(guān)系的建模，從而保留了網(wǎng)絡(luò)的一級(jí)相似度和二級(jí)相似度。

無論是傳統(tǒng)社區(qū)發(fā)現(xiàn)算法還是結(jié)合深度學(xué)習(xí)模型的網(wǎng)絡(luò)表示學(xué)習(xí)算法，均是只考慮了圖的網(wǎng)絡(luò)結(jié)構(gòu)信息，也有一些社區(qū)發(fā)現(xiàn)算法同時(shí)結(jié)合節(jié)點(diǎn)屬性信息與網(wǎng)絡(luò)結(jié)構(gòu)特征。社交網(wǎng)絡(luò)嵌入（Social Network Embedding， SNE）算法[14]中神經(jīng)網(wǎng)絡(luò)的輸入向量是節(jié)點(diǎn)的ID與其他屬性向量的拼接，通過訓(xùn)練模型，提取到網(wǎng)絡(luò)節(jié)點(diǎn)的特征表示。也有學(xué)者提出了將原始無向無權(quán)網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息直接相融合，缺點(diǎn)是只考慮了節(jié)點(diǎn)之間邊的存在性，沒有進(jìn)一步挖掘網(wǎng)絡(luò)結(jié)構(gòu)的隱含信息。Zhang等[15]提出了通過對(duì)節(jié)點(diǎn)屬性信息進(jìn)行K核映射[16]的思路，先得到節(jié)點(diǎn)屬性的表示向量，然后通過Deepwalk算法將網(wǎng)絡(luò)結(jié)構(gòu)信息編碼到節(jié)點(diǎn)屬性表示向量中，實(shí)現(xiàn)了兩者的融合。溫雯等[17]提出了基于頂點(diǎn)信息為先驗(yàn)信息的圖嵌入（Graph embedding by incorporating prior knowledge on Vertex Information， GeVI）算法，調(diào)整skip-gram模型的優(yōu)化函數(shù)中條件概率分布為網(wǎng)絡(luò)結(jié)構(gòu)表示向量和節(jié)點(diǎn)屬性特征向量的乘積，從優(yōu)化函數(shù)角度實(shí)現(xiàn)了兩方面信息的融合。Yang等[18]提出了和文本信息相關(guān)的深度隨機(jī)游走（Text-Associated Deep Walk， TADW）算法，該算法首先證明了Deepwalk算法等價(jià)于上下文矩陣的分解，通過將節(jié)點(diǎn)屬性特征嵌入矩陣分解，借助矩陣分解框架實(shí)現(xiàn)了節(jié)點(diǎn)屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)信息的融合。Huang 等[19]提出了加速屬性網(wǎng)絡(luò)嵌入（Accelerated Attributed Network Embedding， AANE）算法，通過對(duì)節(jié)點(diǎn)屬性相似性矩陣進(jìn)行矩陣分解得到節(jié)點(diǎn)的向量表示，并在優(yōu)化函數(shù)中增加了基于節(jié)點(diǎn)連接關(guān)系的約束項(xiàng)。Yang等[20]提出了Planetoid模型，利用標(biāo)簽信息，將標(biāo)簽相同但不具有連接關(guān)系的節(jié)點(diǎn)連接在一起，從而學(xué)習(xí)出包含節(jié)點(diǎn)標(biāo)簽屬性信息的圖表示?；诠?jié)點(diǎn)文本信息的圖嵌入（Context-Aware Network Embedding， CANE）算法[21]通過對(duì)具有直接連接關(guān)系的節(jié)點(diǎn)的文本信息利用卷積神經(jīng)網(wǎng)絡(luò)[22]進(jìn)行編碼，選擇直接相連的節(jié)點(diǎn)彼此之間相關(guān)性最大的卷積結(jié)果作為節(jié)點(diǎn)的表示向量。相關(guān)主題模型（Relational Topic Model， RTM）算法[23]使用文檔主題生成模型 LDA（Latent Dirichlet Allocation）[24]對(duì)文本進(jìn)行建模，該算法認(rèn)為有直接連接關(guān)系的節(jié)點(diǎn)有著相似的主題分布;基于潛在概率的文本網(wǎng)絡(luò)嵌入（Probabilistic LAtent document Network Embedding， PLANE）方法[25]在RTM算法的基礎(chǔ)上，采用可視化的方法學(xué)習(xí)得到文本的主題以及節(jié)點(diǎn)的表示，這兩種方法要求網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)容必須是文本，因此如果不是文本類型的節(jié)點(diǎn)屬性，則不能處理;除了這兩種算法外，也有一些算法[26]依賴節(jié)點(diǎn)文本內(nèi)容屬性完成網(wǎng)絡(luò)表示學(xué)習(xí)，它們均基于網(wǎng)絡(luò)中節(jié)點(diǎn)的文本內(nèi)容屬性，而沒有充分利用節(jié)點(diǎn)的除文本屬性外的其他描述性屬性特征。

分析以上算法，可以將其分為三種類型：第一種是只考慮文本內(nèi)容屬性信息未考慮網(wǎng)絡(luò)節(jié)點(diǎn)描述屬性特征的，這類算法的不足之處是無法處理非文本類型的節(jié)點(diǎn)屬性特征，因此算法不具有普適性;第二種是只考慮了節(jié)點(diǎn)部分描述屬性，例如SNE算法只考慮了節(jié)點(diǎn)的屬性ID，沒有考慮其他屬性信息，同時(shí)網(wǎng)絡(luò)結(jié)構(gòu)中邊的信息沒有得到充分利用;其他結(jié)合節(jié)點(diǎn)屬性信息的方法，大多是先得到節(jié)點(diǎn)屬性表示向量，再與網(wǎng)絡(luò)結(jié)構(gòu)表示向量相融合，這種融合方式較為低效。為了提高節(jié)點(diǎn)通過網(wǎng)絡(luò)表示學(xué)習(xí)所得向量的質(zhì)量，可以考慮充分利用節(jié)點(diǎn)的描述型屬性特征，使算法具有普適性。同時(shí)也可以先融合節(jié)點(diǎn)屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)信息再去訓(xùn)練得到節(jié)點(diǎn)表示的向量，使節(jié)點(diǎn)屬性特征和網(wǎng)絡(luò)結(jié)構(gòu)特征可以更好地互相補(bǔ)充和制約，以提高節(jié)點(diǎn)網(wǎng)絡(luò)表示學(xué)習(xí)所得向量的質(zhì)量，可以更好地進(jìn)行社區(qū)發(fā)現(xiàn)。

本文主要方法與上述研究的不同之處在于以下兩點(diǎn)：

1）充分利用了節(jié)點(diǎn)的屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)信息，將網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)化為向量表示，采用將節(jié)點(diǎn)屬性信息作為先驗(yàn)信息，根據(jù)用戶屬性相似度重新計(jì)算節(jié)點(diǎn)之間轉(zhuǎn)移概率的方式引入節(jié)點(diǎn)屬性信息，從而進(jìn)一步挖掘網(wǎng)絡(luò)結(jié)構(gòu)的隱含信息。

2）本文提出的算法通過計(jì)算節(jié)點(diǎn)基于網(wǎng)絡(luò)表示學(xué)習(xí)得到的特征向量，用特征向量之間的相似度重置原始網(wǎng)絡(luò)，然后使用Louvain社區(qū)發(fā)現(xiàn)算法完成社區(qū)劃分，避免了將原始無向無權(quán)網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息直接相融合，只考慮了節(jié)點(diǎn)之間邊的存在性的缺點(diǎn)。

2 融合節(jié)點(diǎn)屬性和網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法

基于node2vec網(wǎng)絡(luò)表示學(xué)習(xí)算法，聚焦于網(wǎng)絡(luò)的多維性，本文提出了一種同時(shí)考慮節(jié)點(diǎn)屬性特和網(wǎng)絡(luò)結(jié)構(gòu)兩個(gè)維度特征的社區(qū)發(fā)現(xiàn)算法。在node2vec算法的基礎(chǔ)上，引入節(jié)點(diǎn)屬性信息后，借助自然語言處理領(lǐng)域的特征學(xué)習(xí)方式，將文本的處理方式遷移至網(wǎng)絡(luò)結(jié)構(gòu)中，同時(shí)結(jié)合小世界模型的六度分離理論設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)游走路徑的長度，通過對(duì)網(wǎng)絡(luò)的局部結(jié)構(gòu)進(jìn)行分析，從而挖掘出局部網(wǎng)絡(luò)的隱含特征。當(dāng)網(wǎng)絡(luò)中有新節(jié)點(diǎn)加入時(shí)，不需要遍歷整個(gè)網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，只用計(jì)算與新節(jié)點(diǎn)有直接連接關(guān)系的節(jié)點(diǎn)之間的屬性相似度，然后根據(jù)本文提出的算法在新節(jié)點(diǎn)附近按根據(jù)屬性相似度計(jì)算得到的概率進(jìn)行游走，得到游走路徑后，用神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練即可得到節(jié)點(diǎn)的隱含特征向量，從而提高了算法的可擴(kuò)展性。本文算法流程如圖1所示。

該算法首先加載圖的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)，記錄圖中節(jié)點(diǎn)以及節(jié)點(diǎn)的連接關(guān)系;然后根據(jù)節(jié)點(diǎn)屬性特征計(jì)算節(jié)點(diǎn)之間相似度，用節(jié)點(diǎn)屬性相似度初始化節(jié)點(diǎn)之間連邊的權(quán)重;重構(gòu)原始網(wǎng)絡(luò)為無向有權(quán)網(wǎng)絡(luò)，根據(jù)式（3）計(jì)算節(jié)點(diǎn)之間轉(zhuǎn)移概率，根據(jù)轉(zhuǎn)移概率采樣選擇當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)每個(gè)鄰居節(jié)點(diǎn)被選中的概率等于式（3）計(jì)算的轉(zhuǎn)移概率的值。結(jié)合小世界模型，設(shè)置適當(dāng)?shù)挠巫呗窂介L度，得到新的網(wǎng)絡(luò)結(jié)構(gòu)圖中每個(gè)節(jié)點(diǎn)的游走路徑;利用skip-gram模型采用隨機(jī)梯度下降法和反向傳播算法對(duì)節(jié)點(diǎn)進(jìn)行訓(xùn)練，生成每個(gè)節(jié)點(diǎn)最優(yōu)的向量表示，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示計(jì)算節(jié)點(diǎn)的相似度;最后使用社區(qū)發(fā)現(xiàn)算法完成社區(qū)的劃分，并使用模塊度對(duì)算法效果進(jìn)行評(píng)估。

2.1 基于用戶屬性的節(jié)點(diǎn)轉(zhuǎn)移概率

將用戶屬性用向量表示，計(jì)算用戶屬性之間相似度，如果節(jié)點(diǎn)屬性為種類類型或者布爾型特征，選用Jaccard系數(shù)計(jì)算節(jié)點(diǎn)屬性相似度，計(jì)算式如式（1）所示;如果節(jié)點(diǎn)屬性為連續(xù)數(shù)值型，選用余弦相似度計(jì)算節(jié)點(diǎn)屬性相似度，計(jì)算式如式（2）所示，將節(jié)點(diǎn)屬性的相似度作為節(jié)點(diǎn)之間的權(quán)重，重構(gòu)原始網(wǎng)絡(luò)。

S=J（A，B）=|A∩B||A∪B|（1）

其中：S表示節(jié)點(diǎn)屬性相似度;A表示樣本A，B表示樣本B，J（A，B）表示樣本A和樣本B交集個(gè)數(shù)和并集個(gè)數(shù)的比值。

屬性特征如果是連續(xù)數(shù)值型特征，可選用余弦相似度作為衡量標(biāo)準(zhǔn)。余弦相似度計(jì)算式如式（2）所示：

S=cos（X，Y）=∑ni=1（Xi×Yi）∑ni=1（Xi）2×∑ni=1（Yi）2（2）

其中：S表示節(jié)點(diǎn)屬性相似度;X表示樣本X，Y表示樣本Y，cos（X，Y） 表示樣本X和樣本Y的余弦相似度;n表示樣本特征向量維度;Xi表示樣本X第i維特征，Yi 表示樣本Y第i維特征。

假設(shè)當(dāng)前節(jié)點(diǎn)是v，訪問鄰居節(jié)點(diǎn)x的概率如式（3）所示：

p（v，x）=wv，xZ（3）

其中Z為歸一化因子。wv，x 計(jì)算式如式（4）所示：

wv，x=S/p，dtx=0

1，dtx=1

S/q，dtx=2 （4）

其中：S為節(jié)點(diǎn)屬性相似度;t表示上一個(gè)節(jié)點(diǎn);v表示當(dāng)前節(jié)點(diǎn);x為要訪問的鄰居節(jié)點(diǎn);dtx 表示節(jié)點(diǎn)t和節(jié)點(diǎn)x的最短距離;參數(shù)p控制重復(fù)訪問剛剛訪問過的頂點(diǎn)的概率，p只在dtx=0 時(shí)起作用，dtx=0 表示下一次要訪問的節(jié)點(diǎn)正是之前剛剛訪問過的頂點(diǎn)。 因此如果p值較大，則訪問剛剛訪問過的頂點(diǎn)的概率會(huì)變低;反之會(huì)變高。參數(shù)q則控制著游走的方向是向外還是向內(nèi)，若q值較大，則隨機(jī)游走傾向于訪問和t接近的頂點(diǎn)，游走路徑偏向于廣度優(yōu)先搜索;反之，如果q較小，則隨機(jī)游走過程傾向于訪問遠(yuǎn)離t的頂點(diǎn)，游走路徑偏向于深度優(yōu)先搜索。

2.2 結(jié)合小世界模型的隨機(jī)游走

小世界模型也即六度分離理論，該理論的主要思想是在社會(huì)網(wǎng)絡(luò)中，任意兩個(gè)不認(rèn)識(shí)的人都可以通過“朋友的朋友”建立起一種聯(lián)系，這中間一般需要通過5個(gè)朋友。研究表明，除了社會(huì)網(wǎng)絡(luò)以外，也有很多其他領(lǐng)域的網(wǎng)絡(luò)有類似的“六度分離”結(jié)構(gòu)，如金融經(jīng)濟(jì)領(lǐng)域中的商業(yè)網(wǎng)絡(luò)結(jié)構(gòu)、大自然生態(tài)系統(tǒng)中的食物鏈，甚至人類的腦神經(jīng)元結(jié)構(gòu)等都存在這樣的現(xiàn)象。

本文引入了節(jié)點(diǎn)的屬性信息重構(gòu)網(wǎng)絡(luò)后，節(jié)點(diǎn)之間會(huì)有潛在的連接關(guān)系，本文認(rèn)為被節(jié)點(diǎn)屬性信息重構(gòu)后的網(wǎng)絡(luò)結(jié)構(gòu)具有“六度分離”屬性，因此結(jié)合小世界模型的思想，設(shè)置游走路徑長度為l，其中3

2）基于節(jié)點(diǎn)屬性相似度的社區(qū)發(fā)現(xiàn)（Community Detection based on Node Attribute Similarity， CD-NAS）算法[28]。該算法的特點(diǎn)是不考慮節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)特征，單一地根據(jù)節(jié)點(diǎn)的屬性計(jì)算節(jié)點(diǎn)之間的相似度，然后將節(jié)點(diǎn)之間相似度作為節(jié)點(diǎn)之間連接權(quán)重，根據(jù)節(jié)點(diǎn)屬性相似度進(jìn)行社區(qū)發(fā)現(xiàn)。

3）基于網(wǎng)絡(luò)結(jié)構(gòu)特征相似度的社區(qū)發(fā)現(xiàn)（Community Detection based on Network Structure Feature Similarity， CD-NSFS）算法[11]，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)特征的處理有兩種方式，可以和基于初始結(jié)構(gòu)的Louvain社區(qū)發(fā)現(xiàn)算法的處理方法一樣即直接根據(jù)連接關(guān)系來處理，也可以先根據(jù)網(wǎng)絡(luò)表示學(xué)習(xí)算法得到網(wǎng)絡(luò)中節(jié)點(diǎn)的特征向量，然后根據(jù)節(jié)點(diǎn)的特征向量計(jì)算節(jié)點(diǎn)之間的相似度，然后根據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)特征相似度劃分社區(qū)。

3.4 結(jié)果分析

將節(jié)點(diǎn)屬性作為先驗(yàn)信息，先根據(jù)節(jié)點(diǎn)屬性計(jì)算節(jié)點(diǎn)的相似度，F(xiàn)acebook數(shù)據(jù)集節(jié)點(diǎn)屬性的相似度如表3所示，Giraffe數(shù)據(jù)集節(jié)點(diǎn)屬性的相似度如表4 所示。

將節(jié)點(diǎn)屬性相似度作為節(jié)點(diǎn)之間邊的權(quán)重，重構(gòu)原始網(wǎng)絡(luò)，得到Facebook數(shù)據(jù)集節(jié)點(diǎn)用網(wǎng)絡(luò)表示學(xué)習(xí)方法得到節(jié)點(diǎn)的特征向量一共100維，同時(shí)得到Giraffe數(shù)據(jù)集節(jié)點(diǎn)用網(wǎng)絡(luò)表示學(xué)習(xí)方法得到節(jié)點(diǎn)的特征向量一共100維，利用t分布隨機(jī)鄰域嵌入（t-distributed Stochastic Neighbor Embedding， t-SNE）工具對(duì)節(jié)點(diǎn)特征向量進(jìn)行降維處理。Facebook數(shù)據(jù)集根據(jù)網(wǎng)絡(luò)表示學(xué)習(xí)算法得到的節(jié)點(diǎn)特征向量計(jì)算的相似度如表5所示，包含源節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)以及節(jié)點(diǎn)屬性為先驗(yàn)信息的節(jié)點(diǎn)之間網(wǎng)絡(luò)結(jié)構(gòu)特征的相似度。

源節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)節(jié)點(diǎn)屬性相似度11460.94828137911890.85361916912290.97834576912010.97897261612040.9834241831600.98559850512150.9765135851350.9832997811910.98142946112380.966038461

Giraffe數(shù)據(jù)集根據(jù)網(wǎng)絡(luò)表示學(xué)習(xí)算法得到的節(jié)點(diǎn)特征向量計(jì)算的相似度如表6所示，包含源節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)以及節(jié)點(diǎn)屬性為先驗(yàn)信息的節(jié)點(diǎn)之間網(wǎng)絡(luò)結(jié)構(gòu)特征的相似度。

選用基于初始網(wǎng)絡(luò)結(jié)構(gòu)的Louvain算法進(jìn)行對(duì)比實(shí)驗(yàn)，即：如果網(wǎng)絡(luò)中節(jié)點(diǎn)有連邊，權(quán)重設(shè)置為1;無連邊，權(quán)重設(shè)置為0。對(duì)比實(shí)驗(yàn)選用的算法有：1）Louvain算法;2）只依賴用戶屬性特征的社區(qū)發(fā)現(xiàn)（CD-NAS）算法[28];3）只依賴網(wǎng)絡(luò)結(jié)構(gòu)特征的社區(qū)發(fā)現(xiàn)（CD-NSFS）算法[11];4）本文提出的基于網(wǎng)絡(luò)表示學(xué)習(xí)的非單一維度的社區(qū)發(fā)現(xiàn)算法，也即將節(jié)點(diǎn)屬性作為先驗(yàn)信息的基于網(wǎng)絡(luò)表示學(xué)習(xí)的社區(qū)發(fā)現(xiàn)（Community Detection based on Network Representation Learning between nodes With Node Attribute as priori information， CD-NRLWNA）算法。Facebook數(shù)據(jù)集四種算法的模塊度和運(yùn)行時(shí)間對(duì)比結(jié)果如表7所示，Giraffe數(shù)據(jù)集四種算法的模塊度和運(yùn)行時(shí)間對(duì)比結(jié)果如表8所示。

從表7～8可以看出，無論是在Facebook數(shù)據(jù)集上，還是在Giraffe數(shù)據(jù)集上，本文提出的算法效果都是最好的。在Giraffe數(shù)據(jù)集上，相較于Louvain算法，基于節(jié)點(diǎn)屬性的社區(qū)發(fā)現(xiàn)算法模塊度指標(biāo)提升了2.7%，基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法模塊度指標(biāo)提升了3.0%，而依據(jù)本文提出的非單一維度的社區(qū)發(fā)現(xiàn)算法，其模塊度指標(biāo)提升了3.7%。同時(shí)，因?yàn)榫W(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜度不同，F(xiàn)acebook數(shù)據(jù)集運(yùn)行時(shí)間均高于Giraffe數(shù)據(jù)集。和一般的加權(quán)融合節(jié)點(diǎn)屬性和網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法不同的是，本文提出的算法在用網(wǎng)絡(luò)表示學(xué)習(xí)算法學(xué)習(xí)節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)特征之前，先用節(jié)點(diǎn)屬性作為先驗(yàn)信息，實(shí)驗(yàn)結(jié)果表明這種算法比基于單純節(jié)點(diǎn)屬性特征或基于網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行社區(qū)發(fā)現(xiàn)算法效果都更好。

3.5 參數(shù)敏感性分析

在本節(jié)中，對(duì)本文提出的將節(jié)點(diǎn)屬性作為先驗(yàn)信息的基于網(wǎng)絡(luò)表示學(xué)習(xí)的社區(qū)發(fā)現(xiàn)算法進(jìn)行了參數(shù)敏感性分析。本次實(shí)驗(yàn)選擇Giraffe數(shù)據(jù)集測試，評(píng)價(jià)指標(biāo)為模塊度。本節(jié)分析了在算法中起重要作用的兩個(gè)參數(shù)，分別是隨機(jī)游走路徑長度和特征維度，其他參數(shù)選用默認(rèn)參數(shù)，每個(gè)節(jié)點(diǎn)的隨機(jī)游走次數(shù)為num=50，超參數(shù)p=0.25、q=4，滑動(dòng)窗口w=30，迭代次數(shù)n=5。

模塊度隨隨機(jī)游走路徑的變化如表9所示，模塊度隨特征維度的變化如表10所示。

從表9可以看出，如果隨機(jī)游走的長度取值過小，則隨機(jī)游走得到的節(jié)點(diǎn)序列均是初始節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，不能有效地展現(xiàn)網(wǎng)絡(luò)的實(shí)際結(jié)構(gòu)，具有很大的局限性;隨著游走長度的增加，模塊度的值開始明顯提高，但是當(dāng)游走路徑長度增加到一定程度時(shí)，模塊度的值便不再增加，主要是因?yàn)樗惴ㄔ谑占焦?jié)點(diǎn)的序列后，會(huì)像自然語言處理方法中對(duì)文本句子的處理一樣，限定句子的長度，那么相應(yīng)的序列長度也是固定的，當(dāng)游走長度足夠長時(shí)，已經(jīng)足以獲取網(wǎng)絡(luò)的全局性特征，因此算法也相對(duì)穩(wěn)定。此外，還可以看出，當(dāng)模塊度為10時(shí)，模塊度最大，也驗(yàn)證了引入節(jié)點(diǎn)信息和小世界模型進(jìn)行社區(qū)發(fā)現(xiàn)的必要性。

從表10可以看出，特征維度從20維到128維之間，模塊度一直在增加;從128維到200維，特征維度基本不再變化。這是因?yàn)楫?dāng)特征維度到一定程度時(shí)，已經(jīng)可以完全表示出網(wǎng)絡(luò)結(jié)構(gòu)的信息，如果特征維度繼續(xù)增大，會(huì)造成信息冗余。特征維度如果過低，則不能有效地表示出網(wǎng)絡(luò)的結(jié)構(gòu)特征;但是特征維度如果設(shè)置過大，不僅會(huì)造成信息冗余，也會(huì)增加算法運(yùn)行時(shí)間。因此設(shè)置一個(gè)合適的特征維度對(duì)算法效果有很重要的影響。

Facebook數(shù)據(jù)集和Giraffe數(shù)據(jù)集使用Louvain算法和根據(jù)將節(jié)點(diǎn)屬性作為先驗(yàn)信息的基于網(wǎng)絡(luò)表示學(xué)習(xí)的社區(qū)發(fā)現(xiàn)（CD-NRLWNA）算法得到的社區(qū)發(fā)現(xiàn)效果如圖5～6所示，其中相同顏色的屬于同一個(gè)社區(qū)。

從圖5～6可以直觀地看出，和Giraffe數(shù)據(jù)集相比，F(xiàn)acebook數(shù)據(jù)集得到的社區(qū)結(jié)構(gòu)更明確，社區(qū)劃分更清晰，這和前面得出的Facebook數(shù)據(jù)集模塊度明顯高于Giraffe數(shù)據(jù)集的結(jié)果也是一致的。另一方面，和Louvain算法效果進(jìn)行對(duì)比，本文提出的算法不僅對(duì)于網(wǎng)絡(luò)邊緣一些節(jié)點(diǎn)的社區(qū)歸屬社區(qū)劃分的結(jié)果更合理，同時(shí)社區(qū)劃分的粒度更細(xì)，社區(qū)內(nèi)部的結(jié)構(gòu)更緊湊，更精確地發(fā)現(xiàn)了一些Louvain算法沒有發(fā)現(xiàn)的潛在社區(qū)，如圖中黑色圓圈標(biāo)記所示，被Louvain算法識(shí)別為一個(gè)大社區(qū)的節(jié)點(diǎn)集合，用本文提出的算法可以被劃分為更細(xì)粒度的社區(qū)，驗(yàn)證了本文算法的有效性。

4 結(jié)語

從節(jié)點(diǎn)屬性和網(wǎng)絡(luò)特征兩個(gè)維度出發(fā)，聚焦于網(wǎng)絡(luò)的多維性，本文提出了一種基于網(wǎng)絡(luò)表示學(xué)習(xí)的非單一維度的社區(qū)發(fā)現(xiàn)算法。該算法將節(jié)點(diǎn)屬性作為先驗(yàn)信息，然后基于node2vec算法，結(jié)合網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行社區(qū)發(fā)現(xiàn)，最后使用模塊度對(duì)算法效果進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明本文提出的算法能更好地挖掘節(jié)點(diǎn)的隱含特征，社區(qū)劃分的結(jié)果更準(zhǔn)確。

社區(qū)發(fā)現(xiàn)作為復(fù)雜網(wǎng)絡(luò)分析中一個(gè)重要的研究課題，我們接下來的研究方向主要是進(jìn)一步結(jié)合圖神經(jīng)網(wǎng)絡(luò)的相關(guān)知識(shí)對(duì)節(jié)點(diǎn)屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)的融合進(jìn)行研究。此外，現(xiàn)在網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅僅是代表一個(gè)人或者一個(gè)網(wǎng)頁，節(jié)點(diǎn)之間的連接也不僅僅只代表節(jié)點(diǎn)的連接關(guān)系，如社交網(wǎng)絡(luò)中節(jié)點(diǎn)用戶可能有多種行為，如“點(diǎn)贊” “關(guān)注”或者“評(píng)論”，因此針對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)角色的差異性如何把這些不同的信息結(jié)合起來，也是接下來的一個(gè)研究方向。

參考文獻(xiàn) （References）

[1]MCPHERSON M， SMITH-LOVIN L， COOK J M. Birds of a feather： homophily in social networks [J]. Annual Review of Sociology， 2001， 27： 415-444.

[2]AIELLO L M， BARRAT A， SCHIFANELLA R， et al. Friendship prediction and homophily in social media [J]. ACM Transactions on the Web， 2012， 6（2）： 373-382.

[3]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

[4]NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2 Pt 2）： Article No. 026113.

[5]KERNIGHAN B W， LIN S. A efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal， 1970， 49 （2）： 291-307.

[6]NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（6 Pt 2）： Article No. 066133.

[7]BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008： Article No. P10008.

[8]PEROZZI B， AL-RFOU R， SKIENA S. Deepwalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2014： 701-710.

[9]MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality [C]// Proceedings of the 2013 International Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2013： 3111-3119.

[10]MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space [EB/OL]. [2019-05-20]. https：//arxiv.org/abs/1301.3781.

[11]GROVER A， LESKOVEC J. Node2vec： scalable feature learning for networks [C]// Proceeding of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 855-864.

[12]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. New York： ACM， 2013： 587-596.

[13]WANG D， CUI P， ZHU W. Structural deep network embedding [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 1225-1234.

[14]LIAO L， HE X， ZHANG H， et al. Attributed social network embedding [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（2）： 2257-2270.

[15]ZHANG D， YIN J， ZHU X， et al. User profile preserving social network embedding [C]// Proceedings of the 26th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2017： 3378-3384.

[16]RAHIMI A， RECHT B. Random features for large-scale kernel machines [C]// Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2008： 1177-1184.

[17]溫雯，黃家明，蔡瑞初，等.一種融合節(jié)點(diǎn)先驗(yàn)信息的圖表示學(xué)習(xí)方法[J].軟件學(xué)報(bào)，2018，29（3）：786-798.（WEN W， HUANG J M， CAI R C， et al. Graph embedding by incorporating prior knowledge on vertex information [J]. Journal of Software， 2018，29（3）： 786-798.）

[18]YANG C， LIU Z， ZHAO D， et al. Network representation learning with rich text information [C]// Proceeding of the 24th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2015： 2111-2117.

[19]HUANG X， LI J， HU X. Accelerated attributed network embedding [C]// Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia： SIAM， 2017： 633-641.

[20]YANG Z， COHEN W W， SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings [C]// Proceeding of the 33rd International Conference on Machine Learning. New York： JMLR， 2016： 40-48.

[21]TU C， LIU H， LIU Z， et al. CANE： context-aware network embedding for relation modeling [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Stroudsburg： Association for Computational Linguistics， 2017： 1722-1731.

[22]YANG H W， HSU H C， YANG C K， et al. Differentiating between morphologically similar species in genus Cinnamomum （Lauraceae） using deep convolutional neural networks [J]. Computers and Electronics in Agriculture， 2019， 162： 739-748.

[23]CHANG J， BLEI D M. Relational topic models for document networks [C]// Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Florida： PMLR， 2009： 81-88.

[24]GYAMFI K S， BRUSEY J， HUNT A， et al. A dynamic linear model for heteroscedastic LDA under class imbalance [J]. Neurocomputing， 2019， 343： 65-75.

[25]LE T M V， LAUW H W. Probabilistic latent document network embedding [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway： IEEE， 2014： 270-279.

[26]LI H， WANG H， YANG Z， et al. Variation autoencoder based network representation learning for classification [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics， Student Research Workshop. Stroudsburg： Association for Computational Linguistics， 2017： 56-61.

[27]李南星，盛益強(qiáng)，倪宏.基于LM算法的MLP模型及其應(yīng)用[J].網(wǎng)絡(luò)新媒體技術(shù)，2018，7（1）：59-63.（LI N X， SHENG Y Q， NI H. A multilayer perceptron model based on Levenberg-Marquardt algorithm with its applications [J]. Journal of Network New Media， 2018， 7（1）： 59-63.）

[28]LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations ： can geographic isolation explain this unique trait？ [J]. Behavioral Ecology and Sociobiology， 2003， 54（4）： 396-405.

This work is partially supported by the Special Fund for Strategic Pilot Technology of Chinese Academy of Sciences （XDC02070100）.

CHEN Wanjie， born in 1993， M. S. candidate. Her research interests include data mining， intelligent processing.

SHENG Yiqiang， born in 1978， Ph. D.， associate research fellow. His research interests include intelligent networking， data mining.

收稿日期：2019-06-14;修回日期：2019-09-10;錄用日期：2019-09-23。

基金項(xiàng)目：中國科學(xué)院戰(zhàn)略性科技先導(dǎo)專項(xiàng)課題（XDC02070100）。

作者簡介：陳婉杰（1993—），女，河南南陽人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、智能處理; 盛益強(qiáng)（1978—），男，北京人，副研究員，博士，主要研究方向：智能網(wǎng)絡(luò)、數(shù)據(jù)挖掘。

文章編號(hào)：1001-9081（2019）12-3467-09 DOI：10.11772/j.issn.1001-9081.2019061009