[發明專利]一種基于Memetic算法的網絡表示學習方法

在審

• 申請號: 201811598872.7
• 申請日: 2018-12-26
• 公開（公告）號: CN109740722A
• 公開（公告）日: 2019-05-10
• 發明（設計）人: 公茂果;陳程;王善峰;解宇;武越;張明陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06K9/62
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 孫雅靜

本發明公開一種基于Memetic算法的網絡表示學習方法，包括：根據網絡節點個數n和向量維度d隨機產生實數編碼個體組成初始種群P₀；評價初始種群P₀實數編碼個體的適應度函數值；采用Memetic算法、以實數編碼個體的適應度函數值為依據對初始種群P₀每個實數編碼個體進行迭代優化；將迭代優化后種群中適應度函數值最高的實數編碼個體輸出作為網絡節點的表示向量集合；所述的迭代優化包括依次對初始種群P₀中的實數編碼個體進行交叉概率迭代優化、種群隨機數的變異概率迭代優化和局部搜索迭代優化；實驗結果表明，本發明能夠有效的將網絡結構信息，特別是社區結構信息編碼到表示向量中，可用于節點分類、社區檢測和可視化等任務。

技術領域

本發明屬于社會網絡計算及表示學習技術領域，特別涉及一種基于Memetic算法的網絡表示學習方法，可用于節點分類、社區檢測和可視化等任務。

背景技術

網絡表示學習是將網絡中每個節點嵌入到低維稠密的向量空間，從而得到網絡的向量表示的一種技術。由于傳統的網絡表示方法，比如鄰接矩陣，具有稀疏性和難以反映節點間潛在關系的缺點，所以網絡表示學習技術日益受到相關專家學者們的關注。與傳統的網絡表示相比，通過保存網絡的拓撲結構信息，將網絡嵌入到低維稠密的向量空間得到的網絡表示更加有意義，并且能廣泛應用于基于向量輸入的各種復雜網絡分析模型，比如節點可視化、節點分類和社區檢測等任務。

現有的網絡表示學習技術的一般思想是保持網絡結構的拓撲性，Bryan Perozzi等人提出了一種基于SkipGram模型和隨機游走的網絡表示學習方法DeepWalk，參見Perozzi B,Al-Rfou R,Skiena S,“DeepWalk:online learning of socialrepresentations,”AcmSigkdd International Conference on Knowledge Discovery&Data Mining.ACM,2014。DeepWalk利用隨機游走來獲得節點序列，以此當作詞序列，然后利用SkipGram模型來學得網絡的表示向量。Aditya Grover等人進一步擴展了DeepWalk采集節點序列的方式，通過引入兩個參數使得隨機游走方式具有寬度優先搜索和深度優先搜索的特性，具體參見Grover A,Leskovec J,“node2vec:Scalable Feature Learning forNetworks,”AcmSigkdd International Conference on Knowledge Discovery&DataMining.ACM,2016。這些技術只關注學得的網絡表示向量保持網絡中節點的一階、二階等低階相似度；然后利用現有的常見的機器學習方法進行網絡分析任務，如支持向量機進行節點分類。但是這種方法得到網絡表示沒有明顯的區分性，即類間距離小，這會增加后續模型分析網絡的難度，并且隨機游走這種線性的序列采集方式使得這些方法難以保持網絡節點的非線性特征，比如網絡的社區性。

由于上述網絡表示學習方法只考慮了低階相似度，學得的表示向量沒有明顯的區分性，致使在網絡分析任務上表現具有局限性。因此，研究一種使得網絡表示更加具有區分性的無監督的網絡表示學習方法是本技術領域科技人員的當務之急。

發明內容

本發明的目的在于針對上述已有技術的不足，提出一種基于Memetic算法的網絡表示學習方法，以增強網絡表示向量的區分性，保存網絡的社區結構特征，擴展網絡表示學習算法的應用范圍。

為實現上述目的，本發明的技術方案包括如下：

一種基于Memetic算法的網絡表示學習方法，包括：

步驟一：輸入描述網絡節點之間連接信息的鄰接矩陣A，網絡節點個數為n，向量維度為d；根據網絡節點個數n和向量維度d隨機產生實數編碼個體組成初始種群P₀；