呂少卿，趙雪莉，張 潘，任新成

（1.西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710121；2.陜西省信息通信網(wǎng)絡(luò)及安全重點(diǎn)實(shí)驗(yàn)室，西安 710121；3.陜西省能源大數(shù)據(jù)智能處理省市共建重點(diǎn)實(shí)驗(yàn)室，陜西延安 716000）

0 概述

復(fù)雜網(wǎng)絡(luò)［1-3］作為一種特殊的數(shù)據(jù)類型在現(xiàn)實(shí)世界中隨處可見，例如由社交平臺(tái)上用戶好友關(guān)系抽象得到的社交網(wǎng)絡(luò)、由論文之間引用關(guān)系抽象得到的引文網(wǎng)絡(luò)、由蛋白質(zhì)之間的相互作用關(guān)系抽象得到的蛋白質(zhì)網(wǎng)絡(luò)、由網(wǎng)頁(yè)間鏈接關(guān)系抽象得到的Web 網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，其中蘊(yùn)含著一些值得深入探索和挖掘的信息及規(guī)律。

網(wǎng)絡(luò)的表現(xiàn)形式很大程度上決定了能否對(duì)網(wǎng)絡(luò)進(jìn)行有效分析。早期，人們用鄰接矩陣來(lái)進(jìn)行網(wǎng)絡(luò)的存儲(chǔ)和表達(dá)，但鄰接矩陣只能體現(xiàn)節(jié)點(diǎn)之間的鏈接關(guān)系，并不能體現(xiàn)網(wǎng)絡(luò)的高階關(guān)系［2］。此外，隨著網(wǎng)絡(luò)規(guī)模的增大，鄰接矩陣還面臨著存儲(chǔ)成本高、計(jì)算效率低、數(shù)據(jù)稀疏等問題［4］。因此，研究人員轉(zhuǎn)而研究將節(jié)點(diǎn)表示為低維、稠密的實(shí)值向量形式，即網(wǎng)絡(luò)嵌入［5］（又稱為網(wǎng)絡(luò)表示學(xué)習(xí)）。將網(wǎng)絡(luò)節(jié)點(diǎn)表示為低維、稠密向量就能夠進(jìn)行后續(xù)的網(wǎng)絡(luò)分析任務(wù)，如節(jié)點(diǎn)分類［6］、鏈接預(yù)測(cè)［7］、社區(qū)發(fā)現(xiàn)［8］、可視化［9］等，還可以作為邊信息應(yīng)用到推薦系統(tǒng)［10］等其他任務(wù)中。

從算法所使用的工具角度，可將現(xiàn)有的網(wǎng)絡(luò)嵌入算法分為基于矩陣特征向量的方法、基于矩陣分解的方法、基于簡(jiǎn)單神經(jīng)網(wǎng)絡(luò)的方法和基于深度神經(jīng)網(wǎng)絡(luò)的方法4 類。基于矩陣特征向量的方法是早期的網(wǎng)絡(luò)嵌入算法，包括局部線性嵌入［11］（Locally Linear Embedding，LLE）、拉普拉斯特征映射［12］（Laplacian Eigenmap，LE）等，該類算法通過提取網(wǎng)絡(luò)的關(guān)系矩陣（如鄰接矩陣或拉普拉斯矩陣），然后計(jì)算得到關(guān)系矩陣的特征向量，繼而得到節(jié)點(diǎn)的表示向量。基于矩陣分解的方法包括GraRep［13］、HOPE［14］、NEU［15］等，該類算法通過對(duì)描述網(wǎng)絡(luò)的關(guān)系矩陣進(jìn)行矩陣分解，達(dá)到降維的目的，從而得到節(jié)點(diǎn)的低維表示向量?；诤?jiǎn)單神經(jīng)網(wǎng)絡(luò)的方法包括DeepWalk［16］、Node2vec［17］和LINE［18］等，該類算法對(duì)網(wǎng)絡(luò)進(jìn)行概率建模，通過最大化概率來(lái)保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，從而得到節(jié)點(diǎn)的表示向量。基于深度神經(jīng)網(wǎng)絡(luò)的方法包括SDNE［19］、DNGR［20］等，該類算法通過深度自編碼捕獲網(wǎng)絡(luò)的非線性關(guān)系，進(jìn)而得到節(jié)點(diǎn)的表示。

雖然上述方法保留了網(wǎng)絡(luò)中的微觀結(jié)構(gòu)信息并取得了較好的表示結(jié)果，但卻都忽略了網(wǎng)絡(luò)結(jié)構(gòu)中普遍存在的社區(qū)結(jié)構(gòu)信息［1］。社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)所具有的宏觀結(jié)構(gòu)信息，同一社區(qū)內(nèi)的節(jié)點(diǎn)通常具有密集的鏈接關(guān)系以及相似的特性，而不同社區(qū)節(jié)點(diǎn)間的鏈接則相對(duì)稀疏［21］。社區(qū)結(jié)構(gòu)普遍存在于現(xiàn)實(shí)網(wǎng)絡(luò)中，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、Web 網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等［21-22］，其對(duì)刻畫網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系和完成后續(xù)網(wǎng)絡(luò)分析任務(wù)具有重要作用。鑒于此，本文提出一種保留社區(qū)結(jié)構(gòu)信息的網(wǎng)絡(luò)嵌入算法PCNE。通過構(gòu)造社區(qū)結(jié)構(gòu)嵌入矩陣和社區(qū)隸屬度矩陣得到原始網(wǎng)絡(luò)中的宏觀社區(qū)結(jié)構(gòu)信息，并通過融合一階相似性和二階相似性得到網(wǎng)絡(luò)中的微觀結(jié)構(gòu)信息。在此基礎(chǔ)上，以迭代優(yōu)化的方式對(duì)微觀結(jié)構(gòu)信息、宏觀社區(qū)結(jié)構(gòu)嵌入矩陣和社區(qū)隸屬度矩陣進(jìn)行聯(lián)合優(yōu)化，得到同時(shí)包含網(wǎng)絡(luò)微觀一階、二階結(jié)構(gòu)信息和宏觀社區(qū)結(jié)構(gòu)信息的網(wǎng)絡(luò)嵌入向量。

1 本文方法

表1 列出了本文PCNE 算法使用的符號(hào)及定義。

表1 符號(hào)定義Table 1 Definition of symbols

1.1 相關(guān)概念

本小節(jié)給出本文工作相關(guān)的一些基本概念及定義。

定義1（社區(qū)結(jié)構(gòu)［23］）社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)中存在的一些連接密集的群落（也稱為簇）結(jié)構(gòu)。同一社區(qū)內(nèi)的節(jié)點(diǎn)彼此連接緊密，而各個(gè)不同社區(qū)中的節(jié)點(diǎn)間連接相對(duì)稀疏。

定義2（網(wǎng)絡(luò)嵌入［5］）網(wǎng)絡(luò)嵌入又稱網(wǎng)絡(luò)表示學(xué)習(xí)或圖嵌入。給定一個(gè)無(wú)向網(wǎng)絡(luò)G=(V，E)，網(wǎng)絡(luò)嵌入的目標(biāo)是學(xué)習(xí)一個(gè)映射函數(shù)f：v→rv∈Rd，將網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)映射為一個(gè)d維稠密的實(shí)數(shù)向量，并且滿足d<<|V|。

1.2 算法框架

給定網(wǎng)絡(luò)G=(V，E)。設(shè)A∈Rn×n為網(wǎng)絡(luò)的鄰接矩陣。若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在鏈接關(guān)系，則A中對(duì)應(yīng)元素為1，否則為0。所得到的節(jié)點(diǎn)的表示矩陣為Y，Y中的第i行代表節(jié)點(diǎn)i的表示向量，其中，d表示嵌入空間中節(jié)點(diǎn)表示向量的維數(shù)。

PCNE 算法框架如圖1 所示，其中主要包含兩部分內(nèi)容，即保留網(wǎng)絡(luò)微觀結(jié)構(gòu)信息的模型和保留社區(qū)結(jié)構(gòu)信息的模型。具體而言，首先通過節(jié)點(diǎn)間的鏈接關(guān)系得到包含一階相似性和二階相似性的微觀結(jié)構(gòu)相似性矩陣F，借助對(duì)稱非負(fù)矩陣分解模型得到保留網(wǎng)絡(luò)微觀結(jié)構(gòu)信息的損失函數(shù)；然后引入社區(qū)結(jié)構(gòu)嵌入矩陣P，通過聯(lián)合非負(fù)矩陣分解模型得到保留網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)信息的損失函數(shù)；最后通過聯(lián)合優(yōu)化兩部分損失函數(shù)，得到同時(shí)保留網(wǎng)絡(luò)微觀結(jié)構(gòu)信息和網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)信息的節(jié)點(diǎn)表示。

圖1 PCNE 模型框架Fig.1 Framework of PCNE model

1.3 微觀結(jié)構(gòu)信息建模

本文通過保留網(wǎng)絡(luò)中每對(duì)節(jié)點(diǎn)的一階相似性和二階相似性刻畫網(wǎng)絡(luò)的微觀結(jié)構(gòu)信息。具體地，如果在原始網(wǎng)絡(luò)中一對(duì)節(jié)點(diǎn)之間存在邊，那么它們就具有一階相似性；如果一對(duì)節(jié)點(diǎn)在原始網(wǎng)絡(luò)中沒有邊連接，那么它們之間的一階相似性為0。在現(xiàn)實(shí)世界網(wǎng)絡(luò)中，有邊相連的兩個(gè)節(jié)點(diǎn)之間通常具有相近的性質(zhì)。以社交網(wǎng)絡(luò)為例，如果一個(gè)節(jié)點(diǎn)和另一個(gè)節(jié)點(diǎn)相連（即有好友關(guān)系），那么這兩個(gè)用戶大概率具有相似的興趣愛好或職業(yè)。這表明，在原始網(wǎng)絡(luò)中直接相連的兩個(gè)節(jié)點(diǎn)在嵌入空間中也應(yīng)該彼此接近。本文將網(wǎng)絡(luò)的鄰接矩陣A作為節(jié)點(diǎn)間網(wǎng)絡(luò)結(jié)構(gòu)一階相似性的描述。

現(xiàn)實(shí)網(wǎng)絡(luò)中存在的邊通常是稀疏的［24］，沒有連邊的節(jié)點(diǎn)對(duì)并不代表它們?cè)诘途S空間的表示向量不相似。一種補(bǔ)充一階相似性缺陷的解決方案是考慮他們的共同鄰居，通過共同鄰居來(lái)衡量?jī)蓚€(gè)節(jié)點(diǎn)之間的相似性，即二階相似性。此外，現(xiàn)實(shí)中的網(wǎng)絡(luò)經(jīng)常會(huì)由于觀測(cè)手段的不足導(dǎo)致丟失一些網(wǎng)絡(luò)中本該存在的鏈接關(guān)系，因此保留節(jié)點(diǎn)間的二階相似性就更有必要。本文定義矩陣S∈Rn×n為二階相似度矩陣，并用鄰接矩陣行向量的余弦相似作為其二階相似度，如式（1）所示：

其中：ai為鄰接矩陣A的第i行。

為同時(shí)保留網(wǎng)絡(luò)結(jié)構(gòu)的一階相似性和二階相似性，本文將兩種相似性的加權(quán)和作為網(wǎng)絡(luò)最終的微觀結(jié)構(gòu)相似性，用矩陣F來(lái)表示，并命名為微觀結(jié)構(gòu)相似度矩陣。F計(jì)算公式如式（2）所示：

其中：參數(shù)α>0，為二階相似性的權(quán)重系數(shù)，α的大小體現(xiàn)二階相似性對(duì)節(jié)點(diǎn)表示的重要性。在本文的后續(xù)實(shí)驗(yàn)中，選擇α=3。

由于本文針對(duì)的是無(wú)向網(wǎng)絡(luò)，因此微觀結(jié)構(gòu)相似度矩陣F是一個(gè)非負(fù)的對(duì)稱矩陣。為使所得到的節(jié)點(diǎn)表示能夠保留網(wǎng)絡(luò)的微觀結(jié)構(gòu)信息，本文基于對(duì)稱非負(fù)矩陣分解［23］提出式（3）所示的損失函數(shù)來(lái)最小化節(jié)點(diǎn)之間的嵌入差異：

1.4 社區(qū)結(jié)構(gòu)信息建模

網(wǎng)絡(luò)的鄰接矩陣反映的是網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈接關(guān)系，文獻(xiàn)［23］通過非負(fù)矩陣分解的方式提取網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息。假設(shè)網(wǎng)絡(luò)由k個(gè)社區(qū)組成，則其目標(biāo)函數(shù)如式（4）所示：

其中：矩陣A為網(wǎng)絡(luò)的鄰接矩陣；U∈Rn×k為社區(qū)隸屬度矩陣，反映網(wǎng)絡(luò)中各節(jié)點(diǎn)與各個(gè)社區(qū)之間的從屬關(guān)系。無(wú)論節(jié)點(diǎn)i和節(jié)點(diǎn)j是否屬于同一個(gè)社區(qū)，只要兩節(jié)點(diǎn)之間存在鏈接，其對(duì)應(yīng)元素就為1，因此，蘊(yùn)含在網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)不能通過直接分解鄰接矩陣A來(lái)反映。本文通過分解文獻(xiàn)［25］中所提出的更能反映網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)信息的社區(qū)結(jié)構(gòu)嵌入矩陣P來(lái)提取網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)分布信息，其目標(biāo)函數(shù)形式化表示為：

下面介紹社區(qū)結(jié)構(gòu)嵌入矩陣P的具體構(gòu)造方法。

由于社區(qū)內(nèi)部的節(jié)點(diǎn)彼此之間連接緊密，因此每個(gè)具有鏈接關(guān)系的節(jié)點(diǎn)對(duì)都有落入同一社區(qū)內(nèi)的可能性，定義這種可能性為社區(qū)成員相似性。對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)i和節(jié)點(diǎn)j，它們之間社區(qū)成員相似度的計(jì)算公式如式（6）所示：

現(xiàn)實(shí)世界中的大多數(shù)網(wǎng)絡(luò)都比較稀疏，在網(wǎng)絡(luò)中任意選擇兩個(gè)節(jié)點(diǎn)，他們之間存在邊的可能性幾乎為零。為了最大化具有鏈接關(guān)系的節(jié)點(diǎn)對(duì)的社區(qū)成員相似性，同時(shí)最小化隨機(jī)采樣的節(jié)點(diǎn)對(duì)之間的社區(qū)成員相似性，本文采用負(fù)采樣的方式，設(shè)計(jì)如式（7）所示的損失函數(shù)：

其中：ns為負(fù)采樣樣本數(shù)；jN為負(fù)采樣的隨機(jī)采樣節(jié)點(diǎn)；，di表示節(jié)點(diǎn)i的度，D表示整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)的總和。式（7）又可表示為：

對(duì)式（8）求偏導(dǎo)，得到：

基于以上分析，社區(qū)結(jié)構(gòu)嵌入矩陣P可由式（11）進(jìn)行構(gòu)造：

1.5 保留社區(qū)結(jié)構(gòu)信息的網(wǎng)絡(luò)嵌入

為了將網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)信息融入網(wǎng)絡(luò)嵌入的過程中，利用得到的社區(qū)隸屬度矩陣U對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行約束，使所得節(jié)點(diǎn)表示能夠反映出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)信息，從而在一定程度上提高網(wǎng)絡(luò)表示學(xué)習(xí)的質(zhì)量。本文引入一個(gè)非負(fù)矩陣H∈Rk×d，并命名為社區(qū)表示矩陣，其第i行的行向量hi即為第i個(gè)社區(qū)的向量表示。如果某節(jié)點(diǎn)的表示向量與某一社區(qū)的表示向量相似，則認(rèn)為該節(jié)點(diǎn)屬于該社區(qū)的可能性高。本文將節(jié)點(diǎn)i的表示向量yi與社區(qū)r的表示向量hr的內(nèi)積作為兩向量之間相似性的表達(dá)。因此，若節(jié)點(diǎn)i的表示向量與社區(qū)r的表示向量相互正交，即兩者的表示完全不同，那么節(jié)點(diǎn)i屬于社區(qū)r的可能性近乎為零。由于社區(qū)隸屬度矩陣U體現(xiàn)了每個(gè)節(jié)點(diǎn)與各社區(qū)之間的從屬信息，因此本文希望YHT的結(jié)果與社區(qū)隸屬度U盡可能一致，從而設(shè)計(jì)如式（12）所示的目標(biāo)函數(shù)：

基于上述分析，本文在網(wǎng)絡(luò)的微觀結(jié)構(gòu)模型和社區(qū)發(fā)現(xiàn)模型之間建立了紐帶，進(jìn)而挖掘網(wǎng)絡(luò)表示學(xué)習(xí)的過程中的社區(qū)結(jié)構(gòu)信息。最終目標(biāo)函數(shù)如式（13）所示：

其中：參數(shù)β和γ均為非負(fù)值，β用于提取網(wǎng)絡(luò)中蘊(yùn)藏的社區(qū)結(jié)構(gòu)，γ用于調(diào)節(jié)社區(qū)結(jié)構(gòu)信息在網(wǎng)絡(luò)表示學(xué)習(xí)過程中的貢獻(xiàn)大小。通過調(diào)節(jié)這兩個(gè)參數(shù)的值可以適應(yīng)不同的網(wǎng)絡(luò)和不同的應(yīng)用場(chǎng)景。

1.6 模型優(yōu)化

由于式（13）所示的目標(biāo)函數(shù)是非凸的，因此幾乎不可能找到全局最優(yōu)解。為解決該最優(yōu)化問題，本文基于文獻(xiàn)［26］提出一個(gè)能夠保證收斂到局部最優(yōu)解的迭代更新過程。在保持其他參數(shù)不變的情況下，迭代更新每一個(gè)參數(shù)，具體過程如下：

更新H：保持Y、U不變，式（13）中只有最后一項(xiàng)與矩陣H有關(guān)。由文獻(xiàn)［27］所提非負(fù)矩陣分解模型的乘法更新規(guī)則，得到式（14）：

更新U：保持Y、H不變，為更新矩陣U，本文需要解決一個(gè)聯(lián)合矩陣分解問題。由于式（13）中只有最后兩項(xiàng)與矩陣U有關(guān)，因此只需要最小化式（15）所示的損失函數(shù)：

該約束優(yōu)化問題可以通過引入矩陣U的拉格朗日乘數(shù)矩陣Θ構(gòu)造拉格朗日函數(shù)來(lái)解決。拉格朗日函數(shù)如式（17）所示：

對(duì)矩陣U求偏導(dǎo)，得到：

同理，固定矩陣U和H，可得到矩陣Y的更新規(guī)則，如式（20）所示：

上述更新規(guī)則均具有收斂性，通過迭代交替更新矩陣U、H、Y，可以得到網(wǎng)絡(luò)的節(jié)點(diǎn)表示矩陣Y。

PCNE 算法的偽代碼如下所示：

算法1 PCNE 算法

1.7 復(fù)雜度分析

PCNE算法的時(shí)間復(fù)雜度主要取決于式（14）、式（19）和式（20）的矩陣乘法運(yùn)算，它們的時(shí)間復(fù)雜度分別為O(ndk)、O(n2k+ndk)和O(n2d+ndk)，其中：n為節(jié)點(diǎn)數(shù)量；d為節(jié)點(diǎn)表示維數(shù)；k為網(wǎng)絡(luò)中的社區(qū)數(shù)。由于實(shí)際應(yīng)用中滿足k?n，因此PCNE的算法復(fù)雜度為O（dn2）。DeepWalk 的算法復(fù)雜度為O（dnloga n）［16］，Node2vec 的算法復(fù)雜度為O（dn）［17］，算法LINE 的復(fù)雜度為O（dm）［18］，其中m為網(wǎng)絡(luò)中邊的數(shù)量。雖然這些算法的復(fù)雜度比PCNE 算法低，但是DeepWalk 和Node2vec 都是基于隨機(jī)游走的算法，只考慮了節(jié)點(diǎn)的局部鏈接關(guān)系，LINE只考慮了一階、二階信息，這些算法都沒有考慮宏觀的社區(qū)結(jié)構(gòu)信息，而社區(qū)結(jié)構(gòu)信息對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)分析非常重要。PCNE 通過非負(fù)矩陣分解的方式將社區(qū)結(jié)構(gòu)信息融入到網(wǎng)絡(luò)表示學(xué)習(xí)過程中，在后續(xù)網(wǎng)絡(luò)分析任務(wù)中能夠取得比DeepWalk、Node2vec、LINE 更好的效果。

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

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

本文實(shí)驗(yàn)選取公開的真實(shí)網(wǎng)絡(luò)Karate［28］和WebKB 網(wǎng) 絡(luò)［29］的4個(gè)子網(wǎng)絡(luò)（Cornell、Texas、Washington、Wisconsin）作為數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，如表2所示。Karate［30］數(shù)據(jù)集是描述美國(guó)一所大學(xué)空手道俱樂部中34 個(gè)成員之間社會(huì)關(guān)系的網(wǎng)絡(luò)，由34 個(gè)節(jié)點(diǎn)和78 條邊組成，包含2 個(gè)類別標(biāo)簽；Cornell、Texas、Washington、Wisconsin 是WebKB［31］數(shù)據(jù)集的4 個(gè)子網(wǎng)絡(luò)，均包含5 個(gè)類別標(biāo)簽，分別是由美國(guó)4 所大學(xué)的網(wǎng)頁(yè)之間的鏈接關(guān)系構(gòu)建的，Cornell 數(shù)據(jù)集由195 個(gè)節(jié)點(diǎn)和283 條邊組成，Texas 數(shù)據(jù)集由187 個(gè)節(jié)點(diǎn)和289 條邊組成，Washington 數(shù)據(jù)集由230 個(gè)節(jié)點(diǎn)和366 條邊組成，Wisconsin 數(shù)據(jù)集由265 個(gè)節(jié)點(diǎn)和469 條邊組成。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息Table 2 Information of datasets for experiment

2.2 對(duì)比算法與參數(shù)設(shè)置

為驗(yàn)證本文PCNE 算法的有效性，將其與以下5 個(gè)具有代表性的網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行對(duì)比。

1）DeepWalk［16］算法。該算法通過隨機(jī)游走模型將獲取的節(jié)點(diǎn)序列看作文本中的單詞，作為Word2vec算法的輸入，通過Skip-Gram 模型訓(xùn)練得到各節(jié)點(diǎn)的表示。實(shí)驗(yàn)中參數(shù)設(shè)置：每個(gè)節(jié)點(diǎn)采樣的序列數(shù)量為40，節(jié)點(diǎn)序列長(zhǎng)度為40，窗口大小為10。

2）LINE［18］算法。實(shí)驗(yàn)中用LINE1 和LINE2 分別表示基于一階結(jié)構(gòu)相似性的模型和基于二階結(jié)構(gòu)相似性的模型，用LINE 表示基于一階和二階結(jié)構(gòu)相似性的模型。這3 個(gè)算法的參數(shù)設(shè)置為：負(fù)采樣的樣本數(shù)設(shè)為5，學(xué)習(xí)率的初值設(shè)為0.025。

3）Node2vec［17］算法。該算法在DeepWalk 算法的基礎(chǔ)上引入2 個(gè)超參數(shù)p、q以平衡基于深度的隨機(jī)游走策略和基于廣度的隨機(jī)游走策略。Node2vec算法的參數(shù)設(shè)置為p=0.25，q=0.25，其余參數(shù)與DeepWalk 的參數(shù)一致。

為保證實(shí)驗(yàn)的公平性，節(jié)點(diǎn)的表示向量維度都設(shè)置為20 維。本文PCNE 算法的參數(shù)設(shè)置為：β=0.1，γ=0.5。

2.3 實(shí)驗(yàn)結(jié)果及其分析

本文利用節(jié)點(diǎn)分類任務(wù)評(píng)估PCNE 算法的性能。為了執(zhí)行該任務(wù)，將所得到的節(jié)點(diǎn)嵌入向量視為網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的特征作為分類器的輸入，以預(yù)測(cè)節(jié)點(diǎn)的標(biāo)簽。在實(shí)驗(yàn)中，本文采用scikit-learn 包中的一對(duì)多SVM 分類器，在分類器的訓(xùn)練過程中，訓(xùn)練集百分比即訓(xùn)練率A設(shè)置為｛10%，15%，20%，25%，30%｝，其余部分作為測(cè)試集。為確保實(shí)驗(yàn)結(jié)果的穩(wěn)定性和可靠性，對(duì)每個(gè)數(shù)據(jù)集分別進(jìn)行10 次獨(dú)立重復(fù)實(shí)驗(yàn)，最終實(shí)驗(yàn)結(jié)果取10次實(shí)驗(yàn)的Micro-F1值和Macro-F1值的均值。表3～表7 列出了PCNE 和其他5 個(gè)算法在5 個(gè)數(shù)據(jù)集不同訓(xùn)練比例下的實(shí)驗(yàn)結(jié)果，其中加粗?jǐn)?shù)據(jù)表示最優(yōu)?？梢钥闯?，在Karate、Texas和Washington數(shù)據(jù)集上，PCNE算法明顯優(yōu)于其他算法，無(wú)論是以Micro-F1 還是以Macro-F1 為評(píng)價(jià)標(biāo)準(zhǔn)，其在各訓(xùn)練比例下均取得了最高的評(píng)價(jià)得分：節(jié)點(diǎn)分類性能在Micro-F1 上分別比第2名提高了0.96%～9.36%（Karate）、0.77%～3.51%（Texas）和9.95%～13.01%（Washington），在Macro-F1 上分別比第2 名提高了3.02%～11.44%（Karate）、0.4%～5.66%（Texas）和3.82%～5.93%（Washington）。在Cornell和Wisconsin 數(shù)據(jù)集上，PCNE 雖然沒有在所有數(shù)據(jù)上體現(xiàn)出優(yōu)勢(shì)，但在大部分情況下的表現(xiàn)依然具有一定競(jìng)爭(zhēng)力。例如：在Cornell 數(shù)據(jù)集上，PCNE 在節(jié)點(diǎn)分類任務(wù)上得到了最高的Micro-F1，雖在Macro-F1 分?jǐn)?shù)表現(xiàn)略差，但比最高得分僅低了1%左右；而在Wisconsin數(shù)據(jù)集上，其節(jié)點(diǎn)分類性能指標(biāo)Micro-F1 也在各訓(xùn)練率下均取得了最高評(píng)價(jià)得分。因此，從綜合性能上看，PCNE 算法在節(jié)點(diǎn)分類任務(wù)中的表現(xiàn)仍具有較強(qiáng)的競(jìng)爭(zhēng)力。

表3 Karate 數(shù)據(jù)集上的節(jié)點(diǎn)分類性能Table 3 Node classification performance on Karate dataset %

表4 Cornell 數(shù)據(jù)集上的節(jié)點(diǎn)分類性能Table 4 Node classification performance on Cornell dataset %

表5 Texas 數(shù)據(jù)集上的節(jié)點(diǎn)分類性能Table 5 Node classification performance on Texas dataset %

表6 Washington 數(shù)據(jù)集上的節(jié)點(diǎn)分類性能Table 6 Node classification performance on Washington dataset %

表7 Wisconsin 數(shù)據(jù)集上的節(jié)點(diǎn)分類性能Table 7 Node classification performance on Wisconsin dataset %

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

本文PCNE 算法主要包含β、γ、d這3 個(gè)參數(shù)，分別用以調(diào)節(jié)各目標(biāo)對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)的貢獻(xiàn)大小，其中：參數(shù)β控制網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)劃分的質(zhì)量對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)的影響；參數(shù)γ控制社區(qū)結(jié)構(gòu)信息對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)的影響；參數(shù)d為所學(xué)節(jié)點(diǎn)向量表示維數(shù)。為研究這3 個(gè)參數(shù)對(duì)PCNE 算法的影響，分別在Cornell、Texas、Washington 和Wisconsin數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析。

1）在固定向量表示維數(shù)d=100 的情況下，對(duì)其余2 個(gè)參數(shù)的敏感性進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)中將訓(xùn)練比例固定為30%，并設(shè)置參數(shù)β，γ∈{0.1，0.5，1，5，10}。圖2～圖5 分別記錄并反映了不同數(shù)據(jù)集上2 個(gè)參數(shù)對(duì)節(jié)點(diǎn)分類任務(wù)評(píng)價(jià)指標(biāo)Micro-F1 值的影響，可以看出：在4 個(gè)數(shù)據(jù)集上，隨著參數(shù)β和γ的調(diào)整，PCNE 算法表現(xiàn)都較為穩(wěn)定，性能指標(biāo)Micro-F1 在4 個(gè)數(shù)據(jù)集上的波動(dòng)范圍均在可控范圍內(nèi)，分別為2.89%（Cornell）、4.65%（Texas）、3.17%（Washington）和3.36%（Wisconsin）；而從整體看，隨著2 個(gè)參數(shù)的變化，指標(biāo)Micro-F1 變化范圍較小，變化趨勢(shì)較為平緩。

圖2 Cornell 數(shù)據(jù)集上參數(shù)β 和γ 的敏感性Fig.2 Susceptibility of parameters β and γ on Cornell dataset

圖3 Texas 數(shù)據(jù)集上參數(shù)β 和γ 的敏感性Fig.3 Susceptibility of parameters β and γ on Texas dataset

圖4 Washington 數(shù)據(jù)集上參數(shù)β 和γ 的敏感性Fig.4 Susceptibility of parameters β and γ on Washington dataset

圖5 Wisconsin 數(shù)據(jù)集上參數(shù)β 和γ 的敏感性Fig.5 Susceptibility of parameters β and γ on Wisconsin dataset

2）在固定參數(shù)β和γ的情況下，分析表示向量維數(shù)d的敏感性，即d對(duì)節(jié)點(diǎn)分類性能的影響。實(shí)驗(yàn)中訓(xùn)練比例仍固定為30%，并設(shè)置參數(shù)d∈{20，50，100，150，200}。由于在其他數(shù)據(jù)集上也會(huì)出現(xiàn)相似的結(jié)果，因此本文僅展示在數(shù)據(jù)集Texas 和Washington 上的結(jié)果。圖6記錄并反映了在這2個(gè)數(shù)據(jù)集上表示維數(shù)d對(duì)于分類性能評(píng)價(jià)指標(biāo)Micro-F1 的影響，可以看出：無(wú)論是Texas 數(shù)據(jù)集還是Washington 數(shù)據(jù)集，隨著表示維數(shù)d的增加，節(jié)點(diǎn)分類性能指標(biāo)Micro-F1 也隨之增大，當(dāng)d增加到一定數(shù)值后，Micro-F1便趨于穩(wěn)定，再隨著d增大，Micro-F1 反而有所下降。這說(shuō)明在表示維數(shù)較低的情況下，該算法捕獲的網(wǎng)絡(luò)信息較少，隨著表示維數(shù)的增加，算法捕獲網(wǎng)絡(luò)信息的能力有所提高，而選擇太高的維數(shù)又會(huì)因特征過多導(dǎo)致具有重要區(qū)分度的特征的權(quán)重過小從而影響節(jié)點(diǎn)間的差異。因此，對(duì)于Texas和Washington數(shù)據(jù)集而言，節(jié)點(diǎn)表示維數(shù)選取d=100或50 較為合適。

圖6 表示向量維數(shù)d 的敏感性Fig.6 Susceptibility of dimension d for representation vector

3 結(jié)束語(yǔ)

本文提出一種保留社區(qū)結(jié)構(gòu)信息的網(wǎng)絡(luò)表示學(xué)習(xí)算法PCNE。定義網(wǎng)絡(luò)結(jié)構(gòu)的一階相似性和二階相似性，將其作為網(wǎng)絡(luò)的微觀結(jié)構(gòu)信息進(jìn)行建模。同時(shí)對(duì)網(wǎng)絡(luò)中蘊(yùn)含的社區(qū)結(jié)構(gòu)信息進(jìn)行建模，通過非負(fù)矩陣分解的方式得到社區(qū)隸屬度矩陣，基于此提取網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息。將兩者放在一個(gè)統(tǒng)一的框架下進(jìn)行聯(lián)合優(yōu)化，從而得到保留社區(qū)結(jié)構(gòu)信息及微觀結(jié)構(gòu)信息的節(jié)點(diǎn)表示向量。在真實(shí)數(shù)據(jù)集上的節(jié)點(diǎn)分類對(duì)比實(shí)驗(yàn)結(jié)果驗(yàn)證了PCNE 算法的有效性。該算法與DeepWalk、Node2vec、LINE 等算法都是針對(duì)同質(zhì)網(wǎng)絡(luò)進(jìn)行研究（即網(wǎng)絡(luò)中的節(jié)點(diǎn)為同一類型），雖然同質(zhì)網(wǎng)絡(luò)在現(xiàn)實(shí)世界中更廣泛和普遍，但現(xiàn)實(shí)世界中還存在大量的異質(zhì)網(wǎng)絡(luò)（即在同一個(gè)網(wǎng)絡(luò)中存在多種類型的節(jié)點(diǎn)，如評(píng)價(jià)網(wǎng)絡(luò)、購(gòu)物網(wǎng)絡(luò)等）。因此，如何合理高效地將網(wǎng)絡(luò)結(jié)構(gòu)信息融入異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)，將是后續(xù)深入研究的課題。