[發(fā)明專利]一種聚簇圖集合中的子圖檢索方法

在審

• 申請?zhí)枺?/td>: 201410313170.5
• 申請日: 2014-07-01
• 公開（公告）號: CN104102699A
• 公開（公告）日: 2014-10-15
• 發(fā)明（設計）人: 丁曉鋒;金海;賈建紅;徐慧
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 梁鵬

1.一種聚簇圖集合中的子圖檢索方法，其特征在于，所述方法包括以下步驟：

(1)索引建立步驟：根據(jù)聚簇圖的結構信息和結點屬性計算聚簇圖集合中各聚簇圖之間的相似性，根據(jù)各聚簇圖之間的相似性采用層次聚類算法將相近的聚簇圖聚類，直到剩下一個聚簇圖，從而將聚簇圖集合轉(zhuǎn)化成聚簇圖索引樹；

(2)子圖檢索步驟：根據(jù)用戶發(fā)起查詢圖的結構以及頂點屬性，對聚簇圖索引樹采用樹的自頂向下的方式進行查詢圖的同構匹配；若某中間聚簇圖不包含查詢圖，則其子孫節(jié)點代表的聚簇圖不需要進行匹配，因此將該中間聚簇圖及其子孫過濾掉；若某節(jié)點代表的聚簇圖包含查詢圖，若該聚簇圖不是數(shù)據(jù)圖，則將其孩子節(jié)點表示的聚簇圖加入待檢測隊列，若該聚簇圖是數(shù)據(jù)圖，則將其加入結果集；最終將結果集合返回給用戶。

2.根據(jù)權利要求1所述方法，其特征在于，所述步驟(1)中根據(jù)聚簇圖的結構信息和結點屬性計算聚簇圖集合中各聚簇圖之間的相似性具體根據(jù)下式計算：

任意兩個聚簇圖G₁和G₂之間的相似性為

其中：

IL(G1,G2)=minfΣVC∈GCIL(VC);]]>

IL(VC)=1|VC|Σu∈VCIL(u);]]>

IL(u)=ω1LΣl=1L(1-|Ru(l)_||RVC(l)‾|)+(1-ω)((1-PcloPori)+(1-deg(u)deg(VC)));]]>

公式IL(u)=ω1LΣl=1L(1-|Ru(l)_||RVC(l)‾|)+(1-ω)((1-PcloPori)+(1-deg(u)deg(VC)))]]>用于計算頂點u發(fā)生的信息損失，用于計算屬性信息損失，用于計算結構信息損失；ω為權重參數(shù)，用于調(diào)節(jié)信息損失中屬性信息損失和結構信息損失之間的權重；L表示頂點屬性的個數(shù)，表示頂點u所在結點的第l個屬性的范圍或等級，表示頂點u所在結點聯(lián)合之后相應屬性的范圍；P_clo表示圖形聯(lián)合后，內(nèi)部兩個結點之間被連接的概率，P_ori表示聯(lián)合前的相應概率，用于表示聯(lián)合后結點內(nèi)的結構信息損失；deg(u)表示頂點u所在結點的好友個數(shù)，deg(V_C)表示頂點u所在結點聯(lián)合后相應結點的好友個數(shù)，用于計算聯(lián)合時結點間的信息損失；聯(lián)合一個結點時，結點內(nèi)所有頂點的信息損失是相同的；

公式用于計算聯(lián)合后得到的圖閉包closure中結點V_C的信息損失，|VC|表示聯(lián)合后圖中結點內(nèi)包含的頂點個數(shù)，IL(u)表示聯(lián)合后圖結點內(nèi)某頂點的信息損失，聯(lián)合后的信息損失由聯(lián)合前的所有頂點信息損失的平均值表示；

公式用于根據(jù)兩個聚簇圖聯(lián)合時的結點信息損失計算兩項圖聯(lián)合的信息損失，其中，G_C是G₁和G₂的closure，G_C＝Closure(G₁,G₂)，f是兩個圖進行聯(lián)合時的映射，公式表示兩項聚簇圖聯(lián)合時，結點聯(lián)合的信息損失的最小值表示聯(lián)合兩項圖的信息損失，取得該最小值的映射稱為最優(yōu)映射，該最小值可作為圖集合聚類的度量。