弗吉尼亚大学工程与应用科学学院教授尼古拉斯·西迪罗普洛斯 (Nikolaos Sidiropoulos) 通过开发一种新的计算算法，在图挖掘方面取得了突破。
图挖掘，一种分析社交媒体连接等网络的方法生物系统，帮助研究人员发现不同元素如何相互作用的有意义的模式。新算法解决了在大型网络中寻找紧密连接的簇（称为三角形密集子图）这一长期存在的挑战，这一问题在欺诈检测、计算生物学和数据分析等领域至关重要。
该研究发表于IEEE 知识与数据工程汇刊，是由比利时鲁汶大学电气工程助理教授 Aritra Konar 领导的一项合作项目，他曾是 UVA 的研究科学家。
图挖掘算法通常专注于寻找各个点对之间的密集联系，例如经常在社交媒体上交流的两个人。然而，研究人员的新方法被称为“三角形最密集 k 子图问题”，该方法更进一步，通过查看连接三角形——每对连接的三个点组成的组。这种方法捕获了更紧密的关系，例如彼此互动的小团体朋友，或者在生物过程中协同工作的基因簇。
“我们的方法不仅仅着眼于单个连接，还考虑了三个元素组如何相互作用，这对于理解更多元素至关重要复杂网络”，电气与计算机工程系教授西迪罗普洛斯解释道。“这使我们能够找到更有意义的模式，即使是在海量数据集中也是如此。”
查找三角形密集子图尤其具有挑战性，因为用传统方法很难有效求解。但是新算法使用所谓的子模松弛，这是一种巧妙的捷径，可以将问题简化到足以使其更快地解决而不会丢失重要细节。
这一突破为理解依赖于这些更深层次的多重连接关系的复杂系统开辟了新的可能性。定位子组和模式可以帮助发现可疑活动在欺诈中，识别社区动态社交媒体，或帮助研究人员更精确地分析蛋白质相互作用或遗传关系。
更多信息：Aritra Konar 等人，挖掘固定大小的三角形密集子图：硬度、Lovasz 扩展和应用，IEEE 知识与数据工程汇刊（2024）。DOI：10.1109/TKDE.2024.3444608
引文:新算法推进复杂网络的图挖掘（2024 年 10 月 19 日）检索日期：2024 年 10 月 19 日来自 https://techxplore.com/news/2024-10-algorithm-advances-graph-complex-networks.html
本文档受版权保护。除了出于私人学习或研究目的的任何公平交易外，不得未经书面许可，不得复制部分内容。所提供的内容仅供参考。