Abstract: Graph Partitioning Change Detection (GPCD) problem is important in that it leads to discovery of important events which cause changes of network communities.Aiming at the disadvantages that the existing detecting algorithms do not consider dynamic graph partitioning structures,it employs probabilistic trees to represent probabilistic models of graph partitioning structures,and reduces GPCD into the issue of detecting changes of trees on the basis of the Minimum Description Length (MDL) principle,and proposes Tree algorithm for solving the GPCD problem.Simulation experimental results show that the algorithm realizes significantly less False Alarm Rate(FAR) for change detection than the baseline method called GraphScope.And it is able to detect changes more accurately than GraphScope.

Key words: Graph Partitioning Change Detection (GPCD), Minimum Description Length(MDL), probabilistic tree, cost of change, False Alarm Rate(FAR)

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

关键词: 图分割变化检测, 最小描述长度, 概率树, 变化成本, 虚警率

CLC Number: 

• TP393