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

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

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

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

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

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

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

　　作为弗吉尼亚大学排名第一的综合性大学的一部分，弗吉尼亚大学工程学院是美国最古老、最受尊敬的工程学院之一。我们的使命是通过创造和传播知识，培养未来的工程领导者，让世界变得更美好。来自世界各地的优秀学生和教师选择UVA工程，因为我们不断发展和国际公认的教育和研究项目。就女性毕业生比例而言，弗吉尼亚大学是全美排名第一的公立工程学院，在拥有至少75个学位的学校中；四年制本科毕业率居全美工科院校前列；在博士入学增长率方面，它也是全国增长最快的公立工程学院之一。自2016年以来，我们的研究项目增长了95%。登录engineering.virginia.edu了解更多信息。