# Temporal Label Walk for Community Detection and Tracking in Temporal Network
## 2 Our Method: Temporal Label Walk (TLW)
### Mathematical Definition  
According to the description in Section 2.1, our method is based on two assumptions:  
* Data sets are in the form of data streams,
* Interactions within communities are more frequent than those between communities. Consider a directed graph \(G_{t}=(V,E_{t})\) where \(V\) is the set of all the nodes and \(E_{t}\) is the set of edges at time \(t\). We denote \(T=\{t_{0},t_{1},\cdots,t_{i},\cdots\}\) the set of time sequence when new edges appear in the data streams. Let \(X_{u}(t)\in\mathbb{R}^{|V|}\) denote the label value of node \(u\) at time \(t\). If edge \(v\to u\) appears at time \(t_{i+1}\in T\), now we describe how to compute \(X_{u}(t_{i+1})\). The variations of label value of \(u\) is two-fold:  
* All temporal walks that end in \(v\) at \(t_{i}\), a new temporal walk starts from \(v\) and ends in \(u\) appears at \(t_{i+1}\). The variation of this new temporal walk is: \[\Delta_{1}=X_{v}(t_{i})\cdot\varphi(t_{i+1}-t_{i}),\] (1) where \(\varphi(\tau)=\beta\cdot e^{-c\tau}\) is an exponential decay function, \(\beta\) is a constant and \(\tau=t_{i+1}-t_{i}\). We use \(\varphi\) to represent that interactions at \(t_{i+1}\) are more important than those at \(t_{i}\). Figure 3: Two different situations in temporal networks. (**a**) shows that two communities A and B share the same information exchange within community, the corresponding nodes are of the same importance but belong to different communities. (**b**) shows that nodes \(u\) and \(v\) are in different communities in the beginning and \(v\) sends a message to \(u\) at time \(t_{i}\). If \(v\) sends a message to \(u\) again at \(t_{i+1}\), as shown in (**c**), \(u\) will have a higher probability of belonging to B at \(t_{i+2}\) than those nodes inside A send a message to \(u\) at \(t_{i+1}\), which is illustrated in (**d**). * To maintain the timeliness of information, we define an enhancement function as another variation: \[E_{v}=\alpha\cdot e_{v},\] (2) where \(\alpha\in\mathbb{R}\) and \(e_{v}\) is a unit vector with the \(v\)th element 1 and the rests 0. Note here \(v\) is the index of node \(v\) in set \(V_{t}\). Label value variation of \(u\) is: \[\Delta=E_{v}+\Delta_{1}.\] (3) \(\Delta\) is the variation that \(u\) only interacts with \(v\). Denoting \(S_{u}\) by the set of all nodes that send messages to \(u\) at \(t_{i+1}\), variations of \(u\) is: \[\Delta=E_{v}+\sum_{s\in S_{u}}(E_{s}+X_{s}(t_{i})\cdot\varphi(t_{i+1}-t_{i})).\] (4) At \(t_{i+1}\), the label value of \(u\) is also affected by \(\varphi(\tau)\). We can compute \(X_{u}(t_{i+1})\) by: \[X_{u}(t_{i+1})=X_{u}(t_{i})\cdot\varphi(t_{i+1}-t_{i})+\sum_{s\in S_{u}}(E_{s} +X_{s}(t_{i})\cdot\varphi(t_{i+1}-t_{i})).\] (5) Set the label value \(X_{u}(t_{0})=e_{u}\). Then take the normalized vector \(\frac{X_{u}(t_{i+1})}{\|X_{u}(t_{i+1})\|_{2}^{2}}\) of \(X_{u}(t_{i+1})\) for the next iteration if \(S_{s}\
eq\varnothing\) to avoid the rapid growth of label value. To update label value of \(u\) at \(t_{i+1}\), the complete algorithm is described as follows: \[Step1:X_{u}(t_{0})=e_{u},\] \[Step2:X_{u}(t_{i+1})=X_{u}(t_{i})\cdot\beta\cdot e^{-c(t_{i+1}-t_{i})}+ \sum_{v\in S_{u}}(\alpha\cdot e_{v}+X_{v}(t_{i})\cdot\beta\cdot e^{-c(t_{i+1} -t_{i})}),\] \[Step3:X_{u}(t_{i+1}):=\frac{X_{u}(t_{i+1})}{\|X_{u}(t_{i+1})\|_{2}},\] \[i:=i+1,\] Figure 3:0 (6) Computing label value can be regarded as a mapping \(f:G_{i}\rightarrow\mathbb{R}^{|V|\times|V|}\), where \(G_{i}\) is a snapshot at \(t_{i}\) and \(f(G_{i})=(X_{1}(t_{i}),X_{2}(t_{i}),\cdots,X_{|V|}(t_{i}))\in\mathbb{R}^{|V| \times|V|}\). Community detection problem in temporal network \(G_{t}\) can therefore be transformed to clustering analysis in high-dimensional vector space \(\mathbb{R}^{|V|\times|V|}\). We choose several widely used clustering methods for TLW. Affinity Propagation(AP) [20], Density-Based Spatial Clustering of Applications with Noise(DBSCAN) [21] and Mini Batch K-means are compared in the following tests. AP and DBSCAN are used when that the number of communities is unknown.