[發明專利]一種基于k-truss的面向超圖的社區發現方法

在審

• 申請號: 202111528752.1
• 申請日: 2021-12-14
• 公開（公告）號: CN114168863A
• 公開（公告）日: 2022-03-11
• 發明（設計）人: 易晗;李榮華;高玉金;秦宏超;王國仁;金福生
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 北京圣州專利代理事務所(普通合伙) 11818
• 代理人: 王杰

本發明公開了一種基于k?truss的面向超圖的社區發現方法，具體步驟如下：S1、首先輸入超圖H^G＝(V，E^h)、S、r，計算超圖中所有超邊的support；S2、初始化超圖的極大k?truss下界low＝0，上界up＝0，當Size(|H|)S時，進行以下操作；S3、計算當前超圖中的三角形個數T＝所有超邊的support之和/3，令low＝max(low，最小的超邊support，T/超邊總數)，令up＝max(up，最小的超邊support，r*(T/超邊總數))；S4、將所有support小于上界up的超邊從超圖H中刪除，得到一個新的超圖H。本發明采用上述的一種基于k?truss的面向超圖的社區發現方法，在超圖上實現了k?truss分解和極大k?truss的挖掘，大幅減少了不必要的計算內容，消除了傳統算法的冗余計算過程，實現了對于超圖的社區發現。

技術領域

本發明涉及設計圖數據挖掘技術領域，尤其是涉及一種基于k-truss的面向超圖的社區發現方法。

背景技術

超圖是一種高維的對于數據的圖形展示，彌補了普通圖表示方式信息丟失的缺陷，專用于描述具有成對的組合關系(點與超邊)的體系。超圖由節點和超邊組成，每個節點可以是一個人或一個對象。然而，每個超邊可以充當任意數量節點的交互。

圖社區發現是網絡研究中的一個非常重要的分支，社區是一組擁有密切關系的實體集合。而k-truss作為一種稠密子圖的表現形式，它的緊密程度要小于限制嚴格的團結構，但是大于k-core對于個體之間關系限制程度的要求，能很好的體現出一個社交網絡中各個個體之間的關系。目前，在圖中進行社區挖掘的問題，已經得到了廣泛的研究和應用。由于圖社區發現中常常需要的是一個社區中的極大k-truss，所以該類問題的主要目的通常是挖掘出圖中的極大k-truss。

社區發現的研究對于分析網絡的拓撲結構、理解網絡的功能、發現網絡中的隱藏規律和預測網絡的行為都有十分重要的理論意義和應用前景。在計算機科學、物理、數學、生物、社會學和復雜性科學等領域均有相關的研究和應用，例如用于社會網絡分析(如組織結構管理)，生物網絡分析(如新陳代謝網絡分析、蛋白質交互網絡分析、未知蛋白質功能預測、基因調控網絡分析和主控基因識別等)，Web社區挖掘，基于主題詞的Web文檔聚類和搜索引擎等。對一個大型網絡進行社區發現，其實是對其按照某種標準進行了劃分，在此基礎上可對每個社區做進一步的發掘。而從計算的角度而言，社區發現相當于分解了任務，起到了降低計算復雜度的作用。

目前并沒有基于超圖的極大k-truss挖掘方法，而在圖上使用較為廣泛的方法是基于內存的計算方法，基本的計算思路是將圖讀入內存中并計算出圖中每條邊的支持度；給定一個k值，過濾掉所有支持度小于k-2的邊；不斷地遞增k的值，重復以上步驟，直至圖中所有的邊都被移除為止；最終所留下的k-truss就是該圖的極大k-truss。

這種方法雖然能夠得到結果，但是存在著大量的冗余計算，通過這種方法計算極大k-truss時，需要不斷地遞增k的值，并對每一個k值都計算出相應的k-truss，在這個過程中，還需要不斷的維護所有邊的支持度的大小，而我們最終需要的通常只是最后找到的極大k-truss。因此該過程存在大量的冗余計算。其次，隨著數據規模的增長，圖和超圖的規模也不斷擴大，難以完整的將整個圖載入到內存中，因此在整個圖上進行這樣的計算也是非常困難的。最后，目前在超圖上還未有解決此類問題的方法。

發明內容

本發明的目的是提供一種基于k-truss的面向超圖的社區發現方法，實現了在超圖上的社區發現，解決了圖上傳統算法計算冗余、效率低等問題。通過使用該方法，可以分析網絡的拓撲結構、理解網絡的功能、發現網絡中的隱藏規律和預測網絡的行為。

為實現上述目的，本發明提供了一種基于k-truss的面向超圖的社區發現方法，具體步驟如下：