魏长宝，姚汝贤

（黄淮学院信息工程学院，河南驻马店463000）

·图形图像处理·

基于最小描述长度的图分割变化检测改进算法

魏长宝，姚汝贤

（黄淮学院信息工程学院，河南驻马店463000）

图分割变化检测（GPCD）可检测出可能导致网络社区发生变化的重要事件。针对现有的检测算法未考虑图形分割结构动态特点的不足，利用概率树表示图分割结构的概率模型，将GPCD问题转化为基于最小描述长度的树变化检测问题，并提出一种求解GPCD问题的Tree算法。仿真实验结果表明，与GraphScope基准算法相比，该算法检测图分割结构变化时的虚警率较低，并具有较高的检测精度。

图分割变化检测；最小描述长度；概率树；变化成本；虚警率

中文引用格式：魏长宝，姚汝贤.基于最小描述长度的图分割变化检测改进算法［J］.计算机工程，2015，41（7）：274⁃279，284.

英文引用格式：Wei Changbao，Yao Ruxian.Improved Algorithm of Graph Partitioning Change Detection Based on M inimum Description Length［J］.Computer Engineering，2015，41（7）：274⁃279，284.

1 概述

图分割技术［1⁃3］（也称图聚合问题）是一种按照某种标准将图分成若干子模块的方法。图分割可以使得分割后各子模块中节点联系更紧密，模块间联系更低。该技术在蛋白质网络、网络数据挖掘等许多领域都有广泛应用。本文主要研究如何对二分图时间序列的图分割结构变化进行检测。将该检测问题称为图分割变化检测（Graph Partitioning Change Detection，GPCD）问题。根据链路关系，图分割结构可看成图节点的聚类结构。这一图分割过程将会导致多个网络社区。因此，它有助于社区结构变化检测及图分割结构变化检测，而社区结构变化往往对应于真实世界中的重要世界，因此研究GPCD问题具有重要意义［4⁃5］。……