Mining Periodic Cliques in Temporal Networks

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 a problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose a novel model, called maximal σ-periodic k-clique, that represents a periodic community in temporal networks. Specifically, a maximal σ-periodic k-clique is a clique with size larger than k that appears at least σ times periodically in the temporal graph. We show that the problem of enumerating all those periodic cliques is NP-hard. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we present an efficient enumeration algorithm to enumerate all maximal σ-periodic k-cliques in the reduced graph. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

I. Introduction

In many real-life networks, such as communication networks, scientific collaboration networks, and social networks, the links are often associated with temporal information. For example, in a face-to-face contact network [1], [2], each edge (u, v, t) denotes a contact between two individuals u and v at time t. In an email communication network, each email contains a sender and a receiver, as well as the time when the email was sent. In a scientific collaboration network (e.g., DBLP), each edge (u, v, t) represents that two authors u and v coauthored a paper at time t. The networks that involve temporal information are typically termed as temporal networks [3]–[5].