Periodic Communities Mining in Temporal Networks: Concepts and Algorithms
| Autor: | Ye Yuan, Weihua Yang, Guoren Wang, Lu Qin, Rong-Hua Li, Hongchao Qin |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Clique
Computer science 02 engineering and technology Clique (graph theory) Graph Electronic mail Computer Science Applications Set (abstract data type) Computational Theory and Mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 08 Information and Computing Sciences Enhanced Data Rates for GSM Evolution Periodic graph (geometry) Algorithm Information Systems |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering. 34:3927-3945 |
| ISSN: | 2326-3865 1041-4347 |
| DOI: | 10.1109/tkde.2020.3028025 |
| Popis: | 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. 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 algorith |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|