Mining periodic cliques in temporal networks

Publication Type:
Conference Proceeding
Proceedings - International Conference on Data Engineering, 2019, 2019-April pp. 1130 - 1141
Issue Date:
Filename Description Size
Mining Periodic Cliques in Temporal Networks.pdfPublished version514.46 kB
Adobe PDF
Full metadata record
© 2019 IEEE. 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.
Please use this identifier to cite or link to this item: