發(fā)布時(shí)間：2021-06-07 02:35

　　隨著大數(shù)據(jù)技術(shù)和人工智能技術(shù)的高速發(fā)展,網(wǎng)絡(luò)結(jié)構(gòu)作為一種常用的數(shù)據(jù)結(jié)構(gòu),用于描述現(xiàn)實(shí)世界中實(shí)體之間的復(fù)雜關(guān)系,在許多的領(lǐng)域中已經(jīng)被大量的使用。常見的應(yīng)用包括在網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行社區(qū)檢測,節(jié)點(diǎn)分類,鏈路預(yù)測以及網(wǎng)絡(luò)可視化等等任務(wù)。在工業(yè)界也有著大量的網(wǎng)絡(luò)應(yīng)用,例如在社交網(wǎng)絡(luò)上進(jìn)行詐騙賬戶的判斷等等。但傳統(tǒng)的網(wǎng)絡(luò)數(shù)據(jù)分析方法大都是基于人工定義的網(wǎng)絡(luò)特征。這類方法通常無法很好地適應(yīng)各種下游的網(wǎng)絡(luò)分析任務(wù),同時(shí)有著較高的時(shí)間復(fù)雜度。而本文研究的網(wǎng)絡(luò)表征方法就嘗試解決此類問題。網(wǎng)絡(luò)表征學(xué)習(xí)通過對網(wǎng)絡(luò)中節(jié)點(diǎn)矢量化表征來反映節(jié)點(diǎn)及其拓?fù)涮攸c(diǎn),從而體現(xiàn)現(xiàn)實(shí)中事物之間存在或有可能存在的各種關(guān)系,針對性的解決不同網(wǎng)絡(luò)中不同的網(wǎng)絡(luò)分析任務(wù)。相對于傳統(tǒng)網(wǎng)絡(luò)數(shù)據(jù)分析方法,網(wǎng)絡(luò)表征學(xué)習(xí)使得下游網(wǎng)絡(luò)分析任務(wù)的性能能夠有所提高,同時(shí)還能一定程度上降低復(fù)雜度。本文的工作主要集中在利用復(fù)雜網(wǎng)絡(luò)中的高階結(jié)構(gòu)信息來改進(jìn)目前的網(wǎng)絡(luò)表征算法。目前大多數(shù)網(wǎng)絡(luò)表征學(xué)習(xí)方法主要關(guān)注保持網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特征,即如果兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中距離較近,則它們在表征后的低維空間中的距離也接近。但網(wǎng)絡(luò)中還存在結(jié)構(gòu)等效性,也被稱為節(jié)點(diǎn)角色,例如網(wǎng)絡(luò)中某些節(jié)點(diǎn)之... 

【文章來源】：杭州電子科技大學(xué)浙江省

【文章頁數(shù)】：69 頁

【學(xué)位級別】：碩士

【圖文】：

社區(qū)結(jié)構(gòu)可視化結(jié)構(gòu)等效性可視化

杭州電子科技大學(xué)碩士學(xué)位論文12得網(wǎng)絡(luò)分析的復(fù)雜度得以降低[18,23]。網(wǎng)絡(luò)表征的主要方法就是通過訓(xùn)練出一個(gè)映射函數(shù)，將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)映射為某個(gè)低維向量空間中的點(diǎn)，其目標(biāo)是優(yōu)化這個(gè)映射函數(shù)使得這個(gè)節(jié)點(diǎn)在低維向量空間對應(yīng)向量的幾何關(guān)系能反映出原始網(wǎng)絡(luò)的特征關(guān)系。因此學(xué)習(xí)得到的節(jié)點(diǎn)表征向量可以作為下游機(jī)器學(xué)習(xí)任務(wù)的特征輸入，具體如下圖2.2所示。其中節(jié)點(diǎn)i是網(wǎng)絡(luò)G中的某一個(gè)節(jié)點(diǎn)，同時(shí)假設(shè)網(wǎng)絡(luò)總的節(jié)點(diǎn)總數(shù)為N。進(jìn)過網(wǎng)絡(luò)表征學(xué)習(xí)后，將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)映射成該節(jié)點(diǎn)對應(yīng)的表征向量∈，其中表示表征向量的維數(shù)，通常有，將所有的表征向量組合在一起就得到了網(wǎng)絡(luò)表征矩陣∈×。下一步就開始進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)的實(shí)際應(yīng)用，由于得到的網(wǎng)絡(luò)表征矩陣包含了原始網(wǎng)絡(luò)的特征，同時(shí)又是以矩陣的形式存在，故能直接作為傳統(tǒng)機(jī)器學(xué)習(xí)算法的輸入，例如線性回歸，邏輯回歸等等。圖2.2網(wǎng)絡(luò)表征算法過程圖示進(jìn)一步地，下面用數(shù)學(xué)語言來描述網(wǎng)絡(luò)表征學(xué)習(xí)的過程。已知一個(gè)網(wǎng)絡(luò)數(shù)據(jù)=(,)，網(wǎng)絡(luò)表征學(xué)習(xí)的目的就是找到一個(gè)映射函數(shù)滿足：∈,()→∈，同時(shí)要求以及表征向量能夠保存原始圖數(shù)據(jù)的特征。根據(jù)網(wǎng)絡(luò)表征的具體實(shí)施方法，可以分為三大類：基于矩陣分解的方法（Matrix-Factorizationbasedapproaches），基于網(wǎng)絡(luò)隨機(jī)游走的方法（Random-Walkbasedapproaches），基于深度學(xué)習(xí)的方法（Deep-Learningbasedapproaches）。下面將詳細(xì)介紹各類方法的基本原理并舉例說明。2.3.1基于矩陣分解的方法此類方法首先通過矩陣的形式來表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接[18,19]，經(jīng)常使用的矩陣包括鄰接矩陣，拉普拉斯矩陣，相似度矩陣等等[31,36,37,39,70]。隨后該類方法通過一系列的矩陣運(yùn)算，對使用的矩陣進(jìn)行降維，常用的操作包括：矩陣分解，

燃塾謐勻揮?言處理中的句子（sentence）�；陔S機(jī)游走的網(wǎng)絡(luò)表征方法主要可以分為兩個(gè)步驟：首先通過多次隨機(jī)游走在網(wǎng)絡(luò)上的進(jìn)行連續(xù)的節(jié)點(diǎn)序列采樣，其次將這些采樣得到的節(jié)點(diǎn)序列作為word2vec中的CBOW或skip-gram模型，最后輸出的即是需要的網(wǎng)絡(luò)表征向量。下面以網(wǎng)絡(luò)表征學(xué)習(xí)中的第一個(gè)基于隨機(jī)游走的方法DeepWalk[40]為例，詳細(xì)介紹相關(guān)過程。DeepWalk算法的第一步就是進(jìn)行節(jié)點(diǎn)采樣，具體是在網(wǎng)絡(luò)上每一個(gè)點(diǎn)都進(jìn)行多次重復(fù)且固定長度的隨機(jī)游走，常用的設(shè)置是每個(gè)節(jié)點(diǎn)往前進(jìn)行游走80部步，并且重復(fù)這一過程10次。如圖2.3所示，為網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)為源節(jié)點(diǎn)進(jìn)行隨機(jī)游走的過程�？梢钥闯�，源節(jié)點(diǎn)有5個(gè)鄰居，如果考慮到無權(quán)圖，每個(gè)鄰居被選擇作為下一個(gè)游走序列的概率都是1/5，例如形成節(jié)點(diǎn)序列→的概率就是1/5。如果考慮到有權(quán)圖，相應(yīng)的權(quán)值也能考慮進(jìn)去[6,33]。隨后不斷重復(fù)這個(gè)過程，直到約定的循環(huán)次數(shù)滿足，得到隨機(jī)游走的節(jié)點(diǎn)序列。圖2.3網(wǎng)絡(luò)上隨機(jī)游走過程圖示該算法的第二步是將第一步產(chǎn)生的節(jié)點(diǎn)序列輸入到word2vec中的skip-gram模型中，而skip-gram模型原本用于自然語言處理中產(chǎn)生詞向量（wordembedding），其主要思想是兩個(gè)單詞同時(shí)出現(xiàn)的頻率越高，單詞之間的語義相似性越高。skip-gram模型的主要過程是：通過給定一個(gè)中心詞（centerword），經(jīng)過只含有一個(gè)隱藏層的簡單神經(jīng)網(wǎng)路訓(xùn)練，來最大化其附近的詞，也被稱為上下文（context）。Skip-gram模型的目標(biāo)是以某個(gè)中心詞為條件，最大化中心詞對應(yīng)的上下文出現(xiàn)

【參考文獻(xiàn)】：
期刊論文
[1]網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展[J]. 尹贏,吉立新,黃瑞陽,杜立新.  網(wǎng)絡(luò)與信息安全學(xué)報(bào). 2019(02)
[2]網(wǎng)絡(luò)表示學(xué)習(xí)綜述[J]. 涂存超,楊成,劉知遠(yuǎn),孫茂松.  中國科學(xué):信息科學(xué). 2017(08)
[3]基于核化圖嵌入的最佳鑒別分析與人臉識別[J]. 盧桂馥,林忠,金忠.  軟件學(xué)報(bào). 2011(07)

博士論文
[1]線性圖嵌入算法及其應(yīng)用[D]. 陳江峰.北京交通大學(xué) 2012
[2]基于圖嵌入的特征抽取與人臉識別研究[D]. 萬鳴華.南京理工大學(xué) 2011
[3]智能視頻監(jiān)控中的目標(biāo)識別與異常行為建模與分析[D]. 張一.上海交通大學(xué) 2010

碩士論文
[1]社交網(wǎng)絡(luò)表征算法研究[D]. 石立鵬.太原理工大學(xué) 2018



本文編號：3215668