# Dynamic Community Discovery Method Based on Phylogenetic Planted Partition in Temporal Networks
## 3 Materials  
### Formal Definition  
In this paper, a novel phylogenetic planted partition model is defined for temporal social networks by the following definitions:  
**Definition 1**. : _A social network can be represented by a graph, \(G\), on a set of nodes, \(V\), and a set of edges, \(E\). Nodes and edges are represented by an adjacency matrix \(A\), where \(\rho_{ij}=1\) represents the existence of an edge from node \(i\in V\) to node \(j\in V-\{i\}\), and \(\rho_{ij}=0\) represents the absence of an edge. This paper assumes the network is a directed graph, which is generally \(\rho_{ij}\
eq\rho_{ji}\) and has no self-loop, namely \(\rho_{ii}=0\)._  
**Definition 2**. : _The positive integer \(n\) represents the number of nodes, and \(\varepsilon=(\varepsilon_{1},\ldots,\varepsilon_{k})\) is the probability vector on \([k]=\{1,\ldots,k\}\) (\(k\) is the number of network communities). \(W\) is a symmetric matrix whose element is \(k\times k\) between [0,1]. \((X,G)\) is defined under the Stochastic Block-Mode (SBM) \(SBM(n,\theta,W)\). \(X\) is a \(n\) dimensional random vector; it is independent and identically distributed under \(\varepsilon\). Let the community set \(\mathrm{C}_{r}=\mathrm{C}_{r}(X)=\{C_{1},\ldots,C_{k}\},r\in[k]\) denotes the division of \(V\) into \(k\) communities. In this paper, we use the symbols \(p\) and \(q\) to indicate two generic communities, \(c_{i}\) and \(c_{j}\), where \(i\) and \(j\) are the two nodes of a simple graph \(G\) of \(n\) vertices, which respectively belong to \(c_{i}\) (i.e., \(i\in p\)) and \(c_{j}\) (i.e., \(j\in q\)) at time \(t\). Nodes \(i\) and \(j\) are connected according to a probability \(\varepsilon_{c_{i}^{\dagger}c_{j}^{\dagger}}\), independently from the other node pairs. Therefore, the probability distribution of \((X,G)\)[50] is as follows, where \(G=(V,E)\)._  
\[\Pr\{X=x\} =\prod_{i=1}^{n}\varepsilon_{c_{i}}=\prod_{r=1}^{k}\varepsilon_{ r}|^{C_{r}(x)|} \tag{6}\] \[\Pr\{E=y|X=x\} =\prod_{1\leq i<j\leq n}\varepsilon_{c_{i}c_{j}}^{y_{ij}}(1- \varepsilon_{c_{i}c_{j}})^{1-y_{ij}}\] (7) \[=\prod_{1\leq p<q\leq k}\varepsilon_{p,q}^{N_{pq}(x,y)}(1- \varepsilon_{p,q})^{N_{pq}^{c}(x,y)} \tag{8}\]  
_where \(N_{pq}(x,y)\) represents the observed value of the number of edges in the partition, which can be expressed as \(N_{pq}(x,y)=\sum\limits_{c_{i}=p}\sum\limits_{c_{j}=q}y_{ij}^{t};N_{pq}^{c}(x,y)\) represents the probability value of the number of edges in the partition, which can be expressed as follows._  
\[N_{pq}^{c}(x,y)= \begin{cases}|p|\big{(}|p|-1\big{)}/2-N_{pp}(x,y)&p=q\\ |p|\big{|}q|-N_{pq}(x,y)&p\
eq q\end{cases}  \tag{9}\] \begin{table}
\begin{tabular}{c c c c c} \hline
**Ref.** & **Year** & **Approach** & **Theory** & **Dataset** \\ \hline
[42] & 2015 & Maximum Likelihood Estimation & Consistency & MIT Reality Mining \\
[43] & 2015 & Kalman Filtering + Local Search & / & Facebook wall posts \\
[44] & 2016 & Expectation Maximization & / & Internet AS graphs, \\
[45] & 2016 & Expectation Maximization & Detectability thresholds & Synthetic \\
[46] & 2017 & Expectation Maximization & Detectability thresholds & Synthetic \\
[47] & 2017 & Time-lag corrected & Convergence rates & Synthetic \\
[48] & 2018 & Aggregating SBM subroutines + MLE & Correctness/Stage-wise & Enron emails, Facebook \\  & & & convergence rates & friendships \\
[49] & 2020 & Exhaustive grid search & Convergence rates & Synthetic \\ Our work & 2022 & Graph-based optimization & Convergence rates & MIT Reality Mining, \\  & & & & Enron emails \\ \hline \end{tabular}
\end{table} 
Table 1: Comparison of our work with previous model literatures. Equation (8) can be rewritten by:  
\[\Pr\{E=y|X=x\}=\exp\{\sum_{p=1}^{k}\sum_{q=1}^{k}[N_{pq}(x,y)\log\epsilon_{p,q}+N _{pq}^{c}(x,y)\log(1-\epsilon_{p,q})]\} \tag{10}\]  
**Definition 3**. : _Define an evolutionary sequence of discrete time steps for social network (dynamic Bayesian network); the nodes and edges may appear or disappear with time.