基于有向网络非对等关系的异常子图识别算法

图异常检测将实体间通联关系抽象为复杂网络形式表示,旨在利用结构特征识别网络中存在的异常行为与实体,具有关系客观存在且异常可解释较强的优点.目前该类方法主要以无向网络结构为基础提取特征,以达到识别异常的目的,主要关注于连边层面异常结构,对于由集体异常行为构成的异常子图识别问题研究仍较少,缺少对行为方向异常协同关系的分析....     

基于网络同步的链路预测连边机理分析研究

链路预测是研究复杂网络结构演化趋势的重要组成部分, 用于预测网络丢失的连边和未来可能出现的连边, 具有极大的理论和应用价值.当前链路预测研究成果主要基于网络结构特征对连边进行预测, 具体分析其连边机理的研究较少.网络同步的研究能够深刻反映节点的动力学演化行为与网络结构之间的内在机理.本文针对链路预测考虑的静态网络引入节点动力学模型构成动态网络, 通过分析链路预测连边与动态网络模型同步之间的关系, 对链路预测连边机理进行分析研究.通过实验与理论分析总结发现了链路预测连边具有同步能力稳定性的规律.进一步讨论了链路预测连边的动力学机理, 并揭示了链路预测连边机理与真实网络演化的差别.     

面向复杂网络的异常检测研究进展

异常检测是指识别数据集中显著区别于其他正常模式的数据,广泛应用于欺诈检测、入侵检测、数据分析等领域.现有的异常检测研究大多是基于非结构化数据点集,而现实中数据间复杂的结构关系构成了复杂网络,在数学形式上表示为图,所以面向复杂网络的异常检测的需求日益增加.对此,总结了当前复杂网络异常检测的方法与研究进展:首先提出复杂网络异常检测的必要性与发展历史;其次,分别从静态图和动态图的视角将复杂网络异常检测分为基于结构、社区、关系学习的静态图异常检测和基于节点、边、子图、全图的动态图异常检测;然后,分类别地进行概述、分析与比较,并给出复杂网络异常检测的应用场景;最后,总结未来面向复杂网络异常检测的研究方向.     

基于负载模式识别的Web应用在线异常检测方法

负载模式的动态变化会影响系统度量,使得异常难以准确检测.针对此问题,提出一种基于负载模式识别、在线检测Web应用异常的方法.该方法基于在线增量式聚类算法,运行时识别动态变化的负载模式,根据特定负载模式对应的度量空间,利用局部异常因数检测异常状态,并量化异常程度,并通过学生t测试方法计算度量异常值,以定位异常原因.实验结果表明,所提方法能够准确识别负载模式变化,有效检测出Web应用典型错误所引起的异常状态,并定位异常原因.     

基于拓扑稳定性的有向网络链路预测方法

作为复杂网络研究的热门方向,有向网络链路预测旨在挖掘网络中未知的连边。网络演化机制是许多链路预测方法的理论来源和依据。现有有向相似性指标计算节点间存在连边的可能性时,忽略了实际网络演化过程中节点自身拓扑稳定性和网络结构稳定性。基于此,提出了基于拓扑稳定性的预测方法。该方法首先计算趋于稳定的节点对之间的相似度,然后计算预测节点对之间的拓扑稳定性。在三个衡量标准AUC、precision和排序分下,九个真实网络中的实验分析表明,提出方法具有较高的预测精度。     

基于骨架序列提取的异常行为识别

视频监控系统中的人员异常行为识别研究具有重要意义. 针对传统算法检测实时性和准确性差, 易受环境影响的问题, 提出一种基于骨架序列提取的异常行为识别算法. 首先, 改进YOLOv3网络用以对目标进行检测、结合RT-MDNet算法进行跟踪, 得到目标的运动轨迹; 然后, 利用OpenPose模型提取轨迹中目标的骨架序列; 最后通过时空图卷积网络结合聚类对目标进行异常行为识别. 实验结果表明, 在存在光照变化的复杂环境下, 算法识别准确率达94%, 处理速度达18.25 fps, 能够实时、准确地识别多种目标的异常行为.     

基于复杂网络动力学模型的链路预测方法

链路预测是复杂网络中研究缺失连边和未来形成连边的重要组成部分,当前基于网络结构的链路预测方法成果丰富,而基于复杂网络动力学模型的链路预测研究较少。针对无权无向网络,首先构建了复杂网络动力学模型,然后给出了基于复杂网络动力学模型的链路预测节点中心性的量化评价指标,最后通过给出的节点中心性量化指标,提出了由复杂网络动力学模型定义的链路预测方法。通过在真实网络数据集上进行的实验表明,提出的链路预测方法较基准方法有明显的预测精度的提升。     

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

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

基于局部社团和节点相关性的链路预测算法

基于网络拓扑结构信息的链路预测算法是预测网络未知连边或未来连边的有效方法。在实际应用中,通过进一步提取网络结构信息可以提高网络链路预测结果的精度。文中提出了一种基于局部社团和节点相关性的链路预测算法(HCRP)。该算法把种子节点对的一阶局部社团扩展到二阶局部社团,获得了比一阶局部社团更多的网络结构信息;在用皮尔逊系数计算两个种子节点的相关系数时,该算法也考虑了二阶局部社团的最短路径、边聚类系数和连边密度对两个种子节点相似度的影响,获得了良好的预测网络连边的效果。实验采用了10个真实网络的数据,并对比了HCRP算法和11种知名算法,数值实验结果表明所提算法具有优良的链路预测性能。     

基于改进KNN算法的网络数据流异常识别方法

传统识别方法未对异常数据流进行分类，导致识别正确率不高，提出基于改进K最邻近（K-Nearest Neighbor,KNN）算法的网络数据流异常识别方法。通过预处理异常数据流，提取异常数据流的特征，并以此作为基础，利用KNN算法统计异常数据流的类别，并分类所出现的异常数据。之后，通过计算不同网络环境下识别异常数据的时长，完成网络异常数据流的识别。在仿真实验中，与以往的网络数据流异常识别方法相比，提出的基于改进KNN算法的网络数据流异常识别方法具有更好的识别效果，识别正确率更高。     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

基于熵加权属性子空间的目标社区发现

该文提出一种基于熵加权属性子空间的目标社区发现方法,挖掘与用户偏好相关的社区。首先,从属性和结构两个方面综合考虑节点间的相似度,利用用户给定的样例节点及其邻居扩展得到目标社区中心点集;其次,在中心点集上,设计一种熵加权的属性权重计算方法,得到目标社区的属性子空间权重;再次,利用目标社区的属性子空间权重,基于节点的属性和结构相似度重写网络中边的权重;最后,定义社区适度函数并结合重写后网络中边的权重改进社区适度函数,以中心节点集为核心,挖掘基于用户偏好的内部连接紧密且与外部分离较好目标社区。此外,该方法可以扩展到网络中多个社区发现及离群点检测任务中。在人工网络和真实网络数据集上的实验结果验证了该文所提算法的效率和有效性。     

基于节点相似性和网络嵌入的复杂网络社区发现算法

社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义.传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性.针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法.首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计...     

基于Kullback-Leibler距离的二分网络社区发现方法

现实世界存在大量二分网络,研究二分社区结构有助于从新角度认识和理解复杂网络。由于二分网络特殊的二分结构,使得基于单模网络的现有社区发现算法无法适用。本文提出一种基于Kullback-Leibler距离的二分网络社区发现算法,该算法将异质节点间的连接关系转化为其在用户节点集上的连接概率分布,并建立基于概率分布的KL相似度衡量节点连接模式的差异性,从而克服二分结构对节点相似性评估的不利影响,实现对二分网络异质节点的社区发现。在人工网络和真实网络上的实验和分析表明：该算法能够有效挖掘二分网络社区结构,改善二分网络社区发现的准确性和效率。     

基于Spark的大规模网络结构发现算法

当今社会处于大数据时代,现实中的网络数据越来越多,其结构复杂、规模庞大,有效分析其结构对了解、应用其提供的信息具有重要作用。基于混合模型的网络结构发现算法可挖掘网络中的多类型聚类结构,但不能有效处理大规模网络。基于Graph X图计算模型,提出基于Spark的大规模网络的结构发现算法LNSES,从存储空间和运行时间两方面提升算法效率。为减少网络结构发现算法存储大规模网络邻接矩阵内存耗费量,LNSES算法将边、节点及节点静态属性值进行分布式存储,边分区记录节点连边,可作为索引进行节点间参数传递。为提高网络结构发现算法效率,边分区和节点分区进行拉链操作产生索引结构;更新参数时,节点根据索引找到边分区上对应的边,并行实现节点参数更新。在真实和人工大规模网络数据集上的实验结果表明:LNSES在运行时间和网络结构识别准确度方面都要优于同类网络结构发现算法,可以对大规模网络中的结构进行挖掘分析。     

一种基于模糊相似关系的局部社区发现方法

近几年,在线社交媒体发展飞速,出现了大规模社会网络.传统的基于网络全局结构的社区发现方法难以有效地处理这些大网络.局部社区发现作为一种无需知道网络的全局结构、仅通过分析给定节点的周围节点之间的关系即可找出给定节点所在社区的方法,在社会网络大数据分析中具有重要的应用意义.针对真实世界网络结构中个体间的相似关系是模糊的或不确定性的,提出了一种基于模糊相似关系的局部社区发现方法.首先,采用模糊关系来描述两个节点之间的相似关系,以节点对的相似度作为该模糊关系的隶属函数;然后证明了该关系是一种模糊相似关系,将局部社区定义为给定节点关于模糊相似关系的等价类,进而采用最大连通子图算法求得给定节点所在的社区.分别在仿真网络和真实网络上进行了实验,实验结果表明,该算法能够有效地揭示出给定节点所在的局部社区,相比其他算法,具有更高的F-score.     

基于标签传播的两阶段社区检测算法

社区检测是复杂网络分析的重要研究任务之一,其检测结果有助于人们深入理解复杂网络的社区结构,同时为下游任务提供支持,如内容推荐、链路检测等.针对复杂网络的社区检测问题,提出了一种基于标签传播的两阶段社区检测算法——TS-LPA.TS-LPA采用扩展邻域的思想来量化节点的传播能力,并在此基础上,利用节点信息和网络中边的权重...     

基于特征向量局部相似性的社区检测算法

社区的发现和分析是复杂网络结构和功能研究中的一个热点。目前广泛应用的社区划分算法存在时间复杂度过高、社区核心数量无法准确量化、划分精度不高等问题。文中提出了一种基于特征向量局部相似性的社区检测算法ELSC。该算法首先计算网络中每个节点的特征向量中心性,在此基础上提出了特征向量局部相似性(ELS)和特征向量吸引性(EA)指标。ELS指标表示节点之间的相似性,用来形成初始社区,在同一个社区内部节点之间的相似性较高,在不同社区节点之间的相似性较低;EA指标同时考虑了局部相似性和特征向量中心性的占比,表示节点之间的吸引性,用来优化初始社区,并在此基础上完成网络的社区划分。该算法由最值确定节点,避免了节点数量阈值不确定的问题。在7个真实网络上将所提算法与6种知名算法的模块度和标准化互信息两个指标进行综合比较,结果表明,该算法具有良好的准确性,并且具有较低的时间复杂度。     

基于连边距离矩阵的重叠社区发现

现有重叠社团发现算法大多直接从相邻连边的相似性出发,不能有效利用网络的多层连边信息。基于此,本文提出了一种基于连边距离矩阵的重叠社区发现算法LDM。首先结合连边-节点-连边随机游走模型,以实现多级连边信息的有效利用,其次借助模糊聚类方法,处理连边距离矩阵以获取连边社区,最后根据扩展模块度调整和优化重叠社区结构。在人工网络和真实网络上的实验结果表明,所提算法能够有效提高重叠社区发现算法的准确度。