# Temporal Label Walk for Community Detection and Tracking in Temporal Network
## 1 Introduction  
The concept of community defined by [PERSON] and Girvan is widely accepted and used [1]. Community detection is a significant task and of great value in practical applications. For sales websites, discovering consumers of different products can help website managers purchase selectively; for social networks, it will be easier to recommend friends to users if we can detect communities sharing common interests. Research on community detection falls into two categories: static methods and temporal methods. Some classic methods such as Kernighan-Lin [2] based on graph cut and Label Propagation Algorithm (LPA) are static methods [3]. The famous Girvan and Newman (GN) algorithm [1] is also a static method. The static methods divide a network into different communities based on static graph where the relationship between nodes and edges will not change. However, increasing numbers of real data sets cannot be denoted by a static graph since edges and nodes are changing constantly. These data sets are called temporal data and the networks consisting of temporal data are called temporal networks. Temporal approaches are proposed to deal with temporal networks. Structure-based methods and incremental analysis are the two most common methods used for community detection in a temporal network. Structure-based methods mix temporal data in the time window \(\Delta t\) to a graph snapshot \(G_{i}\) and the temporal networks can be viewed as a sequence \(G_{1}\), \(G_{2}\),..., \(G_{s}\) where each \(G_{i}\) corresponds to the configuration of the graph in the \(i\)th time window [4]. For any \(G_{i}\), it is a static network and the traditional static algorithms can be used for community detection. Meanwhile, the validation measurements used in static networks are making for temporal networks as well. If the ground-truth communities are known, Normalized Mutual Information(NMI) [5] is often used. In addition, Modularity [1] is often used while ground-truth is unknown. Determining the size of window is a problem here. If \(\Delta t\) is too small, few nodes and edges are included in a snapshot. As a result, it is hard to find any community structure. On the contrary, the evolution of communities cannot be tracked if \(\Delta t\) is too large. To avoid selecting appropriate \(\Delta t\), incremental analysis adds vertexes or edges to the network one by one with the transmission of temporal data stream. Much research has used incremental analysis for community detection in temporal networks. [PERSON] et al. divide communities according to permanence index [6]. [PERSON] et al. maximize permanence to detect communities [7]. [PERSON] et al. focus on local interact for community detection [8]. [PERSON] et al. also use local information to find seed nodes [9]. Several pieces of incremental analysis detecting communities detection are based on label propagation [10; 11]. Incremental analysis requires that community structure should be known in the beginning and the structure of networks change stably. However, community structure is unknown in most real data sets, and stability of evolution cannot be guaranteed either. We show the form of temporal data of two methods, and the real graph sequence in Figure 1. Real data set \(Students\)[12] consists of communications in a student organization. The community structure at certain nodes can obviously be observed by compressing one day's interactions together in Figure 2.  
This paper proposes a streaming method to detect and track communities without any fixed \(\Delta t\). Our main contribution is two-fold:  
* Propose a new method called Temporal Label Walk (TLW) to detect community structure in temporal networks without time window. Our approach transforms the community detection in network into a clustering analysis in vector space where no prior about the community structure is required. TLW can also maintain modularity at a reasonable level by combining time information.