PROJECT TITLE :

Periodic Communities Mining in Temporal Networks Concepts and Algorithms

ABSTRACT:

The occurrence of the phenomenon known as periodicity in social interactions within temporal networks is fairly common. Understanding the behaviors of periodic groups in temporal networks requires mining periodic communities, which are essential to this understanding. Unfortunately, the vast majority of previous studies for community mining in temporal networks ignored 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. Specifically, we look at the problem using a temporal network that has been constructed using graph theory. New representations of periodic communities in temporal networks, such as the -periodic k-core and the -periodic k-clique, have been proposed thanks to the work done by our team. To be more specific, a -periodic k-core (or -periodic k-clique) is a k-core (or clique with size greater than k) that appears at least times periodically in the temporal graph. This type of k-core is also known as a -periodic k-clique. The problem of enumerating all periodic cliques is not efficient (NP-hard), but the communities that are produced as a result are very cohesive. The problem of searching for the periodic core is efficient, but the communities that are produced as a result may not be cohesive enough. In order to efficiently compute all of them, we first develop two efficient graph reduction techniques that significantly prune the temporal graph. This allows us to save a significant amount of time. Then, we prove that mining the periodic communities in the temporal graph is equivalent to mining communities in the transformed graph by transforming the temporal graph into a static graph. Following that, we propose an algorithm to search for the maximal -periodic k-core, an algorithm in the style of Bron-Kerbosch to enumerate all maximal -periodic k-cliques, and an algorithm in the branch-and-bound style to locate the maximum -periodic clique. The efficacy, scalability, and efficiency of our algorithms have been validated by the findings of in-depth experiments conducted on five different datasets taken from real-world applications.