[發(fā)明專利]一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法

在審

• 申請?zhí)枺?/td>: 202010721930.1
• 申請日: 2020-07-24
• 公開（公告）號: CN111985086A
• 公開（公告）日: 2020-11-24
• 發(fā)明（設(shè)計(jì)）人: 王彬;丁翠;劉光明
• 申請（專利權(quán)）人: 西安理工大學(xué)
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F17/16;G06K9/62;G06F111/04
• 代理公司: 西安弘理專利事務(wù)所 61214
• 代理人: 羅笛

1.一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，包括以下步驟：

步驟1、獲取相關(guān)的人工網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集，求解網(wǎng)絡(luò)相應(yīng)的鄰接矩陣V_ij；

步驟2、獲取網(wǎng)絡(luò)中相關(guān)節(jié)點(diǎn)的Must-link先驗(yàn)信息，構(gòu)建矩陣M_ij作為節(jié)點(diǎn)間的Must-link關(guān)系矩陣；

步驟3、將Must-link先驗(yàn)信息融合到非負(fù)矩陣分解模型中，構(gòu)建新的社團(tuán)檢測模型；

步驟4、對迭代求解后的節(jié)點(diǎn)劃分矩陣進(jìn)行組稀疏約束；

步驟5、根據(jù)類重表示矩陣進(jìn)行網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測，得到最終的社團(tuán)劃分結(jié)果。

2.如權(quán)利要求1所述的一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，所述步驟1中求解網(wǎng)絡(luò)相應(yīng)的鄰接矩陣V_ij的具體步驟為：

步驟1.1、求出網(wǎng)絡(luò)數(shù)據(jù)集的最大值n，構(gòu)建一個(gè)n×n的初始矩陣V；

步驟1.2、根據(jù)以下公式(1)對初始矩陣V進(jìn)行賦值，得到網(wǎng)絡(luò)的鄰接矩陣V_ij；

式(1)中，E表示網(wǎng)絡(luò)中的邊，v_i，v_j表示節(jié)點(diǎn)i和j。

3.如權(quán)利要求1所述的一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，所述步驟2中Must-link關(guān)系矩陣M_ij的具體構(gòu)建過程為：

如果網(wǎng)絡(luò)中節(jié)點(diǎn)i和節(jié)點(diǎn)j具有Must-link這一關(guān)系，也表示節(jié)點(diǎn)i和節(jié)點(diǎn)j必須屬于同一個(gè)社團(tuán)，因此節(jié)點(diǎn)間的Must-link關(guān)系矩陣M_ij可通過以下公式(2)進(jìn)行定義：

4.如權(quán)利要求1所述的一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，所述步驟3具體為：

步驟3.1、使用歐氏距離來衡量節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的相似程度，表示如以下公式(3)所示：

式(3)中h_i，h_j分別代表節(jié)點(diǎn)i和節(jié)點(diǎn)j的相似向量，sim(h_i,h_j)代表節(jié)點(diǎn)i和節(jié)點(diǎn)j的歐氏距離；

步驟3.2、使用NMF模型對鄰接矩陣V_ij進(jìn)行分解，得到基矩陣W和劃分矩陣H；

步驟3.3、根據(jù)步驟2求得的Must-link關(guān)系矩陣M_ij和步驟3.2求得的劃分矩陣H得到先驗(yàn)信息的計(jì)算公式，如以下公式(4)所示：

式(4)中，Tr代表矩陣的跡，矩陣D代表Must-link關(guān)系矩陣M_ij的對角矩陣，其定義如下公式(5)：

矩陣L＝D-M，是矩陣M的拉普拉斯矩陣；

步驟3.4、將步驟3.3得到的先驗(yàn)信息融合到NMF模型中，形成新的社團(tuán)檢測模型，如以下公式(6)所示：

式(6)中，λ是用來平衡先驗(yàn)信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的參數(shù)，代表求解矩陣的F2范數(shù)，Tr代表求解矩陣的跡；

步驟3.5、對公式(6)所示的模型進(jìn)行求解，得到W和H的迭代公式，W的迭代公式如公式(7)所示，H的迭代公式如公式(8)所示；

步驟3.6、按照公式(7)和公式(8)對模型進(jìn)行迭代求解，直到達(dá)到迭代終止條件，求出最終的節(jié)點(diǎn)劃分矩陣H”。

5.如權(quán)利要求1所述的一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，所述步驟4具體為：

采用L1/L2范數(shù)對節(jié)點(diǎn)劃分矩陣H”進(jìn)行稀疏化處理，其L1/L2范數(shù)定義如下公式(9)所示：

式(9)中，l為向量a的長度，若s(a)的值設(shè)置為0，則向量a沒有進(jìn)行稀疏化處理；若s(a)的值設(shè)置為1，則向量a進(jìn)行了完全稀疏化處理，即向量a中只保留了一個(gè)非零元素，其它元素全部為零。

6.如權(quán)利要求1所述的一種融合先驗(yàn)信息和稀疏約束的社團(tuán)檢測方法，其特征在于，所述步驟5中進(jìn)行網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測的具體過程為：節(jié)點(diǎn)劃分矩陣H”是節(jié)點(diǎn)的新表示矩陣，同時(shí)該矩陣也為節(jié)點(diǎn)的社團(tuán)隸屬矩陣，即社團(tuán)中的某一列代表一個(gè)節(jié)點(diǎn)，那么該列中最大值所在的行即為該節(jié)點(diǎn)的類標(biāo)，然后將這個(gè)類標(biāo)指派給該節(jié)點(diǎn)，從而完成社團(tuán)劃分。