TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network
Temporal network is a basic tool for representing complex systems, such as communication networks and social networks; besides the temporal motif (TM) plays an important role in the analysis of temporal networks. Without considering the temporal information, most existing motif mining methods focus...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8691398/ |
| _version_ | 1818641517022019584 |
|---|---|
| author | Xiaoli Sun Yusong Tan Qingbo Wu Baozi Chen Changxiang Shen |
| author_facet | Xiaoli Sun Yusong Tan Qingbo Wu Baozi Chen Changxiang Shen |
| author_sort | Xiaoli Sun |
| collection | DOAJ |
| description | Temporal network is a basic tool for representing complex systems, such as communication networks and social networks; besides the temporal motif (TM) plays an important role in the analysis of temporal networks. Without considering the temporal information, most existing motif mining methods focus on static networks and are not suitable for mining temporal motifs. In this paper, we study the problem of temporal motif mining for the temporal network. To formulate the problem, we define the temporal motif as a frequently connected subgraph that has a similar sequence of information flows. Moreover, an efficient algorithm called TM-Miner is proposed. Based on the time first search (TFS) algorithm, the TM-Miner builds a canonical labeling system that uses a new lexicographic order and maps the temporal graph to the unique minimum TFS code. By utilizing the canonical labeling system, the computational cost of temporal graph isomorphism is reduced and the efficiency of the algorithm is improved. Finally, we evaluate the performance of the TM-Miner algorithm in real datasets and extensive experiments demonstrate that it is faster than the existing algorithms. |
| first_indexed | 2024-12-16T23:28:25Z |
| format | Article |
| id | doaj.art-bafd60e5ddb3443a8aaa4d5a3eb49871 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-16T23:28:25Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-bafd60e5ddb3443a8aaa4d5a3eb498712022-12-21T22:11:56ZengIEEEIEEE Access2169-35362019-01-017497784978910.1109/ACCESS.2019.29111818691398TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal NetworkXiaoli Sun0https://orcid.org/0000-0003-0191-3410Yusong Tan1Qingbo Wu2Baozi Chen3Changxiang Shen4College of Computer, National University of Defense Technology, Changsha, ChinaCollege of Computer, National University of Defense Technology, Changsha, ChinaCollege of Computer, National University of Defense Technology, Changsha, ChinaCollege of Computer, National University of Defense Technology, Changsha, ChinaCollege of Computer, National University of Defense Technology, Changsha, ChinaTemporal network is a basic tool for representing complex systems, such as communication networks and social networks; besides the temporal motif (TM) plays an important role in the analysis of temporal networks. Without considering the temporal information, most existing motif mining methods focus on static networks and are not suitable for mining temporal motifs. In this paper, we study the problem of temporal motif mining for the temporal network. To formulate the problem, we define the temporal motif as a frequently connected subgraph that has a similar sequence of information flows. Moreover, an efficient algorithm called TM-Miner is proposed. Based on the time first search (TFS) algorithm, the TM-Miner builds a canonical labeling system that uses a new lexicographic order and maps the temporal graph to the unique minimum TFS code. By utilizing the canonical labeling system, the computational cost of temporal graph isomorphism is reduced and the efficiency of the algorithm is improved. Finally, we evaluate the performance of the TM-Miner algorithm in real datasets and extensive experiments demonstrate that it is faster than the existing algorithms.https://ieeexplore.ieee.org/document/8691398/Temporal networktemporal motif (TM)time first search (TFS)TFS codeTM-Miner |
| spellingShingle | Xiaoli Sun Yusong Tan Qingbo Wu Baozi Chen Changxiang Shen TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network IEEE Access Temporal network temporal motif (TM) time first search (TFS) TFS code TM-Miner |
| title | TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network |
| title_full | TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network |
| title_fullStr | TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network |
| title_full_unstemmed | TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network |
| title_short | TM-Miner: TFS-Based Algorithm for Mining Temporal Motifs in Large Temporal Network |
| title_sort | tm miner tfs based algorithm for mining temporal motifs in large temporal network |
| topic | Temporal network temporal motif (TM) time first search (TFS) TFS code TM-Miner |
| url | https://ieeexplore.ieee.org/document/8691398/ |
| work_keys_str_mv | AT xiaolisun tmminertfsbasedalgorithmforminingtemporalmotifsinlargetemporalnetwork AT yusongtan tmminertfsbasedalgorithmforminingtemporalmotifsinlargetemporalnetwork AT qingbowu tmminertfsbasedalgorithmforminingtemporalmotifsinlargetemporalnetwork AT baozichen tmminertfsbasedalgorithmforminingtemporalmotifsinlargetemporalnetwork AT changxiangshen tmminertfsbasedalgorithmforminingtemporalmotifsinlargetemporalnetwork |