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

　　

　　

　　弗吉尼亚大学工程与应用科学学院教授Nikolaos Sidiropoulos通过开发一种新的计算算法，介绍了图挖掘领域的一项突破。

　　图挖掘是一种分析社交媒体连接或生物系统等网络的方法，可以帮助研究人员发现不同元素如何相互作用的有意义的模式。新算法解决了在大型网络中寻找紧密连接的集群（称为三角密集子图）的长期挑战，这个问题在欺诈检测、计算生物学和数据分析等领域至关重要。

　　这项研究发表在《IEEE知识与数据工程学报》（IEEE Transactions on Knowledge and Data Engineering）上，由比利时鲁汶大学（KU Leuven）电子工程助理教授、曾在弗吉尼亚大学（UVA）担任研究科学家的阿里特拉·科纳尔（Aritra Konar）领导。

　　图挖掘算法通常专注于寻找单个点对之间的密集连接，例如经常在社交媒体上交流的两个人。然而，研究人员的新方法，被称为三角形-密度-k-子图问题，通过观察三角形的连接——每对连接的三个点的组，更进一步。这种方法可以捕捉到更紧密的关系，比如互相交流的一小群朋友，或者在生物过程中一起工作的基因群。

　　电气与计算机工程系教授Sidiropoulos解释说：“我们的方法不仅关注单个连接，还考虑了三个元素如何相互作用，这对于理解更复杂的网络至关重要。”“这使我们能够找到更有意义的模式，即使是在大量数据集中。”

　　寻找三角形密集子图尤其具有挑战性，因为用传统方法很难有效地求解。但新的算法使用了所谓的次模松弛，这是一种巧妙的捷径，它简化了问题，使其能够在不丢失重要细节的情况下更快地解决问题。

　　这一突破为理解依赖于这些更深层次、多连接关系的复杂系统开辟了新的可能性。定位子群体和模式可以帮助发现欺诈中的可疑活动，识别社交媒体上的社区动态，或者帮助研究人员更精确地分析蛋白质相互作用或遗传关系。

　　更多信息：Aritra Konar等人，固定大小的三角形密集子图的挖掘：硬度，Lovasz扩展及其应用，IEEE知识与数据工程学报（2024）。引文：新算法推进复杂网络的图挖掘（2024年，10月19日）检索自https://techxplore.com/news/2024-10-algorithm-advances-graph-complex-networks.html。本文受版权保护。除为私人学习或研究目的而进行的任何公平交易外，未经书面许可，不得转载任何部分。内容仅供参考之用。