[發明專利]基于布爾矩陣分解的圖數據壓縮方法

有效

• 申請號: 202210438892.8
• 申請日: 2022-04-25
• 公開（公告）號: CN114826278B
• 公開（公告）日: 2023-04-28
• 發明（設計）人: 翟學萌;潘夢陽;李爍;胡光岷
• 申請（專利權）人: 電子科技大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

1.一種基于布爾矩陣分解的圖數據壓縮方法，包括如下步驟：

步驟S1.對原始圖結構數據進行采樣,具體的，對原始圖結構數據進行拆分，使用自我中心網絡表示，并進行重排序；

步驟S2.矩陣表示，使用鄰接矩陣對排序后的自我中心網絡集合進行表示，生成采樣矩陣；

步驟S3.布爾矩陣分解，將采樣矩陣分解成字典矩陣與稀疏碼矩陣的乘積；

步驟S4.布爾原子挖掘，對布爾矩陣分解得到的字典矩陣進行處理，將矩陣拆分成多個列向量，對每個列向量，將其還原成鄰接矩陣，將所述鄰接矩陣分別恢復成圖結構數據，同時去除其中同構圖，最終得到的就是原子；

步驟S5.在稀疏碼矩陣的指導下，對原子進行線性組合，即可得到采樣恢復矩陣，然后根據采樣階段獲得的采樣節點集合，將各個節點之間的連邊關系按照采樣恢復矩陣進行恢復，即可得到恢復的圖結構數據。

2.根據權利要求1所述的一種基于布爾矩陣分解的圖數據壓縮方法，其特征在于，步驟S1具體分步驟如下：

步驟S11.設定采樣得到的自我中心網絡節點規模大小s；

步驟S12.訪問某個節點i，創建當前節點i的自我中心網絡g_i；

步驟S13.將節點i加入自我中心網絡g_i的節點集合，同時將節點i的一階鄰居加入集合；若當前圖結構數據節點數未超過s，則繼續添加節點i的二階鄰居；若此時節點數未超過s，則補充虛擬節點到集合；若超過，則剔除多余節點；

步驟S14.對節點集合中的節點進行排序，排序規則為：一階鄰居、二階鄰居均按照自我中心網絡g_i中的度從大到小排序；

步驟S15.將節點集合中所有存在的連邊加入自我中心網絡g_i；

步驟S16.遍歷圖結構數據中的每個節點，重復步驟S12-S15，得到若干自我中心網絡。

3.根據權利要求2所述的一種基于布爾矩陣分解的圖數據壓縮方法，其特征在于，步驟S2具體分步驟如下：

步驟S21.構建s*s的矩陣，將自我中心網絡的連邊情況填入，從而得到多個鄰接矩陣；

步驟S22.針對每個鄰接矩陣，進行向量化操作，即將鄰接矩陣的所有列向量按序首尾拼接，從而將一個s*s的矩陣轉換為一個s²*1的列向量；

步驟S23.將步驟S22得到的列向量全部按列拼接，從而得到一個全新的矩陣，該矩陣的維度為s²*N，最終得到一個采樣矩陣Y。

4.根據權利要求3所述的一種基于布爾矩陣分解的圖數據壓縮方法，其特征在于，步驟S3具體分步驟如下：

S31.設置終止閾值c，擴展閾值t；

S32.將初始采樣矩陣拷貝，得到殘差矩陣，初始化字典矩陣與稀疏碼矩陣；

S33.對矩陣中的所有列分別求和，在此基礎上對列排序；

S34.在排序之后的列集合中選出中位數列，作為基列集合；

S35.從基列集合中挨個選取基列，以基列與其它列進行比較，若其它列包含基列中的1的比例達到50％以下，則說明不包含；若其它列包含基列中的1的比例達到50％及以上，則繼續將該列在初始矩陣中的對應列與基列進行包含關系的判斷，如果比例在擴展閾值t及以上，則說明真實包含，該基列的包含個數加1；

S36.統計所有基列的包含個數，選擇最大的那個，將該基列選出，加入到字典矩陣中作為新的一列，將每一列是否包含基列用0與1表示，得到一個行向量，將其加入到稀疏碼矩陣中作為新的一行；

S37.對于殘差矩陣中所有包含基列的列，都與基列做減法運算，若出現負數，也置為0；

S38.重復上述步驟S33-S37，直到誤差無法下降或者誤差低于終止閾值c。