# Dynamic Community Discovery Method Based on Phylogenetic Planted Partition in Temporal Networks
## 3 Materials
### A Migration Partitioning Model for Phylogenetic Evolution
Determine rules: if the differences are small, let the scope be as large as possible; if the difference is large, narrow the approximation. Therefore, Equation (22) is used to judge whether the Taylor approximation is good enough or not. \[\rho=\frac{f(x+\Delta x)-f(x)}{J(x)\Delta x} \tag{22}\]  
where the numerator \(\rho\) is the decreasing value of the actual function, and the denominator is the decreasing value of the approximate model. If \(\rho\) is close to 1, then the approximation is good. If \(\rho\) is too small, meaning that the actual reduced value is far less than the approximate reduced value, then the approximate result is considered to be poor and the approximate range needs to be narrowed. On the contrary, when \(\rho\) is large, it means that the actual decline is larger than expected, and the approximate range can be enlarged. Because the temporal dynamic observation model of system evolution constructed is nonlinear and \(\mathrm{d}f/\mathrm{d}x\) is not easy to obtain, this paper intends to adopt an iterative method (if there is an extreme value, then convergence to approximation) to converge the approximation. The steps are shown in Algorithm 1. ```
1. Given an initial value \(x_{0}\), radius \(r\) and parameter k
2.for the k-th iteration, solving: \(\min\limits_{\Delta x_{k}}\frac{1}{2}||f(x_{k})+J(x_{k})\Delta x_{k}||^{2}\), s. t. \(||D\Delta x_{k}||_{2}\leq r\)
3. Compute \(\rho\)
4.if\(\rho>3/4\)
5.\(r=2r\)
6.elseif\(\rho<1/4\)
7.\(r=0.5r\)
8.\(x_{k+1}=x_{k}+\Delta x_{k}\)
9.if convergence
10.break
11.end
```  
**Algorithm 1** Main procedure of the iterative method  
where the limiting condition \(r\) is the radius of the trust region. In Equation (21), the incremental range is limited to a sphere of radius \(r\), which is seen as an ellipsoid after multiplying by \(D\). \(D\) is taken as a non-negative diagonal matrix, usually with the square root of the diagonal element \(J^{T}J\), and it is equivalent to directly constraining \(\Delta x\) in the ball. \[\min\limits_{\Delta x_{k}}\frac{1}{2}||f(x_{k})+J(x_{k})\Delta x_{k}||^{2}+ \frac{\lambda}{2}||D\Delta x||^{2} \tag{23}\]  
where \(\lambda\) is the Lagrange multiplier. Finally, this paper needs to obtain the gradient by solving the objective function (23). Since it is an optimization problem with inequality constraints, the Lagrange multiplier is used in this paper to transform the objective function into an unconstrained optimization problem. Additionally, then the target function is transformed. Let us expand out the square of the target function of (23). \[ \begin{array}{l}\frac{1}{2}\Big{|}\Big{|}f(x_{k})+J(x_{k})\Delta x_{k}\Big{|} \Big{|}^{2}+\frac{\lambda}{2}\Big{|}\Big{|}D\Delta x_{k}\Big{|}\Big{|}^{2}\\ =\frac{1}{2}(f(x_{k})+J(x_{k})\Delta x_{k})^{T}(f(x_{k})+J(x_{k})\Delta x_{k}) \\ +\frac{\lambda}{2}(D\Delta x_{k})^{T}(D\Delta x_{k})\\ =\frac{1}{2}(\Big{|}\Big{|}f(x_{k})\Big{|}_{2}^{2}+2f(x_{k})^{T}J(x_{k})\Delta x _{k}+\Delta{x_{k}}^{T}J(x_{k})^{T}J(x_{k})\Delta x_{k})\\ +\frac{\lambda}{2}(D^{T}\Delta x_{k}^{T}D\Delta x_{k})\end{array}  \tag{24}\]  
Then, solve the derivative of \(\Delta x_{k}\) in Equation (24) and set it to zero:  
\[2J(x_{k})^{T}f(x_{k})+2J(x_{k})^{T}J(x_{k})\Delta x_{k}+2\lambda D^{T}D\Delta x =0 \tag{25}\]  
The following equations are obtained:  
\[J(x_{k})^{T}J(x_{k})\Delta x_{k}+\lambda D^{T}D\Delta x_{k}=-J(x_{k})^{T}f(x_ {k}) \tag{26}\]  
Let \(J(x_{k})^{T}J(x_{k})=H\), the right-hand side of the equation be defined as \(g\), and the equation can be simplified as follows:  
\[(H+\lambda D^{T}D)\Delta x_{k}=g \tag{27}\]  
In the initial time step of the algorithm, the proposed PPPM method is initialized with the spectral clustering algorithm; that is, the initial estimation of community is generated at the time \(t=1\). The advantage of using the spectral clustering algorithm as the initialization algorithm here is that it can prevent the local search from falling into \(c^{t}\) poor local maximum in the initial time step. The main procedure of the proposed PPPM method can be shown in Algorithm 2.