本文關(guān)鍵詞： 動(dòng)態(tài)網(wǎng)絡(luò) 局部?jī)?yōu)先 標(biāo)簽傳播 重疊社團(tuán) 非重疊社團(tuán)　出處：《西安電子科技大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：復(fù)雜網(wǎng)絡(luò)能夠刻畫(huà)現(xiàn)實(shí)世界中的大量現(xiàn)象,對(duì)復(fù)雜網(wǎng)絡(luò)的研究受到了人們?cè)絹?lái)越多的關(guān)注。在現(xiàn)實(shí)世界中,復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)并不是一成不變的,而是隨著時(shí)間的變化而不斷改變,從而形成了動(dòng)態(tài)網(wǎng)絡(luò)。動(dòng)態(tài)網(wǎng)絡(luò)對(duì)于刻畫(huà)隨時(shí)間變化的自然和社會(huì)現(xiàn)象具有極大的潛力,對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的研究具有很強(qiáng)的現(xiàn)實(shí)意義。傳統(tǒng)的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法往往分別對(duì)每一個(gè)時(shí)刻的網(wǎng)絡(luò)快照進(jìn)行聚類,然后分析相鄰時(shí)刻社團(tuán)之間的演化關(guān)系。這種方法的缺點(diǎn)之一就是沒(méi)有考慮動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)序特點(diǎn),聚類僅僅基于單一時(shí)刻網(wǎng)絡(luò)的結(jié)構(gòu),難以刻畫(huà)社團(tuán)的演化特性�；谶@一觀察,本文提出了一種局部?jī)?yōu)先的演化聚類方法LEOD以及一種基于標(biāo)簽傳播的演化聚類算法DLPAE。對(duì)于LEOD,它針對(duì)某個(gè)時(shí)間點(diǎn)的快照網(wǎng)絡(luò),以網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)為中心,首先在該節(jié)點(diǎn)的鄰居網(wǎng)絡(luò)上通過(guò)標(biāo)簽傳播算法檢測(cè)得到Ego社團(tuán)。然后將這些局部Ego社團(tuán)不斷合并,從而得到網(wǎng)絡(luò)的全局社團(tuán)結(jié)構(gòu)。在執(zhí)行社團(tuán)合并的過(guò)程中,通過(guò)引入社團(tuán)相似度和關(guān)聯(lián)度兩個(gè)概念,并利用演化聚類框架,實(shí)現(xiàn)了局部?jī)?yōu)先的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測(cè)與演化分析。在DLPAE中,節(jié)點(diǎn)的社團(tuán)標(biāo)簽由其鄰居節(jié)點(diǎn)投票決定,且每個(gè)鄰居節(jié)點(diǎn)對(duì)該結(jié)點(diǎn)都具有各自的影響力,我們稱之為置信度。在聚類的過(guò)程中,節(jié)點(diǎn)的置信度的計(jì)算不僅要考慮當(dāng)前時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu),同時(shí)需要考慮前一時(shí)刻網(wǎng)絡(luò)的結(jié)構(gòu),從而保證了聚類的時(shí)序特性。同時(shí),對(duì)于每一個(gè)節(jié)點(diǎn),DLPAE計(jì)算其節(jié)點(diǎn)的置信度方差,并按照節(jié)點(diǎn)置信度方差從大到小的順序更新節(jié)點(diǎn)的標(biāo)簽,從而提高社團(tuán)檢測(cè)結(jié)果的穩(wěn)定性與準(zhǔn)確率。在DLPAE中,每個(gè)節(jié)點(diǎn)可以持有一個(gè)或者多個(gè)社團(tuán)標(biāo)簽,該屬性使得DLPAE能夠同時(shí)發(fā)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)中的重疊社團(tuán)與非重疊社團(tuán)。本文在真實(shí)和人工數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)來(lái)評(píng)估本文提出算法的性能。實(shí)驗(yàn)結(jié)果表明,LEOD能夠有效地檢測(cè)出動(dòng)態(tài)網(wǎng)絡(luò)中的重疊社團(tuán)結(jié)構(gòu),發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的信息;而DLPAE能夠同時(shí)檢測(cè)網(wǎng)絡(luò)中的重疊社團(tuán)和非重疊社團(tuán);和同類算法相比,本文提出的算法表現(xiàn)出了較好的性能。
[Abstract]:Complex networks can describe many phenomena in the real world, the research on complex networks have attracted more and more attention. In the real world, the complex network structure is not immutable and frozen, but with the change of time and change, thus forming a dynamic network. The dynamic network for characterization of natural and social phenomena change with time has great potential, has a strong practical significance to research on the dynamic network. The traditional dynamic network community discovery algorithm often separately for each time snapshot of the network clustering, and then analyze the evolutionary relationship between adjacent communities. One of the disadvantages of this method is that there is no consideration of the timing characteristics of dynamic network, clustering only based on the structure of a single network, difficult to characterize the evolution characteristics of society. Based on this observation, this paper proposes a local priority algorithm LEOD clustering method and a DLPAE. clustering algorithm based on evolution of label propagation for LEOD, aiming at a point in time snapshot of the network, with each node in the network as the center, first in the network through the neighbor node label propagation algorithm detected by the Ego society. Then the local Ego community continue to merge in order to get the global community structure of the network. In the implementation process of community integration, through the introduction of community similarity and correlation degree of the two concepts, and using the evolutionary clustering framework, realized the detection and analysis of the dynamic evolution of network community local priority. In DLPAE, nodes of the community label decided by its neighbor nodes and each neighbor vote. The node has its own node influence, we call confidence. In the process of clustering, calculate the confidence of the nodes should not only consider the current network structure, At the same time the need to consider the structure of the former network, thus ensuring the timing characteristics of clustering. At the same time, for each node, the variance of confidence in the calculation of DLPAE, and in accordance with the node reliability variance order from large to small update node labels, so as to improve the stability of community detection results and accuracy. In DLPAE, each node can hold one or more community label, this property makes DLPAE can also find out the overlapping community in dynamic networks and non overlapping community. Based on the real and artificial data sets on a large number of experiments to evaluate the performance of the proposed algorithm. The experimental results show that LEOD can effectively detect the overlapping community structure in dynamic networks, the network is found in the potential information; while DLPAE can simultaneously detect overlapping and non overlapping community network; and compared with other algorithms, this paper proposes The algorithm shows good performance.

【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

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

1 孫鶴立;黃健斌;田勇強(qiáng);宋擒豹;劉懷亮;;Detecting overlapping communities in networks via dominant label propagation[J];Chinese Physics B;2015年01期

2 張長(zhǎng)水;張見(jiàn)聞;;演化數(shù)據(jù)的學(xué)習(xí)[J];計(jì)算機(jī)學(xué)報(bào);2013年02期

，

本文編號(hào)：1468433