在线多分辨率时间演化图聚类及簇演变模式挖掘

各种真实世界网络以及链接关系数据随处可见，其海量性、复杂性、动态性、异构性等特征使得图数据挖掘成为当前一项颇具挑战性的研究课题。研究时间演化图中的高密度簇及其演变模式的在线多分辨率挖掘方法，对于高效、实时地揭示网络的内在社团结构、理解其功能特性、发现其演化规律、监控与预测其演变行为等均有重要意义。本项目采用图聚类分析技术，重点研究针对大规模动态网络的在线多分辨率、参数自适应、增量式图聚类算法，支持实时网络社团探测的图流聚类算法，支持异构网络分析的互聚类算法，以及针对多时间戳网络的图演化聚类与簇演变模式分析算法。实现大规模动态网络内在社团结构的自动、快速、准确、及时发现，社团形成、生长、分裂、合并、萎缩、凋亡等演化事件的自动监控，以及社团生命周期中各类演变模式的有效分析和挖掘。设计实现时空效率高、无需用户干预、可伸缩性强、鲁棒性好的算法软件包，并使其能广泛用于分析各种真实网络系统。

在当今互联网时代下，各种复杂网络系统和链接关系数据随处可见。这些网络中呈现出明显的内在的社团结构。同时，真实世界中的复杂网络还是随时间动态演化的，随时会有新的结点加入或旧的结点消失，结点间的链接关系也会发生变化。故而真实网络中的社团必然跟随时间而不断发生变化。因此，研究动态复杂网络中的社团探测及其演变模式分析方法，揭示真实复杂网络中的社团结构以及社团演变的事件、模式和规则具有深远的科学价值。. 本项目研究的“在线多分辨率时间演化图聚类及簇演变模式挖掘”就是实现对大规模网络的在线、多分辨率图聚类研究，并在此基础上进行动态图聚类算法研究，进而将问题延伸到多时间戳图上，研究针对连续多时间戳图的演化聚类算法，用于挖掘时间演化网络中社团的演变事件以及多路演变模式。在本项目组的不懈探索下，至项目结题之时，该研究已经取得了丰硕的成果，包括多篇学术论文，专利、算法软件包等若干项。通过研究大规模时间演化图聚类问题，我们已经可以实现动态、时变网络中社团的在线、自动、快速、准确发现和多分辨率分析；通过研究连续多时间戳图中高密度簇的演变事件与模式分析问题，实现了对动态网络中社团的形成、生长、分裂、合并、萎缩、凋亡等生命事件，及其演变过程与模式的实时监控与有效跟踪。. 研究成果对于揭示动态复杂网络的内在拓扑结构、理解其功能特性、发现其中组织的演变规律、监控和预测网络的行为等均有十分重要的理论意义。此外，该研究成果所带来的潜在应用价值不胜枚举，例如挖掘万维网中的社团，实现Web文档的主题聚类，而且对提高网络搜索的性能，实现信息过滤、热点话题跟踪，网络舆情分析，客户群挖掘，犯罪核心监控等均有重要作用。本项目的研究具有深刻的理论意义，丰富的实用价值和广阔的应用前景。