论文标题
动态图的结构熵的增量测量
Incremental Measurement of Structural Entropy for Dynamic Graphs
论文作者
论文摘要
结构熵是一个指标，可在层次抽象的策略下衡量图形结构数据中嵌入的信息量。为了测量动态图的结构熵，我们需要解码与每个快照的最佳社区分区相对应的最佳编码树。但是，当前方法不支持动态编码树更新和增量结构熵计算。为了解决此问题，我们提出了Incre-2DSE，这是一个新颖的增量测量框架，可以动态调整社区分配并有效地计算每个更新的图表的更新结构熵。具体而言，INCRE-2DSE包括基于两种动态调整策略的增量算法，用于二维编码树，即天真的调整策略和节点移动调整策略，支持更新的结构熵的理论分析，并为较低的结构侧型提供了逐步优化社区分配。我们对Hawkes Process和3个现实世界数据集生成的3个人工数据集进行了广泛的实验。实验结果证实，我们的增量算法有效地捕获了社区的动态演变，减少时间消耗并提供了极大的解释性。
Structural entropy is a metric that measures the amount of information embedded in graph structure data under a strategy of hierarchical abstracting. To measure the structural entropy of a dynamic graph, we need to decode the optimal encoding tree corresponding to the best community partitioning for each snapshot. However, the current methods do not support dynamic encoding tree updating and incremental structural entropy computation. To address this issue, we propose Incre-2dSE, a novel incremental measurement framework that dynamically adjusts the community partitioning and efficiently computes the updated structural entropy for each updated graph. Specifically, Incre-2dSE includes incremental algorithms based on two dynamic adjustment strategies for two-dimensional encoding trees, i.e., the naive adjustment strategy and the node-shifting adjustment strategy, which support theoretical analysis of updated structural entropy and incrementally optimize community partitioning towards a lower structural entropy. We conduct extensive experiments on 3 artificial datasets generated by Hawkes Process and 3 real-world datasets. Experimental results confirm that our incremental algorithms effectively capture the dynamic evolution of the communities, reduce time consumption, and provide great interpretability.
