[發(fā)明專利]一種復(fù)雜網(wǎng)絡(luò)社區(qū)數(shù)量的估計方法

在審

• 申請?zhí)枺?/td>: 201810794522.1
• 申請日: 2018-07-19
• 公開（公告）號: CN109039716A
• 公開（公告）日: 2018-12-18
• 發(fā)明（設(shè)計）人: 杜航原
• 申請（專利權(quán)）人: 山西大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 太原市科瑞達(dá)專利代理有限公司 14101
• 代理人: 李富元

本發(fā)明涉及復(fù)雜網(wǎng)絡(luò)挖掘領(lǐng)域，特別涉及一種復(fù)雜網(wǎng)絡(luò)社區(qū)數(shù)量的估計方法。一種復(fù)雜網(wǎng)絡(luò)社區(qū)數(shù)量估計方法，該復(fù)雜網(wǎng)絡(luò)表示為圖的形式，記作網(wǎng)絡(luò)G(V,E)，網(wǎng)絡(luò)G(V,E)中包含個m網(wǎng)絡(luò)節(jié)點，記作V＝(v₁,v₂,…,v_m)，其中第i個網(wǎng)絡(luò)節(jié)點(1≤i≤m)記作v_i；網(wǎng)絡(luò)節(jié)點之間共形成了n個連接，表現(xiàn)為n條連邊，記作E＝(e₁,e₂,…,e_n)，其中第l條邊(1≤l≤n)記作e_l；確定網(wǎng)絡(luò)G(V,E)中所含社區(qū)數(shù)量及各社區(qū)中心節(jié)點。無需任何先驗信息，能夠充分反映網(wǎng)絡(luò)社區(qū)內(nèi)部稠密和外部稀疏的本質(zhì)結(jié)構(gòu)特征，對于網(wǎng)絡(luò)中社區(qū)數(shù)量的估計精度較高，有利于提高網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的估計性能，對于現(xiàn)實網(wǎng)絡(luò)數(shù)據(jù)分析具有較高實用價值。

技術(shù)領(lǐng)域

本發(fā)明涉及復(fù)雜網(wǎng)絡(luò)挖掘領(lǐng)域，特別涉及一種復(fù)雜網(wǎng)絡(luò)社區(qū)數(shù)量的估計方法。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)一般指節(jié)點數(shù)目眾多、連接關(guān)系復(fù)雜的網(wǎng)絡(luò)。飛速發(fā)展的互聯(lián)網(wǎng)技術(shù)和信息爆 炸式增長，使人類社會步入了網(wǎng)絡(luò)時代，我們的大量生產(chǎn)實踐活動都處于各類復(fù)雜網(wǎng)絡(luò)環(huán)境 中，例如，社會網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)、Internet網(wǎng)絡(luò)等。這些復(fù)雜網(wǎng)絡(luò)中鏈路分 布的不均勻性暗示了網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的存在，大量研究也表明網(wǎng)絡(luò)通常由一些結(jié)構(gòu)明顯的社 區(qū)構(gòu)成。社區(qū)內(nèi)部節(jié)點間連接相對緊密，而社區(qū)間連接比較稀疏。網(wǎng)絡(luò)中的社區(qū)是現(xiàn)實世界 社會關(guān)系的一種映射，社區(qū)發(fā)現(xiàn)的研究工作具有很多現(xiàn)實意義，人們通過挖掘和識別社區(qū)結(jié) 構(gòu)可以了解網(wǎng)絡(luò)中蘊含的豐富內(nèi)容，理解網(wǎng)絡(luò)社團(tuán)組織結(jié)構(gòu)的發(fā)展規(guī)律以及它們之間拓?fù)浣Y(jié) 構(gòu)的相互關(guān)系等。近年來，針對網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題已經(jīng)形成了大量具有代表性的算法，大致 可分為幾類：基于層次聚類的社區(qū)發(fā)現(xiàn)方法，基于優(yōu)化模型的社區(qū)發(fā)現(xiàn)方法，基于圖分割的 社區(qū)發(fā)現(xiàn)方法以及啟發(fā)式方法等。

公開號為CN106453096A的專利《一種動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法及裝置》提供一種動態(tài)網(wǎng) 絡(luò)社區(qū)發(fā)現(xiàn)方法及裝置。該發(fā)明實施例通過獲得的初始網(wǎng)絡(luò)結(jié)構(gòu)，獲取初始網(wǎng)絡(luò)結(jié)構(gòu)中每條 邊對應(yīng)的兩個節(jié)點的相似度，然后基于相似度結(jié)果，獲得兩個節(jié)點屬于同一個社區(qū)的第二概 率，最后將相似度大于第二概率的邊所連接的兩個節(jié)點劃分到同一個社區(qū)。當(dāng)初始網(wǎng)絡(luò)結(jié)構(gòu) 發(fā)生動態(tài)變化后,重新獲得變化后的網(wǎng)絡(luò)結(jié)構(gòu)，將變化后的網(wǎng)絡(luò)結(jié)構(gòu)與初始網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行對比 得到變化節(jié)點集合，對變化節(jié)點集合中的每個點，重新計算變化節(jié)點集合中的每個點與相連 的鄰居網(wǎng)絡(luò)節(jié)點相似度，依據(jù)重新計算的相似度和第一概率，將相似度大于第一概率的兩個 節(jié)點劃分到同一個社區(qū)。更新社區(qū)劃分的結(jié)果，從而發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)社區(qū)。公開號為 CN103778192A的專利《一種復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)方法》公開了一種復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā) 現(xiàn)方法，從包含源節(jié)點的初始社區(qū)出發(fā)通過逐漸擴(kuò)展找到源節(jié)點所隸屬的網(wǎng)絡(luò)局部社區(qū)。其 步驟為：S1初始化核心路徑，將源節(jié)點添加到該路徑；S2對于以核心路徑中最后一個節(jié)點為 中心的鄰域內(nèi)的每個節(jié)點，計算其與最后一個節(jié)點的連通強(qiáng)度值，找到使得連通強(qiáng)度最大的 節(jié)點z；S3判斷節(jié)點z是否在核心路徑中，如果沒包含則將節(jié)點z加入核心路徑，返回步驟 S2；否則對核心路徑中可能存在的多余節(jié)點進(jìn)行過濾；S4將核心路徑中的節(jié)點確定為初始社 區(qū)。公開號為CN103747033A的專利《一種社區(qū)發(fā)現(xiàn)的方法》公開了一種社區(qū)發(fā)現(xiàn)的方法， 包括以下步驟：1)利用MapReduce模型實現(xiàn)并行計算；2)在Map階段，將計算任務(wù)分為N 份，每份計算任務(wù)包括隨機(jī)游走過程和數(shù)據(jù)處理過程，其中通過隨機(jī)游走獲得復(fù)雜網(wǎng)絡(luò)的一 個遍歷節(jié)點序列，通過對遍歷節(jié)點序列進(jìn)行數(shù)據(jù)分析，獲得兩個節(jié)點之間的連接的緊密程度； 3)在Reduce階段，對并行計算的結(jié)果進(jìn)行整合得到節(jié)點之間的連接緊密程度，根據(jù)節(jié)點之 間連接的緊密程度來進(jìn)行社區(qū)發(fā)現(xiàn)；4)對處于社區(qū)重疊部分的節(jié)點進(jìn)行分析，以概率形式對 節(jié)點歸屬于哪個社區(qū)做出描述。