[發明專利]一種聚簇圖集合中的子圖檢索方法在審
| 申請號： | 201410313170.5 | 申請日： | 2014-07-01 |
| 公開（公告）號： | CN104102699A | 公開（公告）日： | 2014-10-15 |
| 發明（設計）人： | 丁曉鋒;金海;賈建紅;徐慧 | 申請（專利權）人： | 華中科技大學 |
| 主分類號： | G06F17/30 | 分類號： | G06F17/30 |
| 代理公司： | 華中科技大學專利中心 42201 | 代理人： | 梁鵬 |
| 地址： | 430074 湖北*** | 國省代碼： | 湖北;42 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 聚簇圖 集合 中的 檢索 方法 | ||
技術領域
本發明屬于圖形數據檢索技術領域，更具體地，涉及一種聚簇圖集合中的子圖檢索方法。
背景技術
圖形數據被廣泛作為社交應用的數學模型，為了防止惡意攻擊者根據用戶特有的好友關系還原用戶并獲取用戶的敏感信息，科技工作者設計了各種各樣的匿名方法。聚簇化是將屬性和結構相近的用戶組合到一起，對外呈現同一屬性和結構的方式。聚簇化后，數據擁有者將數據發布到開放的數據共享平臺以供科技工作者利用社交應用的數據進行相關的研究工作。但是，由于聚簇化后的圖數據匹配中，結點之間存在一對多的映射關系，目前尚未存在有效子圖檢索技術用于解決該類型數據集合中的子圖檢索問題。
發明內容
針對現有技術的以上缺陷或改進需求，本發明的目的是提供一種聚簇圖集合中的子圖檢索方法，其通過為聚簇圖集合建立樹形索引，盡早過濾掉不符合查詢約束的聚簇圖數據項，縮小查詢空間，進而提高檢索效率。
為實現上述目的，本發明提供了一種聚簇圖集合中的子圖檢索方法，所述包括以下步驟：
(1)索引建立步驟：根據聚簇圖的結構信息和結點屬性計算聚簇圖集合中各聚簇圖之間的相似性，根據各聚簇圖之間的相似性采用層次聚類算法將相近的聚簇圖聚類，直到剩下一個聚簇圖，從而將聚簇圖集合轉化成聚簇圖索引樹；
(2)子圖檢索步驟：根據用戶發起查詢圖的結構以及頂點屬性，對聚簇圖索引樹采用樹的自頂向下的方式進行查詢圖的同構匹配；若某中間聚簇圖不包含查詢圖，則其子孫節點代表的聚簇圖不需要進行匹配，因此將該中間聚簇圖及其子孫過濾掉；若某節點代表的聚簇圖包含查詢圖，若該聚簇圖不是數據圖，則將其孩子節點表示的聚簇圖加入待檢測隊列，若該聚簇圖是數據圖，則將其加入結果集；最終將結果集合返回給用戶。
本發明的一個實施例中，所述步驟(1)中根據聚簇圖的結構信息和結點屬性計算聚簇圖集合中各聚簇圖之間的相似性具體根據下式計算：
任意兩個聚簇圖G1和G2之間的相似性為
其中：
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于華中科技大學，未經華中科技大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201410313170.5/2.html，轉載請聲明來源鉆瓜專利網。
