呂少卿,趙雪莉,張 潘,任新成
(1.西安郵電大學(xué) 通信與信息工程學(xué)院,西安 710121;2.陜西省信息通信網(wǎng)絡(luò)及安全重點(diǎn)實(shí)驗(yàn)室,西安 710121;3.陜西省能源大數(shù)據(jù)智能處理省市共建重點(diǎn)實(shí)驗(yàn)室,陜西延安 716000)
復(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 列出了本文PCNE 算法使用的符號(hào)及定義。
表1 符號(hào)定義Table 1 Definition of symbols
本小節(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|。
給定網(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
本文通過保留網(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)之間的嵌入差異:
網(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)造:
為了將網(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)景。
由于式(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 算法
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 更好的效果。
本文實(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
為驗(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。
本文利用節(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 %
本文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
本文提出一種保留社區(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ù)深入研究的課題。