动态网络模式挖掘方法及其应用

静态复杂网络研究在揭示社会网络、信息网络和生物网络的形成和演化机制方面取得了重要成果,其方法和结果对系统生物学产生了重要影响.但现实世界中,很多网络是随时间发生变化的,即动态网络.以动态网络为对象,对动态网络的拓扑特性分析、动态网络相关的各种模式挖掘模型和方法进行了综述、比较和分析.特别地,将动态网络模式分析方法应用于生物网络和社会网络,分析了生物网络相关的动态功能模块和模式演化问题、科学家合作网络和社交网络的动态模式.最后指出了动态网络的模式挖掘方法及其在动态生物网络和社会网络研究中存在的问题和挑战,并对未来的研究方向进行了分析.     

动态攻击网络演化分析模型*

将基于攻击图的脆弱性评估技术和动态网络演化分析相结合,提出了一种动态攻击网络演化与分析模型。该模型首先借鉴演变图的思想将攻击图拓展为随时间域和空间域同时变化的演变攻击图,在子图相似度定义的基础上构建攻击演化模式,分析模式内暂态变化的同时结合时序数据分析模式间的连接变化,以攻击演变挖掘算法为核心的模型应用分析过程可以确定整个过程中攻击模式的数量,明晰每个模式的典型攻击结构,实例证明本文提出的模型和方法可以有效地模拟攻击发生的过程,当需要防御手段进行干预时,可有针对性的选择危害大的阶段或者节点来抑制攻击过程的发生     

支持复杂社会网络演化的过程挖掘技术综述

复杂社会网络演化过程研究对于发现社会网络群体的隐含结构和演化规律,以及风险预测具有重要意义。首先梳理了过程挖掘技术的发展脉络,阐述复杂社会网络分析方法与过程挖掘技术相结合在复杂社会网络演化模式研究、组织结构发现中的应用现状,结合社会网络分析方法和大数据技术,运用服务工程思想,进而从社会和资源维度综述社会网络跨组织业务过程发现、动态社会网络演化过程发现、角色挖掘与服务挖掘等技术,指出现有复杂社会网络过程挖掘研究面对大数据质量和跨组织异构等研究方面的不足,对大规模社会网络过程挖掘领域的研究难点和发展趋势进行了讨论。     

空间co-location模式增量挖掘及演化分析

空间co-location模式挖掘是空间数据挖掘的一个重要研究方向.空间co-location模式是空间对象的一个子集,它们的实例在空间中频繁关联.到目前为止,空间co-location模式挖掘都只关注某一个时刻的空间co-location模式.然而,在实际应用中,数据库中的数据是随着时间改变的,所以高效地增量挖掘空间co-location模式是非常必要的;空间co-location模式演化分析可以发现空间co-location模式的变化规律,预测特定事件的发生,但是对这些问题的研究并未见诸报道.研究了高效的空间co-location模式增量挖掘及空间co-location模式的演化分析,首先,提出了高效的空间co-location模式增量挖掘基本算法及剪枝算法.其次,在多个随时间变化的真实数据集上挖掘co-location演化模式.再次,证明了空间co-location模式增量挖掘基本算法及剪枝算法是正确的和完备的.最后,在"模拟+真实"的数据集上用充分的实验验证了增量挖掘基本算法的性能以及剪枝算法的剪枝效果.此外,把空间co-location增量挖掘基本算法、剪枝算法及演化模式挖掘算法应用到三江并流区域珍稀植物数据集上,增量挖掘出空间co-location模式及演化模式,预测了co-location模式的演化规律,更好地实现了对珍稀植物的动态跟踪和保护.     

基于加权动态网络的频繁模式挖掘研究

不同时刻的动态网络往往具有不同权重,针对加权动态网络的频繁模式挖掘,提出一种挖掘算法WGDM,它适用于加权动态社会网络、生物网络等方面的频繁模式挖掘。WGDM算法利用支持度的反单调性裁剪搜索空间,从而减少冗余候选子图,提高算法效率。通过实验测试了WGDM算法的性能,并根据中国实际股票市场网络,利用WGDM算法挖掘股票市场网络中有趣的频繁模式。     

在线社会网络的动态社区发现及演化

在线社会网络研究中,动态隐含社区或群组结构的发现及演化探测是一个十分关键的核心问题,它对于在中观(Mesoscopic)视图观察在线社会网络隐结构特征、预测演化趋势、掌控网络势态、发现网络异常群体事件等具有重要意义.文中首先分析了动态社区发现和社区演化研究的关系,给出动态社区研究中关键挑战问题;然后根据问题背景的不同,从“同构社会网络的动态社区研究”和“异构社会网络的动态社区研究”两个方面进行国内外相关研究现状的阐述和分析,其中,在“同构社会网络的动态社区研究”中,根据评价方法的差异和关注问题的不同将当前相关研究分为基于时空独立评价、时空集成评价、统一评价和增量式算法4大类进行综述,同时对动态社区发现的重要应用——异常群体发现的研究进行介绍;最后对在线社会网络动态社区领域的难点和发展趋势进行分析和展望.     

动态基因调控网演化分析

动态基因调控网是展现生物体内基因与基因之间相互关系随时间变化而变化的动力学行为的复杂网络.这种相互作用关系可以分为两类：激励和抑制.对动态基因调控网网络演化的研究,可以预测未来时刻生物体内的基因调控关系,从而在疾病预测和诊断、药物开发、生物学实验等领域起到重要的指导和辅助作用.现实世界中,动态基因调控网的网络演化是一个复杂而巨大的系统,当前,对于其演化机制的研究存在只关注静态网络而忽略动态网络和只关注相互作用关系而忽略相互作用类型的缺陷.针对上述问题,提出了一种动态基因调控网演化分析方法（dynamic gene regulatory network evolution analyzing method,简称DGNE）,将研究扩展到了动态带符号网络领域.通过该方法包含的基于模体转换概率的连边预测算法（link prediction algorithm based on motif transfer probability,简称MT）和基于隐空间特征的符号判别算法,能够动态地捕捉基因调控网的演化机制,并准确地预测未来时刻基因调控网的连边情况.实验结果表明,DGNE方法在仿真数据集和真实数据集上均有良好的表现.     

基于扩散理论的动态社区挖掘

针对动态社区挖掘问题进行分析和研究,基于优先情节和增长定律,根据节点的度数分布,提出以时间为轴动态模拟社会网络的形成演化机制,同时进行社区划分。以Zachary Club和工二s Miscrablcs网络作为实验数据集,对提出的算法进行了实验验证,结果表明,该算法挖掘到的社区都是强连通社区,能够动态、精确地挖掘网络中存在的社区结构,具有较高的实用价值。     

动态空间网络中的黑洞模式挖掘算法

黑洞模式是人类移动模式研究中的标志性成果,但在移动模式的演化建模方面存在局限性,因此研究具有时间演化特性的黑洞模式。新模式定义需要满足群体规模性、空间区域性和时间持续性3方面要求。提出具有时间演化特性的动态空间网络模型,基于此模型定义新的黑洞模式,并提出相应的挖掘算法。为了提升模式挖掘算法的效率,设计了基于时空划分的候选模式剪枝算法,有效降低了挖掘算法在时空维中的搜索代价。最后,基于真实数据的实验结果表明了该黑洞模式及其挖掘算法的有效性和可行性。     

动态信息网络中的角色演化异常及其发现

现实世界中的社交网络、合作者网络、邮件网络等诸多复杂系统均可抽象为动态信息网络。动态信息网络具有时序、复杂、多变的特征,分析其网络结构随时间演化的过程,尤其演化过程中出现的异常现象,对理解复杂系统的行为倾向于演化趋势具有重要意义。致力于动态信息网络中异常结构演化过程的发现,通过角色定义刻画网络的结构特征,提出了角色演化异常(role evolving outliers,REOutliers)的概念,并给出了基于模式挖掘的角色演化异常发现算法(pattern-based role evolving outliers detection,P-REOD)。该算法挖掘整个网络中角色随时间演化的频繁模式,通过比较节点到频繁模式的相异程度进行REOutliers发现。实验表明,该算法能够进行有效的角色演化异常发现。     

社群演化的稳健迁移估计及演化离群点检测

时序数据集中的社群演化模式是网络行为动力学研究与应用的重要领域.基于社群演化的离群点检测不仅能够发现新颖的异常行为模式,同时也有利于更准确地理解社群的演化趋势.运用成员关于社群隶属关系的变化,提出了社群演化迁移矩阵的概念,研究并揭示了迁移矩阵的若干性质及其与社群结构演化之间的关系.在采用稳健回归M-估计方法进一步优化迁移矩阵降低异常点干扰的同时,对社群演化离群点加以刻画和定义.鉴于复杂网络包含大量随机游走的边缘个体,所定义的离群点综合考虑其在社群中角色的变化和相对于社群总体迁移模式的差异.基于上述思想提出的演化离群点检测算法能够适应各类社群演化趋势,更有效地聚焦和发现大规模社会网络中重要成员的异常演化行为.实验结果表明,所提出的方法能够从大规模社会网络演化序列中发现重要的离群演化模式,并在现实中找到合理的解释.     

C_2风格软件构架的演化研究

软件演化是软件生命周期中始终存在的变化活动,软件维护只是软件演化的特定阶段的活动和组成部分。由于软件复用思想的兴起,基于构件和构架的软件开发方法得到越来越广泛的应用,而相应的软件演化就成为组成软件系统的构件的演化和构架的演化。该文探讨了软件演化和构架演化的概念,研究了构架动态演化所涉及到的问题,并在分析软件构架风格的基础上重点研究了C2构架风格对构架动态演化的支持能力。该文提出的构架动态演化模型及其与C2风格的结合能够支持实际的构架演化。     

基于Agent的森林火灾系统建模仿真

为研究森林火灾系统的整体发展态势及演化规律,引入面向模式的基于Agent的建模方法,进行了融合自然、社会微观作用机理的计算机仿真研究,以Agent元模型为软件实现基础建立起森林火灾系统模型,有机融合了林火蔓延的元胞自动机模式和协作扑救的网络协作模式.对森林火灾系统模型进行动态仿真实验,实验结果表明了有关模式对系统态势发展的影响,以及基于Agent的建模方法对森林火灾系统研究的有效性.     

恐怖组织网络的时空演化规律

为了理解恐怖组织网络的时空演化特性及形成机理,本文运用统计物理学方法,结合Multi-agent,提出了一个恐怖组织网络的时空演化模型, 并对恐怖组织网络的演化规律进行了数值模拟研究.模拟过程中考虑了恐怖组织网络在时间与空间上节点与边的动态联结变化.研究发现:网络演化过程中, 恐怖组织的网络演化不仅兼具小世界、无标度特性和等级结构,不同级别的中心节点将网络连为一体,而且存在促进恐怖网络不断演化的主要因素, 即与恐怖分子信念的增加及环境资源的增长有关; 反恐方的选择性打击对网络的增长具有抑制作用和一定的控制效果.     

复杂网络演化的舆论动力学模型及仿真分析

针对舆论传播过程中复杂动力学演化问题,提出一种基于传播动力学的舆论动态演化模型。首先,构建舆论及舆论演化模型,通过方程变换求出静态解;其次,引入Fokker-Planck方程对舆论演化渐近行为进行分析,得到稳态解决方案并求解,构建复杂网络与模型的关联并提出仿真研究实验目的;最后,通过对舆论演化模型及引入Fokker-Planck方程的舆论意见模型进行仿真分析,并以真实微博舆论数据为例进行实证分析,研究舆论在复杂网络中传播和演化的实质。实验结果表明舆论网络演化渐近行为与度分布相一致,网络舆论传播中的连接方式会受到节点意见影响,模型能有效描述微博舆论传播网络形成和演化过程的动力学行为。     

基于节点匹配度的动态网络链路预测方法

现实世界存在众多真实网络,研究真实网络中的动态演化趋势和时序性特征是热点问题。链路预测技术作为网络科学领域重要研究工具可通过挖掘历史连边信息推测网络演化规律,进而对未来连边进行预测。通过分析动态真实网络中的拓扑结构演化,发现通过分析网络拓扑中节点间的交互性和匹配度问题能够更充分捕捉网络的动态特征,提出一种基于节点匹配度的动态网络链路预测方法。该方法对网络节点的属性特征进行分析,定义基于原生影响力和次生影响力的节点重要性量化方法;引入时间衰减因子,刻画不同时刻网络拓扑对连边形成的影响程度;结合节点重要性和时间衰减因子定义动态节点匹配度（TMDN,temporal matching degree of nodes）方法,用于衡量节点对之间未来形成连边的可能性。在5个真实动态网络数据集中的实验结果表明,相比现有 3 类主流动态网络链路预测方法,所提方法在 AUC 和Ranking Score 两种评价标准下均取得更优的预测性能,预测结果最高提升 42%,证明了节点间存在着交互匹配优先级,同时证实了节点原生影响力和次生影响力的有效性。     

生物过程的数学方法

生物信息学的研究内容分为两类:研究生物在细胞和分子水平的静态特征下的静态问题,和研究这些静态特征的动态演化规律的动态问题,并称后一类问题为生物过程。这两类问题在数学方法上的主要区别是:前者以寻找和设计高效的算法为主;后者主要是建立生物过程的数学模型,以便模拟和分析。综述了生物过程数学建模的三种主要方法:微分方程方法,贝叶斯网和概率布尔网络方法,以及进程代数方法。最后对这几种方法进行讨论。     

一种基于特征演变的新闻话题演化挖掘方法

话题演化挖掘研究可以准确完整地获取新闻话题动态演化各个阶段的话题内容,帮助用户理解新闻话题的来龙去脉以及话题内容之间的相关性和差异性,因此在网络新闻检索、网络舆情监控、互联网突发事件检测与应急管理等方面具有十分重要的作用和应用前景.现有工作由于缺乏对话题特征随时间发展而动态演变的深入分析,仅仅采用均值泛化的思想去增量扩充演化中的话题特征,引入大量话题无关信息,影响了话题关联的准确率,从而导致最终话题演化挖掘结果的偏斜.因此,针对以上问题,文中通过引入话题特征演变特性,提出一种针对话题演化的特征计算模型,在此基础上利用已有话题相关文档和最新文档进行话题信息动态增量扩充,通过对话题特征进行正向融合以及逆向过滤完成对特征信息的抗噪处理,提高话题关联的正确率,有效地解决了话题演化的偏斜问题.     

基于链路预测的社会网络事件检测方法

网络演化分析与事件检测,是当前社会网络研究的热点和难点.现有的研究工作主要是针对网络提出不同的模型,并用网络特征指标对仿真结果进行评价.这些方法存在如下问题:(1) 每种方法仅针对特定网络,通用性不高;(2) 特征指标多种多样,不同模型的表现情况缺乏统一的评价标准;(3) 未考虑网络演化的时间特性,难以描述网络演化的波动性,无法检测事件.针对上述问题,提出一种基于链路预测的社会网络事件检测方法LinkEvent(由相似性计算算法SimC和事件检测算法EventD组成),它可以对不同网络的波动性进行统一评价,并依此建立事件检测模型.主要工作包括:(1) 证明了链路预测可以反映网络演化机制,相同机制下的模型演化法和链路预测在分析网络演化上具有内在的一致性;(2) 基于链路预测,提出一种网络相似性计算算法SimC(similar computing),并在考虑微观因素的基础上进行改进;(3) 利用相似性计算结果,提出一种事件检测算法EventD(event detecting)检测出新事件.在不同特征的网络上进行实验,结果表明:所提出的LinkEvent方法能够较好地解决网络演化波动性问题,实现事件检测;同时也证明了利用链路预测技术进行网络演化分析的可行性以及相似性计算和事件检测算法的有效性.     

基于话题概率模型的语义社区发现方法研究

语义社会网络(Semantic social network, SSN)是一种由信息节点及社会关系构成的复杂网络, 也是语义信息时代社会网络技术研究的热点, 相较于传统社会网络更具实用价值. 其研究内容包含了社会网络的语义分析及社会关系分析, 因此, 语义社会网络的社区挖掘建模具有一定的复杂性. 在语义社会网络的社区挖掘研究方面, 本文分析了当前基于话题概率模型的语义社区发现方法, 并在综述其内容的同时总结了各方法的优缺点, 为后续研究提供了理论基础. 在语义社会网络社区挖掘结果的评判方面, 本文归纳了相关的评价模型, 并通过实验分析对比了各模型对拓扑相关性和语义相关性的倾向性.