[發(fā)明專利]網(wǎng)絡(luò)中重疊社團(tuán)的挖掘方法

有效

• 申請?zhí)枺?/td>: 201710419287.5
• 申請日: 2017-06-06
• 公開（公告）號: CN107133877B
• 公開（公告）日: 2021-02-09
• 發(fā)明（設(shè)計(jì)）人: 孫麗萍;羅永龍;劉君;鮑舒婷;鄭孝遙;陳付龍
• 申請（專利權(quán)）人: 安徽師范大學(xué)
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 蕪湖安匯知識產(chǎn)權(quán)代理有限公司 34107
• 代理人: 朱圣榮

本發(fā)明揭示了一種網(wǎng)絡(luò)中重疊社團(tuán)的挖掘方法，包括步驟A、通過定義種子選擇的過程，在種子選擇迭代過程中依次選擇不屬于覆蓋集的頂點(diǎn)作為種子，并根據(jù)頂點(diǎn)覆蓋增長率的變化范圍確定種子數(shù)目，自適應(yīng)產(chǎn)生最優(yōu)種子；B、利用個性化PageRank算法以各頂點(diǎn)為起點(diǎn)擴(kuò)展社團(tuán)范圍，覆蓋多數(shù)頂點(diǎn)；C、將未覆蓋頂點(diǎn)自適應(yīng)劃分到鄰近社團(tuán)中，調(diào)整社團(tuán)結(jié)構(gòu)，完成社團(tuán)劃分。本發(fā)明的優(yōu)點(diǎn)在于網(wǎng)絡(luò)中重疊社團(tuán)的挖掘方法通過對頂點(diǎn)增長覆蓋率等的定義，可在種子選擇階段根據(jù)社團(tuán)結(jié)構(gòu)自行產(chǎn)生最優(yōu)種子，并能在個性PageRank算法后自適應(yīng)地合并和調(diào)整未覆蓋頂點(diǎn)。

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

本發(fā)明涉及在復(fù)雜網(wǎng)絡(luò)中對重疊社團(tuán)進(jìn)行檢測和劃分的方法，具體涉及一種基于種子選擇和種子擴(kuò)展的自適應(yīng)社團(tuán)檢測方法。

背景技術(shù)

挖掘復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對于發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律、預(yù)測網(wǎng)絡(luò)行為以及增強(qiáng)網(wǎng)絡(luò)的安全可信度具有重要的理論意義和廣泛的應(yīng)用前景。社團(tuán)檢測作為網(wǎng)絡(luò)分析領(lǐng)域中的基礎(chǔ)課題，在生物科學(xué)、社會學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)等眾多研究領(lǐng)域都具有應(yīng)用價值。對于某一特定的網(wǎng)絡(luò)，可以采用一定的模型將其轉(zhuǎn)化為只考慮邊和頂點(diǎn)關(guān)系的圖結(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)的一大基本特征是具有較明顯的“社團(tuán)”劃分，屬于同一社團(tuán)的頂點(diǎn)間連接緊密，而不同社團(tuán)間連接稀疏。相同社團(tuán)內(nèi)的頂點(diǎn)具有某些相似的特征，而不同社團(tuán)的頂點(diǎn)特征差異較大。針對真實(shí)復(fù)雜網(wǎng)絡(luò)的社團(tuán)檢測有利于識別網(wǎng)絡(luò)結(jié)構(gòu)，分析網(wǎng)絡(luò)特性。

多數(shù)傳統(tǒng)的社團(tuán)檢測方法將圖中頂點(diǎn)劃分到某一特定社團(tuán)中。然而在現(xiàn)實(shí)世界，頂點(diǎn)可能屬于多社團(tuán)共享狀態(tài)。如社交網(wǎng)絡(luò)中，個人鑒于其不同身份，參與多個社交圈子。考慮頂點(diǎn)屬于多個社團(tuán)的情況更具有實(shí)用性和研究價值。重疊社團(tuán)檢測允許多個社團(tuán)間相互重疊，重疊區(qū)域內(nèi)的頂點(diǎn)屬于這若干個社團(tuán)共有。因此，重疊社團(tuán)檢測成為社團(tuán)檢測問題中需要進(jìn)一步探究的問題。

Whang等人提出兩種不同的種子選擇方法，分別使用各社團(tuán)的中心頂點(diǎn)和“高密度”頂點(diǎn)作為種子來源，不能有效處理含離群點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)；種子數(shù)目事先指定，無法根據(jù)社團(tuán)規(guī)模自行調(diào)整。Coscia等人提出的DEMON方法采用“局部為先”思想，結(jié)合了標(biāo)記傳播法進(jìn)行社團(tuán)檢測，易陷入局部最優(yōu)的狀態(tài)，無法根據(jù)社團(tuán)整體結(jié)構(gòu)動態(tài)調(diào)整種子分布。

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

本發(fā)明所要解決的技術(shù)問題是實(shí)現(xiàn)一種能夠處理復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測問題的方法，也是一種復(fù)雜網(wǎng)絡(luò)的重疊社團(tuán)挖掘方法，該方法需要能夠自適應(yīng)各類型的復(fù)雜網(wǎng)絡(luò)中的重疊社團(tuán)檢測，根據(jù)社團(tuán)整體結(jié)構(gòu)動態(tài)調(diào)整種子分布，達(dá)到適用范圍廣泛，效率較高的要求。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案為：網(wǎng)絡(luò)中重疊社團(tuán)的挖掘方法，包括以下步驟：

步驟1、種子選擇階段：在定義種子選擇的過程中根據(jù)社團(tuán)結(jié)構(gòu)自適應(yīng)產(chǎn)生最優(yōu)的種子；

步驟2、種子擴(kuò)展階段：利用個性化PageRank算法，并根據(jù)社團(tuán)和種子頂點(diǎn)間的關(guān)系進(jìn)行種子擴(kuò)展，覆蓋網(wǎng)絡(luò)多數(shù)頂點(diǎn)；

步驟3、社團(tuán)擴(kuò)展階段：將未覆蓋的頂點(diǎn)自適應(yīng)劃分到鄰近社團(tuán)中，完成社團(tuán)劃分。

所述步驟1中，先定義種子集、覆蓋集和頂點(diǎn)覆蓋增長率的概念，將頂點(diǎn)按照度從大到小排序，之后在種子選擇迭代過程中依次選擇不屬于覆蓋集的頂點(diǎn)作為種子，并根據(jù)頂點(diǎn)覆蓋增長率的變化范圍確定種子數(shù)目，根據(jù)頂點(diǎn)覆蓋增長率的定義選擇頂點(diǎn)，并獲取初始種子集。

所述步驟2中，基于種子選擇階段得到的初始種子集按順序?qū)ζ渲械姆N子及其鄰接點(diǎn)進(jìn)行種子擴(kuò)展。

所述步驟3中，在PageRank算法結(jié)束時，未被覆蓋的社團(tuán)可分成兩種類型，種類一、頂點(diǎn)至少有一個鄰接點(diǎn)屬于簇類中，種類二、頂點(diǎn)是離群點(diǎn)，其所有鄰接點(diǎn)也都未被覆蓋，如果頂點(diǎn)屬于種類一，則將頂點(diǎn)與其鄰接點(diǎn)分到同一社團(tuán)中；如果頂點(diǎn)屬于種類二，則將頂點(diǎn)與可能存在的鄰接點(diǎn)組成一個新社團(tuán)。

所述步驟1包括以下步驟：