新算法助力！複雜網絡圖挖掘迎來重大突破

弗吉尼亞大學工程與應用科學學院的教授尼古拉奧斯·西迪羅普洛斯在圖挖掘方面取得了突破，開發了一種新的計算算法。

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

這項研究發表於 《IEEE 知識與數據工程彙刊》 上，是由比利時魯汶大學電氣工程助理教授阿里特拉·科納爾（Aritra Konar）領導的合作成果，他之前是弗吉尼亞大學的研究科學家。

圖挖掘算法通常專注於尋找單個的點對之間的密集連接，例如在社交媒體上經常交流的兩個人。然而，研究人員的新方法，被稱爲“三角形 - 最密集 - k - 子圖”問題，更進一步，通過查看連接三角形——每對都相互連接的三個點組成的組。這種方法捕捉到更緊密的關係，比如相互交流的一小羣友人，或者在生物過程中共同起作用的基因簇。

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

尋找三角形密集子圖尤其具有難度，因爲採用傳統方法難以有效地解決這一問題。

但新算法運用了所謂的子模鬆弛，這是一條巧妙的捷徑，它把問題簡化到足以讓其更快地被解決，而且不會遺漏重要細節。

這一突破爲理解依賴於這些更爲深入、多重連接關係的複雜系統開闢了新的可能。

定位子羣和模式有助於發現欺詐中的可疑活動，識別社交媒體上的社區動態，亦或幫助研究人員更精準地分析蛋白質相互作用或遺傳關係。