Incremental Measurement of Structural Entropy for Dynamic Graphs

(“Two-dimensional encoding tree” means the height of the encoding tree is restricted to $2$. The corresponding structural entropy of the two-dimensional encoding tree is named “two-dimensional structural entropy”.; Additionally, we also generalize our incremental methods to undirected weighted graphs and conduct a detailed discussion on the calculation of one-dimensional structural entropy for directed weighted graphs.; Extending the proposed methods to weighted graphs and providing new incremental computation methods for directed weighted graphs.; Section 5 gives discussion on more complex graphs.; Finally, we give further discussion between the two proposed dynamic adjustment strategies.; An example graph with its two equivalent two-dimensional encoding trees.; An example graph with its two equivalent two-dimensional encoding trees.; An intuitive way to calculate the updated two-dimensional structural entropy is to update the variables in Eq. (4) and then compute via the updated formula Eq. (14). However, the incremental size $n$ affects all terms in the summation equation in Eq. (14). Therefore, the updating and calculation process costs at least $O(|\mathcal{V}|)$, which is huge when the graph becomes extremely large. So how can we find an incremental formula with a smaller time complexity only related to the incremental size $n$? An intuitive attempt is to make a difference between the updated structural entropy and the original one to try to compute the incremental entropy in $O(n)$. Nevertheless, the fact that $m$ changes to $m+n$ in all terms of Eq. (14) makes it difficult to derive a concise formula of $O(n)$ from the difference equation. ; To address this issue, we here introduce Global Invariant and Local Difference. We define the Global Invariant (Definition 5) as an approximate updated structural entropy that only updates $m$ to $m+n$ in Eq. (4) and keeps other variables unchanged. The Local Difference (Definition 6) is defined as the difference between the updated structural entropy and the Global Invariant, which can also be regarded as the approximate error.; Obviously,; by computing and summing up the Global Invariant and the Local Difference. In the experimental part, we use a more explicit and practiced form of the structural entropy update formula (Eq. (55)) derived from the Global Invariant and the Local Difference.; Discussion: The boundedness analysis gives the lower and upper bound of the Local Difference. This suggests that when we compute Global Invariant to quickly get an approximate value of the updated structural entropy, the approximate error is bounded and decreases as the graph grows larger and thus the validity and accuracy of the approximation are guaranteed. ; Discussion: The convergence analysis gives proof of the convergence of the Local Difference and its first-order absolute moment. That is, when we use Global Invariant to approximate the updated structural entropy, the approximate error and its absolute value’s expectation both converge to $0$ no slower than $O(\frac{\log m}{m})$ as the graph edge number $m$ grows larger, suggesting a high level of confidence that our approximation is reliable. Additionally, the convergence analysis also demonstrates that the updated structural entropy is mainly contributed by the incremental size $n$ other than the position of the incremental edges when the graph is extremely large. It is because when the graph grows larger, we can approximate the updated structural entropy with an approximate error that converges to $0$ by simply changing $m$ to $m+n$. ;

3.1.5 Limitations

The limitations of the naive adjustment strategy are listed below. First, this strategy cannot deal with multiple incremental edges at the same time, e.g. a new node appears connecting with two different existing nodes. An alternative solution is to arrange all incremental edges at a certain time stamp into a sequence with which we can add the edges one by one while keeping the connectivity of the graph. In this way, the community of newly introduced nodes is inevitably related to the input order of the incremental edges. Second, it cannot handle edge or node deletions. Third, the community of the existing nodes remains unchanged, which is sub-optimal in most cases.

; as the best community for a target node, i.e., if the target node moves into its OPC, the overall two-dimensional structural entropy must be the lowest compared to other community other than OPC.; First; for further theoretical analysis; Second; Further Discussion between the Two Dynamic Adjustment Strategies; Further Discussion between the Two Dynamic Adjustment Strategies; Similarities: (1) Both dynamic adjustment strategies are designed to incrementally change the original two-dimensional encoding trees to adapt the incremental edges and nodes in dynamic scenarios. (2) The time complexities for computing the updated structural entropy of both strategies are significantly lower than the original calculation formula (detailed analysis is shown in Section 4.3). (3) Both strategies cannot handle the birth of new communities and the dismission of the existing communities. ; Differences: (1) The focuses of the two strategies are different. The naive adjustment strategy emphasizes theoretical analysis, such as boundedness and convergence analysis, and acts as a fast incremental baseline in experimental evaluations. By contrast, the node-shifting adjustment strategy mainly focuses on addressing the limitations of the naive strategy (Section 3.1.5) and the dynamic optimization of the existing communities towards a lower structural entropy. (2) The ways of updating encoding trees, or updating community partitionings, of these two strategies are different. In the naive adjustment strategy, new edges do not change the communities of the existing nodes, and new nodes are assigned to the direct neighbors’ communities. While in the node-shifting adjustment strategy, the influence on community adjustment of new edges is considered and the new nodes’ community is also determined by the incremental edges. (3) The time complexity of the naive adjustment strategy is fixed while that of the node-shifting strategy grows nearly linearly with the iteration number $N$. Experiments show that the naive strategy is faster than the node-shifting strategy with $N\geq 5$ in most cases (Fig. 13). ; Definitions; Definitions; In this part, we present the definitions of Structural Data, Structural Expressions, and Adjustment, which will be employed in subsequent sections. ; efficiently; while dynamically adjusting the community partitioning; Baseline: the Traditional Offline Algorithm; Baseline: the Traditional Offline Algorithm; Extensions on More Complex Graphs; Extensions on More Complex Graphs; In this section, we discuss the feasibility of the extension to weighted or directed graphs of our methods. First, we argue that the method for undirected weighted graphs can be extended naturally from that of undirected unweighted graphs. Second, we analyze the fundamental differences between the paradigm of structural entropy incremental computation for directed graphs and that for undirected graphs and present new methods for calculating one-dimensional structural entropy incrementally on directed weighted graphs. ; Undirected Weighted Graphs; Undirected Weighted Graphs; The incremental measurement method of structural entropy for undirected weighted graphs can be intuitively and easily extended from the methods for undirected unweighted graphs proposed earlier. In the following, we first introduce the definition of two-dimensional structural entropy of undirected weighted graphs. Then we update the definition of the Adjustment and propose an incremental formula for structural entropy computation under the new circumstance. ; Two-dimensional structural entropy of undirected weighted graphs. An undirected weighted graph can be denoted as $G_{W}=(\mathcal{V},\mathcal{E},w)$, where $w(e)\in\mathbb{R}^{+}$ represents the weight of $e\in\mathcal{E}$. For any $e\notin\mathcal{E}$, let $w(e)=0$. According to Li and Pan [6], the definition of the encoding tree for an undirected weighted graph remains unchanged, and the two-dimensional structural entropy of $G_{W}=(\mathcal{V},\mathcal{E},w)$ by its two-dimensional encoding tree $\mathcal{T}$ is defined as ;

$$H^{\mathcal{T}}(G_{W})=\sum_{\alpha_{i}\in A}(-\frac{g_{\alpha_{i}}}{V_{\lambda}}\log\frac{V_{\alpha_{i}}}{V_{\lambda}}+\sum_{v_{j}\in T_{\alpha_{i}}}-\frac{d_{j}}{V_{\lambda}}\log\frac{d_{j}}{V_{\alpha_{i}}}),$$

(57)

; where new degree $d_{j}=\sum_{v_{i}\in\mathcal{N}(v_{j})}w(v_{j},v_{i})$ ($\mathcal{N}(v)$ denotes the set of neighbors of node $v$), new volume $V_{\alpha}=\sum_{v_{i}\in T_{\alpha}}d_{i}$, and new cut edge number $g_{\alpha}$ is replaced with the sum of the weights of the edges with exactly one endpoint in $T_{\alpha}$. ; Adjustment definition of undirected weighted graphs. Due to the continuity of edge weights, the original node level and graph level Adjustment definitions (Definition 11) no longer apply. We renew the Adjustment definitions of the two levels as follows:

1. 1.

   (node level) the total weight change $\delta(v_{i})=d^{\prime}_{i}-d_{i}$ for each node $v_{i}\in\phi_{\lambda}$;

2. 2.

   (graph level) the total weight change of the whole graph denoted by $\delta_{V}(\lambda)$.

; Incremental formula for structural entropy computation.; According to Eq. (57), the incremental computation formula for undirected weighted graphs can then be formulated as (extended from Eq. (55)); HT′(G′W)=-1Vλ+δV(λ)[^S′N+^S′C+^S′Glog(Vλ+δV(λ))],; where ; ^S′N=^SN+∑vk∈ϕλ[(dk+δ(vk))log(dk+δ(vk))-dklogdk];^S′C=^SC+∑α∈A[(gα+δg(α)+Vα+δV(α))log(Vα+δV(α))-(gα+Vα)logVα];^S′G=^SG+∑α∈A-δg(α).; Directed Weighted Graphs; Directed Weighted Graphs; The main method proposed in this paper is difficult to transfer to directed graph scenarios since the measurement of the structural entropy of directed graphs is fundamentally different from that of undirected graphs. The key difference is that the directed graph needs to be transferred into a transition matrix and stationary distribution needs computed. In this part, we briefly present an incremental scheme for measuring the one-dimensional structural entropy of directed weighted graphs since the incremental computation of two-dimensional structural entropy is quite complex. Specifically, we first define the directed weighted graph and its non-negative matrix representation. After that, we introduce the formula of the structural entropy of directed weighted graphs [6]. Finally, we review the traditional methods, namely Eigenvector Calculation and Global Aggregation, for accurately or approximately calculating the one-dimensional structural entropy of directed weighted graphs and then propose an incremental iterative approximation algorithm, i.e., Local Propagation. ; Directed Weighted Graph and Non-Negative Matrix; Directed Weighted Graph and Non-Negative Matrix; Directed Weighted Graph; A directed weighted graph can be denoted as $G_{DW}=(\mathcal{V},\mathcal{E},f)$, which satisfies the following properties: 1. $\mathcal{V}=\{v_{1},v_{2},...,v_{N}\}$ is the node set; 2. $\mathcal{E}$ denotes the set of directed edges $e=(v_{i},v_{j})$; 3. for each directed edge $e=(v_{i},v_{j})\in\mathcal{E}$, $f(e)=f(v_{i},v_{j})>0$ is the edge weight from $v_{i}$ to $v_{j}$. For $e=(v_{i},v_{j})\notin\mathcal{E}$, we denote $f(e)=f(v_{i},v_{j})=0$. ; The definition of directed weighted graphs is shown in Definition 12. Given a directed weighted graph $G_{DW}=(\mathcal{V},\mathcal{E},f)$ with $N$ nodes, we fix the nodes in $\mathcal{V}$ in an order like $v_{1},v_{2},...,v_{N}$. For $i,j\in\{1,2,..,N\}$, we define $a_{ij}=f(v_{i},v_{j})$. Then we can obtain a non-negative matrix $\mathbf{A}=(a_{ij})$, named as a matrix of $G_{DW}$. In other words, a directed weighted graph can be represented by a non-negative matrix. The definition of the non-negative matrix representation of directed weighted graphs is presented in Definition 13. ; Directed Weighted Graph Represented by Non-Negative Matrix; A directed weighted graph $G_{DW}=(\mathcal{V},\mathcal{E},f)$ can be denoted as an $N\times N$ non-negative matrix $\mathbf{A}=(a_{ij})\in\mathbb{R}^{N\times N}_{\geq 0}$, where for each $i,j\in\{1,2,...,N\}$, $a_{ij}=f(v_{i},v_{j})\geq 0$. ; One-Dimensional Structural Entropy of Directed Weighted Graphs; One-Dimensional Structural Entropy of Directed Weighted Graphs; For direct graphs, the structural entropy is an uncertainty measurement defined on strongly connected graphs whose matrices must be irreducible (Definition 14). ; Irreducible Matrix; Given a non-negative matrix $\mathbf{A}\in\mathbb{R}^{N\times N}_{\geq 0}$, if there exists a permutation matrix $\mathbf{P}$ such that $$\mathbf{P}\mathbf{A}\mathbf{P}=\begin{bmatrix}\mathbf{X}&\mathbf{Y}\\ \mathbf{0}&\mathbf{Z}\end{bmatrix},$$ (60) where $\mathbf{X}$ and $\mathbf{Z}$ are square matrices, then $\mathbf{A}$ is said to be a reducible matrix, otherwise $\mathbf{A}$ is an irreducible matrix. ; Normalize each row in an irreducible matrix $\mathbf{A}$, i.e., for each $i$ and $j$, let

$$b_{ij}=\frac{a_{ij}}{\sum_{k=1}^{N}a_{ik}}.$$

(61)

Then we can get a normalized irreducible matrix $\mathbf{B}=(b_{ij})$ where the sum of elements in each row is $1$. $b_{ij}$ is called the normalized edge weight. There is a fundamental theorem for normalized irreducible matrices like $\mathbf{B}$. ; Perron Forbenius; If $\mathbf{B}\in\mathbb{R}^{N\times N}_{\geq 0}$ is an irreducible matrix where for each $i$, $\sum_{k=1}^{N}b_{ik}=1$, then 1. the maximum eigenvalue of $\mathbf{B}$ is $1$; 2. the maximum eigenvalue of $\mathbf{B}$ has a unique left eigenvector; 3. The unique left eigenvector of the maximum eigenvalue of $\mathbf{B}$ is a probability distribution, denoted by $\pi=[\pi_{1},\pi_{2},...,\pi_{N}]$. ; According to Theorem 5, the stationary distribution of $\mathbf{A}$ can then be defined in Definition 9. ; Stationary Distribution; Let $\mathbf{A}\in\mathbb{R}^{N\times N}_{\geq 0}$ be an irreducible matrix and $\mathbf{B}$ represents the normalized matrix of $\mathbf{A}$ where for each $i$, $\sum_{k=1}^{N}b_{ik}$ $=1$. The stationary distribution of $\mathbf{A}$ is defined as the unique left eigenvector of the maximum eigenvalue of $\mathbf{B}$, denoted by $\pi=[\pi_{1},\pi_{2},...,\pi_{N}]$. ; Finally, the one-dimensional structural entropy (Definition 16) of an irreducible non-negative matrix (or a directed weighted graph) is defined as the Shannon entropy of the stationary distribution, which measures the total amount of uncertainty embedded in a directed weighted graph. ; One-Dimensional Structural Entropy; Let $\mathbf{A}\in\mathbb{R}^{N\times N}_{\geq 0}$ be an irreducible matrix and $\pi=[\pi_{1},\pi_{2},...,\pi_{N}]$ is the stationary distribution of $\mathbf{A}$. The one-dimensional structural entropy is defined as ; $$\mathcal{H}^{1}(\mathbf{A})=-\sum_{i=1}^{N}\pi_{i}\log_{2}\pi_{i}.$$ (62) ; Incremental Measurement of One-Dimensional Structural Entropy; Incremental Measurement of One-Dimensional Structural Entropy; Generally, the exact value of one-dimensional structural entropy can be obtained by Eq. (62) in $O(n)$ given the stationary distribution. However, calculating the exact stationary distribution needs to solve the eigenvectors of the normalized irreducible matrix, which usually costs $O(n^{3})$. In dynamic scenarios, the directed weighted graph evolves as time passes by. When an irreducible matrix $\mathbf{A}\in\mathbb{R}^{N\times N}_{\geq 0}$ representing a directed weighted graph gets an incremental $\Delta\mathbf{A}$, it becomes an updated irreducible matrix $\mathbf{A}^{\prime}=\mathbf{A}+\Delta\mathbf{A}$. Let $n=||\Delta\mathbf{A}||_{0}$ denote the incremental size. Let $\mathbf{B}$ and $\mathbf{B}^{\prime}$ be the normalized matrices of $\mathbf{A}$ and $\mathbf{A}^{\prime}$. Define $\Delta\mathbf{B}=\mathbf{B}^{\prime}-\mathbf{B}$. We can calculate $\Delta\mathbf{B}=(\Delta b_{ij})$ from $\mathbf{A}$ and $\Delta\mathbf{A}$ by

$$\Delta b_{ij}=b^{\prime}_{ij}-b_{ij}=\frac{a^{\prime}_{ij}}{\sum_{k=1}^{N}a^{\prime}_{ik}}-\frac{a_{ij}}{\sum_{k=1}^{N}a_{ik}}=\frac{a_{ij}+\Delta a_{ij}}{(\sum_{k=1}^{N}a_{ik}+\Delta a_{ik})}-\frac{a_{ij}}{\sum_{k=1}^{N}a_{ik}}.$$

(63)

Since a non-zero element of $\Delta\mathbf{A}$ may influence at most all $N$ elements of a row in $\mathbf{B}$, $||\Delta\mathbf{B}||_{0}$, named as the normalized incremental size, will be no more than $nN$. In addition, the number of the influenced rows in $\mathbf{B}$, denoted by $n_{B}$, will be no more than $n$. In the following, three ways are listed to compute the updated one-dimensional structural entropy. ; Exact value calculation by Eigenvector Calculation.; The first way is to calculate the exact value of the updated one-dimensional structural entropy by Definition 15 and 16. Specifically, the new exact stationary distribution $\pi^{\prime}$ is first computed by solving the left eigenvector of the maximum eigenvalue of $\mathbf{B}^{\prime}$. Then the updated one-dimensional structural entropy can be calculated by

$$\mathcal{H}^{1}(\mathbf{A^{\prime}})=-\sum_{i=1}^{N}\pi^{\prime}_{i}\log_{2}\pi^{\prime}_{i}.$$

(64)

Generally, the total time complexity of this way is $O(N^{3})$. ; Approximate value calculation by Global Aggregation.; According to the theory of the Markov chain, the approximate stationary distribution can be approximated by iteratively right-multiplying $\mathbf{B}^{\prime}$, i.e.,

$$\pi^{(\theta)}=\pi\mathbf{B}^{\prime\theta}=\pi(\mathbf{B}+\Delta\mathbf{B})^{\theta},$$

(65)

where $\theta\in\mathbb{N}$ is the iteration number. Whenever $\pi^{(\theta)}$ updates to $\pi^{(\theta+1)}$ by right-multiplying $\mathbf{B}+\Delta\mathbf{B}$, the updating process is equivalent to an information aggregation operation on graphs along directed edges, i.e., for each node $v_{i}$,

$$\pi^{(\theta+1)}_{i}=\sum_{v_{j}\in\mathcal{N}(v_{i})}\pi^{(\theta)}_{j}b_{ji},$$

(66)

where $\mathcal{N}(v_{i})$ denotes the neighbors of $v_{i}$. Since for each iteration, all nodes need to be updated, we name this calculation method as “Global Aggregation”. Finally, we compute the Shannon entropy of $\pi^{(\theta)}$ as the approximate one-dimensional structural entropy:

$$\mathcal{H}^{1}(\mathbf{A^{\prime}})\approx-\sum_{i=1}^{N}\pi^{(\theta)}_{i}\log_{2}\pi^{(\theta)}_{i}.$$

(67)

The total computational complexity of Global Aggregation is about $O(\theta N^{2})$ in the form of matrix multiplication using Eq. (65). Utilizing graph perspective (Eq. (66)), the time complexity can be reduced to $O(\theta N\overline{d})=O(\theta|\mathcal{E}|)$, where $\overline{d}$ denotes the mean direct successor number of all graph nodes. ; Fast approximate value calculation by Local Propagation.; In Global Aggregation, all nodes and edges need to be traversed in each iteration, which leads to high computational redundancy. In this part, we propose a new method for fast approximation of the updated one-dimensional structural entropy, namely Local Propagation. As the name suggests, the key idea is to use an information propagation scheme involving only changed local nodes to further reduce the redundancy of the aggregation process in Eq. (66). ; An illustration of Local Propagation. Note that all edge weights are normalized. In the first step (a), the red arrows denote the edges whose weight changes after getting an incremental, i.e., the involved edges. The stationary distributions of the involved nodes ($\pi_{2},\pi_{4},\pi_{10}$) are updated. In the second step (b), the direct successors of the last involved nodes update their stationary distributions and become new involved nodes. Then the procedure of (b) is repeated until the maximum iteration number is reached. ; An illustration of Local Propagation. Note that all edge weights are normalized. In the first step (a), the red arrows denote the edges whose weight changes after getting an incremental, i.e., the involved edges. The stationary distributions of the involved nodes ($\pi_{2},\pi_{4},\pi_{10}$) are updated. In the second step (b), the direct successors of the last involved nodes update their stationary distributions and become new involved nodes. Then the procedure of (b) is repeated until the maximum iteration number is reached. ; In particular, Local Propagation contains two steps. In the first step (Fig. 9(a)), we define the set of directed edges in $\mathbf{B}$ influenced by $\Delta\mathbf{B}$ as “involved edges” (red edges in Fig. 9(a)). We then let $\pi^{(1)}=\pi^{(0)}$. For each involved edge $(v_{i},v_{j})$, the stationary distribution value of the pointed node $v_{j}$ is updated by

$$\pi^{(1)}_{j}\leftarrow\pi^{(1)}_{j}+\Delta b_{ij}\pi_{i},$$

(68)

and $v_{j}$ is added into an “involved nodes” set denoted by $I^{(1)}$. The time complexity of the first step is linearly correlated to the size of the involved edge set, i.e., $O(nN)$. ; In the second step, we repeat the following procedure for $\theta-1$ times. Let $\pi^{(\theta+1)}=\pi^{(\theta)}$. For each node $v_{i}$ in $I^{(\theta)}$, we update the stationary distribution values of all $v_{i}$’s direct successors (like Fig. 9(b)) by

$$\pi^{(\theta+1)}_{j}\leftarrow\pi^{(\theta+1)}_{j}+b^{\prime}_{ij}(\pi^{(\theta)}_{i}-\pi^{(\theta-1)}_{i}),v_{j}\in\mathcal{N}_{s}(v_{i}),$$

(69)

where $\mathcal{N}_{s}(v_{i})$ denotes the direct successors of $v_{i}$. After all nodes in $I^{(\theta)}$ are traversed, $I^{(\theta)}$ is updated as $I^{(\theta+1)}$, i.e., all the direct successors of nodes of the original set $I^{(\theta)}$. For each iteration, the time complexity is $O(|I^{(\theta)}|\overline{d}^{(\theta)})$, where $\overline{d}^{(\theta)}$ denotes the mean direct successor number of nodes in $I^{(\theta)}$. In other words, let $E^{(\theta)}$ ($\theta\geq 1$) denote the set of edges whose starting points belong to $I^{(\theta)}$, we have $|I^{(\theta)}|\overline{d}^{(\theta)}=|E^{(\theta)}|$. Therefore, the time complexity of each iteration is $O(|E^{(\theta)}|)$ which must be less or equal to the complexity of Eq. (66), $O(|\mathcal{E}|)$. ; Parameter descriptions of the three methods are listed below:; Random parameters:; Gaussian parameters:; This method creates $k$ communities each with a size drawn from a normal distribution with mean $s$ and variance $s/v$. Nodes are connected within communities with probability $p_{\mathrm{in}}$ and between communities with probability $p_{\mathrm{ac}}$. ; SBM parameters:; This method partitions the nodes in communities of given sizes $\mathcal{S}=[s_{1},s_{2},...]$, and places edges between pairs of nodes independently, with a probability that depends on the communities. ; The generation process of the artificial Hawkes datasets.; The generation process of the artificial Hawkes datasets.; In this process, we first randomly choose a node $x$ to be the target node (Fig. 10($t=1$)). Second, we add edges or nodes with given probabilities. Specifically, with probability $p_{\mathrm{hn}}$ (Fig. 10(Node Addition)), we connect a new node with $x$. With probability $1-p_{\mathrm{hn}}$ (Fig. 10(Edge Addition)), we (1) use Node2vec [25] to get embedding vectors of all nodes; (2) calculate the conditional intensity function $\Lambda_{y_{i}|x}$ between $x$ and each of its non-neighboring nodes $y$: ; where $\textbf{e}_{x},\textbf{e}_{y}$ refers to the embedding vectors of nodes $x$ and $y$, $h$ refers to the historical neighbor nodes connected to $x$ at time $t_{h}$ before $t$, and $\delta_{x}$ refers to the discount rate, defined in this paper as the number of neighbors of $x$; and (3) add an edge between $x$ and $y_{i}$ with the Softmax conditional probability: ; Subsequently, we repeat the above two steps to generate incremental sequences and updated graphs (Fig. 10($t=2,3,...,T$)). The chosen parameter settings of the initial states and Hawkes Process are described in Table 2. ; Parameter Values of the Generated Initial States and Hawkes Process. ; Parameter Values of the Generated Initial States and Hawkes Process. ; Statistics Description of the Artificial and Real-World Datasets.; Statistics Description of the Artificial and Real-World Datasets.; Datasets; Random-Hawkes; 6,000; 203,659; 1,017; 20,365; Gaussian-Hawkes; 6,000; 164,482; 596; 11,942; SBM-Hawkes; 6,000; 176,526; 592; 11,942; 25,656; 132,119; 235; 10,727; DBLP; 7,184; 13,451; 3,379; 7,907; 14,094; 72,809; 2,233; 26,000; DBLP contains a co-authorship network of computer science papers from $1954$ to $2015$ in which authors are represented as vertices and co-authors are linked by an edge.; (on real-world datasets) and Fig. 12 (on artificial datasets); NAGA+AIUA; compared with NAGA+AIUA; In Fig. 11, the performance of NSGA+AIUA is only slightly weaker than $TOA$ with Infomap on Cit-HepPh and Facebook. Further, it even achieves lower structural entropy than the offline algorithm when Louvain and Leiden are chosen. Two main reasons are listed as follows. (1) In the incremental algorithms, the new community partitioning is obtained by locally modifying the original partitioning of the initial state. While in $TOA$ the community partitioning is reconstructed globally from snapshots (updated graphs) by the static methods. Although $TOA$ spends a large amount of time searching for optimal partitioning globally, there is no theoretical proof that it must be better than local and greedy optimization used in incremental algorithms. (2) Additionally, the optimization objectives of incremental algorithms and $TOA$ are different. The former focuses on the structural entropy itself while the latter aims to optimize modularity (Louvain and Leiden) or minimize the expected length of information transmission (Infomap). ; From the experimental results on artificial datasets (Fig. 12), we can conclude that our incremental algorithms have higher stability in the dynamic calculation of structural entropy. In most cases, there are many mutations in the structural entropy value using TOA, while our algorithms maintain a continuous and stable decrease. It is because TOA globally reconstructs the community for each iteration so that small node or edge changes may cause more influence. By contrast, our algorithms dynamically adjust the community partitioning from the last snapshot, which affects only locally involved nodes. ; The structural differences between different static methods on artificial Hawkes datasets are really small indicating that the initial community partitionings of the three methods are almost the same. ; Table 5 shows the time comparison between our online algorithm NSGA+ AIUA ($N=5$) and the offline algorithm TOA. As we can see from the results, all our proposed incremental algorithms are significantly faster than the existing static methods. Specifically, for example, NSGA+AIUA ($N=5$) obtain over $140.93$x and $77.81$x speed up on average on DBLP and SBM-Hawkes, respectively, in contrast with the static method using Infomap. ; Time Consumption Comparison of Our Incremental Algorithms (Online Time) and the Baseline Traditional Offline Algorithm (Offline Time).; Time Consumption Comparison of Our Incremental Algorithms (Online Time) and the Baseline Traditional Offline Algorithm (Offline Time).; The Influence on Total Time Consumption and Structural Entropy of Different Updated Threshold $\theta$ on Cit-HepPh dataset with Infomap static method.; The Influence on Total Time Consumption and Structural Entropy of Different Updated Threshold $\theta$ on Cit-HepPh dataset with Infomap static method.;

6.3.5 Robustness Analysis

; The structural entropy of NAGA/NSGA+AIUA and TOA with Infomap under different initial state parameter $p_{\text{ac}}$ representing different noise conditions.; The structural entropy of NAGA/NSGA+AIUA and TOA with Infomap under different initial state parameter $p_{\text{ac}}$ representing different noise conditions.; One-Dimensional Structural Entropy Measurement of Directed Weighted Graphs; One-Dimensional Structural Entropy Measurement of Directed Weighted Graphs; ER initial state.; The initial state of the ER dataset is created by the Erdős-Rényi model implemented by erdos_renyi_graph in Networkx [22] which has two main parameters. One is the number of nodes $n$ and the other is the probability of edge creation $p$. In this dataset, the Erdős-Rényi model chooses each of the $n(n-1)$ possible directed edges with probability $p$. ; Cycle initial state.; The Cycle dataset’s initial state contains cyclically connected nodes, where the edge direction is in increasing order. For example, a cycle dataset $\{v_{0},v_{1},...,v_{n}\}$ has $n+1$ direct edges $\{(v_{0},v_{1}),(v_{1},v_{2}),...,(v_{n-1},v_{n})$ $,(v_{n},v_{0})\}$. ; Weight and incremental settings.; For the initial states of ER and Cycle datasets, we first set all edge weights as random integers in $[1,10]$. Then we generate several incremental sequences with sizes $500$, $2000$, $5000$, and $10000$, respectively, corresponding to four different updated graphs from each initial state. Specifically, for each incremental edge, we randomly choose two nodes to add a direct edge between them with random weight in $[1,10]$. If the edge exists, we randomly change its weight as another value in $[1,10]$. ; Experimental settings.; Experimental results.; Time consumption of Global Aggregation and Local Propagation on ER and Cycle dataset. Note that only the time consumption of Global Aggregation of $n=500$ is shown since the theoretical time consumption of different incremental size $n$ is the same. ; Time consumption of Global Aggregation and Local Propagation on ER and Cycle dataset. Note that only the time consumption of Global Aggregation of $n=500$ is shown since the theoretical time consumption of different incremental size $n$ is the same. ; on undirected graphs; Besides, we also discuss the computation method for one-dimensional structural entropy on directed weighted graphs.; Further, we discuss the extension of our proposed methods to weighted graphs and the one-dimensional structural entropy computation on directed and weighted graphs.)