大規模時間グラフのためのスケーラブルなモチーフ計数【JST・京大機械翻訳】

Gao Zhongqiang; Cheng Chuanqi; Yu Yanwei; Cao Lei; Huang Chao; Dong Junyu

プレプリント

J-GLOBAL ID：202202209324961020 整理番号：22P0335447

大規模時間グラフのためのスケーラブルなモチーフ計数【JST・京大機械翻訳】

Scalable Motif Counting for Large-scale Temporal Graphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (6件)： , , , , ,
資料名：
発行年： 2022年04月20日プレプリントサーバーでの情報更新日： 2022年04月20日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

時間グラフ解析における1つの基本的問題は,異常検出,構造予測,およびネットワーク表現学習のような広範囲の実世界アプリケーションに利益を与える,小接続部分グラフパターン(すなわち,モチーフ)の発生を数えることである。しかし,時間的モチーフを厳密に行うことは,それらの重い計算コストまたは並列性の固有不備性のため,大規模時間グラフデータにスケーラブルでない。本研究では,大規模時間グラフにおける時間的モチーフを正確に計数するためのスケーラブル並列フレームワークを提案した。まず,それらの明確な特性に基づく時間的モチーフを分類し,次に,各カテゴリのモチーフインスタンスを正確に計数するための効率的な戦略を提供するカスタム化アルゴリズムを設計した。さらに,著者らのコンパクトなデータ構造,すなわち3重と4重計数器は,エッジ情報とエッジ間の関係に従って,各カテゴリの時間的モチーフインスタンスを直接同定することを可能にし,従って,計数効率を著しく改善する。提案した計数アルゴリズムに基づいて,ノード間およびノード内並列戦略の両方を特徴とする階層的並列フレームワークを設計し,同時に全ての時間モチーフを同時に計数するために,現代のCPUのマルチスレッド能力を完全に利用した。16の実世界の時間グラフデータセットに関する広範な実験は,時間モチーフ計数のための提案フレームワークの優位性と能力を実証し,最先端の方法と比較して538×高速化を達成した。この方法のソースコードは,https://github.com/steven ccq/FAST temporal motifで利用可能である。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , , 【Automatic Indexing@JST】

人工知能 , 数値計算 , ディジタル計算機方式一般 , 分子・遺伝情報処理 , 通信網

, , ,

前のページに戻る