# Temporal Label Walk for Community Detection and Tracking in Temporal Network
## 2 Our Method: Temporal Label Walk (TLW)
### Basic Idea  
In temporal networks, new nodes and edges are added in turn. If we use static method for community detection, we must mix the data streams in a time window to a snapshot so that each snapshot can be regarded as a static graph. In fact, there are two problems. First, how to select the time window. Snapshots in different time windows consist of different information. Second, how to mix data streams. To simply stack all edges or the weighted edges both can make result dissimilar. In fact, the intensity of interactions between two nodes depends on time in temporal networks. The result is stronger now than the past. The importance of nodes is also different due to different intensity of interactions. A natural idea is to divide communities according to the importance of nodes. Temporal walk defined by [PERSON] and [PERSON] in 2016 is a good tool to measure importance of nodes in temporal networks. They use temporal walk to make an extension of static PageRank [13]. A sequence of edges \(v_{1}\xrightarrow{t_{0}}v_{2}\xrightarrow{t_{1}}v_{3}\xrightarrow{t_{2}} \cdots\xrightarrow{t_{j-2}}v_{j}\) denotes a temporal walk from \(v_{1}\) to \(v_{j}\) where \(t_{i}\leq t_{i+1}\). B\(\grave{\text{e}}\)[PERSON] et al. also use temporal walk to extend static Katz centrality to temporal networks [14]. The effectiveness of temporal walks is verified in measuring the importance of nodes in temporal networks. In real networks, interactions within communities are dense but between communities they are sparse [1]. It is possible for temporal walks used to divide community structure in temporal network. However, there are some special cases that make it difficult to divide communities only by measuring the importance of nodes. Meanwhile, time is an important factor in temporal data. The information received by a node recently may be more crucial than the past. We give an example in Figure 3a,b, respectively.  
The importance of nodes from different communities may be the same. Our solution is to give each node a label value then compute it by temporal walks. In this way, label values between two communities are different and thus can be divided. As to how to divide communities according to label values, we use clustering methods because each node is represented by a vector. Please note that using clustering analysis for community detection has been already considered by many researchers and it is proved to be an effective approach. [PERSON] et al. propose a measure of similarities based on random walks to find the dense subgraphs of communities [15]. [PERSON] et al. evaluate the performance of repeated random walks in community detection of social networks [16]. [PERSON] et al. add a pre-processing step in which edges are weighted according to their centra  
Figure 2: Mixing all 113 edges appear on 87 nodes on 27 June 2014. It is easy to find that nodes 1713 and 3 interact more frequently with other nodes.  
topology and raise the accuracy of existing algorithms on real-life data sets [17]. In addition, they combine advantages of global approaches and local methods to propose a new clustering method [18]. [PERSON] et al. use clustering analysis to re-identify multiple addresses belonging to a same user for bitcoin user activity [19]. We apply this idea to temporal networks and more detail is described in Section 2.2.  
To summarize, we propose a streaming method for community detection in temporal networks. Label value is defined for each node and computed by temporal walk. The division of nodes is obtained by the clustering analysis of label values. The result of clustering division is the division of communities in networks.