Community detection in dynamic networks using constraint non-negative matrix factorization

Abstract

Community structure, a foundational concept in understanding networks, is one of the most important properties of dynamic networks. A large number of dynamic community detection methods proposed are based on the temporal smoothness framework that the abrupt change of clustering within a short period is undesirable. However, how to improve the community detection performance by combining network topology information in a short period is a challenging problem. Additionally, previous efforts on utilizing such properties are insufficient. In this paper, we introduce the geometric structure of a network to represent the temporal smoothness in a short time and propose a novel Dynamic Graph Regularized Symmetric NMF method (DGR-SNMF) to detect the community in dynamic networks. This method combines geometric structure information sufficiently in current detecting process by Symmetric Non-negative Matrix Factorization (SNMF). We also prove the convergence of the iterative update rules by constructing auxiliary functions. Extensive experiments on multiple synthetic networks and two real-world datasets demonstrate that the proposed DGR-SNMF method outperforms the state-of-the-art algorithms on detecting dynamic community.

Keywords

Community detection dynamic networks evolutionary clustering geometric structure non-negative matrix factorization

1. Introduction

Community structure, one of the most prominent features of networks, plays an important role in network analysis [1, 2]. Accordingly, a large number of community detection techniques have been proposed to identify accurate community structure of networks [3, 4]. However, most of these efforts focus on dealing with community detection in static networks, which have overlooked the temporal feature of community in dynamic networks. In reality, networks especially the online social networks present a high degree of dynamics when the users (nodes) join and leave optionally at any time, which brings noises to networks. Consequently, traditional methods, used in static networks, are not competent for community detection in dynamic networks that are ambiguous and subject to noise. Therefore, a growing number of efforts have been made on community detection in dynamic networks recently [5].

Although a lot of work has been done to address the problem of Dynamic Community Detection (DCD), it is still highly not trivial to design effective and efficient algorithms for DCD. Several reasons are responsible for this issue. Firstly, since no unified definition is given for dynamic community, the varied definitions will make different DCD algorithms incomparable so as to reduce the scalability of algorithms. Secondly, the introduction of time dimension increases the model complexity. Unlike the traditional community detection, DCD must take into account evolution of network structure which stems from the variation of nodes and edges in networks over time. Lastly but not least, the diversity of evolution events for community brings great challenges to DCD. According to the existing literature [6, 7], there are eight kinds of evolution events for community, namely birth, death, growth, contraction, merge, split, continue, and resurgence. At present, no any DCD algorithms can fully identify and track all these evolution events. Despite various difficulties mentioned above, some excellent techniques have been proposed to improve the performance of DCD. Among them, evolutionary clustering, first proposed by Chakrabarti et al. [8], is one of the most widely used approaches for DCD. This method detect communities at time $t$ by introducing a temporal smoothness framework, which takes into account the topology of network at time $t$ as well as previously found community structures with the underlying assumption that abrupt changes of clustering in a short time period are not desirable. For this purpose, an overall cost, consisting of two terms which are a snapshot cost ( $C S$ ) and a temporal cost ( $C T$ ) respectively, is defined as follows,

$\displaystyle\textit{Cost}=\alpha CS+(1-\alpha)CT$ (1)

where the snapshot cost measures how well a community structure fits the network at time $t$ , and the temporal cost measures how similar a community structure acquired at time $t$ is to the community structure at the previous time step. The parameter $\alpha$ is used to balance the importance of $C S$ and $C T$ . This framework has been employed in many literatures [9, 10, 11] to detect community in dynamic networks by introducing different object functions based on modularity, Normalized Mutual Information and spectral clustering etc. However, how to combine community structure information at the previous time with that in current processing at time $t$ is an important problem, and some efforts on utilizing such properties are insufficient.

Non-negative Matrix Factorization (NMF), widely used in information retrieval, computer vision and pattern recognition, has currently been introduced to solve the problem of community detection by presenting its excellent performance [12, 13]. As for the DCD, some researchers [14, 15, 16] have incorporated NMF into the temporal smoothness framework, forming many effective DCD models. However, though studies [17, 18] have shown that NMF is optimal for learning the parts of objects, it cannot capture the geometrical structure of the data space which is essential for clustering. According to spectral graph theory [19] and manifold learning theory [20], graph regularization method can obtain the geometric structure of data. In addition, under the assumption of temporal smoothness, the geometric structure of networks will not change sharply in a short time period. Therefore, we argue that it will be intuitively effective to use graph regularization to model the temporal cost function.

Our main contributions can be summarized as follows:

First of all, we propose a novel Dynamic Graph Regularized Symmetric Non-negative Matrix Factorization (DGR-SNMF) model for DCD, which introduces the graph regularization term as the temporal cost function at the previous time, holding the smoothness of geometric structure. Secondly, we design efficient update rules which can adapt to the change of number of nodes and number of communities over time, and provide the theoretical analysis on their convergence. Finally, extensive experiments on dynamic synthetic networks and real-world networks show the superior performance of DGR-SNMF over the other state-of-the-art methods.

The rest of the paper is organized as follows. In Section 2, we discuss related work. Section 3 describes the details of the proposed model. Section 4 depicts the DGR-SNMF algorithm and proves its convergence. In Section 5 experimental results on synthetic and real-world dynamic networks are presented, followed by a comparison with other existing methods. Finally in Section 6, we give some conclusions and discuss the future directions.

2. Related work

Although it’s not been a long time since the concept of community in complex network was introduced, a large number of approaches have been proposed to solve the problem of community detection in networks from different perspectives. As an intrinsic nature of network, temporal dimension always plays a significant role in the network analysis. Therefore, dynamic community detection has attracted wide attentions recently, so that many approaches have been summarized and classified. According to Aynaud et al. [21], DCD methods can be divided into three categories: two-stage approaches, evolution clustering and coupling graphs. While Hartmann et al. [22] argued that all the existing DCD methods could be identified as either online or offline method. Rossetti and Cazabet [5] proposed a latest survey about community detection in dynamic networks, which presented the distinctive features and challenges of DCD and proposed a novel classification of published approaches. Since our method is based on the temporal smoothness framework, we mainly focus on the related work based on evolutionary clustering.

Lin et al. [23] introduced the evolutionary clustering to analyze communities and their evolutions in dynamic networks. They proposed a novel framework called FacetNet, which can discover communities by jointly maximizing the fit to the observed data and the temporal evolution. Chi et al. [24] proposed two frameworks based on evolutionary spectral clustering in which temporal smoothness is incorporated. The two frameworks, called Preserving Cluster Quality (PCQ) and Preserving Cluster Membership (PCM), are different in how the temporal cost is defined. PCQ measures the consistence between the current clustering result and the network at the previous time step. While PCM represents the smoothness of clustering results between the current and the previous snapshots. Folino and Pizzuti [25] formulated DCD as a multi-objective optimization problem, which maximizes clustering accuracy at the current time step and minimizes clustering drift from one time step to the successive one simultaneously. Ma and Dong [26] proposed two Evolutionary Nonnegative Matrix Factorization (ENMF) frameworks and proved the equivalence relationship among ENMF, the evolutionary modularity density and evolutionary spectral clustering. In addition, they introduced a semi-supervised method called sE-NMF which incorporates a priori information into ENMF. Gao et al. [14] presented a DCD model using nonnegative matrix factorization, which incorporated the community membership transition matrix into the temporal cost term to regularize the smooth changes of community structure. Jiao et al. [15] proposed a similar DCD model with Gao’s. However, the difference between them lies in the snapshot cost. The former used the standard NMF method as the snapshot cost function, while the latter adopted the symmetric NMF (SNMF). Liu and Yuan [27] proposed a DCD model using triple nonnegative matrix factorization which introduced the node weight matrix to achieve good interpretability. Yang et al. [16] presented a DCD method based on NMF considering the strength between nodes. Their basic idea is that node pairs with stronger connection strength have more possibility to be in the same community. Different from other methods mentioned above, they constructed a smoothed node strength matrix representing the connection strength of nodes. Then, the smoothed matrix is decomposed by standard NMF to detect communities in dynamic networks. Our work differs from all these studies in that we employ the graph regularization to capture the historical geometric structure information, which has not been utilized in the existing DCD methods.

3. Proposed model

3.1 Notation

In this subsection, we present the notations that will be used in the remaining of the paper. Let $G=\{G_{1},G_{2},\ldots G_{T}\}$ be a sequence of networks, where the subscript $t$ represents the time step. $G_{t}=\{V_{t},E_{t}\}$ is the network at time $t$ with a vertex set $V_{t}$ and an edge set $E_{t}$ . Let $A_{t}$ be the adjacency matrix of network $G_{t}$ , whose entries are 0 or 1. The corresponding dynamic community is denoted as $C=\{C_{1},C_{2},\ldots C_{T}\}$ . And we use $N_{t}$ and $K_{t}$ to denote the number of nodes and the number of communities in the network at time $t$ , respectively. In addition, the operators $(g)^{T}$ stands for matrix transposition, e.g. $H^{T}$ , and the Frobenius norms will be denoted by $\left\|g\right\|_{F}$ . $Tr(\cdot)$ indicates the trace of a matrix.

3.2 Snapshot cost

Figure 1.

A simple toy example of the stochastic block model: (a) the original graph, (b) the bipartite graph with two communities, and (c) how to generate an edge $a_{34}$ . The figures are from Ref. [23].

According to the existing literature, many approaches have been presented to measure how well a community structure fits the given network. Therein, the stochastic block model [28] is a good measurement which introduces bipartite graph to factorize graph. Similar to Lin et al. [23], we adopt a toy example with 6 nodes and 2 communities (see Fig. 1) to illustrate the main idea of this model. The model employs a special bipartite graph (Fig. 1b), where an edge can only occur between a node $v$ and a community $c$ , to approximate the original network (Fig. 1a). Figure 1c explains how an edge $a_{34}$ is generated in the mixture model. In Fig. 1c, $\lambda_{k}$ represents the prior probability that an edge is due to the $k$ -th community, and $x_{ik}$ denotes the probability that an interaction in community $k$ involves node $v_{i}$ . Therefore, the interaction $a_{34}$ is a combined effect of all the two communities, i.e., $a_{34}\approx\lambda_{1}x_{31}x_{41}+\lambda_{2}x_{32}x_{42}$ . Given a network with $n$ nodes and $m$ communities, the adjacency matrix can be written as follows,

$\displaystyle A\approx X\Lambda X^{T}$ (2)

where $X\in\mathbb{R}^{n\times m}$ is a non-negative matrix, and $\Lambda$ is an $m\times m$ non-negative diagonal matrix with $\lambda_{k}$ as diagonal elements. According to [23], the product of matrices $X$ and $\Lambda$ fully characterizes the community structure in the mixture model. Let $H=X\sqrt{\Lambda}$ . Then, the Eq. (2) can be transformed to the following style

$\displaystyle A\approx HH^{T}$ (3)

where $H$ indicates the community structure for a given network. It is easy to see that Eq. (3) is a standard form of Symmetric Non-negative Matrix Factorization (SNMF). In addition, SNMF has several nice properties for clustering [29]. First of all, as its inherent ability, SNMF can maintain the near-orthogonality of $H$ , which usually leads to clustering performance improvement [30]. Secondly, the SNMF is equivalent to sophisticated normalized cut spectral clustering, which is a principled and effective approach for solving Normalized Cuts [31]. Therefore, we employ the SNMF as the snapshot cost function to measure how well the approximate graph fits the observed network at time $t$ . So, the snapshot cost of a graph at time $t$ can be defined as

$\displaystyle CS=\left\|{A_{t}-H_{t}H_{t}^{T}}\right\|_{F}^{2}$ (4)

where the lower the value of $C S$ is, the higher the quality of graph factorization is.

3.3 Temporal cost

In the evolutionary process, the underlying network is continuously updated over time by either inserting or removing nodes or edges. Under the assumption of temporal smoothness framework, it is almost impossible that nodes or edges change drastically between two consecutive time slices. Therefore, the geometric structure of a graph will not change dramatically between two neighboring time steps. Based on this idea, we argue that it is beneficial to employ the intrinsic geometry to regularize the temporal evolution of network. According to related studies on spectral graph theory [19] and manifold learning theory [20], we introduce graph Laplacian to capture the intrinsic geometrical structure of the data space. The graph Laplacian is defined as follows

$\displaystyle L=D-A$ (5)

where $D$ is a diagonal matrix whose entries are row sums of $A$ , i.e., $D_{ii}=\sum_{j=1}^{n}{A_{ij}}$ . $L$ is a discrete approximation to the Laplace-Beltrami operator on the manifold [20]. Thus, the metric [18], which measures the smoothness of the mapping function along the geodesics in the intrinsic geometry, can be approximated as the following

$\displaystyle R=Tr(H^{T}LH)$ (6)

Here, we can get a mapping function which is sufficiently smooth on the data manifold by minimizing Eq. (6).

Consequently, we construct a temporal cost function as follows

$\displaystyle CT=Tr(H_{t}^{T}L_{t-1}H_{t})$ (7)

where $C T$ implements our target of employing the historical geometrical structure to regularize the dynamic evolution of communities.

3.4 The total cost function

According to Eqs (1), (4), and (7), we can derive the total cost function

$\displaystyle\textit{Cost}=\alpha\left\|{A_{t}-H_{t}H_{t}^{T}}\right\|_{F}^{2}% +(1-\alpha)Tr(H_{t}^{T}L_{t-1}H_{t})$ (8)

Here, the optimal community structure at time $t$ can be acquired by minimizing this total cost function.

Considering a given set of dynamic networks $G=\{G_{1},G_{2},\ldots G_{T}\}$ , we could obtain the optimal set of dynamic communities $C=\{C_{1},C_{2},\ldots C_{T}\}$ by solving the following objective function

$\displaystyle\left\{{{\begin{array}[]{l}\min\limits_{H_{t}\geqslant 0}\alpha% \left\|{A_{t}-H_{t}H_{t}^{T}}\right\|_{F}^{2}+(1-\alpha)Tr(H_{t}^{T}L_{t-1}H_{% t}),\text{ if }t>1\\ \min\limits_{H_{t}\geqslant 0}\left\|{A_{t}-H_{t}H_{t}^{T}}\right\|_{F}^{2},% \text{ if }t=1\\ \end{array}}}\right.$ (9) $\displaystyle\text{s.t. }(H_{t})_{ij}\geqslant 0,\forall i,j$

4. Algorithm

4.1 The update rules

In this section, we introduce an iterative approach to solve the optimization objective function. As to the first temporal slice of a given dynamic networks $G$ , i.e., $t=1$ , we can get the following update rule

$\displaystyle(H_{1})_{ij}\leftarrow(H_{1})_{ij}\sqrt{\frac{(A_{1}H_{1})_{ij}}{% (H_{1}H_{1}^{T}H_{1})_{ij}+\varepsilon}}$ (10)

where the parameter $\varepsilon$ is a very small positive number, mainly to prevent the denominator from approaching zero, which can ensure the convergence and numerical stability of the algorithm. In our experiments, we set the parameter $\varepsilon=10^{-5}$ .

For temporal slices after the first one, the objective function can be reformulated as

$\displaystyle\textit{Cost}=\alpha(Tr(A_{t}A_{t}^{T})-2Tr(A_{t}H_{t}H_{t}^{T})+% Tr(H_{t}H_{t}^{T}H_{t}H_{t}^{T}))+(1-\alpha)Tr(H_{t}^{T}L_{t-1}H_{t})$ (11)

Let $\phi_{ij}$ be the Lagrange multiplier for the constraint $(H_{t})_{ij}\geqslant 0$ , and $\Phi=[{\phi_{ij}}]$ , the Lagrange function $\ell$ of Eq. (11) can be formulated as

$\displaystyle\ell=\alpha(Tr(A_{t}A_{t}^{T})-2Tr(A_{t}H_{t}H_{t}^{T})+Tr(H_{t}H% _{t}^{T}H_{t}H_{t}^{T})){}+(1-\alpha)Tr(H_{t}^{T}L_{t-1}H_{t})+Tr(\Phi H_{t})$ (12)

Due to $L_{t-1}=D_{t-1}-A_{t-1}$ , the partial derivative of $\ell$ with respect to $H_{t}$ is

$\displaystyle\frac{\partial\ell}{\partial H_{t}}=-4\alpha A_{t}H_{t}-2({1-% \alpha})A_{t-1}H_{t}{}+4\alpha H_{t}H_{t}^{T}H_{t}+2({1-\alpha})D_{t-1}H_{t}+\Phi$ (13)

According to the Karush-kuhn-Tucker condition $\phi_{ij}(H_{t})_{ij}=0$ , the following equation holds

$\displaystyle[-2\alpha(A_{t}H_{t})_{ij}-({1-\alpha})(A_{t-1}H_{t})_{ij}+2% \alpha(H_{t}H_{t}^{T}H_{t})_{ij}+({1-\alpha})(D_{t-1}H_{t})_{ij}](H_{t})_{ij}=0$ (14)

Consequently, we can obtain the following update rule for networks at time $t>1$

$\displaystyle(H_{t})_{ij}\leftarrow(H_{t})_{ij}\left({\frac{(2\alpha A_{t}H_{t% }+({1-\alpha})A_{t-1}H_{t})_{ij}}{(2\alpha H_{t}H_{t}^{T}H_{t}+({1-\alpha})D_{% t-1}H_{t})_{ij}+\varepsilon}}\right)^{\frac{1}{4}}$ (15)

where the effect of the parameter $\varepsilon$ is identical to that in Eq. (10). The total cost function is nonincreasing under the update rule Eq. (15), whose proof will be given in a later section.

4.2 The DGR-SNMF algorithm

According to the update rules Eqs (10) and (15), we design a Dynamic Graph Regularized Symmetric Non-negative Matrix Factorization algorithm (DGR-SNMF) to detect community structure of a sequence of dynamic networks. The brief flow of DGR-SNMF algorithm is presented in Algorithm 1. Some technique details are described below.

Algorithm 1 DGR-SNMF
Input: $G=\{G_{1},G_{2},\cdots,G_{T}\}$ : dynamic networks $\alpha$ : parameter for balancing $C S$ and $C T$
Output: $C=\{C_{1},C_{2},\ldots,C_{T}\}$ : dynamic community
1: repeat: from $t=1$ to $t=T$
2: Calculate the number of community according to Eq. (17)
3: if $t=1$ then:
4: Random initialize $H_{1}$
5: while not convergent do
6: Update $H_{1}$ according to Eq. (10)
7: end while
8: Obtain the local community $C_{1}$
9: end if
10: else:
11: Initialize $H_{t}$ according to the rules mentioned in the paper
12: While not convergent do
13: Update $H_{t}$ according to Eq. (16)
14: end while
15: Obtain the local community $C_{t}$
16: end else
17: end repeat

Firstly, due to its unavailability, especially in real world, how to determine the number of community is a challenging problem. Among the existing approaches, we choose to employ an objective function guided strategy proposed by Ma and Dong [26], which is based on the matrix spectrum theory. According to the theory, given a network $G_{t}$ , its adjacency matrix $A_{t}$ can be denoted as $A_{t}=\sum_{i=1}^{n}\lambda_{it}x_{it}x_{it}^{T}$ , where $\lambda_{it}$ and $x_{it}$ is an eigenvalue and its corresponding eigenvector of $A_{t}$ , respectively. We select $k_{t}$ as the number of community for the network at time $t$ , which satisfies the following condition

$\displaystyle k_{t}={\arg\min\limits_{k}}\sqrt{{\left\|{\sum\limits_{i=1}^{k}{% \lambda_{it}x_{it}x_{it}^{T}}}\right\|}/{\left\|{A_{t}}\right\|}}>\delta$ (16)

where $\delta$ is a parameter controlling the approximation, which is selected empirically. According to [26], we set $\delta=$ 0.55 in our experiments.

Secondly, we must determine how to handle the case of inserting or removing nodes, which is common in real dynamic networks. From Eq. (15), we can find that the history geometric structure information is captured by $A_{t-1}$ and $D_{t-1}$ . Moreover, $D_{t-1}$ comes from $A_{t-1}$ . Thus, we just need to consider the adjacency matrix $A_{t-1}$ . When there are $n_{1}$ new nodes joining the network, i.e., $N_{t-1}<N_{t}$ , we pad $n_{1}$ rows and $n_{1}$ columns of zeroes to $A_{t-1}$ , which means that we have no any history information about the $n_{1}$ new nodes. Correspondingly, we handle $n_{2}$ removed nodes by removing corresponding $n_{2}$ rows and $n_{2}$ columns from $A_{t-1}$ . By this way, we can extend DGR-SNMF to the case where the number of nodes changes over time.

Although the change of the number of communities cannot interrupt the update process based on Eq. (15), we should consider how to initialize the community indicator matrix $H_{t}$ when it changes over time, which could affect the performance of our algorithm. Considering the temporal smoothness of community structure, if the number of communities keeps stable between two consecutive time slices, we initialize $H_{t}$ with $H_{t-1}$ . Otherwise, we randomly initialize $H_{t}$ with the values between 0 and 1. The reason for this rule is that we argue there will be relatively obvious changes in the community structure when the number of communities changes over time. In this case, initializing $H_{t}$ based on $H_{t-1}$ will be inferior to initializing $H_{t}$ randomly, which has been verified in experiments.

4.3 Convergence analysis

In order to testify the convergence of our iterative update algorithm, we employ the method proposed by Lee and Seung [32], which makes use of an auxiliary function similar to that used in the Expectation-Maximization algorithm [33, 34]. So, we begin with the definition of the auxiliary function.

Definition 1 $Z(H,\widetilde{H})$ is an auxiliary function for $F(H)$ if the conditions

$\displaystyle Z(H,\widetilde{H})\geqslant F(H),Z(H,H)=F(H)$ (17)

are satisfied.

Lemma 1 If $Z$ is an auxiliary function of $F$ , then $F$ is nonincreasing under the update

$\displaystyle H^{t+1}=\arg\min\limits_{H}Z(H,H^{t})$ (18)

where the superscript $t$ represents the $t$ -th iteration.

According to the lemma of the auxiliary function, it is clear to see that constructing an appropriate auxiliary function is the key to prove the convergence of our algorithm under the update step in Eq. (15). Considering the terms of Eq. (8) which are only relevant to $H_{t}$ , we rewrite Eq. (8) as

$\displaystyle J(H_{t})=-2\alpha Tr(A_{t}H_{t}H_{t}^{T})-({1-\alpha})Tr(H_{t}^{% T}A_{t-1}H_{t}){}+\alpha Tr(H_{t}H_{t}^{T}H_{t}H_{t}^{T})+({1-\alpha})Tr(H_{t}% ^{T}D_{t-1}H_{t})$ (19)

Lemma 2[35] For any matrices $A\in\mathbb{R}_{+}^{n\times n}$ , $B\in\mathbb{R}_{+}^{k\times k}$ , $S\in\mathbb{R}_{+}^{n\times k}$ and ${S}^{\prime}\in\mathbb{R}_{+}^{n\times k}$ , when $A$ and $B$ are symmetric, the following inequality holds

$\displaystyle\sum\limits_{ip}{\frac{(A{S}^{\prime}B)_{ip}S_{ip}^{2}}{{S}^{% \prime}_{ip}}}\geqslant Tr(S^{T}\textit{ASB})$ (20)

Lemma 3[36] For any nonnegative symmetric matrices $A\in\mathbb{R}_{+}^{k\times k}$ , $B\in\mathbb{R}_{+}^{k\times k}$ and any nonnegative matrix $H\in\mathbb{R}_{+}^{n\times k}$ , the following relation holds

$\displaystyle Tr(\textit{HAH}^{T}\textit{HBH}^{T})\leqslant\sum_{ik}\left(% \frac{H^{\prime}AH^{\prime T}H^{\prime}B+H^{\prime}BH^{\prime T}H^{\prime}A}{2% }\right)_{ik}\frac{{H}_{ik}^{{}^{\prime}4}}{{H}_{ik}^{{}^{\prime}3}}$ (21)

Limited to space, we omit the proof for Lemmas 2 and 3.

Proposition 1 Given the objective function $J$ defined as in Eq. (19), the following function

$\displaystyle Z(H_{t},\widetilde{H_{t}})=-2\alpha\sum\limits_{ijk}{(A_{t})_{jk% }(\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\left(1+\log\frac{(H_{t})_{% ij}(H_{t})_{ik}}{(\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\right){}-({% 1-\alpha})\sum\limits_{ijk}{(A_{t-1})_{jk}(\widetilde{H_{t}})_{ij}(\widetilde{% H_{t}})_{ik}}\left(1+\log\frac{(H_{t})_{ij}(H_{t})_{ik}}{(\widetilde{H_{t}})_{% ij}(\widetilde{H_{t}})_{ik}}\right){}+\alpha\sum\limits_{ij}{(\widetilde{H_{t}% }\widetilde{H_{t}}^{T}\widetilde{H_{t}})_{ij}}\frac{(H_{t})_{ij}^{4}}{(% \widetilde{H_{t}})_{ij}^{3}}+({1-\alpha})\sum\limits_{ij}{\frac{(D_{t-1}% \widetilde{H_{t}})_{ij}}{2}}\frac{(H_{t})_{ij}^{4}+(\widetilde{H_{t}})_{ij}^{4% }}{(\widetilde{H_{t}})_{ij}^{3}}$ (22)

is an auxiliary function for $J(H_{t})$ .

Proof. It is straightforward to see $Z(H_{t},H_{t})=J(H_{t})$ . So, we need only investigate whether the relation $Z(H_{t},\widetilde{H_{t}})>J(H_{t})$ holds. By applying Lemma 3 and setting $A=B=I$ , we have

$\displaystyle Tr(H_{t}H_{t}^{T}H_{t}H_{t}^{T})\leqslant\sum\limits_{ij}{(% \widetilde{H_{t}}\widetilde{H_{t}}^{T}\widetilde{H_{t}})_{ij}}\frac{(H_{t})_{% ij}^{4}}{(\widetilde{H_{t}})_{ij}^{3}}$ (23)

In addition, according to Lemma 2 and the inequality of $a^{2}+b^{2}\geqslant 2ab$ , we can derive

$\displaystyle Tr(H_{t}^{T}D_{t-1}H_{t})\leqslant\sum\limits_{ij}{(D_{t-1}% \widetilde{H_{t}})_{ij}\frac{H_{ij}^{2}}{\widetilde{H_{ij}}}}\leqslant\sum% \limits_{ij}{\frac{(D_{t-1}\widetilde{H_{t}})_{ij}}{2}}\frac{(H_{t})_{ij}^{4}+% (\widetilde{H_{t}})_{ij}^{4}}{(\widetilde{H_{t}})_{ij}^{3}}$ (24)

For the negative terms in Eq. (22), we employ the inequality of $z\geqslant 1+\log z$ , which holds for any $z>0$ , and can obtain

$\displaystyle-Tr(A_{t}H_{t}H_{t}^{T})\leqslant-\sum\limits_{ijk}{(A_{t})_{jk}(% \widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\left(1+\log\frac{(H_{t})_{ij}% (H_{t})_{ik}}{(\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\right)$ (25)

and

$\displaystyle-Tr(A_{t-1}H_{t}H_{t}^{T})\leqslant-\sum\limits_{ijk}{(A_{t-1})_{% jk}(\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\left(1+\log\frac{(H_{t})_% {ij}(H_{t})_{ik}}{(\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ik}}\right)$ (26)

Based on Eqs (23) $\sim$ (26), it is easy to be derived that the proposed function $Z(H_{t},\widetilde{H_{t}})$ satisfies the Definition 1 for an auxiliary function, i.e., $Z(H_{t},\widetilde{H_{t}})\geqslant J(H_{t})$ . Therefore, $Z(H_{t},\widetilde{H_{t}})$ is an auxiliary function for $J(H_{t})$ . $\qed$

In order to find out the minimum of $Z(H_{t},\widetilde{H_{t}})$ , we take

$\displaystyle\frac{\partial Z(H_{t},\widetilde{H_{t}})}{\partial(H_{t})_{ij}}=% -4\alpha\frac{(A_{t}\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ij}}{(H_{t})_{% ij}}-2({1-\alpha})\frac{(A_{t-1}\widetilde{H_{t}})_{ij}(\widetilde{H_{t}})_{ij% }}{(H_{t})_{ij}}{}+4\alpha\frac{(\widetilde{H_{t}}\widetilde{H_{t}}^{T}% \widetilde{H_{t}})_{ij}(H_{t})_{ij}^{3}}{(\widetilde{H_{t}})_{ij}^{3}}+2({1-% \alpha})\frac{(D_{t-1}\widetilde{H_{t}})_{ij}(H_{t})_{ij}^{3}}{(\widetilde{H_{% t}})_{ij}^{3}}$ (27)

In addition, according to the same derivation as in [35, 37, 38, 39], the Hessian matrix of $Z(H_{t},\widetilde{H_{t}})$ , containing the second derivatives

$\displaystyle\frac{\partial Z(H_{t},\widetilde{H_{t}})}{\partial(H_{t})_{ij}% \partial(H_{t})_{kl}}=\delta_{ik}\delta_{jl}Y_{ij}$ (28)

is a diagonal matrix with positive entries. Thus $Z(H_{t},\widetilde{H_{t}})$ is a convex function with respect to $H_{t}$ . By setting ${\partial Z(H_{t},\widetilde{H_{t}})}/{\partial(H_{t})_{ij}}=0$ , we can get the following update rule corresponding to the global minimum of $Z(H_{t},\widetilde{H_{t}})$

$\displaystyle(H_{t})_{ij}\leftarrow(\widetilde{H_{t}})_{ij}\left({\frac{(2% \alpha A_{t}\widetilde{H_{t}}+({1-\alpha})A_{t-1}\widetilde{H_{t}})_{ij}}{(2% \alpha\widetilde{H_{t}}\widetilde{H_{t}}^{T}\widetilde{H_{t}}+({1-\alpha})D_{t% -1}\widetilde{H_{t}})_{ij}}}\right)^{\frac{1}{4}}$ (29)

Comparing Eqs (15) and (29), it is obvious that they are equivalent. Similarly, the update rule from Eq. (10) can also be derived by applying the same steps mentioned above. Therefore, we can guarantee the proposed algorithm is convergent.

5. Experiments

To evaluate the performance of DGR-SNMF algorithm, we employ two existing algorithms for comparison, including DYNMOGA [25] and FacetNet [23]. The reason why these two are selected is that, as far as we know, DYNMOGA is renowned for its excellent performance, and FacetNet is among the most well-known algorithms for evolutionary clustering. For each algorithm, 50 runs are conducted on all experiments and the average results are reported.

5.1 Evaluation measures

In experiments, we employed two widely used evaluation metrics, which are Normalized Mutual Information (NMI) [40] and modularity [41], to measure the quality of dynamic communities detected by algorithms. Among them, NMI and modularity are applicable to networks with real communities and without ground truth respectively. Then, we will briefly describe the details of these two metrics.

NMI, stemming from information theory, can be defined as

$\displaystyle\textit{NMI}(C,C^{\prime})=\frac{-2\sum\nolimits_{i=1}^{k}{\sum% \nolimits_{j=1}^{l}{F_{ij}\log\left({\frac{F_{ij}N}{F_{i\cdot}F_{\cdot j}}}% \right)}}}{\sum\nolimits_{i=1}^{k}{F_{i\cdot}\log\left({\frac{F_{i\cdot}}{N}}% \right)}+\sum\nolimits_{j=1}^{l}{F_{\cdot j}\log\left({\frac{F_{\cdot j}}{N}}% \right)}}$ (30)

where $C$ and ${C}^{\prime}$ are respectively the set of communities derived from algorithm and the ground truth. According to $C$ and ${C}^{\prime}$ , we can construct a confusion matrix $F$ , whose entry $F_{ij}$ represents the number of nodes that belong to both the community $C_{i}$ and ${C}^{\prime}_{j}$ . In addition, $F_{\cdot i}$ and $F_{\cdot j}$ indicate the sum of the $i$ -th row and the sum the $j$ -th column of the confusion matrix, respectively. Moreover, parameters $k$ and $l$ represent the number of communities $C$ and ${C}^{\prime}$ , and $N$ is the total number of all nodes in a given network.

The other metric modularity, an elegant concept proposed by Newman and Girvan [41], can be formulated as

$\displaystyle Q=\frac{1}{2m}\sum\limits_{i}{\sum\limits_{j}{\left[{A_{ij}-% \frac{k_{i}k_{j}}{2m}}\right]}}\delta(C_{i},C_{j})$ (31)

where $m$ indicates the number of edges, and $k_{i}$ represents the degree of node $i$ . If node $i$ and $j$ are in the same community, $\delta(C_{i},C_{j})=1$ , otherwise $\delta(C_{i},C_{j})=0$ . For detailed explanation of modularity, please refer to [41].

5.2 Synthetic datasets

5.2.1 Dynamic LFR benchmark

To generate realistic benchmark networks, Greene et al. [42] developed a dynamic benchmark generator1

¹
http://mlg.ucd.ie/dynamic/.

built upon LFR [43] that can produce static netwoks with embedded ground truth communities. The generator can output sets of unweighted undirected networks with different events such as switch, birth and death, expansion and contraction, mergeing and splitting, which are controlled by user-specified parameters. In addition, there are other sharing parameters determining the network structrue such as the number of nodes (

N

), the number of time steps (

s

), average degree (

k

), maximum degree (

\max k

), and mixing coefficient (

\mu

), etc. Since it being proposed, the dynamic LFR model has been widely applied to verify the performance of DCD [25, 26]. Therefore, we also employ this model to generate dynamic benchmarks in our experiments.

Figure 2.

Parameter effects of in terms of NMI on synthetic switch datasets. (a) $p=$ 0.1, (b) $p=$ 0.2.

Due to the existence of the weighted parameter $\alpha$ , we should first investigate how it influences the performance of DGR-SNMF. This work is implemented in dynamic networks with switch events, which flips memberships between communities at each step. To generate dynamic graph with switch events, we should specify a parameter $p$ , representing the probability of a node switching community membership between time steps. We assign $p$ to 0.1 and 0.2 respectively, and set $s=$ 5 to construct five dynamic networks over 5 time steps. These graphs share other parameters: $N=$ 250, $k=$ 10, $\max k=$ 20, $\mu=$ 0.2. The default values are considered for the rest of the parameters. We apply DGR-SNMF algorithm to detect dynamic communities by adjusting $\alpha$ from 0.1 to 0.9 for investigating the effect of the only parameter. Here, due to limited space, we do not display all results in Fig. 2, which shows how the parameter $\alpha$ determines the performance of DGR-SNMF algorithm in terms of NMI. As illustrated in Fig. 2, the accuracy of DGR-SNMF increases with the increase of $\alpha$ , but it almost always achieves the best performance at $\alpha=$ 0.5 in all experiments. When $\alpha$ is greater than 0.5, the performance of DGR-SNMF stops increasing and even drops in some cases. It differs from other algorithms such as FacetNet, evolutionary spectral clustering [24] and Kim-Han [44], where the parameter $\alpha$ corresponding to the best performance is set to 0.8 or more. The reason for this may be that the geometric structure plays more important role than other information in the evolution of community structure. In other words, the history geometric structure of a network has a strong constraint on the dynamic evolution of communities. Consequently, we designate $\alpha$ as 0.5 in the following experiments.

In order to testify the performance of DGR-SNMF, we first compare our algorithm with 2 baseline methods mentioned above, i.e., FacetNet and DYNMOGA, in dynamic LFR networks with switch events. Moreover, we set the best parameters in these two algorithms according to related literature. Due to the existence of the ground truth for the community memberships at each time step, we employ NMI to represent the performance. Figure 3 gives the performance on dynamic synthetic benchmarks with $p=$ 0.1 and $p=$ 0.2. As can be seen from figures, our algorithm DGR-SNMF clearly outperforms the two baseline algorithms at all time steps in both cases. Whether how dramatically the community structure changes, DGR-SNMF can acquire excellent performance at each time step.

To furthermore investigate the performance of DGR-SNMF, we apply these algorithms on the dynamic synthetic networks with some main events such as birth and death, expansion and contraction, merging and splitting, which may characterize the evolution of dynamic networks. By the generator proposed by Greene et al. [42], we generate three dynamic synthetic networks with 10 consecutive time steps for the three different types of events. Each dynamic network is constituted by 100 nodes, average node degree 10, maximum node degree 20, and mixing parameter 0.2. For birth and death events, 20% of communities are created by removing nodes from existing communities, and 10% of the existing communities are randomly removed. To generate expansion and contracion events, 10% of communities are randomly expanded and contracted by 25% of their size at each time step, and nodes are chosen at random. Among the networks embedded by merging and splitting events at each subsequent time step, 10% of communities are split, another 10% of communities are chosen at random, and couples of them are merged. Figure 4 depicts the NMIs obtained by compared algorithms on the three types of dynamic networks, which clearly shows that DGR-SNMF achieves the best performance in all three evolution events. In particular, it is worth to note that the performance of FacetNet decreases dramatically as time goes for the network with birth and death events, while the other two algorithms are stable. The reason for this is that the FacetNet algorithm is based on the PCM framework, in which the error in communities at the previous time step can be passed down to the detected communities at the next neighboring time steps. However, DGR-SNMF and DYNMOGA algorithms rely on the geometric structure and network topology at two consecutive time steps respectively, which avoids this limitation. In addition, we notice that the DYNMOGA algorithm is not always superior to FacetNet as can be seen in Fig. 4b. On the contrary, DGR-SNMF outperforms the other two algorithms at almost all time steps in all three types of events, except for the fifth time steps in merging and splitting events (as seen in Fig. 4c).

Figure 3.

NMI on dynamic LFR synthetic datasets with switch events. (a) $p=$ 0.1, (b) $p=$ 0.2.

Figure 4.

NMI on dynamic LFR synthetic datasets with (a) birth and death events, (b) expansion and contraction events, (c) merging and splitting events.

5.2.2 SYN-FIX and SYN-VAR networks

In this section, we introduce two other kinds of data sets, named SYN-FIX and SYN-VAR from [44], to verify the performance of our algorithm. SYN-FIX is a dynamic network with a fixed number of communities, while SYN-VAR is a dynamic network with a variable number of communities over times. SYN-FIX consists of 128 nodes divided into 4 communities where each of them contains 32 nodes. Every node has an average degree of 16 and shares $z$ links with the other nodes outside of its community. The parameter $z$ determines the noise level of a network, which means that the larger $z$ , the more fuzzy the community structure. To produce dynamic network, 3 nodes are randomly chosen for each community at current time step and assigned to the other communities at random at the next time step. SYN-VAR is a modified version of SYN-FIX by introducing the forming and dissolving of communities. In particular, the initial network has 256 nodes grouped into 4 communities with 64 nodes in each. At each time step, we choose 8 nodes from each community and form a new community with these 32 nodes. Repeating this procedure for 5 time steps, then the nodes return to original communities. Thus, the number of communities in the 10 temporal snapshots is 4, 5, 6, 7, 8, 8, 7, 6, 5, 4 in turn.

We run DGR-SNMF and FacetNet on the SYN-FIX and SYN-VAR, and compare the results with DYNMOGA as seen in Figs 5 and 6. It should be noted that the results reported for DYNMOGA are from [25], provided by the authors. Figure 5 demonstrates that when the community structure is clear (Fig. 5a), the NMIs of DGR-SNMF and DYNMOGA are comparable, up to 1.0 at almost all time steps. However, as the fuzziness increases, DGR-SNMF shows better performance than DYNMOGA (Fig. 5b). Although the performance of DYNMOGA is better than that of DGR-SNMF at fifth and sixth time steps, its NMI fluctuates dramatically, ranging from 0.9 to 1.0. However, the DGR-SNMF is relatively stable, maintaining an NMI value above 0.98. Overall, compared with DYNMOGA, our algorithm increases averagely 3.4% in terms of NMI on SYN-FIX networks when $z=$ 5. This behavior can also be found in the SYN-VAR networks with $z=$ 3 and $z=$ 5 (Fig. 6). In addition, the performance of FacetNet has been greatly improved, even being superior to DYNMOGA at some time steps. Nevertheless, in either SYN-FIX or SYN-VAR networks, DGR-SNMF is always superior to FacetNet.

Figure 5.

NMI on SYN-FIX networks when (a) $z=$ 3, (b) $z=$ 5.

Figure 6.

NMI on SYN-VAR networks when (a) $z=$ 3, (b) $z=$ 5.

5.2.3 A commonly used synthetic dataset

In this section, a commonly used synthetic dataset, proposed by Lin et al. [23], is employed to investigate the effectiveness of our algorithm. This network consists of 128 nodes clustered into 4 communities of 32 nodes each. Each node shares $z$ links with the nodes out of its community, which determined the fuzziness of community structure. Similar to Lin et al., we generate dynamic networks with 50 consecutive time steps, where the average degree for the nodes is set to 20. To investigate the effect of $z$ for the DCD algorithms, we take two values, $z=$ 5 and $z=$ 6, into consideration. In addition, for each fixed $z$ , we consider the two cases with 10% and 30% nodes changing their communities at each time step. In the former case, the community structure is relatively stable over time. While for the latter, it changes dramatically over time.

From the comparison results given in Fig. 7, it can be seen that our algorithm shows excellent performance, especially when the community structure is distinct, i.e., $z=$ 5. However, with the gradual fuzziness of community structure ( $z$ from 5 to 6), the average NMI obtained by DGR-SNMF drastically decreases from 0.79 to 0.29 and from about 0.69 to 0.19 when 10% and 30% nodes changing their communities, respectively. In addition, when fixing $z$ , as the number of nodes changing their communities increases from 10% to 30%, the performance of DGR-SNMF decreases obviously. However, DGR-SNMF still outperforms the other two baseline algorithms at almost all cases. Although the values of NMI obtained by DGR-SNMF are lower than those of FacetNet or DYNMOGA at some time steps, the average performance is still superior to the other two algorithms over all time steps. By computing and comparing the average NMIs on 50 time slices, the performance of our algorithm is improved by 72%, 68%, 113%, and 31% respectively, compared with the suboptimal algorithm for the four dynamic networks. In addition, it is worth noting that FacetNet is not always superior to DYNMOGA. When the community structure becomes less clear, the performance of the two algorithms is comparable, and even DYNMOGA outperforms FacetNet in terms of average NMI. This result illustrates that the geometric structure can not only improve the accuracy of DCD algorithms, but also increase the robustness of algorithms.

Figure 7.

NMI on commonly used synthetic datasets when avgdegree $=$ 20 with (a) $z=$ 5 and nc $=$ 10%, (b) $z=$ 5 and nc $=$ 30%, (c) $z=$ 6 and nc $=$ 10%, (d) $z=$ 6 and nc $=$ 30%.

5.2.4 RDyn benchmark

RDyn,2

²
https://github.com/GiulioRossetti/RDyn.

a novel dynamic network generator proposed by Rossetti [45], is able to simulate not only interaction dynamics but also community ones. This generator can allow users to deeply customize the generated topology and related dynamics by several controlling variables, among which community quality threshold

\kappa

is one of the most important. Conductance is commonly employed as a way to continuously assess clustering stability and identify community shifts. The lower the value of

\kappa

, the higher the partition quality. RDyn is defined as an iterative process since the generated topologies are the results of subsequent choices made by the nodes within it. Once completed each iteration the status of the resulting communities is evaluated, returned if considered stable, and community dynamics are planted. For more detailed information about RDyn, see [45]. By RDyn, we generate three dynamic networks with 100 nodes, corresponding to

\kappa=

0.2, 0.3, 0.4. In addition, we set the number of iterations to 100 and the average degree of each node to 15, keeping the other parameters default.

Figure 8 gives a detailed comparison of the performance of various algorithms for RDyn benchmark. We can observe that DGR-SNMF achieves the best performance in most cases followed by FacetNet. In order to see clearly the performance difference between DGR-SNMF and FacetNet, we analyze the distribution of the difference of NMI obtained by the two algorithms separately (Fig. 8b, d, f). Although the performance improvement of DGR-SNMF is not obvious, the proportion of positive values increases with the decrease of the community quality threshold $\kappa$ , which is 78%, 82% and 88% respectively. Moreover, we find that most of the disadvantages of DGR-SNMF always appear at the first several time steps, which is due to the fact that geometric structure does not play an effect role at the initial stage when the community structure is fuzzy. To illustrate this phenomenon, we also employ the static SNMF algorithm, which is applied to each static snapshot independently, to detect community for each snapshot. It can be seen clearly from Fig. 8 that SNMF always performs poorly at the initial stage. However, as time goes by, the performance of SNMF gradually improves, but still worse than FacetNet. Therefore, the introduction of geometric structure information significantly improves the performance of DCD. In addition, we also observe that DYNMOGA performs worst on RDyn networks among all these algorithms, and its NMI decreases gradually with time.

Figure 8.

Comparison of the DCD algorithms on RDyn in terms of NMI ((a) $\kappa=$ 0.2, (c) $\kappa=$ 0.3, (e) $\kappa=$ 0.4), and the difference of NMI between DGR-SNMF and FacetNet algorithms ((b) $\kappa=$ 0.2, (d) $\kappa=$ 0.3, (f) $\kappa=$ 0.4).

5.3 Real-world networks

In foregoing paragraphs, we analyze the effectiveness of DGR-SNMF on some synthetic dynamic networks, where the ground truth community is known. In this section, we will check whether our algorithm is effective on two real-world dynamic networks t namely Cell Phone Calls (CPC)3

³
http://www.cs.umd.edu/hcil/VASTchallenge08/.

and Enron Mail (EM).4

⁴

http://www-2.cs.cmu.edu/∼enron/.

The CPC dataset is composed of cell call phone records among the members of the fictitious Paraiso movement, covering a period of ten days in June 2006. The network can be generated by regarding a unique cell phone as a node while a phone call between two members of Paraiso movement as one edge. We can generate 10 networks, corresponding to one network with 400 nodes per day. The EM dataset is an email collection with potential anomalous email communications spanning over about 3 years. To facilitate comparative analysis, we use the same method as DYNMOGA to process the EM dataset focusing on the year 2001, generating 12 networks, one for each month.

We first apply DGR-SNMF on the CPC networks to detect dynamic communities. For comparison, besides DYNMOGA, we also employ Adaptive Label Propagation Algorithm (ALPA) [46] with excellent performance to verify the performance of our method. In addition, SNMF algorithm is also applied to the CPC networks to verify whether the geometric structure is effective in detecting dynamic communities. Since the true community structure is unknown, we employ modularity to measure the community quality. Table 1 reports the results of these algorithms and some statistical information regarding the CPC networks. As can be seen from Table 1, DGR-SNMF achieves optimal performance, which is represented by the larger modularity values, in all networks except the first one where there is no historical geometric structure to use. Therefore, our algorithm, incorporating geometric structure based on SNMF, performs better than SNMF, showing that the historical geometric structure is indeed effective for community detection in dynamic networks. In addition, it is worth noting that although ALPA performs well on some synthetic dynamic networks, DGR-SNMF is superior to ALPA on real networks.

Table 1

The detail statistic information of CPC network

T	$\|$ V $\|$	$\|$ E $\|$	SNMF		DYNMOGA		ALPA		DGR-SNMF
			$\|$ C $\|$	M	$\|$ C $\|$	M	$\|$ C $\|$	M	$\|$ C $\|$	M
1	370	525	21	0.6248	32	0.6640	36	0.5758	22	0.6262
2	373	499	24	0.6574	35	0.6561	32	0.6065	27	0.6745
3	374	509	15	0.6473	30	0.6587	33	0.5974	25	0.6706
4	374	514	18	0.6501	31	0.6540	36	0.5913	19	0.6666
5	373	508	25	0.6548	32	0.6626	31	0.6109	22	0.6737
6	373	512	16	0.6617	25	0.6651	32	0.6094	19	0.6785
7	367	498	16	0.6496	33	0.6571	32	0.6058	17	0.6663
8	365	511	22	0.6359	36	0.6329	29	0.5875	17	0.6561
9	374	518	19	0.6432	34	0.6538	32	0.6064	21	0.6639
10	384	530	22	0.6452	32	0.6467	31	0.6016	19	0.6578

T is the number of time steps, $|$ V $|$ the number of nodes, $|$ E $|$ the number of edges, $|$ C $|$ the number of communities, M the modularity.

Although the true community structure is unknown, we can follow the same approach of Lin et al. [23] to generate the overall network by aggregating all edges over all ten time steps into a single network, and apply our algorithm to detect communities. After that, the communities obtained on the aggregated network can be considered as the ground truth partition. Then, we can compute the NMI between the ground truth partition and the communities obtained at each time step, as reported in Fig. 9a. It can be seen that the similarity between the communities obtained on the aggregated network and those calculated at each time step is around 0.5, which represents a balance between the snapshot and the temporal costs as described by [25]. However, different from DYNMOGA, the number of communities detected at each time step is close to that obtained on the overall network, which is consistent with intuition.

Figure 9.

NMI for CPC network (a) and EM network (b).

Similarly, we perform the same analysis on the EM network as shown in Table 2 and Fig. 9b. As can be seen from Table 2, DGR-SNMF is still the best of the four algorithms, although it is slightly inferior to DYNMOGA at the fifth time step. In addition, we also observe that the number of community division on overall network is 7, which is close to the average number of communities for all 12 networks. As for the NMI between the ground truth division on the overall network and the communities detected for each network, we come to the same conclusion as the CPC network.

Table 2

The detail statistic information of EM network

T	$\|$ V $\|$	$\|$ E $\|$	SNMF		DYNMOGA		ALPA		DGR-SNMF
			$\|$ C $\|$	M	$\|$ C $\|$	M	$\|$ C $\|$	M	$\|$ C $\|$	M
1	96	180	7	0.6328	11	0.6368	15	0.6329	6	0.6427
2	93	204	6	0.6771	7	0.6803	11	0.6465	6	0.6911
3	97	218	5	0.6194	12	0.6550	14	0.6373	6	0.6609
4	108	257	7	0.6479	12	0.6571	17	0.6173	8	0.6651
5	125	292	7	0.5465	15	0.5699	17	0.4695	13	0.5606
6	120	231	11	0.6742	10	0.6943	24	0.6100	8	0.6981
7	109	252	7	0.6524	10	0.6530	17	0.5981	15	0.6655
8	131	396	6	0.5582	9	0.5356	13	0.4976	13	0.5628
9	128	361	8	0.6188	10	0.6324	24	0.5604	14	0.6425
10	135	575	8	0.5590	13	0.5302	14	0.5163	9	0.5667
11	127	469	5	0.6041	9	0.5707	16	0.5755	13	0.6253
12	113	325	7	0.6129	8	0.6152	17	0.5753	5	0.6201

T is the number of time steps, $|$ V $|$ the number of nodes, $|$ E $|$ the number of edges, $|$ C $|$ the number of communities, M the modularity.

6. Conclusion and future directions

Dynamic community detection represents one of the most challenging problems with broad applications. In this paper, we present a graph regularized non-negative matrix factorization (DGR-SNMF) based approach to address the issue of DCD. In addition, we design an effective iterative algorithm based on multiplicative update rules, and provide the detailed proof process. Experimental results on multiple kinds of synthetic dynamic networks and two real-world datasets show that DGR-SNMF achieves better performance than other state-of-the-art algorithms, providing an insight into understanding the effect of historical geometric structure in detecting dynamic communities.

Even though our algorithm outperforms the other algorithms in terms of overall performance, the improvements on some networks are not significant. Therefore, it is worth further study about how to make best use of the historical geometric structure to detect dynamic communities. Furthermore, extending DGR-SNMF to detect overlapping communities in dynamic networks is also interesting and meaningful.

Footnotes

Acknowledgments

The authors wish to thank Francesco Folino for providing us the codes of DYNMOGA, including the generator of dynamic LFR benchmark and the results obtained by his method on these synthetic dynamic networks, Giulio Rossetti for the software generator of RDyn benchmark.

References

Girvan

and Newman

M.E.J.

, Community structure in social and biological networks, Proc Natl Acad Sci U S A 99(12) (2002), 7821–7826.

Tong

A.H.

Drees

Nardelli

et al., A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules, Science 295(5553) (2002), 321–324.

Fortunato

and Hric

, Community detection in networks: A user guide, Physics Reports 659 (2016), 1–44.

Coscia

Giannotti

and Pedreschi

, A classification for community discovery methods in complex networks, Statistical Analysis & Data Mining 4(5) (2011), 512–546.

Rossetti

and Cazabet

, Community Discovery in Dynamic Networks: a Survey, 2017.

Palla

Barabási

A.L.

and Vicsek

, Quantifying social group evolution, Nature 446(7136) (2007), 664.

Cazabet

and Amblard

, Dynamic Community Detection, Springer New York, 2014.

Chakrabarti

Kumar

and Tomkins

, Evolutionary clustering, in: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 554–560.

Folino

and Pizzuti

, Multiobjective evolutionary community detection for dynamic networks, in: Conference on Genetic and Evolutionary Computation, ACM, 2010, pp. 535–536.

10.

Crane

and Dempsey

, Community detection for interaction networks, Immunology 86(3) (2015), 469–474.

11.

Gong

M.G.

Zhang

L.J.

J.J.

et al., Community detection in dynamic social networks based on multi-objective immune algorithm, Journal of Computer Science & Technology 27(3) (2012), 455–467.

12.

Yang

and Leskovec

, Overlapping community detection at scale: A nonnegative matrix factorization approach, 2013, 587–596.

13.

Wang

et al., Community discovery using nonnegative matrix factorization, Data Mining & Knowledge Discovery 22(3) (2011), 493–521.

14.

Gao

Yuan

Wang

et al., Dynamic community detection using nonnegative matrix factorization, in: International Conference on Computing Intelligence and Information System, IEEE Computer Society, 2017, pp. 39–45.

15.

Jiao

et al., Exploring temporal community structure and constant evolutionary pattern hiding in dynamic networks,Â Neurocomputing, 2018.

16.

Yang

Guo

and Liu

J.Q.

, Community detection via measuring the strength between nodes for dynamic networks, Physica A Statistical Mechanics & Its Applications (2018), 509.

17.

Lee

, Learning the parts of objects with nonnegative matrix factorization, Nature 401(6755) (1999), 788.

18.

Cai

Han

et al., Graph regularized non-negative matrix factorization for data representation, IEEE Trans Pattern Anal Mach Intell 33(8) (2011), 1548–1560.

19.

Fan

R.K.C.

, Spectral graph theory, Spectral graph theory, in: Published for the Conference Board of the Mathematical Sciences by the American Mathematical Society, 1997, p. 212.

20.

Belkin

Niyogi

, Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in Neural Information Processing Systems 14(6) (2001), 585–591.

21.

Aynaud

Fleury

Guillaume

J.L.

et al., Communities in evolving networks: Definitions, detection, and analysis techniques, dynamics on and of complex networks, Springer New York 2 (2013), 159–200.

22.

Hartmann

Kappes

and Wagner

, Clustering Evolving Networks, Algorithm Engineering, Springer International Publishing, 2016.

23.

Lin

Y.R.

Chi

Zhu

et al., Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, in: International Conference on World Wide Web, ACM, 2008, pp. 685–694.

24.

Chi

Song

Zhou

et al., On evolutionary spectral clustering, Acm Transactions on Knowledge Discovery from Data 3(4) (2009), 1–30.

25.

Folino

and Pizzuti

, An evolutionary multiobjective approach for community discovery in dynamic networks, IEEE Transactions on Knowledge & Data Engineering 26(8) (2014), 1838–1852.

26.

and Dong

, Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks, IEEE Transactions on Knowledge & Data Engineering 29(5) (2017), 1045–1058.

27.

Liu

and Yuan

L.M.Z.

, Community Detection in Temporal Networks Using Triple Nonnegative Matrix Factorization, DEStech Transactions on Computer Science and Engineering, 2017.

28.

, Soft clustering on graphs, Nips, 2005, 5.

29.

Wang

Zhu

et al., Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization, in: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2008, pp. 307–314.

30.

Ding

and He

, K-means clustering via principal component analysis, in: Proceedings of the Twenty-first International Conference on Machine Learning, ACM, 2004, p. 29.

31.

Shi

and Malik

, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8) (2000), 888–905.

32.

Lee

D.D.

and Seung

H.S.

, Algorithms for non-negative matrix factorization, Advances in Neural Information Processing Systems, 2001, 556–562.

33.

Dempster

A.P.

Laird

N.M.

and Rubin

D.B.

, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society Series B (methodological) (1977), 1–38.

34.

Saul

and Pereira

, Aggregate and mixed-order Markov models for statistical language processing, arXiv preprint, 1997, 9706007.

35.

Ding

and Peng

et al., Orthogonal nonnegative matrix t-factorizations for clustering, in: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2006, pp. 126–135.

36.

Wang

Huang

and Ding

, Simultaneous clustering of multi-type relational data via symmetric nonnegative matrix tri-factorization, in: Proceedings of the 20th ACM International Conference on Information and Knowledge Management, ACM, 2011, pp. 279–284.

37.

and Zhou

, Co-clustering on manifolds, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2009, pp. 359–368.

38.

Ding

C.H.Q.

and Jordan

M.I.

, Convex and semi-nonnegative matrix factorizations, IEEE Transactions on Pattern Analysis and Machine Intelligence 32(1) (2010), 45–55.

39.

Wang

and Zhang

, Semi-supervised clustering via matrix factorization, in: Proceedings of the 2008 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, 2008, pp. 1–12.

40.

Danon

Diazguilera

Duch

et al., Comparing community structure identification, Journal of Statistical Mechanics: Theory and Experiment 2005(9) (2005).

41.

Newman

M.E.J.

and Girvan

, Finding and evaluating community structure in networks, Phys Rev E Stat Nonlin Soft Matter Phys 69(2) (2004), 026113.

42.

Greene

Doyle

and Cunningham

, Tracking the Evolution of Communities in Dynamic Social Networks, in: International Conference on Advances in Social Networks Analysis and Mining, IEEE, 2010, pp. 176–183.

43.

Lancichinetti

Fortunato

and Radicchi

, Benchmark graphs for testing community detection algorithms, Physical Review E Statistical Nonlinear & Soft Matter Physics 78(4 Pt 2) (2008), 046110.

44.

Kim

M.S.

and Han

, A particle-and-density based evolutionary clustering method for dynamic networks, Proceedings of the Vldb Endowment 2(1) (2009), 622–633.

45.

Rossetti

, RDyn: Graph benchmark handling community dynamics, 5(6) (2017), 893–912.

46.

Han

Zhao

et al., Community detection in dynamic networks via adaptive label propagation, PLoS ONE 12(11) (2017).

Community detection in dynamic networks using constraint non-negative matrix factorization

Abstract

Keywords

1. Introduction

3. Proposed model

3.1 Notation

3.2 Snapshot cost

4.1 The update rules

5.1 Evaluation measures

5.2.1 Dynamic LFR benchmark

1 http://mlg.ucd.ie/dynamic/.

2 https://github.com/GiulioRossetti/RDyn.

3 http://www.cs.umd.edu/hcil/VASTchallenge08/.

Footnotes

Acknowledgments

References

¹
http://mlg.ucd.ie/dynamic/.

²
https://github.com/GiulioRossetti/RDyn.

³
http://www.cs.umd.edu/hcil/VASTchallenge08/.