新算法助力!复杂网络图挖掘迎来重大突破
弗吉尼亚大学工程与应用科学学院的教授尼古拉奥斯·西迪罗普洛斯在图挖掘方面取得了突破,开发了一种新的计算算法。
图挖掘这种方法用于分析像社交媒体连接或生物系统之类的网络,帮助研究人员发现不同元素相互作用的有意义模式。新算法解决了在大型网络中寻找紧密连接的簇(称为三角形密集子图)这一长期存在的挑战,这一问题在欺诈检测、计算生物学以及数据分析等领域都极为重要。
这项研究发表于 《IEEE 知识与数据工程汇刊》 上,是由比利时鲁汶大学电气工程助理教授阿里特拉·科纳尔(Aritra Konar)领导的合作成果,他之前是弗吉尼亚大学的研究科学家。
图挖掘算法通常专注于寻找单个的点对之间的密集连接,例如在社交媒体上经常交流的两个人。然而,研究人员的新方法,被称为“三角形 - 最密集 - k - 子图”问题,更进一步,通过查看连接三角形——每对都相互连接的三个点组成的组。这种方法捕捉到更紧密的关系,比如相互交流的一小群友人,或者在生物过程中共同起作用的基因簇。
“我们的方法不仅仅看单一的连接,而是考虑三个元素的组如何相互作用,这对于理解更复杂的网络至关重要,”电气和计算机工程系的教授西迪罗普洛斯解释道。“这使我们能够在海量数据集中找到更有意义的模式。”
寻找三角形密集子图尤其具有难度,因为采用传统方法难以有效地解决这一问题。
但新算法运用了所谓的子模松弛,这是一条巧妙的捷径,它把问题简化到足以让其更快地被解决,而且不会遗漏重要细节。
这一突破为理解依赖于这些更为深入、多重连接关系的复杂系统开辟了新的可能。
定位子群和模式有助于发现欺诈中的可疑活动,识别社交媒体上的社区动态,亦或帮助研究人员更精准地分析蛋白质相互作用或遗传关系。