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

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

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

【學位級別】：碩士

【圖文】：

社區(qū)結構可視化結構等效性可視化

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

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

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

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

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



本文編號：3215668