現(xiàn)實(shí)生活中許多系統(tǒng)可以表示成復(fù)雜網(wǎng)絡(luò),如社會關(guān)系網(wǎng)、蛋白質(zhì)互作用網(wǎng)、交通運(yùn)輸網(wǎng)等,復(fù)雜網(wǎng)絡(luò)分析在社會學(xué),生物學(xué)等領(lǐng)域有著廣泛的應(yīng)用。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要特征之一,即一個(gè)網(wǎng)絡(luò)可以分成若干個(gè)社區(qū),每個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)之間連接相對緊密,各社區(qū)間的節(jié)點(diǎn)連接相對稀疏。設(shè)計(jì)有效的社區(qū)發(fā)現(xiàn)算法可以發(fā)現(xiàn)社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、生物網(wǎng)絡(luò)中的蛋白質(zhì)功能模塊等,有助于深入研究各種類型復(fù)雜網(wǎng)絡(luò)的功能模塊及其演化特征,對準(zhǔn)確地理解并分析復(fù)雜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)及動(dòng)力學(xué)特性具有十分重要的理論意義和應(yīng)用價(jià)值。針對復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題,本文主要包括以下兩方面內(nèi)容:（1）對網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似性進(jìn)行合理度量是社區(qū)發(fā)現(xiàn)的核心問題。針對此,給出了一種基于節(jié)點(diǎn)間點(diǎn)不重復(fù)路徑的節(jié)點(diǎn)相似性指標(biāo),以此為基礎(chǔ),提出了一種基于節(jié)點(diǎn)間路徑度量的圖聚類算法（a graph clustering algorithm based on local paths between nodes in complex networks,PGC）,包括節(jié)點(diǎn)相似性計(jì)算、中心節(jié)點(diǎn)選擇、初始社區(qū)劃分和社區(qū)優(yōu)化四個(gè)主要過程。采用節(jié)點(diǎn)間點(diǎn)不重復(fù)路徑對節(jié)點(diǎn)相似性進(jìn)行度量... 

【文章來源】：山西大學(xué)山西省

【文章頁數(shù)】：67 頁

【學(xué)位級別】：碩士

【部分圖文】：

v和v間的點(diǎn)重復(fù)路徑={,,}Pvvvvvv

ij所以，當(dāng)iv 和jv 在 G 中不存在連邊時(shí)，iv 和jv 間不存在長度為 3 的點(diǎn)重復(fù)路徑。綜合情形 1 和情形 2，可得(3)(3)(3)1, ( ), ( )ij i j i jijij i jd d vv E Gavv E G ，其中(3)ija 表示節(jié)iv 和jv 間所有長度為 3 的路徑數(shù)，(3)ij 表示iv 和jv 間所有長度為 3 的點(diǎn)不重復(fù)路徑。證畢由引理 3 可得，節(jié)點(diǎn)iv 和jv 間的長度為 3 的點(diǎn)重復(fù)路徑的數(shù)目與它們的度成正。節(jié)點(diǎn)度越大，經(jīng)過該節(jié)點(diǎn)的點(diǎn)重復(fù)路徑越多，這導(dǎo)致采用 Katz、LP、LS 等指標(biāo)節(jié)點(diǎn)相似性進(jìn)行度量時(shí)，網(wǎng)絡(luò)中的大度節(jié)點(diǎn)通常與其鄰域中節(jié)點(diǎn)的相似性偏高。如 3.2 所示網(wǎng)絡(luò) G，根據(jù)公式(2.8)，有7 8 7 15(v , v ) 4.6 (v , v) 4.2LS LSS S ，在 LS 指標(biāo)，由于計(jì)算了由大度節(jié)點(diǎn)8v 引起的較多點(diǎn)重復(fù)路徑，節(jié)點(diǎn)7v 傾向于與度數(shù)較大的節(jié)8v 有更高的相似性。而實(shí)際上，邊7 8v v 為圖 G 的橋，具有較高的邊介數(shù)。通常由介較高的邊連接的兩個(gè)節(jié)點(diǎn)更傾向于分屬不同的社區(qū)[20]。

選擇 k=2 作為最終的社區(qū)個(gè)數(shù)。圖 3.3 ( )h hP c 隨 h 變化的曲線圖3.3 算法描述選擇社區(qū)中心之后，根據(jù)定義 1 給出的相似性指標(biāo) SLP，計(jì)算網(wǎng)絡(luò)中的其它非中心節(jié)點(diǎn)與 k 個(gè)社區(qū)中心的相似性，并將其分配至與其相似性最高的中心節(jié)點(diǎn)所在社區(qū)中，得到初始社區(qū)劃分結(jié)果。為了對算法劃分社區(qū)的質(zhì)量進(jìn)行監(jiān)督，選擇基于互補(bǔ)熵的社區(qū)評價(jià)函數(shù)[30]作為優(yōu)化目標(biāo)對當(dāng)前社區(qū)劃分結(jié)果 進(jìn)行評價(jià)，如公式(2.10)所示。算法迭代進(jìn)行，直至 F( )趨于穩(wěn)定，得到最終的社區(qū)發(fā)現(xiàn)結(jié)果。本節(jié)給出基于“中心-擴(kuò)展”策略的圖聚類方法 PGC，包括節(jié)點(diǎn)相似性計(jì)算、中


本文編號：2984388