[發(fā)明專利]一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201811277145.0
• 申請(qǐng)日: 2018-10-30
• 公開（公告）號(hào): CN109389179A
• 公開（公告）日: 2019-02-26
• 發(fā)明（設(shè)計(jì)）人: 胡學(xué)鋼;何偉;楊恒宇
• 申請(qǐng)（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 合肥市浩智運(yùn)專利代理事務(wù)所(普通合伙) 34124
• 代理人: 丁瑞瑞

本發(fā)明公開了一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分方法，方法包括：1)、獲取待劃分網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)在當(dāng)前時(shí)刻的前一時(shí)刻的標(biāo)簽值；2)、判斷振蕩次數(shù)是否大于預(yù)設(shè)閾值；3)、若否，獲取節(jié)點(diǎn)的第一偏好權(quán)值；將第一偏好值作為節(jié)點(diǎn)的當(dāng)前偏好值；4)、若是，獲取節(jié)點(diǎn)的第二偏好權(quán)值；將第二偏好值作為節(jié)點(diǎn)的當(dāng)前偏好值；5)、更新當(dāng)前時(shí)刻節(jié)點(diǎn)的標(biāo)簽值；返回執(zhí)行步驟2)，直至待劃分網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)都被劃分到由標(biāo)簽值相同的節(jié)點(diǎn)組成的社團(tuán)中。本發(fā)明實(shí)施例還提供了一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分裝置。應(yīng)用本發(fā)明實(shí)施例，可以提高社團(tuán)劃分的準(zhǔn)確度。

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

本發(fā)明涉及一種社團(tuán)劃分方法及裝置，更具體涉及一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分方法及裝置。

背景技術(shù)

現(xiàn)實(shí)世界中存在著大量的復(fù)雜網(wǎng)絡(luò)系統(tǒng)，如Internet、社交網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)等。在復(fù)雜網(wǎng)絡(luò)中，網(wǎng)絡(luò)的各個(gè)組成個(gè)體之間的關(guān)系不同，因此，個(gè)體之間的連接關(guān)系存在親疏有別的現(xiàn)象，因此，復(fù)雜網(wǎng)絡(luò)會(huì)分成存在界限的社團(tuán)，根據(jù)復(fù)雜網(wǎng)絡(luò)被劃分成的社團(tuán)可以對(duì)網(wǎng)絡(luò)中各個(gè)個(gè)體之間的相互關(guān)系進(jìn)行研究。社團(tuán)結(jié)構(gòu)描述了網(wǎng)絡(luò)中的一種非均質(zhì)連接特性，即網(wǎng)絡(luò)由不同的節(jié)點(diǎn)簇所構(gòu)成，簇內(nèi)節(jié)點(diǎn)連接相對(duì)緊密，而簇間的連接相對(duì)稀疏。作為介于網(wǎng)絡(luò)微觀結(jié)構(gòu)和宏觀結(jié)構(gòu)之間的中尺度結(jié)構(gòu)，社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)中個(gè)體行為與整體功能之間的橋梁，對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能分析具有重要意義。社團(tuán)劃分旨在揭示網(wǎng)絡(luò)中所蘊(yùn)含的社團(tuán)結(jié)構(gòu)，有助于對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的分析、對(duì)網(wǎng)絡(luò)功能的推斷、對(duì)網(wǎng)絡(luò)拓?fù)涞膬?yōu)化，并指導(dǎo)現(xiàn)實(shí)網(wǎng)絡(luò)結(jié)構(gòu)的識(shí)別、構(gòu)建和預(yù)測(cè)，因而是理解和探索網(wǎng)絡(luò)結(jié)構(gòu)與功能的關(guān)鍵問題。

傳統(tǒng)的社團(tuán)劃分大多針對(duì)具有固定拓?fù)浣Y(jié)構(gòu)的靜態(tài)網(wǎng)絡(luò)，實(shí)際網(wǎng)絡(luò)往往會(huì)隨著時(shí)間推移發(fā)生改變。例如，在科學(xué)家合作網(wǎng)絡(luò)中，新的研究者不斷加入，已有研究者也會(huì)退出；不同領(lǐng)域的研究者會(huì)開展新的合作，原有合作也可能停止。這種變化導(dǎo)致網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的持續(xù)演化，傳統(tǒng)的靜態(tài)方法無法用于動(dòng)態(tài)性分析。為了對(duì)動(dòng)態(tài)變化的復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，可以采用LPA(Label Propagation Algorithm，標(biāo)簽傳播算法)算法對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分。在LPA算法中，將復(fù)雜網(wǎng)絡(luò)抽象成一個(gè)由節(jié)點(diǎn)相互連接而成的網(wǎng)絡(luò)，復(fù)雜網(wǎng)絡(luò)中的每一個(gè)個(gè)體被抽象為一個(gè)節(jié)點(diǎn)，個(gè)體之間的連接關(guān)系被抽象為邊；然后，為每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)不同的標(biāo)簽值，而且，每一個(gè)節(jié)點(diǎn)相對(duì)于其他節(jié)點(diǎn)具有偏好權(quán)重，然后將某一節(jié)點(diǎn)的標(biāo)簽值更新為其鄰居節(jié)點(diǎn)中偏好權(quán)值最高的節(jié)點(diǎn)的標(biāo)簽值；循環(huán)往復(fù)，進(jìn)而將將復(fù)雜網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)的標(biāo)簽值進(jìn)行了更新，如果有多個(gè)標(biāo)簽滿足此條件，將這些標(biāo)簽作為候選，從中隨機(jī)抽取一個(gè)作為節(jié)點(diǎn)的更新標(biāo)簽。如果節(jié)點(diǎn)當(dāng)前的標(biāo)簽在候選集中，則節(jié)點(diǎn)保持當(dāng)前標(biāo)簽。每次迭代中，節(jié)點(diǎn)的更新順序完全隨機(jī)。在整個(gè)標(biāo)簽擴(kuò)散，也稱為標(biāo)簽傳播的過程中，連接緊密的節(jié)點(diǎn)標(biāo)簽通常會(huì)快速趨于一致。標(biāo)簽擴(kuò)散算法具有時(shí)間復(fù)雜度低、準(zhǔn)確率較高、便于并行化等優(yōu)點(diǎn)。

但是，現(xiàn)有的標(biāo)簽傳播算法中，從兩個(gè)方面引入了隨機(jī)性：當(dāng)進(jìn)行標(biāo)簽值的更新時(shí)，具有多個(gè)符合條件的標(biāo)簽值時(shí)，隨機(jī)選擇一個(gè)；而且節(jié)點(diǎn)的更新順序也是隨機(jī)進(jìn)行的，因此，現(xiàn)有技術(shù)產(chǎn)生的社團(tuán)劃分結(jié)果會(huì)在時(shí)序上產(chǎn)生較大的差異，進(jìn)而使得算法具有較差的魯棒性和穩(wěn)定性。因此，現(xiàn)有技術(shù)存在動(dòng)態(tài)社團(tuán)劃分結(jié)果不準(zhǔn)確的技術(shù)問題。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題在于提供了一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分方法及裝置，以提高動(dòng)態(tài)社團(tuán)劃分結(jié)果的準(zhǔn)確性。

本發(fā)明是通過以下技術(shù)方案解決上述技術(shù)問題的：

本發(fā)明實(shí)施例提供了一種基于標(biāo)簽擴(kuò)散的時(shí)序平滑社團(tuán)劃分方法，所述方法包括：

1)、獲取待劃分網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)在當(dāng)前時(shí)刻的前一時(shí)刻的標(biāo)簽值，其中，所述待劃分網(wǎng)絡(luò)是由所述節(jié)點(diǎn)連接而成的抽象網(wǎng)絡(luò)；

2)、獲取當(dāng)前次更新中標(biāo)簽值發(fā)生變化的節(jié)點(diǎn)數(shù)量，并根據(jù)所述節(jié)點(diǎn)數(shù)量更新標(biāo)簽值發(fā)生變化的節(jié)點(diǎn)數(shù)量的振蕩次數(shù)，判斷所述振蕩次數(shù)是否大于預(yù)設(shè)閾值；