TY - JOUR
T1 - Periodic Communities Mining in Temporal Networks
T2 - Concepts and Algorithms
AU - Qin, Hongchao
AU - Li, Rong Hua
AU - Yuan, Ye
AU - Wang, Guoren
AU - Yang, Weihua
AU - Qin, Lu
N1 - Publisher Copyright:
© 1989-2012 IEEE.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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 σ-periodic k-core and σ-periodic k-clique, that represent periodic communities in temporal networks. Specifically, a σ-periodic k-core (or σ-periodic k-clique) is a k-core (or clique with size larger than k) that appears at least σ 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 σ-periodic k-core, a Bron-Kerbosch style algorithm to enumerate all maximal σ-periodic k-cliques, and a branch-and-bound style algorithm to find the maximum σ-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
AB - 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 σ-periodic k-core and σ-periodic k-clique, that represent periodic communities in temporal networks. Specifically, a σ-periodic k-core (or σ-periodic k-clique) is a k-core (or clique with size larger than k) that appears at least σ 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 σ-periodic k-core, a Bron-Kerbosch style algorithm to enumerate all maximal σ-periodic k-cliques, and a branch-and-bound style algorithm to find the maximum σ-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
KW - Periodic community
KW - k-core
KW - maximal clique
KW - maximum clique
KW - temporal networks
UR - http://www.scopus.com/inward/record.url?scp=85134166624&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.3028025
DO - 10.1109/TKDE.2020.3028025
M3 - Article
AN - SCOPUS:85134166624
SN - 1041-4347
VL - 34
SP - 3927
EP - 3945
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 8
ER -