新算法推动复杂网络的图挖掘

Josiah02

弗吉尼亚大学工程与应用科学学院教授 Nikolaos Sidiropoulos 介绍了一种新计算算法在图形挖掘领域取得的突破。
图挖掘是一种分析社交媒体连接或生物系统等网络的方法，它可以帮助研究人员发现不同元素相互作用的有意义模式。新算法解决了在大型网络中寻找紧密连接的簇（称为三角密集子图）的长期挑战——这一问题在欺诈检测、计算生物学和数据分析等领域至关重要。
该项研究发表在《IEEE 知识与数据工程学报》上，是由比利时鲁汶大学电气工程助理教授 Aritra Konar 领导的合作研究，他曾是 UVA 的研究科学家。
图挖掘算法通常侧重于寻找单个点对之间的紧密联系，例如在社交媒体上经常交流的两个人。然而，研究人员的新方法，即三角密集 k 子图问题，更进一步，通过研究连接三角形（每对连接的三个点组成的组）来做到这一点。这种方法可以捕捉更紧密的关系，比如彼此互动的小朋友群体，或在生物过程中协同工作的基因簇。
“我们的方法不只是研究单一连接，还考虑三个元素如何相互作用，这对于理解更复杂的网络至关重要，”电气和计算机工程系教授西迪罗普洛斯解释说。“这使我们能够找到更有意义的模式，即使在海量数据集中也是如此。”
寻找三角形密集子图尤其具有挑战性，因为用传统方法很难有效解决。但新算法采用了所谓的子模松弛法，这是一种巧妙的捷径，可以简化问题，使其更快地解决，而不会丢失重要细节。
这一突破为理解依赖于这些更深层次、多连接关系的复杂系统开辟了新的可能性。定位子群和模式可以帮助发现欺诈中的可疑活动，识别社交媒体上的社区动态，或帮助研究人员更精确地分析蛋白质相互作用或遗传关系。