# Modeling Community Evolution Characteristics of Dynamic Networks with Evolutionary Bayesian Nonnegative Matrix Factorization

Authors: Wei Yu; Xiaoming Li; Huaming Wu; Xue Chen; Minghu Tang; Yang Yu; Wenjun Wang
Journal: Complexity
 (2021)

---

## Abstract

In most cases, the block structures and evolution characteristics always coexist in dynamic networks. This leads to inaccurate results of temporal community structure analysis with a two-step strategy. Fortunately, a few approaches take the evolution characteristics into account for modeling temporal community structures. But the number of communities cannot be determined automatically. Therefore, a model, Evolutionary Bayesian Nonnegative Matrix Factorization (EvoBNMF), is proposed in this paper. It focuses on modeling the temporal community structures with evolution characteristics. More specifically, the evolution behavior, which is introduced into EvoBNMF, can quantify the transfer intensity of communities between adjacent snapshots for modeling the evolution characteristics. Innovatively, the most appropriate number of communities can be determined autonomously by shrinking the corresponding evolution behaviors. Experimental results show that our approach has superior performance on temporal community detection with the virtue of autonomous determination of the number of communities.


---

## Body

## 1. Introduction

Dynamic network analysis, as an important branch of complex network science, has attracted wide attention in recent years [1]. Temporal community structure analysis is one of the important research problems, which includes two subproblems: temporal community detection [1] and community evolution analysis [2]. However, community structure analysis of dynamic networks first detects the community structures and then analyzes the corresponding evolution pattern with a heuristic strategy in most cases. These works ignore the evolution characteristics of community structures when doing the temporal community detection. In fact, the block structures and evolution characteristics always coexist in dynamic networks. This leads to inaccurate results of temporal community detection. Therefore, it is very necessary to propose a model which describes the community structures with evolution characteristics for improving the accuracy of temporal community detection.At present, temporal community detection has been widely concerned, which focuses on mining the meaningful block structures or functional modules hiding in the network snapshots of dynamic networks. In the beginning, two-stage approaches are introduced into temporal community detection, which first detect communities on each snapshot with a static method and then match them across different snapshots [3]. These types of approaches detect the communities of current snapshots ignoring the historical community structures from last snapshots, which take away the evolution characteristics of temporal community structures and are usually sensitive to noise. Later, evolutionary clustering- [4] based approaches are proposed, which effectively make up for this shortcoming by detecting the communities at the current snapshot with not only the current topology structure but also the previous community structures [5]. However, most of these works ignore determining the number of communities at each snapshot automatically and need to be specified in advance. In fact, the determination of the number of communities is a model selection problem, which is a common challenge for community detection. In addition, most of these works just focus on identifying temporal communities accurately but ignore analyzing the corresponding community evolution.In addition, community evolution analysis exposes the evolution behaviors, which quantify the transition relationships of communities between adjacent snapshots, and helps to trace the change trends of dynamic networks. At first, the heuristic-based approaches [3] are proposed, which usually summarize the changing laws over time for analyzing the evolution pattern after detecting communities. Then, the feature engineering-based approaches [6] are proposed, which extract the evolution feature based on the detected temporal communities with a machine learning algorithm. The first two types of methods tend to analyze the evolution laws after detecting communities so that the results of the evolution analysis rely too much on the results of community detection. They ignore that community structures and evolution characteristics coexist in dynamic networks. Fortunately later, generative model-based approaches [7], which model the generative mechanism of community structure and community evolution synchronously, are able to make up for that shortcoming. However, most of these existing approaches just describe the evolution behaviors qualitatively but not quantitatively. And few of these approaches can deal with model selection problems automatically.For addressing the above issues, we pay attention to model the community structures with evolution characteristics for boosting temporal community detection and determining autonomously the number of communities at each snapshot of dynamic networks synchronously. In this paper, a model called Evolutionary Nonnegative Matrix Factorization (EvoBNMF) is proposed based on a Bayesian probabilistic model. In detail, we introduce the evolution behaviors to model the evolution characteristics of community structures with Bayesian Nonnegative Matrix Factorization (BNMF) [8] in an evolutionary clustering framework [4]. Then, we develop a gradient descent algorithm to optimize the parameters of EvoBNMF by maximizing the posterior estimate. Innovatively, the most appropriate number of communities can be determined autonomously by shrinking the corresponding evolution behaviors. Last but not least, experimental results from synthetic networks and real-world networks over several state-of-the-art methods show that our proposed EvoBNMF has superior performance on temporal community detection with the virtue of autonomous determination of the number of communities. It is worthwhile to highlight several contributions of this work here:(i)
A model called Evolutionary Nonnegative Matrix Factorization (EvoBNMF) is proposed by modeling community detection with evolution characteristics for improving the performance of temporal community detection(ii)
The proposed EvoBNMF catches the most appropriate number of communities autonomously by shrinking the corresponding evolution behaviors of each snapshot network(iii)
An effective algorithm is developed to optimize the objective function of EvoBNMF, of which the time complexity can be degraded to be linear(iv)
Extensive experiments on synthetic and real-world dynamic networks demonstrate that our proposed EvoBNMF has superior performance on temporal community detection in comparison with state-of-the-art methods


## 2. Related Works

According to the core idea of the related works, the methods for temporal community detection can be divided into three categories: the snapshot matching-based methods [9, 10], the historical structural dependency-based methods [11, 12], and the community evolution model-based methods [13, 14].The basic idea of the snapshot matching-based method is first to discover each network snapshot independently based on the static community detection algorithm and then to match the communities between snapshots based on some similarity strategy. For example, Seifikar et al. [9] proposed a new Louvain-based dynamic community detection algorithm that relied on the derived knowledge of the previous steps of the network evolution. Mishra et al. [10] proposed a tree-based community detection algorithm exploiting two important properties, connectedness and influence, for finding communities in the network. However, this kind of method pays more attention to discover the community structures on each network snapshot but ignores the smoothness of the evolution characteristics of dynamic network structure, splitting the evolution of community structure into multiple snapshots.The basic idea of the historical structural dependency-based method is derived from the assumption of smoothness of the evolution of dynamic complex network structure. It is believed that the community structure of the current snapshot is evolved slowly from the previous network snapshot so that the result of the current community structure depends on the community structure of one or more historical network snapshots. For example, Yin et al. [12] proposed an efficient and effective multiobjective method via modifying the traditional evolutionary clustering framework and the particle swarm algorithm. Rossetti et al. [5] proposed an online incremental clustering dynamic community detection algorithm (Tiles) based on modularity incremental optimization. The calculation of the network substructure is local and the number of nodes and communities involved is limited, thus speeding up the updating efficiency. In addition, Wang et al. [15] constructed a novel similarity combining structural perturbation theory and network topology characteristics and proposed a dynamic community mining algorithm based on evolutionary clustering. All of these methods can avoid the matching of community structure between snapshots and incorporate the smoothness of dynamic community evolution.The community evolution model-based method simulates the generation rules and the attribute characteristics hiding in the networks from the perspective of a dynamic complex network generation mechanism. At the same time, a reasonable network evolution mechanism is embedded to construct a parameterized dynamic community evolution generation model. Finally, the model parameters are solved to obtain the optimal community structure and the evolution pattern. For example, Ting et al. [13] proposed a novel framework for fitting the multilayer stochastic block model (SBM) that builds on multislice modularity maximization. It can discover a common community partition of all snapshots simultaneously. In addition, Yu et al. [16] constructed a matrix decomposition model containing an edge evolution time function for mining the evolution patterns in the microstructure (edge) of dynamic networks, which can be applied to structural trend prediction, link prediction, and anomaly detection of dynamic networks. Li et al. [14] proposed a method to learn the graph embedding and dynamic community detection via joint learning graph representation and NMF. In general, this kind of method abandons the two-step strategy in the snapshot matching-based method and continues the evolution smoothness property in the historical structural dependency-based method. It makes up for the lack of evolution mechanism in the historical structural dependency-based methods and gradually becomes the most popular method in the field of dynamic community detection.


## 3. Methodology

### 3.1. Notations

A dynamic network is usually cut as a series of network snapshots according to a fixed time window. It can be expressed asG=Vt,Et,t∈1,2,…,T, where Vt=1,…,Nt is the entity or node sets, Et is edge sets at snapshot t, and T is the number of snapshots. Network snapshot t is represented with an Nt×Nt adjacency matrix At, where the element at snapshot t is(1)Aijt=1,i,j∈Et,0,i,j∉Et.In addition, we summarize the main notations in Table 1.Table 1
Notations.
SymbolDefinitiontThe snapshot label, andt∈1,TVtThe node sets of snapshott, and Vt=1,2,…,NtEtThe edge sets of snapshottAtThe adjacent matrix at snapshott, and At∈R+Nt×NtWtThe basis matrix att, and Wt∈R+Nt×KtHtThe community membership matrix att, and Ht∈R+Kt×NtZtThe evolution behavior matrix at snapshott, and Zt∈RKt×Kt−1CtThe community label matrix of snapshottKtThe number of communities of snapshottAs community number is unknown in most of the real cases, from the perspective of the Bayesian model, we assume that the community membership degree and the evolution tendency follow some probability distribution, respectively. At the same time, we assume that the parameters of the probability distribution of the evolution tendency follow a given prior distribution. Then, we construct the dynamic community evolution model EvoBNMF under the framework of the NMF and transform the optimization problem from maximizing the a posteriori probability of minimizing the negative logarithm of the posterior probability. Therefore, the tasks of the dynamic community evolution model EvoBNMF are summarized as follows:(i)
Input: the adjacency matrix sequence of the dynamic complex networkAtt∈1,T, and the hyperparameters a and b(ii)
Output: the dynamic community structuresCt∈1,T, the community evolution matrix sequence Ztt∈2,T, and the number of communities Ktt∈1,T


### 3.2. EvoBNMF Model

Here, we design the generative graphical model of EvoBNMF (see Figure1) with a Bayesian probabilistic model using the core idea of evolutionary clustering. For snapshot 1, as there is no historical structure information, EvoBNMF can be constructed similarly according to the static BNMF. Accordingly, the observed adjacency matrix A1 is influenced by an unobserved expectation snapshot network A^1, of which element A^ij1 denotes the expected link weight that takes place between i and j at snapshot 1. The expectation snapshot network can be composed of a basis matrix W1∈R+N1×K1 and a community membership matrix H1∈R+K1×N1 so that Aij1≈A^1=W1H1, where Hkj1 captures the propensity of node j belonging to community k and K1 is the unknown number of communities. Similar to [8], we assume that A^ij1 is drawn from a Poisson distribution with rate A^ij1=∑k=1K1Wik1Hkj1. And Wik1 and Hkj1 are both drawn from a half-normal distribution with scale parameters β1=βk1. In addition, we consider that the conjugate prior [17] of half-normal distribution is Gamma distribution. Therefore, β1 is drawn from Gamma distribution with two hyperparameters a1 and b1. According to the graphical model in Figure 1, the model of snapshot 1 is the same as that of [8], and the corresponding posterior of the model at snapshot 1 is(2)PW1,H1,β1|A1=PA1|W1,H1⋅PW1|β1⋅PH1|β1⋅Pβ1PA1.Figure 1
Graphical model of the proposed EvoBNMF.The task of minimizing the negative log posterior, which is equivalent to the task of maximizing the posterior, can be regarded as the objective function of snapshot 1, and its specific form is as follows [8]:(3)L1=−logPA1|A^1−logPW1|β1−logPH1|β1−logPβ1=−∑i=1N1∑j=1N1Aij1logAij1A^ij1+A^ij1−Aij1+12∑k=1K∑i=1N1βk1Wik12+∑j=1N1βk1Hkj12+∑k=1Kβk1b1−a1−1logβk1−2Nlogβk1+C,where C denotes a constant.For the case of snapshott2≤t≤T, similarly, the observed adjacency matrix At is influenced by an unobserved expectation snapshot network A^t, of which element A^ijt denotes the expected link weight that takes place between i and j at snapshot t. The expectation snapshot network can be composed of a basis matrix Wt∈R+Nt×Kt and a community membership matrix Ht∈R+Kt×Nt so that Aijt≈A^t=WtHt, where Hkjt captures the propensity that node j belongs to community k and Kt is the unknown number of communities. Differently, we consider the historical structure information into the model of the current snapshot according to the core idea of evolutionary clustering. In addition, we introduce an evolution matrix Zt to model the evolution behaviors of communities synchronously. The element Zlkt denotes the propensity that nodes of community l of snapshot t−1 transfer into community k of snapshot t. Here, we think that the current community membership Ht is evolved from Ht−1 by modeling some evolution behaviors Zt and introduce a penalty term to force that Ht≈H^t=ZtTHt−1. In detail, we assume that Hjkt is drawn from a Poisson distribution with rate H^kjt=∑l=1Kt−1ZlktHljt−1, Wikt and Zlkt are both drawn from a half-normal distribution with scale parameters βt=βkt, and βt is drawn from Gamma distribution with two hyperparameters at and bt [17]. According to the graphical model in Figure 1, the joint distribution at snapshot t can be represented as follows:(4)PAt,Ht−1,Wt,Ht,Zt,βt,α=PAt|Wt,Ht⋅PHt|Ht−1,Zt,α⋅PZt|βt⋅PWt|βt⋅Pβt,where α is a balance parameter. Therefore, the corresponding posterior is(5)PWt,Ht,Zt,βt|At,Ht−1,α=PAt,Ht−1,Wt,Ht,Zt,βt,αPAt,Ht−1,α.The task of minimizing the negative log posterior, which is equivalent to the task of maximizing the posterior, can be regarded as the objective function of snapshott, and its specific form is as follows:(6)Lt=−logPAt|A^t−logPHt|Ht−1,Zt,α−logPZt|βt−logPβt.We assume thatAijt is drawn from a Poisson distribution with rate A^t=∑k=1KtWiktHkjt, Hjkt is drawn from a Poisson distribution with rate H^kjt=∑l=1Kt−1ZlktHljt−1, Wikt and Zlkt are both drawn from a half-normal distribution with scale parameters βt=βkt, and βt is drawn from Gamma distribution with at, and bt. Then, Lt can be rewritten as(7)Lt=∑i=1Nt∑j=1NtAijtlogAijt∑k=1KinitialWiktHkjt+∑k=1KinitialWiktHkjt−Aijt+α∑i=1Nt∑k=1KinitialHkitlogHkit∑l=1Kt−1Hlit−1Zlkt+∑l=1Kt−1Hlit−1Zlkt−Hkit+∑l=1Kt−1∑k=1Kinitial12βktZlkt2−Kt−12logβkt+∑i=1Nt∑k=1Kinitial12βktWikt2−Nt2logβkt+∑k=1Kinitialβktbt−at−1logβkt+C,where C is a constant.


### 3.3. Updating Rules

For snapshot 1, EvoBNMF is reduced to BNMF. So, the updating rules of the objective functionL1 are the same as those of [8]; in detail,(8)H1⟵H1W1T1+diagβ1H1⊙W1TA1W1H1,(9)W1⟵W11H1T+W1diagβ1⊙A1W1H1H1T,(10)βk1⟵N1+a1−11/2∑iWik12+∑jHkj12+b1.Similarly, for snapshottt∈2,T, we optimize equation (7) for Wt, Ht, Zt, and βt with a gradient descent algorithm, and the updated rules are as follows:(11)Ht⟵HtWtT1+α⊙WtTAtWtHtT+αZtTHt−1Ht,(12)Wt⟵Wt1HtT+Wtdiagβt⊙AtWtHtHtT,(13)Zlkt⟵ZtZtdiagβt+αHt−11⊙αHt−1HtZtTHt−1T,(14)βkt⟵Kt−1+Nt+2at−2∑lKt−1Zlkt2+∑l=1NtWikt2+2bt.We update iterativelyWt, Ht, Zt, and βt according to the above rules until converges. We determine automatically the most appropriate number of communities of each snapshot with a statistical model selection method. In detail, we set a large value (e.g., Kinitialt=Nt/4) as the initial number of communities. After parameter optimization, we shrink Wt, Ht, Zt to Wt∗, Ht∗, and Zt∗ by removing the irrelevant rows or columns of which sum is zero or very close to zero. The pseudocode of the solving algorithm of EvoBNMF is presented in Algorithm 1. The returned community label vectors Ctt∈1,T are the results of temporal community detection. And the returned evolution matrices Zt∗ are the results of quantifying evolution behaviors.Algorithm 1: EvoBNMF.
(1)
InitializeWt, Ht, Zt, βt, where t∈1,T;(2)
while not converge do(3)
UpdateW1, H1, β1 according to equations (8)–(10);(4)
fort∈2,Tdo(5)
while not converge do(6)
Wt, Ht, Zt, βt according to equations (11)–(14);(7)
fort∈1,Tdo(8)
shrinkWt, Ht, and Zt to Wt∗, Ht∗, and Zt∗;(9)
Cit=argmaxkHikt∗;(10)
returnCt, Zt∗.According to Algorithm1, iteratively updating of Ht is most time-consuming. The time complexity of each iterative is ON2Kinitial+NKinitial2. Here, we set the average number of iterations as ρ, and the whole time complexity is about OρTN2Kinitial+NKinitial2. As we know, dynamic networks are usually very sparse in real cases. Then, N2 can be replaced with the average number of edges E^ approximatively at each snapshot. In addition, Kinitial can be ignored as it is usually much less than N. Naturally, the time complexity of the optimization algorithm of EvoBNMF can be degraded to OρTE^+N.


## 3.1. Notations

A dynamic network is usually cut as a series of network snapshots according to a fixed time window. It can be expressed asG=Vt,Et,t∈1,2,…,T, where Vt=1,…,Nt is the entity or node sets, Et is edge sets at snapshot t, and T is the number of snapshots. Network snapshot t is represented with an Nt×Nt adjacency matrix At, where the element at snapshot t is(1)Aijt=1,i,j∈Et,0,i,j∉Et.In addition, we summarize the main notations in Table 1.Table 1
Notations.
SymbolDefinitiontThe snapshot label, andt∈1,TVtThe node sets of snapshott, and Vt=1,2,…,NtEtThe edge sets of snapshottAtThe adjacent matrix at snapshott, and At∈R+Nt×NtWtThe basis matrix att, and Wt∈R+Nt×KtHtThe community membership matrix att, and Ht∈R+Kt×NtZtThe evolution behavior matrix at snapshott, and Zt∈RKt×Kt−1CtThe community label matrix of snapshottKtThe number of communities of snapshottAs community number is unknown in most of the real cases, from the perspective of the Bayesian model, we assume that the community membership degree and the evolution tendency follow some probability distribution, respectively. At the same time, we assume that the parameters of the probability distribution of the evolution tendency follow a given prior distribution. Then, we construct the dynamic community evolution model EvoBNMF under the framework of the NMF and transform the optimization problem from maximizing the a posteriori probability of minimizing the negative logarithm of the posterior probability. Therefore, the tasks of the dynamic community evolution model EvoBNMF are summarized as follows:(i)
Input: the adjacency matrix sequence of the dynamic complex networkAtt∈1,T, and the hyperparameters a and b(ii)
Output: the dynamic community structuresCt∈1,T, the community evolution matrix sequence Ztt∈2,T, and the number of communities Ktt∈1,T


## 3.2. EvoBNMF Model

Here, we design the generative graphical model of EvoBNMF (see Figure1) with a Bayesian probabilistic model using the core idea of evolutionary clustering. For snapshot 1, as there is no historical structure information, EvoBNMF can be constructed similarly according to the static BNMF. Accordingly, the observed adjacency matrix A1 is influenced by an unobserved expectation snapshot network A^1, of which element A^ij1 denotes the expected link weight that takes place between i and j at snapshot 1. The expectation snapshot network can be composed of a basis matrix W1∈R+N1×K1 and a community membership matrix H1∈R+K1×N1 so that Aij1≈A^1=W1H1, where Hkj1 captures the propensity of node j belonging to community k and K1 is the unknown number of communities. Similar to [8], we assume that A^ij1 is drawn from a Poisson distribution with rate A^ij1=∑k=1K1Wik1Hkj1. And Wik1 and Hkj1 are both drawn from a half-normal distribution with scale parameters β1=βk1. In addition, we consider that the conjugate prior [17] of half-normal distribution is Gamma distribution. Therefore, β1 is drawn from Gamma distribution with two hyperparameters a1 and b1. According to the graphical model in Figure 1, the model of snapshot 1 is the same as that of [8], and the corresponding posterior of the model at snapshot 1 is(2)PW1,H1,β1|A1=PA1|W1,H1⋅PW1|β1⋅PH1|β1⋅Pβ1PA1.Figure 1
Graphical model of the proposed EvoBNMF.The task of minimizing the negative log posterior, which is equivalent to the task of maximizing the posterior, can be regarded as the objective function of snapshot 1, and its specific form is as follows [8]:(3)L1=−logPA1|A^1−logPW1|β1−logPH1|β1−logPβ1=−∑i=1N1∑j=1N1Aij1logAij1A^ij1+A^ij1−Aij1+12∑k=1K∑i=1N1βk1Wik12+∑j=1N1βk1Hkj12+∑k=1Kβk1b1−a1−1logβk1−2Nlogβk1+C,where C denotes a constant.For the case of snapshott2≤t≤T, similarly, the observed adjacency matrix At is influenced by an unobserved expectation snapshot network A^t, of which element A^ijt denotes the expected link weight that takes place between i and j at snapshot t. The expectation snapshot network can be composed of a basis matrix Wt∈R+Nt×Kt and a community membership matrix Ht∈R+Kt×Nt so that Aijt≈A^t=WtHt, where Hkjt captures the propensity that node j belongs to community k and Kt is the unknown number of communities. Differently, we consider the historical structure information into the model of the current snapshot according to the core idea of evolutionary clustering. In addition, we introduce an evolution matrix Zt to model the evolution behaviors of communities synchronously. The element Zlkt denotes the propensity that nodes of community l of snapshot t−1 transfer into community k of snapshot t. Here, we think that the current community membership Ht is evolved from Ht−1 by modeling some evolution behaviors Zt and introduce a penalty term to force that Ht≈H^t=ZtTHt−1. In detail, we assume that Hjkt is drawn from a Poisson distribution with rate H^kjt=∑l=1Kt−1ZlktHljt−1, Wikt and Zlkt are both drawn from a half-normal distribution with scale parameters βt=βkt, and βt is drawn from Gamma distribution with two hyperparameters at and bt [17]. According to the graphical model in Figure 1, the joint distribution at snapshot t can be represented as follows:(4)PAt,Ht−1,Wt,Ht,Zt,βt,α=PAt|Wt,Ht⋅PHt|Ht−1,Zt,α⋅PZt|βt⋅PWt|βt⋅Pβt,where α is a balance parameter. Therefore, the corresponding posterior is(5)PWt,Ht,Zt,βt|At,Ht−1,α=PAt,Ht−1,Wt,Ht,Zt,βt,αPAt,Ht−1,α.The task of minimizing the negative log posterior, which is equivalent to the task of maximizing the posterior, can be regarded as the objective function of snapshott, and its specific form is as follows:(6)Lt=−logPAt|A^t−logPHt|Ht−1,Zt,α−logPZt|βt−logPβt.We assume thatAijt is drawn from a Poisson distribution with rate A^t=∑k=1KtWiktHkjt, Hjkt is drawn from a Poisson distribution with rate H^kjt=∑l=1Kt−1ZlktHljt−1, Wikt and Zlkt are both drawn from a half-normal distribution with scale parameters βt=βkt, and βt is drawn from Gamma distribution with at, and bt. Then, Lt can be rewritten as(7)Lt=∑i=1Nt∑j=1NtAijtlogAijt∑k=1KinitialWiktHkjt+∑k=1KinitialWiktHkjt−Aijt+α∑i=1Nt∑k=1KinitialHkitlogHkit∑l=1Kt−1Hlit−1Zlkt+∑l=1Kt−1Hlit−1Zlkt−Hkit+∑l=1Kt−1∑k=1Kinitial12βktZlkt2−Kt−12logβkt+∑i=1Nt∑k=1Kinitial12βktWikt2−Nt2logβkt+∑k=1Kinitialβktbt−at−1logβkt+C,where C is a constant.


## 3.3. Updating Rules

For snapshot 1, EvoBNMF is reduced to BNMF. So, the updating rules of the objective functionL1 are the same as those of [8]; in detail,(8)H1⟵H1W1T1+diagβ1H1⊙W1TA1W1H1,(9)W1⟵W11H1T+W1diagβ1⊙A1W1H1H1T,(10)βk1⟵N1+a1−11/2∑iWik12+∑jHkj12+b1.Similarly, for snapshottt∈2,T, we optimize equation (7) for Wt, Ht, Zt, and βt with a gradient descent algorithm, and the updated rules are as follows:(11)Ht⟵HtWtT1+α⊙WtTAtWtHtT+αZtTHt−1Ht,(12)Wt⟵Wt1HtT+Wtdiagβt⊙AtWtHtHtT,(13)Zlkt⟵ZtZtdiagβt+αHt−11⊙αHt−1HtZtTHt−1T,(14)βkt⟵Kt−1+Nt+2at−2∑lKt−1Zlkt2+∑l=1NtWikt2+2bt.We update iterativelyWt, Ht, Zt, and βt according to the above rules until converges. We determine automatically the most appropriate number of communities of each snapshot with a statistical model selection method. In detail, we set a large value (e.g., Kinitialt=Nt/4) as the initial number of communities. After parameter optimization, we shrink Wt, Ht, Zt to Wt∗, Ht∗, and Zt∗ by removing the irrelevant rows or columns of which sum is zero or very close to zero. The pseudocode of the solving algorithm of EvoBNMF is presented in Algorithm 1. The returned community label vectors Ctt∈1,T are the results of temporal community detection. And the returned evolution matrices Zt∗ are the results of quantifying evolution behaviors.Algorithm 1: EvoBNMF.
(1)
InitializeWt, Ht, Zt, βt, where t∈1,T;(2)
while not converge do(3)
UpdateW1, H1, β1 according to equations (8)–(10);(4)
fort∈2,Tdo(5)
while not converge do(6)
Wt, Ht, Zt, βt according to equations (11)–(14);(7)
fort∈1,Tdo(8)
shrinkWt, Ht, and Zt to Wt∗, Ht∗, and Zt∗;(9)
Cit=argmaxkHikt∗;(10)
returnCt, Zt∗.According to Algorithm1, iteratively updating of Ht is most time-consuming. The time complexity of each iterative is ON2Kinitial+NKinitial2. Here, we set the average number of iterations as ρ, and the whole time complexity is about OρTN2Kinitial+NKinitial2. As we know, dynamic networks are usually very sparse in real cases. Then, N2 can be replaced with the average number of edges E^ approximatively at each snapshot. In addition, Kinitial can be ignored as it is usually much less than N. Naturally, the time complexity of the optimization algorithm of EvoBNMF can be degraded to OρTE^+N.


## 4. Experiments

In order to verify the principle and the effectiveness of EvoBNMF, we design the comparison experiments on synthetic networks and real-world networks. In this section, we mainly introduce the experimental settings, discuss the experimental results, and analyze the parameter sensitivity and algorithm convergence.


### 4.1. Settings

#### 4.1.1. Datasets

We test the performance of our EvoBNMF on the eight dynamic networks. Four networks are generated according to SYN-FIX [18], and the other four networks are from real-world KIT-mail (https://i11www.iti.uni-karlsruhe.de/en/projects/spp1307/emaildata). We show their statistical information including the number of snapshots T, the average number of nodes V¯, the average number of edges E¯, and the average number of K¯ in Table 2. The details are described as follows:(1)
SYN-FIX [19]: this type of dataset is generated one snapshot by one snapshot with Girvan Newman benchmark. During the specific generation process, the parameters of network properties are set as follows: the number of snapshots T is 10, the number of nodes N is 128, the number of communities K is 4, the mixed parameter Z is 3 which is used to control the degree of the noise, the average degree of the nodes d is 16 and 20, and the community transfer parameter NC is used to control the dynamic level of nodes moving from the current community to other communities, which is set at 10% and 30%.(2)
LFR [20]: the classical synthetic network LFR is mainly to describe the dynamics of networks by considering some community evolution events, which include Birth, Death, Growth, Contraction, Merging, and Splitting. Here, we select the Mergesplit event to generate datasets. We set different probabilities P1 and P2 during network generation to control the probability of community merging and splitting.(3)
KIT-Email: it is a mail communication network from the Information Department of Karlsruhe Institute of Technology (KIT) in Germany. The members are nodes, and the number of mail communication times is the weight of the edge. Different research groups are the corresponding communities. Here, the network data of 48 from September 2006 to August 2010 are divided into different dynamic complex networks. Specifically, we construct each snapshot by shading consecutive 2, 3, 4, and 6 months, respectively, and get four different dynamic networks.Table 2
Statistical information of dynamic networks.
DatasetsNetworksTV¯E¯K¯SYN-FIX [18]Net. 11012820484Net. 21012823744Net. 31012819774Net. 41012824194LFR [20]Net. 51012820484Net. 61012823744Net. 71012819774Net. 81012824194KIT-mailNet. 9241382948123Net. 10161702996325Net. 11121952978825Net. 1282312788327


#### 4.1.2. Evaluation Metrics

The performance of community detection is evaluated with two widely used indexes: the Normalized Mutual Information (NMI) and Error Rate (ER) [7]. In detail,(15)NMI=2IG^,GℋG^+ℋG,ER=G^G^T−GGTF2,where G^ denotes the community structures detected from the algorithm and G denotes the ground truth. ℋG^ and ℋG denotes the entropy of G^ and G, and IG^,G denotes the mutual information between G^ and G, respectively [18]. Here, the entropy and the mutual information are computed with the equation ℋX=∑k=1KNklogNk/N, and IX;Y=∑k=1KX∑l=1KYNkllogN⋅Nkl/NkX⋅NlY, respectively, where N is the number of nodes, and K is the number of communities, respectively. NMI as an entropy measure restrained in 0,1 is usually used to measure the consistency between two partitions. ER is usually used to measure the difference between two different partitions, and the smaller it is, the better its performance is. Universally, ER tends to increase with the scale of networks.And the accuracy of the autonomous determination of the number of communities is evaluated with KA [21]; in detail,(16)KA=1−C∗|−|C^2C∗,where C∗ denotes the grand truth of the number of communities and C^ denotes the number of communities detected by the methods.


#### 4.1.3. Comparison Approaches

In this work, five state-of-the-art approaches are chosen for detecting communities as compared groups as follows:(i)
BNMF [8]: it is a two-steps strategy, which segments the snapshots into discrete time steps and community detection with the static Bayesian NMF on each snapshot, respectively. When the snapshot label t=1, EvoBNMF is reduced to BNMF.(ii)
Dyluvain [3]: it optimizes the temporal modularity with a greedy heuristic method. The resolution parameter γ and couple parameter omiga are set to 1 and 0.5, which are the commonly used parameter settings in the related works.(iii)
PisCES [22]: it is a temporal community detection model based on global spectral clustering, which is derived from the idea of evolutionary clustering and degree modification. The parameter α is set to 0.1, and the maximum community number defaults to 1/10 of the number of nodes.(iv)
DYNMO [18]: it is a multiobjective approach based on evolutionary clustering, which is formalized as a multiobjective optimization problem to be optimized by a genetic algorithm.(v)
ESPRA [15]: it is an evolutionary clustering algorithm based on the fusion of structural perturbation and network topological features, which can automatically determine the number of communities. In this model, the smoothness balance parameter alpha is set to 0.8, and the perturbation and similarity information balance parameter β is set to 0.5.


### 4.2. Experimental Results

#### 4.2.1. Illustrative Example

To clarify the working principle of EvoBNMF, we take an illustrative example on the results of Net. 1 in Figure2. Due to space constraints, we just show the results of snapshots 1−3. At snapshot 1, the learned matrices W1 and H1 are decomposed from the observed A1. Obviously, there are just four columns of W1 and four rows of H1 have a high value. And the number of rows of H1∗ is the targeted number of communities after the adaptive compression of the rows with a low value. Then, the compressed H1∗ and the observed A2 are both the input of the model at snapshot 2. For snapshot tt≥2, the matrices Wt and Ht are decomposed from the observed At and the matrices Ht−1∗ and Zt are decomposed from the Ht synchronously in a unified model. It is worth noting that we can obtain the evolution matrices Zt∗ after the adaptive compression of the rows of Zt. And the evolution matrices correspond to quantitative results of the evolution behavior of communities.Figure 2
An illustration of EvoBNMF on network 1.The community evolution matrixZt mined from the dynamic network through EvoBNMF can represent its evolution pattern and reflect the community evolution relationship between adjacent snapshots. Because the scale of the evolution matrix of different snapshots is different, the row normalization of Ztis carried out, so that ∀l,∑kZlkt=1. Then, Zlkt can be regarded as the propensity that the node transfer from community Cl to community Ck between snapshot t−1 and snapshot t. In Figure 3, the community evolution relationship between adjacent snapshots of Net. 1 is given, and the shade of color in the figure represents the node transition probability between communities. In each subgraph, the vertical coordinate represents the community label Cl of the current network snapshot, the horizontal coordinate represents the community label Ck of the next snapshot, and the shade of the color represents the transition probability, which corresponds to the value of Zlkt of the community label in the current snapshot t. On the whole, the diagonals of these subgraphs always show a yellow (light) color, which means that most of the internal nodes of the communities are likely to remain in the current communities. This phenomenon reflects that the evolution of the dynamic network is slow.Figure 3
The propensity of the evolutionZt between adjacent snapshots on Net. 1.It is worth noting that the subgraphs ofZ6, Z7, Z8, and Z9 have taken place an anomaly about the evolution patterns. For example, in the subgraph of Z6, the new community C5 is derived when the network evolves from snapshot 6 to 7. And the probability that nodes transfer from community C2 to community C5 is relatively high, and the probability that nodes keep in community C2 is obviously relatively low. Therefore, it can be speculated that community C5 is split from community C2. In addition, in the subgraph of Z7, it can be found that community C5 disappears again when the network snapshot evolves from 7 to 8. And its nodes have a high probability to move to community C1. Similarly, it can be found community C6 and C5 appear in the subgraphs of Z8 and Z9 and then disappear. This phenomenon indicates that the evolution of community structure is unstable after snapshot 6. The Birth/Death of community structure is actually corresponding to the dynamic community evolution events, which is first defined by Palla et al. [23]. In real-world social networks, if there are a large number of similar community evolution events, it can indicate that there are real events behind them, which proves that EvoBNMF can be applied to event detection with real-world social networks.In order to more vividly represent the evolution process of a dynamic community, corresponding to the community evolution of dynamic network Net. 1 in Figure3, a visual schematic diagram of evolution and its transition over time is given in Figure 4. In Figure 4, the horizontal axis represents the network snapshot label t, the vertical axis represents the dynamic community label k, the colored circle represents different communities, the circle size represents the relative size of communities, and the dotted arrow represents the node transfer relationship between communities. The community evolution intensity in Figure 3 corresponds to the node transfer relationship between communities and the changing situation of communities in Figure 4. For example, in Figure 3, there is a high diagonal strength in many subgraphs, corresponding to Figure 4, and the community changes little over time in most cases. In addition, new communities appear in snapshots 7 and 9 and disappear again in snapshots 8 and 10, respectively. This phenomenon echoes strongly with Figure 4. In general, Figures 3 and 4 show the evolution pattern of a dynamic community and give a visual diagram of evolution, which can effectively deepen people’s understanding of the evolution of temporal communities in the networks.Figure 4
The visualization of the nodes transition among communities at snapshots of Net. 1.


#### 4.2.2. Temporal Community Detection

In order to investigate the effectiveness, we compare the accuracy of our proposed EvoBNMF with five state-of-the-art methods on temporal community detection, including BNMF [8], Dyluvain [3], PisCES [22], DYNMO [18], and ESPRA [15]. The hyperparameters are set as α=0.2, a=8, and b=5 in experiments.At first, the results are shown in Table3 over NMI, ER, and KA of the five methods on Net. 1−4 of SYN-FIX. The best results, which are bolded out, demonstrate that Dyluvain and our proposed EvoBNMF are comparable in performance and both are better than others. The reason is that Dyluvain optimizes the temporal modularity with a greedy heuristic method and is suitable to the synthetic data SYN-FIX. In addition, the results of BNMF, which is the static version of EvoBNMF, are obviously lower than EvoBNMF. The phenomenon verifies the validity of the proposed EvoBNMF.Table 3
The comparison results of five methods on Net.1−4.
Net.IndexBNMFDyluvainPisCESDYNMOESPRAEvoBNMF1NMI0.6510.980.590.970.99ER2956.220229.943256.9113861.56KA0.44110.38112NMI0.6110.970.560.391ER3015.260244.343340.4341250KA0.41110.380.5613NMI0.260.440.300.230.280.45ER4189.563630.997615.984436.614467.803576.38KA0.0780.540.750.0690.710.694NMI0.390.970.920.410.290.92ER4285.79128.96559.144024.734942.20500.30KA0.29110.310.610.99Furthermore, we show the results over NMI, ER, and KA of the five methods on network5−8 from top to bottom in Figure 5, respectively. These results are the average results of ten repetitions including the corresponding variance bar. In addition, the x-axis is the snapshot label t, and the y-axis is NMI or ER or KA values. From all the subfigures, DyLouvain and EvoBNMF have higher NMI and ER values, and DYNMO and EvoBNMF have higher KA values. This is a strong indication that the proposed EvoBNMF has superior performance not only on temporal community detection but also on autonomous determination of the number of communities.Figure 5
The comparison result of five methods on Net.5−8.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Similarly, the subfigures in Figure6 show the results over NMI, ER, and KA of the five methods on network 9−12 from top to bottom, respectively. From all the subfigures, we found that the results over NMI, ER, and KA of EvoBNMF have the highest accuracy in most cases, but not at the first snapshot. The main reason is that there is no historical structure information for the first snapshot, and EvoBNMF degenerates to BNMF. In addition, there is significantly improved accuracy from snapshot 1 to snapshot 2, which fully demonstrates the effectiveness of EvoBNMF.Figure 6
The comparison result of five methods on Net.9−12.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)


#### 4.2.3. Parameter Sensitivity and Algorithm Convergence

We test the sensitivity of the balance parameterα of EvoBNMF on Net. 9−12 over NMI by ranging α∈0,0.5 with a step length of 0.02. As shown in Figure 7(a), the performance of EvoBNMF is not sensitive when parameter α≥0.1, which is the best on about 0.2.Figure 7
(a) Parameter analysis of the balance parameterα on Net. 9−12; (b) the convergence analysis of Lt on Net. 12.
(a)(b)In addition, we verify the convergence of EvoBNMF on Net. 12 withα=0.2. Figure 7(b) shows the convergence of Lt at snapshots 2−5 of Net. 12. We find that the value of Lt always tends to converge when the times of iterations niter are no more than 50, which demonstrates that the convergence rate is relatively fast.


## 4.1. Settings

### 4.1.1. Datasets

We test the performance of our EvoBNMF on the eight dynamic networks. Four networks are generated according to SYN-FIX [18], and the other four networks are from real-world KIT-mail (https://i11www.iti.uni-karlsruhe.de/en/projects/spp1307/emaildata). We show their statistical information including the number of snapshots T, the average number of nodes V¯, the average number of edges E¯, and the average number of K¯ in Table 2. The details are described as follows:(1)
SYN-FIX [19]: this type of dataset is generated one snapshot by one snapshot with Girvan Newman benchmark. During the specific generation process, the parameters of network properties are set as follows: the number of snapshots T is 10, the number of nodes N is 128, the number of communities K is 4, the mixed parameter Z is 3 which is used to control the degree of the noise, the average degree of the nodes d is 16 and 20, and the community transfer parameter NC is used to control the dynamic level of nodes moving from the current community to other communities, which is set at 10% and 30%.(2)
LFR [20]: the classical synthetic network LFR is mainly to describe the dynamics of networks by considering some community evolution events, which include Birth, Death, Growth, Contraction, Merging, and Splitting. Here, we select the Mergesplit event to generate datasets. We set different probabilities P1 and P2 during network generation to control the probability of community merging and splitting.(3)
KIT-Email: it is a mail communication network from the Information Department of Karlsruhe Institute of Technology (KIT) in Germany. The members are nodes, and the number of mail communication times is the weight of the edge. Different research groups are the corresponding communities. Here, the network data of 48 from September 2006 to August 2010 are divided into different dynamic complex networks. Specifically, we construct each snapshot by shading consecutive 2, 3, 4, and 6 months, respectively, and get four different dynamic networks.Table 2
Statistical information of dynamic networks.
DatasetsNetworksTV¯E¯K¯SYN-FIX [18]Net. 11012820484Net. 21012823744Net. 31012819774Net. 41012824194LFR [20]Net. 51012820484Net. 61012823744Net. 71012819774Net. 81012824194KIT-mailNet. 9241382948123Net. 10161702996325Net. 11121952978825Net. 1282312788327


### 4.1.2. Evaluation Metrics

The performance of community detection is evaluated with two widely used indexes: the Normalized Mutual Information (NMI) and Error Rate (ER) [7]. In detail,(15)NMI=2IG^,GℋG^+ℋG,ER=G^G^T−GGTF2,where G^ denotes the community structures detected from the algorithm and G denotes the ground truth. ℋG^ and ℋG denotes the entropy of G^ and G, and IG^,G denotes the mutual information between G^ and G, respectively [18]. Here, the entropy and the mutual information are computed with the equation ℋX=∑k=1KNklogNk/N, and IX;Y=∑k=1KX∑l=1KYNkllogN⋅Nkl/NkX⋅NlY, respectively, where N is the number of nodes, and K is the number of communities, respectively. NMI as an entropy measure restrained in 0,1 is usually used to measure the consistency between two partitions. ER is usually used to measure the difference between two different partitions, and the smaller it is, the better its performance is. Universally, ER tends to increase with the scale of networks.And the accuracy of the autonomous determination of the number of communities is evaluated with KA [21]; in detail,(16)KA=1−C∗|−|C^2C∗,where C∗ denotes the grand truth of the number of communities and C^ denotes the number of communities detected by the methods.


### 4.1.3. Comparison Approaches

In this work, five state-of-the-art approaches are chosen for detecting communities as compared groups as follows:(i)
BNMF [8]: it is a two-steps strategy, which segments the snapshots into discrete time steps and community detection with the static Bayesian NMF on each snapshot, respectively. When the snapshot label t=1, EvoBNMF is reduced to BNMF.(ii)
Dyluvain [3]: it optimizes the temporal modularity with a greedy heuristic method. The resolution parameter γ and couple parameter omiga are set to 1 and 0.5, which are the commonly used parameter settings in the related works.(iii)
PisCES [22]: it is a temporal community detection model based on global spectral clustering, which is derived from the idea of evolutionary clustering and degree modification. The parameter α is set to 0.1, and the maximum community number defaults to 1/10 of the number of nodes.(iv)
DYNMO [18]: it is a multiobjective approach based on evolutionary clustering, which is formalized as a multiobjective optimization problem to be optimized by a genetic algorithm.(v)
ESPRA [15]: it is an evolutionary clustering algorithm based on the fusion of structural perturbation and network topological features, which can automatically determine the number of communities. In this model, the smoothness balance parameter alpha is set to 0.8, and the perturbation and similarity information balance parameter β is set to 0.5.


## 4.1.1. Datasets

We test the performance of our EvoBNMF on the eight dynamic networks. Four networks are generated according to SYN-FIX [18], and the other four networks are from real-world KIT-mail (https://i11www.iti.uni-karlsruhe.de/en/projects/spp1307/emaildata). We show their statistical information including the number of snapshots T, the average number of nodes V¯, the average number of edges E¯, and the average number of K¯ in Table 2. The details are described as follows:(1)
SYN-FIX [19]: this type of dataset is generated one snapshot by one snapshot with Girvan Newman benchmark. During the specific generation process, the parameters of network properties are set as follows: the number of snapshots T is 10, the number of nodes N is 128, the number of communities K is 4, the mixed parameter Z is 3 which is used to control the degree of the noise, the average degree of the nodes d is 16 and 20, and the community transfer parameter NC is used to control the dynamic level of nodes moving from the current community to other communities, which is set at 10% and 30%.(2)
LFR [20]: the classical synthetic network LFR is mainly to describe the dynamics of networks by considering some community evolution events, which include Birth, Death, Growth, Contraction, Merging, and Splitting. Here, we select the Mergesplit event to generate datasets. We set different probabilities P1 and P2 during network generation to control the probability of community merging and splitting.(3)
KIT-Email: it is a mail communication network from the Information Department of Karlsruhe Institute of Technology (KIT) in Germany. The members are nodes, and the number of mail communication times is the weight of the edge. Different research groups are the corresponding communities. Here, the network data of 48 from September 2006 to August 2010 are divided into different dynamic complex networks. Specifically, we construct each snapshot by shading consecutive 2, 3, 4, and 6 months, respectively, and get four different dynamic networks.Table 2
Statistical information of dynamic networks.
DatasetsNetworksTV¯E¯K¯SYN-FIX [18]Net. 11012820484Net. 21012823744Net. 31012819774Net. 41012824194LFR [20]Net. 51012820484Net. 61012823744Net. 71012819774Net. 81012824194KIT-mailNet. 9241382948123Net. 10161702996325Net. 11121952978825Net. 1282312788327


## 4.1.2. Evaluation Metrics

The performance of community detection is evaluated with two widely used indexes: the Normalized Mutual Information (NMI) and Error Rate (ER) [7]. In detail,(15)NMI=2IG^,GℋG^+ℋG,ER=G^G^T−GGTF2,where G^ denotes the community structures detected from the algorithm and G denotes the ground truth. ℋG^ and ℋG denotes the entropy of G^ and G, and IG^,G denotes the mutual information between G^ and G, respectively [18]. Here, the entropy and the mutual information are computed with the equation ℋX=∑k=1KNklogNk/N, and IX;Y=∑k=1KX∑l=1KYNkllogN⋅Nkl/NkX⋅NlY, respectively, where N is the number of nodes, and K is the number of communities, respectively. NMI as an entropy measure restrained in 0,1 is usually used to measure the consistency between two partitions. ER is usually used to measure the difference between two different partitions, and the smaller it is, the better its performance is. Universally, ER tends to increase with the scale of networks.And the accuracy of the autonomous determination of the number of communities is evaluated with KA [21]; in detail,(16)KA=1−C∗|−|C^2C∗,where C∗ denotes the grand truth of the number of communities and C^ denotes the number of communities detected by the methods.


## 4.1.3. Comparison Approaches

In this work, five state-of-the-art approaches are chosen for detecting communities as compared groups as follows:(i)
BNMF [8]: it is a two-steps strategy, which segments the snapshots into discrete time steps and community detection with the static Bayesian NMF on each snapshot, respectively. When the snapshot label t=1, EvoBNMF is reduced to BNMF.(ii)
Dyluvain [3]: it optimizes the temporal modularity with a greedy heuristic method. The resolution parameter γ and couple parameter omiga are set to 1 and 0.5, which are the commonly used parameter settings in the related works.(iii)
PisCES [22]: it is a temporal community detection model based on global spectral clustering, which is derived from the idea of evolutionary clustering and degree modification. The parameter α is set to 0.1, and the maximum community number defaults to 1/10 of the number of nodes.(iv)
DYNMO [18]: it is a multiobjective approach based on evolutionary clustering, which is formalized as a multiobjective optimization problem to be optimized by a genetic algorithm.(v)
ESPRA [15]: it is an evolutionary clustering algorithm based on the fusion of structural perturbation and network topological features, which can automatically determine the number of communities. In this model, the smoothness balance parameter alpha is set to 0.8, and the perturbation and similarity information balance parameter β is set to 0.5.


## 4.2. Experimental Results

### 4.2.1. Illustrative Example

To clarify the working principle of EvoBNMF, we take an illustrative example on the results of Net. 1 in Figure2. Due to space constraints, we just show the results of snapshots 1−3. At snapshot 1, the learned matrices W1 and H1 are decomposed from the observed A1. Obviously, there are just four columns of W1 and four rows of H1 have a high value. And the number of rows of H1∗ is the targeted number of communities after the adaptive compression of the rows with a low value. Then, the compressed H1∗ and the observed A2 are both the input of the model at snapshot 2. For snapshot tt≥2, the matrices Wt and Ht are decomposed from the observed At and the matrices Ht−1∗ and Zt are decomposed from the Ht synchronously in a unified model. It is worth noting that we can obtain the evolution matrices Zt∗ after the adaptive compression of the rows of Zt. And the evolution matrices correspond to quantitative results of the evolution behavior of communities.Figure 2
An illustration of EvoBNMF on network 1.The community evolution matrixZt mined from the dynamic network through EvoBNMF can represent its evolution pattern and reflect the community evolution relationship between adjacent snapshots. Because the scale of the evolution matrix of different snapshots is different, the row normalization of Ztis carried out, so that ∀l,∑kZlkt=1. Then, Zlkt can be regarded as the propensity that the node transfer from community Cl to community Ck between snapshot t−1 and snapshot t. In Figure 3, the community evolution relationship between adjacent snapshots of Net. 1 is given, and the shade of color in the figure represents the node transition probability between communities. In each subgraph, the vertical coordinate represents the community label Cl of the current network snapshot, the horizontal coordinate represents the community label Ck of the next snapshot, and the shade of the color represents the transition probability, which corresponds to the value of Zlkt of the community label in the current snapshot t. On the whole, the diagonals of these subgraphs always show a yellow (light) color, which means that most of the internal nodes of the communities are likely to remain in the current communities. This phenomenon reflects that the evolution of the dynamic network is slow.Figure 3
The propensity of the evolutionZt between adjacent snapshots on Net. 1.It is worth noting that the subgraphs ofZ6, Z7, Z8, and Z9 have taken place an anomaly about the evolution patterns. For example, in the subgraph of Z6, the new community C5 is derived when the network evolves from snapshot 6 to 7. And the probability that nodes transfer from community C2 to community C5 is relatively high, and the probability that nodes keep in community C2 is obviously relatively low. Therefore, it can be speculated that community C5 is split from community C2. In addition, in the subgraph of Z7, it can be found that community C5 disappears again when the network snapshot evolves from 7 to 8. And its nodes have a high probability to move to community C1. Similarly, it can be found community C6 and C5 appear in the subgraphs of Z8 and Z9 and then disappear. This phenomenon indicates that the evolution of community structure is unstable after snapshot 6. The Birth/Death of community structure is actually corresponding to the dynamic community evolution events, which is first defined by Palla et al. [23]. In real-world social networks, if there are a large number of similar community evolution events, it can indicate that there are real events behind them, which proves that EvoBNMF can be applied to event detection with real-world social networks.In order to more vividly represent the evolution process of a dynamic community, corresponding to the community evolution of dynamic network Net. 1 in Figure3, a visual schematic diagram of evolution and its transition over time is given in Figure 4. In Figure 4, the horizontal axis represents the network snapshot label t, the vertical axis represents the dynamic community label k, the colored circle represents different communities, the circle size represents the relative size of communities, and the dotted arrow represents the node transfer relationship between communities. The community evolution intensity in Figure 3 corresponds to the node transfer relationship between communities and the changing situation of communities in Figure 4. For example, in Figure 3, there is a high diagonal strength in many subgraphs, corresponding to Figure 4, and the community changes little over time in most cases. In addition, new communities appear in snapshots 7 and 9 and disappear again in snapshots 8 and 10, respectively. This phenomenon echoes strongly with Figure 4. In general, Figures 3 and 4 show the evolution pattern of a dynamic community and give a visual diagram of evolution, which can effectively deepen people’s understanding of the evolution of temporal communities in the networks.Figure 4
The visualization of the nodes transition among communities at snapshots of Net. 1.


### 4.2.2. Temporal Community Detection

In order to investigate the effectiveness, we compare the accuracy of our proposed EvoBNMF with five state-of-the-art methods on temporal community detection, including BNMF [8], Dyluvain [3], PisCES [22], DYNMO [18], and ESPRA [15]. The hyperparameters are set as α=0.2, a=8, and b=5 in experiments.At first, the results are shown in Table3 over NMI, ER, and KA of the five methods on Net. 1−4 of SYN-FIX. The best results, which are bolded out, demonstrate that Dyluvain and our proposed EvoBNMF are comparable in performance and both are better than others. The reason is that Dyluvain optimizes the temporal modularity with a greedy heuristic method and is suitable to the synthetic data SYN-FIX. In addition, the results of BNMF, which is the static version of EvoBNMF, are obviously lower than EvoBNMF. The phenomenon verifies the validity of the proposed EvoBNMF.Table 3
The comparison results of five methods on Net.1−4.
Net.IndexBNMFDyluvainPisCESDYNMOESPRAEvoBNMF1NMI0.6510.980.590.970.99ER2956.220229.943256.9113861.56KA0.44110.38112NMI0.6110.970.560.391ER3015.260244.343340.4341250KA0.41110.380.5613NMI0.260.440.300.230.280.45ER4189.563630.997615.984436.614467.803576.38KA0.0780.540.750.0690.710.694NMI0.390.970.920.410.290.92ER4285.79128.96559.144024.734942.20500.30KA0.29110.310.610.99Furthermore, we show the results over NMI, ER, and KA of the five methods on network5−8 from top to bottom in Figure 5, respectively. These results are the average results of ten repetitions including the corresponding variance bar. In addition, the x-axis is the snapshot label t, and the y-axis is NMI or ER or KA values. From all the subfigures, DyLouvain and EvoBNMF have higher NMI and ER values, and DYNMO and EvoBNMF have higher KA values. This is a strong indication that the proposed EvoBNMF has superior performance not only on temporal community detection but also on autonomous determination of the number of communities.Figure 5
The comparison result of five methods on Net.5−8.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Similarly, the subfigures in Figure6 show the results over NMI, ER, and KA of the five methods on network 9−12 from top to bottom, respectively. From all the subfigures, we found that the results over NMI, ER, and KA of EvoBNMF have the highest accuracy in most cases, but not at the first snapshot. The main reason is that there is no historical structure information for the first snapshot, and EvoBNMF degenerates to BNMF. In addition, there is significantly improved accuracy from snapshot 1 to snapshot 2, which fully demonstrates the effectiveness of EvoBNMF.Figure 6
The comparison result of five methods on Net.9−12.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)


### 4.2.3. Parameter Sensitivity and Algorithm Convergence

We test the sensitivity of the balance parameterα of EvoBNMF on Net. 9−12 over NMI by ranging α∈0,0.5 with a step length of 0.02. As shown in Figure 7(a), the performance of EvoBNMF is not sensitive when parameter α≥0.1, which is the best on about 0.2.Figure 7
(a) Parameter analysis of the balance parameterα on Net. 9−12; (b) the convergence analysis of Lt on Net. 12.
(a)(b)In addition, we verify the convergence of EvoBNMF on Net. 12 withα=0.2. Figure 7(b) shows the convergence of Lt at snapshots 2−5 of Net. 12. We find that the value of Lt always tends to converge when the times of iterations niter are no more than 50, which demonstrates that the convergence rate is relatively fast.


## 4.2.1. Illustrative Example

To clarify the working principle of EvoBNMF, we take an illustrative example on the results of Net. 1 in Figure2. Due to space constraints, we just show the results of snapshots 1−3. At snapshot 1, the learned matrices W1 and H1 are decomposed from the observed A1. Obviously, there are just four columns of W1 and four rows of H1 have a high value. And the number of rows of H1∗ is the targeted number of communities after the adaptive compression of the rows with a low value. Then, the compressed H1∗ and the observed A2 are both the input of the model at snapshot 2. For snapshot tt≥2, the matrices Wt and Ht are decomposed from the observed At and the matrices Ht−1∗ and Zt are decomposed from the Ht synchronously in a unified model. It is worth noting that we can obtain the evolution matrices Zt∗ after the adaptive compression of the rows of Zt. And the evolution matrices correspond to quantitative results of the evolution behavior of communities.Figure 2
An illustration of EvoBNMF on network 1.The community evolution matrixZt mined from the dynamic network through EvoBNMF can represent its evolution pattern and reflect the community evolution relationship between adjacent snapshots. Because the scale of the evolution matrix of different snapshots is different, the row normalization of Ztis carried out, so that ∀l,∑kZlkt=1. Then, Zlkt can be regarded as the propensity that the node transfer from community Cl to community Ck between snapshot t−1 and snapshot t. In Figure 3, the community evolution relationship between adjacent snapshots of Net. 1 is given, and the shade of color in the figure represents the node transition probability between communities. In each subgraph, the vertical coordinate represents the community label Cl of the current network snapshot, the horizontal coordinate represents the community label Ck of the next snapshot, and the shade of the color represents the transition probability, which corresponds to the value of Zlkt of the community label in the current snapshot t. On the whole, the diagonals of these subgraphs always show a yellow (light) color, which means that most of the internal nodes of the communities are likely to remain in the current communities. This phenomenon reflects that the evolution of the dynamic network is slow.Figure 3
The propensity of the evolutionZt between adjacent snapshots on Net. 1.It is worth noting that the subgraphs ofZ6, Z7, Z8, and Z9 have taken place an anomaly about the evolution patterns. For example, in the subgraph of Z6, the new community C5 is derived when the network evolves from snapshot 6 to 7. And the probability that nodes transfer from community C2 to community C5 is relatively high, and the probability that nodes keep in community C2 is obviously relatively low. Therefore, it can be speculated that community C5 is split from community C2. In addition, in the subgraph of Z7, it can be found that community C5 disappears again when the network snapshot evolves from 7 to 8. And its nodes have a high probability to move to community C1. Similarly, it can be found community C6 and C5 appear in the subgraphs of Z8 and Z9 and then disappear. This phenomenon indicates that the evolution of community structure is unstable after snapshot 6. The Birth/Death of community structure is actually corresponding to the dynamic community evolution events, which is first defined by Palla et al. [23]. In real-world social networks, if there are a large number of similar community evolution events, it can indicate that there are real events behind them, which proves that EvoBNMF can be applied to event detection with real-world social networks.In order to more vividly represent the evolution process of a dynamic community, corresponding to the community evolution of dynamic network Net. 1 in Figure3, a visual schematic diagram of evolution and its transition over time is given in Figure 4. In Figure 4, the horizontal axis represents the network snapshot label t, the vertical axis represents the dynamic community label k, the colored circle represents different communities, the circle size represents the relative size of communities, and the dotted arrow represents the node transfer relationship between communities. The community evolution intensity in Figure 3 corresponds to the node transfer relationship between communities and the changing situation of communities in Figure 4. For example, in Figure 3, there is a high diagonal strength in many subgraphs, corresponding to Figure 4, and the community changes little over time in most cases. In addition, new communities appear in snapshots 7 and 9 and disappear again in snapshots 8 and 10, respectively. This phenomenon echoes strongly with Figure 4. In general, Figures 3 and 4 show the evolution pattern of a dynamic community and give a visual diagram of evolution, which can effectively deepen people’s understanding of the evolution of temporal communities in the networks.Figure 4
The visualization of the nodes transition among communities at snapshots of Net. 1.


## 4.2.2. Temporal Community Detection

In order to investigate the effectiveness, we compare the accuracy of our proposed EvoBNMF with five state-of-the-art methods on temporal community detection, including BNMF [8], Dyluvain [3], PisCES [22], DYNMO [18], and ESPRA [15]. The hyperparameters are set as α=0.2, a=8, and b=5 in experiments.At first, the results are shown in Table3 over NMI, ER, and KA of the five methods on Net. 1−4 of SYN-FIX. The best results, which are bolded out, demonstrate that Dyluvain and our proposed EvoBNMF are comparable in performance and both are better than others. The reason is that Dyluvain optimizes the temporal modularity with a greedy heuristic method and is suitable to the synthetic data SYN-FIX. In addition, the results of BNMF, which is the static version of EvoBNMF, are obviously lower than EvoBNMF. The phenomenon verifies the validity of the proposed EvoBNMF.Table 3
The comparison results of five methods on Net.1−4.
Net.IndexBNMFDyluvainPisCESDYNMOESPRAEvoBNMF1NMI0.6510.980.590.970.99ER2956.220229.943256.9113861.56KA0.44110.38112NMI0.6110.970.560.391ER3015.260244.343340.4341250KA0.41110.380.5613NMI0.260.440.300.230.280.45ER4189.563630.997615.984436.614467.803576.38KA0.0780.540.750.0690.710.694NMI0.390.970.920.410.290.92ER4285.79128.96559.144024.734942.20500.30KA0.29110.310.610.99Furthermore, we show the results over NMI, ER, and KA of the five methods on network5−8 from top to bottom in Figure 5, respectively. These results are the average results of ten repetitions including the corresponding variance bar. In addition, the x-axis is the snapshot label t, and the y-axis is NMI or ER or KA values. From all the subfigures, DyLouvain and EvoBNMF have higher NMI and ER values, and DYNMO and EvoBNMF have higher KA values. This is a strong indication that the proposed EvoBNMF has superior performance not only on temporal community detection but also on autonomous determination of the number of communities.Figure 5
The comparison result of five methods on Net.5−8.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Similarly, the subfigures in Figure6 show the results over NMI, ER, and KA of the five methods on network 9−12 from top to bottom, respectively. From all the subfigures, we found that the results over NMI, ER, and KA of EvoBNMF have the highest accuracy in most cases, but not at the first snapshot. The main reason is that there is no historical structure information for the first snapshot, and EvoBNMF degenerates to BNMF. In addition, there is significantly improved accuracy from snapshot 1 to snapshot 2, which fully demonstrates the effectiveness of EvoBNMF.Figure 6
The comparison result of five methods on Net.9−12.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)


## 4.2.3. Parameter Sensitivity and Algorithm Convergence

We test the sensitivity of the balance parameterα of EvoBNMF on Net. 9−12 over NMI by ranging α∈0,0.5 with a step length of 0.02. As shown in Figure 7(a), the performance of EvoBNMF is not sensitive when parameter α≥0.1, which is the best on about 0.2.Figure 7
(a) Parameter analysis of the balance parameterα on Net. 9−12; (b) the convergence analysis of Lt on Net. 12.
(a)(b)In addition, we verify the convergence of EvoBNMF on Net. 12 withα=0.2. Figure 7(b) shows the convergence of Lt at snapshots 2−5 of Net. 12. We find that the value of Lt always tends to converge when the times of iterations niter are no more than 50, which demonstrates that the convergence rate is relatively fast.


## 5. Conclusion

In this paper, we focus on modeling temporal community structure with evolution characteristics for boosting community detection and propose the EvoBNMF model which can trace the corresponding evolution behaviors synchronously in dynamic networks. In addition, a gradient descent algorithm is developed to optimize our model. Importantly, the number of communities of each snapshot can be determined automatically by shrinking the evolution behavior in EvoBNMF. Finally, experimental results on synthetic and real-world networks demonstrate the effectiveness of EvoBNMF. In the future, we will do some predictive tasks of dynamic networks (e.g., links or community structures prediction), which are of great practical significance and application value.



---

*Source: 7215888-2021-11-05.xml*