论文部分内容阅读
复杂网络的挖掘研究拥有广泛的应用领域，例如生物网络、化学网络、Internet、合作网和社会网络等。挖掘动态网络模式已经引起了极大的关注，这是因为现实世界中大多数的复杂系统都是动态演化的，可以用动态可变的网络来描述，其蕴含的动态模式无法用静态网络准确描述。已有的频繁子图模式、聚类和社区结构挖掘等问题的研究成果，大都足基于静态网络的，仅能反映动态网络中一个子图内的模式，并不能很好地揭示时间和空间区域内所蕴含的演化模式与演化规律。挖掘动态网络中隐藏的动态模式为我们带来了全新的挑战。本文对多种动态演化模式挖掘的若干问题和算法进行了深入探索，力图从微观角度揭示复杂网络在时空区域内的演化规律，主要研究工作如下：
(1)关于动态网络的挖掘，目前主要集中在挖掘无权图的拓扑结构，较少涉及有权图的挖掘，然而动态有权图在真实网络中是大量存在的，权值的演化也是网络演化中不可分割的一部分。针对动态有权图，提出了一种基于相关子模式的δ-STC模型，并设计了一种联合聚类(Biclustering)算法δ-STC，挖掘在一定时间区间内边的权值演化趋势线性相关的时空区域。算法以后缀树为索引结构，避免了穷举各种模式，从而快速提取全部聚类结果。合成数据与真实基因调控网络数据的实验证明了算法的有效性和可行性。
(2)对动态有权图，挖掘权值变化非线性相关的趋辨Motif。趋势Motif是一种有向子图，反映拓扑结构与权值共同作用时在一定时间区间上的演化模式。引入广义信息论中二次互信息作为相似性函数，结合滑动窗口技术，建立了一种权值向量非线性相关模型。在此基础上提出了复杂网络趋势Motif挖掘算法MI-TMotif。实验结果显示MI-TMotif算法具有良好的运行性能，成功挖掘出非线性相关的趋势Motif。
(3)研究动态无权网络微观演化模式的挖掘问题，即从边演化的角度，挖掘在时间维上反复出现的子图序列和对应的演化动作序列。提出了挖掘算法EPMiner，以随机过程的状态转移描述演化过程，以演化时子图拓扑结构的变化描述演化模式，提取其中的频繁模式，以揭示演化动作与频繁子图拓扑结构之间的关联关系。通过挖掘合成数据与真实数据，验证了算法的有效性，所得到的演化模式显示，此类模式能够提供丰富的动态演化信息。
(4)已有的频繁子图挖掘方法，通常是挖掘时间上同步的频繁子图，或者忽略时间因素，不能移动时间标记进行对齐，即不能识别时间异步的频繁子图。为揭示更加复杂的演化模式，对动态无权图，挖掘在时间维上的频繁演化Motif，即由同步同构和异步同构的频繁子图所构成的演化状态序列，从而观察子图结构在随时间演化时所经历的演化轨迹，揭示局部子图结构在演化中所起的作用。提出了挖掘算法CloEM，首先生成单独的频繁Motif，然后扩展构造闭合的演化Motif。为有效提取闭合演化Motif，提出了既能扩展频繁演化Motif，又能有效剪枝，并同时完成闭合检验的混合扩展策略，该策略无需维护候选集。实验表明，CloEM算法能够有效挖掘出隐藏住数据中的频繁演化Motif。