2022/07/26 by Runze Yang, Hao Peng, Yang, Runze +4 · 1 citation
Computer Science · Neuroscience · Physics and Astronomy · #Advanced Graph Neural Networks #Algorithm #Complex Network Analysis Techniques #Computer science #Data mining #Entropy (arrow of time) #FOS: Computer and information sciences #Functional Brain Connectivity Studies #Graph #Information Theory (cs.IT) #Interpretability #Machine learning #Snapshot (computer storage) #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2207.12653
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.