Periodic Communities Mining in Temporal Networks Concepts and Algorithms
Abstract : Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities.In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including s-periodic k-core and s –periodic k-clique, that represent periodic communities in temporal networks.Specifically, as- periodic k-core(ors-periodic k-clique) is a k-core (or clique with size larger thank) that appears at least s times periodically in the temporal graph. The problem of searching periodic core is efficient but the resulting communities may be not enough cohesive; the problem of enumerating all periodic cliques is not efficient (NP-hard) but the resulting communities are very cohesive. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph.Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph.Subsequently, we propose a decomposition algorithm to search maximal s-periodic k-core, a Bron-Kerbosch style algorithm to enumerate all maxi mals-periodic k-cliques, and a branch-and-bound style algorithm to find the maxi mum s-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
? We conduct comprehensive experiments using 9 real-life temporal graphs to evaluate the proposed algorithm.
? The results indicate that our algorithms significantly outperform the baselines in terms of the com-munity quality.
? We also perform a case study on the Enron dataset.
? The results demonstrate that our approach can identify many meaningful and interesting bursting communities that cannot be found by the other methods.
? In addition, we also evaluate the efficiency of the proposed algorithms, and the results demonstrate the high efficiency of our algorithms.
? In this paper, we investigate a novel data mining problem for temporal networks : periodic community mining, or the detection of all communities that occur at regular time intervals, and show that the proposed technique can be applied to discover the inherent periodicity of communities in a temporal network.
? Mining the periodic community patterns could be very useful for many practical applications, two of which are listed as follows.
? The problem of mining communities on temporal graphs has attracted much attention due to numerous applications.
? 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 datasets 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
? we conduct extensive experiments to eval-uate the efficiency and effectiveness of the proposed algorithms.
? In our experiments, we implement various algo-rithms for comparison.•MPCO-KCis a baseline algorithm integrated with k-corereduction techniques.
? It first computesPTuandEPTuvfor nodes and edges inKCoreofGusing Algorithm 2,and then constructs a transformed graph ~G.
? It uses thecore decomposition algorithm to searchMPCoreon ~G.•MPCO-NCdenotes the MPCO-KC algorithm integratedwith thePNClusterreduction rule.
|