維吉尼亞大學工程與應用科學學院教授 Nikolaos Sidiropoulos 透過開發新的計算演算法，在圖挖掘方面取得了突破。

圖挖掘，一種分析社交媒體連接等網路的方法生物系統，幫助研究人員發現不同元素如何相互作用的有意義的模式。新演算法解決了在大型網路中尋找緊密連接的簇（稱為三角形密集子圖）這一長期存在的挑戰，這一問題在欺詐檢測、計算生物學和數據分析等領域至關重要。

該研究發表於IEEE 知識與資料工程彙刊，是由比利時魯汶大學電機工程助理教授 Aritra Konar 領導的一項合作項目，他曾是 UVA 的研究科學家。

圖探演算法通常專注於尋找各點對之間的密集聯繫，例如經常在社群媒體上交流的兩個人。然而，研究人員的新方法被稱為“三角形最密集 k 子圖問題”，該方法更進一步，透過查看連接三角形——每對連接的三個點組成的組。這種方法捕捉了更緊密的關係，例如彼此互動的小團體朋友，或在生物過程中協同工作的基因簇。

「我們的方法不僅著眼於單一連接，還考慮了三個元素組如何相互作用，這對於理解更多元素至關重要複雜網路”，電機與計算機工程系教授西迪羅普洛斯解釋道。“這使我們能夠找到更有意義的模式，即使是在海量數據集中也是如此。

尋找三角形密集子圖尤其具有挑戰性，因為用傳統方法很難有效求解。但是新演算法使用所謂的子模鬆弛，這是一種巧妙的捷徑，可以將問題簡化到足以使其更快解決而不會丟失重要細節。

這項突破為理解依賴這些更深層的多重連結關係的複雜系統開闢了新的可能性。定位子組和模式可以幫助發現可疑活動在詐欺中，識別社區動態社群媒體，或幫助研究人員更精確地分析蛋白質交互作用或遺傳關係。

更多資訊：Aritra Konar 等人，挖掘固定大小的三角形密集子圖：硬度、Lovasz 擴展和應用，IEEE 知識與資料工程彙刊（2024）。DOI：10.1109/TKDE.2024.3444608