本文選題：復雜網絡　切入點：社區(qū)發(fā)現　出處：《吉林大學》2016年博士論文

【摘要】：現實世界的許多復雜系統(tǒng)都可以表示成復雜網絡,如社會網、生物網、技術網等。社區(qū)結構是復雜網絡中的一個重要屬性,它表明網絡中的節(jié)點具有集聚化特性。網絡具有的復雜性、多樣性、動態(tài)性等特點會使發(fā)現社區(qū)結構的研究工作變得更加復雜,也使該工作成為最具挑戰(zhàn)的課題任務之一。檢測社區(qū)結構可用于分析和理解網絡中的結構功能、發(fā)現網絡中的隱含模式、預測網絡的動態(tài)發(fā)展規(guī)律,乃至對于網絡的認知和利用具有非常重要的意義。在解決社會網絡、無線傳感器網絡、郵件交互網絡等實際問題中,社區(qū)發(fā)現的研究工作是網絡分析中的重要組成部分。雖然目前諸多社區(qū)結構挖掘算法已經被廣泛應用于網絡社區(qū)發(fā)現問題,但如何能夠在不需要先驗知識的基礎上,既降低算法的復雜度又提高社區(qū)劃分結果的準確度,一直是社區(qū)發(fā)現算法不斷發(fā)展和研究的方向。本文研究復雜網絡中的社區(qū)發(fā)現、重疊社區(qū)發(fā)現、動態(tài)社區(qū)發(fā)現三個方面的內容,主要貢獻與創(chuàng)新工作如下:1.為了解決基于模塊度優(yōu)化的社區(qū)發(fā)現方法存在的分辨率限制問題,本文將社區(qū)發(fā)現看做是一個多目標優(yōu)化問題,首次利用布谷鳥算法求解社區(qū)發(fā)現問題并提出了一種基于多目標布谷鳥優(yōu)化的社區(qū)發(fā)現方法(MDCL)。該算法通過同時優(yōu)化兩個互相沖突的目標函數Negative Ratio Association和Ratio Cut來控制網絡中的社區(qū)規(guī)模,同時,MDCL設計了滿足要求的離散形式位置更新公式和放棄操作算子,并采用局部搜索和克隆策略提高種群質量。在人工和真實網絡數據集上驗證了算法的有效性,實驗結果表明MDCL方法相比于其他算法可以挖掘出高質量的社區(qū)結構。2.本文提出了一種基于蟻群算法的重疊社區(qū)發(fā)現方法(Ant CBO)。該算法主要包括螞蟻初始化、螞蟻移動和后處理三個模塊。算法在初始化階段確定螞蟻位置和各節(jié)點中的初始標簽;在移動階段,通過螞蟻在轉移機制的啟發(fā)下自由移動實現各個節(jié)點中標簽信息的更新,當終止條件滿足時各個節(jié)點會得到相應的標簽序列;最后,通過后處理策略得到網絡中的重疊社區(qū)劃分結果。另外,本文提出了一種求解轉移概率的啟發(fā)式信息計算方法。在人工和真實數據集上的實驗結果均表明,相比于其他算法,Ant CBO算法具有更好的性能,可以更加準確地檢測出網絡中重疊節(jié)點和重疊社區(qū)結構。3.為解決基于邊聚類算法導致社區(qū)結構出現節(jié)點過度重疊的問題,同時為有效地提高重疊社團劃分的準確性,本文提出了一種基于密度邊聚類的重疊社區(qū)發(fā)現算法(DBLC)。該算法在邊擴展階段基于核心密度可達概念對核心邊進行初始聚類得到若干邊社團,然后通過更新策略將未分類的邊劃分至與之相似度最高的社團中。同時,我們提出了一種計算邊與邊相似度的方法�；谌斯祿驼鎸嵕W絡數據集上的實驗結果表明,該算法在挖掘重疊社區(qū)結構和重疊節(jié)點方面性能表現更優(yōu)。4.靜態(tài)網絡中的社區(qū)發(fā)現研究工作會忽略網絡的動態(tài)性,難以識別網絡中社區(qū)結構的變化,而動態(tài)社區(qū)發(fā)現算法研究可有效地檢測動態(tài)社區(qū)結構。本文提出了一種基于多目標生物地理優(yōu)化動態(tài)社區(qū)發(fā)現算法(MBBOD)。該方法采用分解機制同時優(yōu)化分別表示快照代價的目標函數模塊度和表示時間代價的目標函數標準化互信息,提出了一種新的排序策略并利用該策略比較生物地理優(yōu)化算法中棲息地質量優(yōu)劣進而獲取物種數目。另外,本文設計了針對特定問題的遷移模型和變異模型以提高算法的有效性。實驗結果表明,MBBOD算法與DYNMOGA和Facet Net算法相比具有較好的性能,可以得到準確度更高的社區(qū)劃分結果。5.基于演化聚類框架的動態(tài)社區(qū)發(fā)現算法通過優(yōu)化由快照代價和時間代價組成的代價函數實現動態(tài)社區(qū)發(fā)現。為了避免人為輸入參數控制快照代價和時間代價的權重限制算法性能和影響優(yōu)化結果精準性的問題,本文將動態(tài)社區(qū)發(fā)現問題轉換成多目標優(yōu)化問題,提出了一種基于多目標布谷鳥優(yōu)化的動態(tài)社區(qū)發(fā)現算法(MODCS)。算法首先采用基于有序鄰居列表的編碼方式對鳥巢進行編碼,重點在離散布谷鳥框架中重定義了符合社區(qū)發(fā)現問題的離散位置更新策略和放棄操作算子,最后結合擁擠距離和非占優(yōu)排序機制實現動態(tài)社區(qū)發(fā)現。在人工數據集和真實數據集上的實驗結果表明,MODCS算法可有效地挖掘出每個時刻的高質量的網絡社區(qū)結構。
[Abstract]:......
【學位授予單位】：吉林大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP18;O157.5

【相似文獻】

相關期刊論文 前10條

1 韓進;;算法淺說[J];廣西教育學院學報;2008年04期

2 王貴竹;一種產生單向分解值的算法[J];安徽大學學報(自然科學版);2001年03期

3 高廣尚;蔣泰;;ISO 18000-6 Type C中的防沖突機制分析[J];廣西科學院學報;2008年04期

4 石連栓;離散變量結構優(yōu)化設計算法研究綜述[J];天津職業(yè)技術師范學院學報;2001年01期

5 張宏哲;;FFT算法的一種改進[J];長安大學學報(自然科學版);1988年01期

6 范曉平;;最小生成樹(MST)的“分級選樹”算法[J];西南交通大學學報;1983年01期

7 劉志奎;劉慶民;;零件矩形邊界框區(qū)域自動提取算法及應用[J];光學技術;2012年02期

8 戴光明;張全元;包建全;;一種車型特征提取的新算法[J];武漢大學學報(信息科學版);2009年10期

9 李躍波;王麗珍;;AUCBoost算法處理不平衡分類問題[J];云南大學學報(自然科學版);2007年S2期

10 顧翔,徐克t，

本文編號：1686836