本文選題：動態(tài)社區(qū)發(fā)現(xiàn) + 隨機(jī)游走　； 參考：《蘭州交通大學(xué)》2017年碩士論文

【摘要】：現(xiàn)實(shí)世界中的許多系統(tǒng)均可以抽象成復(fù)雜網(wǎng)絡(luò)的形式,而且復(fù)雜網(wǎng)絡(luò)還普遍存在著社區(qū)結(jié)構(gòu)特征。社區(qū)結(jié)構(gòu)為復(fù)雜網(wǎng)絡(luò)研究提供了可行的切入點(diǎn),它可為復(fù)雜網(wǎng)絡(luò)的其它研究提供重要的基礎(chǔ),相應(yīng)地社區(qū)發(fā)現(xiàn)已成為復(fù)雜網(wǎng)絡(luò)研究的主要熱點(diǎn)之一。傳統(tǒng)的社區(qū)發(fā)現(xiàn)研究主要關(guān)注靜態(tài)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn),但在實(shí)際場景中社區(qū)隨時間變化的情況更為常見,且目前多數(shù)動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究主要是針對非加權(quán)網(wǎng)絡(luò),而權(quán)值的缺失會造成網(wǎng)絡(luò)劃分的失真,因此展開動態(tài)加權(quán)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)的研究顯得尤為重要。論文以動態(tài)加權(quán)網(wǎng)絡(luò)為研究對象,針對傳統(tǒng)譜聚類算法相似矩陣構(gòu)建過程較復(fù)雜的問題,引入capocci算法和隨機(jī)游走理論,設(shè)計(jì)并實(shí)現(xiàn)了一種加權(quán)譜聚類動態(tài)社區(qū)發(fā)現(xiàn)算法,最后采用實(shí)際數(shù)據(jù)集驗(yàn)證了該算法的有效性。主要研究內(nèi)容包括:1.綜述了動態(tài)社區(qū)發(fā)現(xiàn)的相關(guān)概念,總結(jié)譜聚類算法以及圖分割理論的基本思想,研究了Yun Chi進(jìn)化譜聚類算法,并分析了該算法在構(gòu)建加權(quán)網(wǎng)絡(luò)的相似矩陣時存在的不足。2.針對Yun Chi算法存在的問題,分析了標(biāo)準(zhǔn)割函數(shù)、馬爾科夫鏈以及轉(zhuǎn)移概率矩陣之間的關(guān)系,利用這些關(guān)系優(yōu)化了Yun Chi算法的求解目標(biāo)函數(shù),使其能夠直接處理加權(quán)鄰接矩陣,從而簡化了算法的流程。3.設(shè)計(jì)實(shí)現(xiàn)了一種加權(quán)譜聚類動態(tài)社區(qū)發(fā)現(xiàn)算法,并基于中科院自動化所發(fā)布的合作網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了對比實(shí)驗(yàn),結(jié)果驗(yàn)證了該算法的有效性。
[Abstract]:Many systems in the real world can be abstracted into the form of complex networks. Community structure provides a feasible entry point for the study of complex networks, which can provide an important basis for other studies of complex networks. Accordingly, community discovery has become one of the main hotspots in the research of complex networks. Traditional community discovery studies focus on community discovery in static networks, but community changes over time are more common in actual scenarios, and most of the current dynamic network community discovery studies focus on unweighted networks. The lack of weights can lead to the distortion of network division, so it is very important to study community discovery in dynamic weighted networks. Aiming at the complex process of constructing similarity matrix of traditional spectral clustering algorithm, capocci algorithm and random walk theory are introduced to design and implement a weighted spectral clustering dynamic community discovery algorithm. Finally, the validity of the algorithm is verified by the actual data set. The main research contents include: 1. This paper summarizes the related concepts of dynamic community discovery, summarizes the basic ideas of spectral clustering algorithm and graph segmentation theory, studies the Yun Chi evolutionary spectral clustering algorithm, and analyzes the shortcomings of this algorithm in constructing the similarity matrix of weighted networks. Aiming at the problems of Yun Chi algorithm, the relations among standard cut function, Markov chain and transition probability matrix are analyzed. By using these relations, the solving objective function of Yun Chi algorithm is optimized, which enables it to deal with the weighted adjacency matrix directly. Thus simplifying the algorithm flow. 3. A dynamic community discovery algorithm based on weighted spectral clustering is designed and implemented. The validity of the algorithm is verified by a comparative experiment based on the cooperative network data set published by the automation institute of the Chinese Academy of Sciences.
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.13;O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 潘劍飛;徐麗麗;董一鴻;;動態(tài)社區(qū)演化研究進(jìn)展[J];電信科學(xué);2017年01期

2 國琳;左萬利;彭濤;;基于隸屬度的社會化網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)及動態(tài)集群演化分析[J];電子學(xué)報(bào);2016年03期

3 高虎;陳宏強(qiáng);馮志;;基于GIS的復(fù)雜網(wǎng)絡(luò)特性在城市道路研究分析中的應(yīng)用[J];測繪技術(shù)裝備;2015年04期

4 李志明;;復(fù)雜網(wǎng)絡(luò)在無線網(wǎng)絡(luò)中的應(yīng)用研究[J];河西學(xué)院學(xué)報(bào);2015年05期

5 王莉;程學(xué)旗;;在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J];計(jì)算機(jī)學(xué)報(bào);2015年02期

6 盧華玲;周燕;唐建波;;基于復(fù)雜網(wǎng)絡(luò)的虛擬品牌社區(qū)演化研究[J];圖書館學(xué)研究;2014年13期

7 李建元;周腳根;關(guān)佶紅;周水庚;;譜圖聚類算法研究進(jìn)展[J];智能系統(tǒng)學(xué)報(bào);2011年05期

8 蔡曉妍;戴冠中;楊黎斌;;譜聚類算法綜述[J];計(jì)算機(jī)科學(xué);2008年07期

相關(guān)博士學(xué)位論文 前1條

1 徐曉華;圖上的隨機(jī)游走學(xué)習(xí)[D];南京航空航天大學(xué);2008年

相關(guān)碩士學(xué)位論文 前1條

1 吳永亮;異質(zhì)網(wǎng)絡(luò)中重疊社區(qū)發(fā)現(xiàn)技術(shù)研究[D];蘭州交通大學(xué);2016年

，

本文編號：1921211