[發(fā)明專利]一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110079776.7
• 申請(qǐng)日: 2021-01-21
• 公開（公告）號(hào): CN112417316A
• 公開（公告）日: 2021-02-26
• 發(fā)明（設(shè)計(jì)）人: 楊艾森;史曉春;陳文;鄧三鴻;劉留;李祥睿
• 申請(qǐng)（專利權(quán)）人: 南京數(shù)聯(lián)銘品科技有限公司
• 主分類號(hào): G06F16/9536
• 分類號(hào): G06F16/9536;G06Q50/00
• 代理公司: 武漢聚信匯智知識(shí)產(chǎn)權(quán)代理有限公司 42258
• 代理人: 馬尚偉

本發(fā)明提供了一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法，屬于復(fù)雜網(wǎng)絡(luò)技術(shù)領(lǐng)域，該一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法包括S100，輸入復(fù)雜網(wǎng)絡(luò)圖：將需要進(jìn)行社區(qū)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)輸入Bron?Kerbosch算法之中；S200，使用Bron?Kerbosch算法進(jìn)行初始化：使用Bron?Kerbosch算法對(duì)數(shù)據(jù)進(jìn)行處理，得到極大團(tuán)并融合重疊部分的團(tuán)，為極大團(tuán)中的節(jié)點(diǎn)賦予一致標(biāo)簽，完成對(duì)標(biāo)簽傳播的初始化，即賦予節(jié)點(diǎn)初始標(biāo)簽；本發(fā)明更改初始化策略并采用異步更新之后，每次計(jì)算的結(jié)果幾乎相同，克服了多標(biāo)簽傳播算法在發(fā)現(xiàn)重疊社區(qū)時(shí)結(jié)果不穩(wěn)定的問題。

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

本發(fā)明屬于復(fù)雜網(wǎng)絡(luò)技術(shù)領(lǐng)域，具體而言，涉及一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)來源廣泛，社會(huì)中或自然界的任何對(duì)象都可以被看作節(jié)點(diǎn)，而節(jié)點(diǎn)之間的關(guān)聯(lián)可以看作連接節(jié)點(diǎn)的邊，只要有點(diǎn)和邊就能構(gòu)成復(fù)雜網(wǎng)絡(luò)，但這些復(fù)雜網(wǎng)絡(luò)之中節(jié)點(diǎn)之間的整體關(guān)系還需要發(fā)掘，于是出現(xiàn)了對(duì)將現(xiàn)實(shí)數(shù)據(jù)結(jié)構(gòu)化轉(zhuǎn)為復(fù)雜網(wǎng)絡(luò)，并對(duì)其中社區(qū)進(jìn)行發(fā)現(xiàn)的算法，為人類更好地理解自然和社會(huì)開啟了嶄新的篇章。

全世界的專家學(xué)者從研究開始至今，已發(fā)明了許多社區(qū)發(fā)現(xiàn)算法模型，包括：1.非重疊社區(qū)發(fā)現(xiàn)算法，著名的有：i. 標(biāo)簽傳播算法：首先初始化每個(gè)節(jié)點(diǎn)，設(shè)置不同的標(biāo)簽，然后采用同步更新的方式計(jì)算標(biāo)簽隸屬度，并更新節(jié)點(diǎn)的標(biāo)簽，不斷迭代直至結(jié)果收斂；ii. FN 算法：首先將每個(gè)節(jié)點(diǎn)初始化為一個(gè)社區(qū)，接著計(jì)算鄰接節(jié)點(diǎn)加入這個(gè)社區(qū)后模塊度的變化量，如果變化量為較大的正值則將鄰接節(jié)點(diǎn)正式并入社區(qū)，迭代直至模塊度最大化。2. 重疊社區(qū)發(fā)現(xiàn)算法，其中包括：i. CPM算法：首先篩選所有擁有k個(gè)節(jié)點(diǎn)的完全子圖k派系，然后將k派系當(dāng)作一個(gè)節(jié)點(diǎn)代替原來k個(gè)節(jié)點(diǎn)，如果兩個(gè)k派系中有k-1個(gè)節(jié)點(diǎn)屬于共同擁有，則在兩個(gè)替代節(jié)點(diǎn)間建立一條邊，社區(qū)劃分即構(gòu)成的新圖中的連通子圖；ii.COPRA算法：使用標(biāo)簽傳播算法為基底，但是允許節(jié)點(diǎn)屬于多個(gè)標(biāo)簽，在標(biāo)簽傳播階段對(duì)鄰接節(jié)點(diǎn)所有標(biāo)簽的隸屬度進(jìn)行計(jì)算并選擇隸屬度高的標(biāo)簽進(jìn)行更新，如果多個(gè)標(biāo)簽隸屬度相同則隨機(jī)選擇，不斷迭代直至結(jié)果收斂。

但是這些傳統(tǒng)社區(qū)發(fā)現(xiàn)算法依然有以下不足：

1.很多傳統(tǒng)算法不能發(fā)現(xiàn)重疊社區(qū)，因?yàn)榇蠖嗨惴▽⒛骋还?jié)點(diǎn)歸入一個(gè)社區(qū)時(shí)，大多會(huì)導(dǎo)致該節(jié)點(diǎn)從考慮的集合中刪除，不然會(huì)發(fā)掘出許多不完整細(xì)碎的社區(qū)，使發(fā)現(xiàn)結(jié)果不具有實(shí)際意義，所以大多數(shù)算法去除了節(jié)點(diǎn)從屬于多個(gè)社區(qū)的可能性，故而不能發(fā)現(xiàn)重疊社區(qū)。

2.使用標(biāo)簽傳播算法的重疊社區(qū)發(fā)現(xiàn)算法穩(wěn)定性較差，因?yàn)樵诔跏蓟瘶?biāo)簽與標(biāo)簽傳播的過程中都有隨機(jī)選擇標(biāo)簽的過程，初始化時(shí)標(biāo)簽傳播算法為每個(gè)節(jié)點(diǎn)隨機(jī)分配了各不相同的標(biāo)簽，導(dǎo)致早期傳播不穩(wěn)定；同時(shí)，在標(biāo)簽傳播過程中，標(biāo)簽傳播算法使用了同步更新，導(dǎo)致出現(xiàn)同一節(jié)點(diǎn)的多個(gè)標(biāo)簽的隸屬度相同時(shí)，隨機(jī)選擇標(biāo)簽更新的處理方法的不穩(wěn)定性增加。最終這兩個(gè)穩(wěn)定性方面的問題使得標(biāo)簽傳播算法發(fā)現(xiàn)社區(qū)的結(jié)果每次都有所不同。

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

本發(fā)明實(shí)施例提供了一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法，其目的在于解決現(xiàn)有的算法不能發(fā)現(xiàn)重疊社區(qū)和使用標(biāo)簽傳播算法的重疊社區(qū)發(fā)現(xiàn)算法穩(wěn)定性較差的問題。

鑒于上述問題，本發(fā)明提出的技術(shù)方案是：

本發(fā)明提供一種基于多標(biāo)簽傳播的半監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法，包括以下步驟：

S100，輸入復(fù)雜網(wǎng)絡(luò)圖：將需要進(jìn)行社區(qū)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)輸入重疊社區(qū)發(fā)現(xiàn)算法之中；

S200，使用Bron-Kerbosch算法進(jìn)行初始化：使用Bron-Kerbosch算法對(duì)數(shù)據(jù)進(jìn)行處理，得到極大團(tuán)并融合重疊部分的團(tuán)，為極大團(tuán)中的節(jié)點(diǎn)賦予一致標(biāo)簽，完成對(duì)標(biāo)簽傳播的初始化，即賦予節(jié)點(diǎn)初始標(biāo)簽；

S300，計(jì)算每個(gè)節(jié)點(diǎn)的PageRank值：根據(jù)節(jié)點(diǎn)與邊的權(quán)重計(jì)算每個(gè)節(jié)點(diǎn)的PageRank值，即值，再依據(jù)值對(duì)節(jié)點(diǎn)行排序；