復(fù)雜網(wǎng)絡(luò)中基于數(shù)據(jù)場的自適應(yīng)聚類算法研究徐翠畢業(yè)論文答辯

1、整理ppt復(fù)雜網(wǎng)絡(luò)中基于數(shù)據(jù)場的復(fù)雜網(wǎng)絡(luò)中基于數(shù)據(jù)場的自適應(yīng)聚類算法研究自適應(yīng)聚類算法研究答答 辯辯 人人: : 指導(dǎo)老師指導(dǎo)老師: : 劉玉華劉玉華 教授教授答辯時間：答辯時間：整理ppt目目 錄錄研究背景與意義1基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)2基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)3結(jié)論與展望4整理ppt研究背景與意義研究背景與意義(1/3)(1/3)圖論圖論隨機(jī)圖理論隨機(jī)圖理論復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)n復(fù)雜網(wǎng)絡(luò)發(fā)展史復(fù)雜網(wǎng)絡(luò)發(fā)展史n復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu) l 簇內(nèi)的節(jié)點(diǎn)邊的連接相互緊密，簇之間節(jié)點(diǎn)邊的連接稀疏n發(fā)現(xiàn)網(wǎng)絡(luò)簇結(jié)構(gòu)的意義發(fā)現(xiàn)網(wǎng)絡(luò)簇結(jié)構(gòu)的意義當(dāng)網(wǎng)絡(luò)復(fù)雜化大規(guī)?；覀兙秃茈y通過肉眼識

2、別出網(wǎng)絡(luò)的簇結(jié)構(gòu)，更難預(yù)測其行為和功能網(wǎng)絡(luò)簇結(jié)構(gòu)的研究在社會學(xué)中的社區(qū)探測、生物學(xué)中新陳代謝功能的理解、互聯(lián)網(wǎng)各大功能的區(qū)分等領(lǐng)域有著廣泛的應(yīng)用計算機(jī)學(xué)院計算機(jī)學(xué)院整理ppt研究背景與意義研究背景與意義(2/3)(2/3)n 復(fù)雜網(wǎng)絡(luò)聚類算法分析復(fù)雜網(wǎng)絡(luò)聚類算法分析圖2.1復(fù)雜網(wǎng)絡(luò)中劃分簇結(jié)構(gòu)的聚類算法分類示意圖整理pptn本文研究內(nèi)容本文研究內(nèi)容l提出節(jié)點(diǎn)的重要性因子的概念l構(gòu)造聚類評價函數(shù)l引入數(shù)據(jù)場拓?fù)鋭輨澐执豯引入節(jié)點(diǎn)的相似度概念l構(gòu)造多目標(biāo)聚類評價函數(shù) 研究背景與意義研究背景與意義(3/3)(3/3)整理ppt 基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(1/6)(

3、1/6)n 算法思想算法思想l指出網(wǎng)絡(luò)中心節(jié)點(diǎn)的評價指標(biāo)適用于聚類算法中初始節(jié)點(diǎn)的選擇，提出了節(jié)點(diǎn)重要性因子的概念l利用物理場拓?fù)鋭莺蚹-means算法的思想成簇l通過構(gòu)造合適的聚類評價函數(shù)來實(shí)現(xiàn)算法的自適應(yīng)性，解決初始簇結(jié)構(gòu)個數(shù)難以抉擇的問題整理ppt基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(2/6)(2/6)n 節(jié)點(diǎn)的重要性因子節(jié)點(diǎn)的重要性因子n 聚類評價函數(shù)的構(gòu)建聚類評價函數(shù)的構(gòu)建l簇內(nèi)相似度(Similarity Within Clusters) ( )( )( )( )CDIiCi CiC i2( )( )11( )inkiiwjijSkxcl 簇間相似度(Sim

4、ilarity Between Clusters) 22( )( )( )(1)11kkijSkccbk kiji l聚類評價函數(shù)( )/ (k 1)( )( )/ (nk)bbwwSkSkSk( )( )1Dd iCin1(1)( )nCijjnCidlog ( )log ( ),( , )0d id jiI i j與j直接相連其他1( , )( )(1)log(1)njII i jC inn度中心化度中心化緊密度緊密度中心化中心化互信息互信息中心化中心化整理ppt基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(3/6)(3/6)n 數(shù)據(jù)場和勢數(shù)據(jù)場和勢l定義1 場強(qiáng)函數(shù)。在數(shù)

5、據(jù)場中，空間中共有n個對象，令x代表對象所處位置，則在該數(shù)據(jù)場中x處對象xi 所產(chǎn)生的勢為： 2( )ixxxiixmel定義2勢函數(shù)。數(shù)據(jù)場是具有疊加性的，因此，任意數(shù)據(jù)對象vjV 的拓?fù)鋭菘啥x為：21( )( )ixxnnxiiiiF xxme整理ppt基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(4/6)(4/6)n算法實(shí)現(xiàn)流程算法實(shí)現(xiàn)流程 按照上面的思想對算法進(jìn)行實(shí)現(xiàn)，可以分為7個步驟，其流程圖如右圖所示圖3.3 本算法流程圖 表3-2 本算法與GN算法復(fù)雜度比較算法 復(fù)雜度說明 GN 算法m為邊數(shù)，n為節(jié)點(diǎn)數(shù) 本算法n為節(jié)點(diǎn)個數(shù) 2()O mn2()O n整理ppt

6、基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(5/6)(5/6)圖3.7 本算法與GN算法準(zhǔn)確度的曲線圖分析仿真結(jié)果可以發(fā)現(xiàn)，整體來看，本算法的準(zhǔn)確度優(yōu)于GN算法，且穩(wěn)定性更好。 n仿真結(jié)果仿真結(jié)果l算法準(zhǔn)確性評估+=16inoutZZ整理pptn仿真結(jié)果仿真結(jié)果l算法有效性評估基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的自適應(yīng)聚類算法實(shí)現(xiàn)(6/6)(6/6)圖3.5 Zachary空手道俱樂部成員關(guān)系網(wǎng)絡(luò)圖 3.6 基于GN算法的聚類結(jié)果圖3.7 基于本文算法的聚類結(jié)果整理ppt基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(1/6)(1/6)n 算法

7、思想算法思想l引入節(jié)點(diǎn)相似度概念來發(fā)現(xiàn)核心外圍結(jié)構(gòu)的網(wǎng)絡(luò)簇結(jié)構(gòu)的中心節(jié)點(diǎn)l利用物理場和k-means算法的思想劃分簇l構(gòu)造多目標(biāo)評價函數(shù)以發(fā)現(xiàn)不同網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，且對各種聚類評價函數(shù)進(jìn)行一個綜合考量整理pptn 節(jié)點(diǎn)相似度的選取節(jié)點(diǎn)相似度的選取基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(2/6)(2/6)( )( )( , )( )( )SauvSu vuv n 簇中心節(jié)點(diǎn)的選取簇中心節(jié)點(diǎn)的選取( )(i, j)sai coreS jSn 多目標(biāo)聚類函數(shù)的構(gòu)造多目標(biāo)聚類函數(shù)的構(gòu)造221111( )( )( )2211(2)1(c)1(c 1)(3)(c)(c 1)

8、ccssccciiccbwbwmmd id ix iQQmmmmxMinMaxCutMinMaxCutxSS(c)max(1)(2)(3),(1)(2),(1)(3),(2)(3)cccccccccFfffffffff1,( )0( ),1,2,30,ccif x ist f iiotherwise 當(dāng)c=1時，規(guī)定 。(1)0F集合中元集合中元素的個數(shù)素的個數(shù)節(jié)點(diǎn)節(jié)點(diǎn)u的鄰的鄰居節(jié)點(diǎn)集合居節(jié)點(diǎn)集合整理ppt基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(3/6)(3/6)n 算法步驟算法步驟Step1 設(shè) core = c1(聚類中心節(jié)點(diǎn)集合，c1為網(wǎng)絡(luò)中度最大的節(jié)

9、點(diǎn))， V1=V - core (聚類中心以外的節(jié)點(diǎn)集合)，c=2 ；Step2 若|core|c， V2=V1 ，轉(zhuǎn) Step3；否則，轉(zhuǎn) Step4；Step3 若V2，則選擇節(jié)點(diǎn)集合V2中度最大的節(jié)點(diǎn)c1 ，V2=V1-c1，對于 任何vcore，計算S(c1, v) 的值，若S(c1, v)且S(c1) ，則將c1作 為一個聚類中心：core=core c1 ，V1=V1 - c1，否則轉(zhuǎn)Step7；整理ppt基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(4/6)(4/6)Step4 計算集合core中c個節(jié)點(diǎn)對集合V1中節(jié)點(diǎn)i的影響度，若存在兩個中心節(jié)點(diǎn)對

10、某節(jié)點(diǎn)i的影響度值相等或小于，則將該節(jié)點(diǎn)i加入到 Temp集中，否則將節(jié)點(diǎn)i加入影響度值最大的中心節(jié)點(diǎn)j所在的簇中； Step5 若Temp ，計算與節(jié)點(diǎn)i (i Temp )相連的d(i) (d(i)為節(jié)點(diǎn)的度數(shù))個節(jié)點(diǎn)與集合core中c個節(jié)點(diǎn)的勢函數(shù)之和，并將節(jié)點(diǎn)i 加入到勢值影響最大的core中的節(jié)點(diǎn)所在的簇中；Step6 計算當(dāng)前簇劃分下的聚類評價函數(shù) F(c)值，c=c+1 ，轉(zhuǎn)Step2；Step7 選擇 F(c)值最大時的簇拓?fù)浣Y(jié)構(gòu)輸出，算法結(jié)束。n 算法步驟算法步驟整理pptl空手道俱樂部網(wǎng)絡(luò)結(jié)果圖4.3 本算法對空手道俱樂部網(wǎng)絡(luò)的劃分結(jié)果示意圖l寬吻海豚家族網(wǎng)絡(luò)圖4.4 寬吻

11、海豚家族網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(5/6)(5/6)n 實(shí)驗結(jié)果分析實(shí)驗結(jié)果分析整理pptn 實(shí)驗結(jié)果分析實(shí)驗結(jié)果分析圖4.5 本算法對寬吻海豚網(wǎng)絡(luò)的劃分結(jié)果圖4.6 GN算法對寬吻海豚網(wǎng)絡(luò)劃分為4個簇結(jié)構(gòu)的結(jié)果基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)基于數(shù)據(jù)場的多目標(biāo)自適應(yīng)聚類算法實(shí)現(xiàn)(6/6)(6/6)整理pptn文章小結(jié)文章小結(jié)l指出網(wǎng)絡(luò)中心節(jié)點(diǎn)的評價指標(biāo)適用于聚類算法中初始節(jié)點(diǎn)的選擇，提出了節(jié)點(diǎn)重要性因子的概念l引入了節(jié)點(diǎn)相似度的概念來挖掘更適合的簇中心節(jié)點(diǎn)l通過構(gòu)造合適的聚類評價函數(shù)來實(shí)現(xiàn)算法的自適應(yīng)性，解決初始簇結(jié)構(gòu)個數(shù)難以

12、抉擇的問題l利用物理場拓?fù)鋭莺蚹-means算法的思想成簇提出了一種新的聚類算法?？偨Y(jié)與展望總結(jié)與展望n 工作展望工作展望l 研究有權(quán)有向的復(fù)雜網(wǎng)絡(luò)聚類l 發(fā)現(xiàn)重疊的簇結(jié)構(gòu)l 盡可能多的考慮節(jié)點(diǎn)的屬性整理ppt在校期間發(fā)表論文在校期間發(fā)表論文n發(fā)表論文：發(fā)表論文：lYuhua Liu, Cui Xu, Ke Xu, Jianzhi Jin. An Improved Clustering Method Based on Data Field. 2013 2nd International Conference on Advanced in Control Engineering and Info

13、rmation Science(CACE-13), atlantis, Hongkong, China, October 12-13, 2013. (EI收錄)lCui Xu, Yuhua Liu, Kaihua Xu and Ke Xu. An Adaptive Clustering Algorithm Based on Data Field in Complex Networks. 2013 Third IEEE International Conference on Information Science and Technology(ICIST 2013), IEEE, Yangzho

14、u, China, March 23-25, 2013. (EI收錄)lKe Xu, Yuhua Liu, Cui Xu, Kaihua Xu. A Cluster-based and Range free MDS-MAP Location Scheme in WSN. 3rd International Conference on Computer Engnieering and Network(CENet 2013), Springer, Shanghai, China, July 20-21, 2013. (EI收錄)lDi Zhang, Yuhua Liu, Cui Xu and Yo

15、ngqiang Qi. One OCDMA PON System with 2D Multi-Length Two-Weight CHPCs. Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation(ISCCCA-13), atlantis, Taiyuan, China, April 6-7, 2013. (EI收錄)lYuhua Liu, Zhenrong Luo, Ke Xu and Cui Xu. The Research of Routing A

16、lgorithm Based on Shortest Path Tree in WSNs. 2013 International Conference on Computer Science, Electronic Technology and Intelligent System(CSETIS 2013), atlantis, Hangzhou, China, March 22-23, 2013. (EI收錄)lYuhua Liu, Jianzhi Jin, Yi Zhang and Cui Xu. A New Clustering Algorithm Based on Data Field in Complex Networks. The Journal of Supercomputing, Springer, Vol. 67, No. 3, March, 2014, pp.723-737. (SCI收錄)l劉玉華, 張翼, 徐翠徐翠, 晉建志. 一種基于數(shù)據(jù)場的復(fù)雜網(wǎng)絡(luò)聚類算法. 計算機(jī)科學(xué). 2013, 40(11):70-73.l劉玉華, 鄭梅容,許凱華, 徐翠徐翠. 基于耦合系數(shù)的無標(biāo)度網(wǎng)絡(luò)模型 (BA-S)的中心化研究. 計算機(jī)科