大規模複雑グラフ上の発火グループ情報活用のための高速高精度アルゴリズムの開発

点击翻译按钮获取中文摘要

【コンパクトでスケーラブルな全距離近傍関数スケッチ(KDD'16採択)】グラフに対するスケッチデータ構造として， All-Distances Sketches (ADS) は，様々な指標の推定を，理論的保証付きで可能にするため，注目されている．特に，本研究課題としては，ADS は group closeness centrality の推定も行うことができる点が重要である．理論的には非常に優れた性質を持っているため，実用化が強く期待される技術だが，実用的には，定数項の影響でデータ構造のサイズが非常に大きくなってしまい，大規模なグラフで使うことができないことが分かってきた．そこで，本研究では，ADS に潜む冗長性に注目し，冗長性を取り除いたスケッチデータ構造である Sketch Retrieval Shortcuts (SRS) を提案する．SRS は ADS から 10 倍以上サイズが小さいが，SRS を計算しておけば，瞬時に ADS と全く同じ精度での任意の推定を行うことができる．また，group closeness centrality 推定のために必要な combined ADS も，SRS より高速に復元できる．【Temporal Network におけるシュタイナー木の高速計算アルゴリズム(NDA'16採択)】辺に出現・消滅の時刻がついたネットワークを Temporal Network と呼ぶ．Temporal Network 上の全域木問題の拡張として，発火頂点集合の関係を時系列を考慮し表現するための定式化としてのシュタイナー木問題を定義し，それに対する高速かつ厳密なアルゴリズムを与えた．