[發明專利]一種彩色k-星核分解方法

在審

• 申請號: 202110326947.1
• 申請日: 2021-03-26
• 公開（公告）號: CN112950728A
• 公開（公告）日: 2021-06-11
• 發明（設計）人: 高森;李榮華;王國仁;金福生;秦宏超
• 申請（專利權）人: 北京理工大學
• 主分類號: G06T7/90
• 分類號: G06T7/90;G06K9/62
• 代理公司: 北京圣州專利代理事務所(普通合伙) 11818
• 代理人: 劉巖

本發明公開了一種彩色k?星核分解方法，步驟如下：S1、設置一個包含k個節點的k?星圖，其中一個中間節點與其他k?1個點相連，給定圖G和一個點u，u作為中間節點參與的k?星的數量記作該點的k?星度；S2、用貪婪算法對給定的圖G進行著色；S3、計算每個點初始的彩色k?星度；S4、按彩色k?星度的大小對所有節點從小到大排序；S5、每次刪除當前子圖中彩色k?星度最小的點u直到刪除所有點，并將當前的核值賦給u，同時更新該點的鄰居的彩色k?星度，最后得到每個點的彩色k?星核值以及一個節點被刪除的順序。本發明采用上述的一種彩色k?星核分解方法，分解過程的復雜度更低，效率加快，能夠很好的表征出子圖的稠密屬性。

技術領域

本發明涉及圖數據技術領域，尤其是涉及一種彩色k-星核分解方法。

背景技術

真實世界中的圖數據，例如社交網絡、生物網絡和通信網絡，通常由稠密子圖組成。從圖中挖掘稠密子圖是網絡分析中的一個基礎問題，這也在數據庫和數據挖掘社區引起了很多關注。

目前，存在的稠密子圖定義有k-核、k-團(k-clique)、k-clans、k-plex、f-group、k-club等，他們中的大多數都是NP-難的計算復雜度。

在稠密子圖挖掘問題中，目前廣泛應用的兩個衡量標準是邊密度和k-團密度，其中k-團是具有k個結點的子圖。給定圖G，邊密度定義為圖中所有邊的數量除以所有點的數量；k-團密度定義為圖中所有k-團的數量除以所有點的數量。而挖掘稠密子圖的任務則轉化為在給定的圖中尋找最大邊密度的子圖和尋找最大k-團密度的子圖。

Tsourakakis在2015年將這兩個概念歸納統一，將邊密度推廣到2-團密度，并提出了尋找最大k-團密度子圖的精確和近似算法。

Tsourakakis所提出的精確算法采用最大流計算獲得，近似算法通過依次刪除圖中參與k-團數量最少的點，在得到的所有子圖中選取最大k-團密度的子圖。近似算法得到的k-團密度是真實值的近似，即小于等于真實值，大于等于真實值的。

現有的稠密子圖的度量主要以下缺陷：

(1)k-團密度度量計算的時間復雜度高，運行效率低；

(2)其他度量不能充分刻畫圖的稠密屬性，即可能存在尋找到稀疏的子圖。

發明內容

本發明的目的是提供一種彩色k-星核分解方法，分解過程的復雜度更低，效率加快，能夠很好的表征出子圖的稠密屬性。

為實現上述目的，本發明提供了一種彩色k-星核分解方法，步驟如下：

S1、設置一個包含k個節點的k-星圖，其中一個中間節點與其他k-1個點相連，給定圖G和一個點u，u作為中間節點參與的k-星的數量記作該點的k-星度；

S2、用貪婪算法對給定的圖G進行著色，使得沒有兩個相鄰結點具有相同的顏色值；

S3、計算每個點初始的彩色k-星度；

S4、按彩色k-星度的大小對所有節點從小到大排序；

S5、每次刪除當前子圖中彩色k-星度最小的點u直到刪除所有點，并將當前的核值賦給u，同時更新該點的鄰居的彩色k-星度，最后得到每個點的彩色k-星核值以及一個節點被刪除的順序。

彩色k-星h-核是滿足所有點的彩色k-星度都大于等于h的最大子圖。所有包含結點u的彩色k-星h-核中的最大整數值h，稱為該點的彩色k-星核值。彩色k-星核分解問題即計算每個點的彩色k-星核值。

優選的，步驟S2中，首先先將點u的鄰居按顏色分為若干組，然后利用動態規劃的方式來計算該點作為中間節點所參與的彩色k-星的數量；