疑似独立集合制約と正規化カットを用いたグラフの構造比較
スポンサーリンク
概要
- 論文の詳細を見る
ソーシャルネットワーク等において時間の経過や地域による差を調べるために,ノーマライズカットを用いたグラフの比較法を提案する.グラフを比較する際,モジュラリティや k-Plex などで差異を示す頂点集合を検出する方法が提案されているが,サイズの大きな頂点集合の検出には適していない.本稿では,比較対象の 2 つのグラフのうち,一方のグラフに対しては疑似独立集合 (補グラフにおける k-Plex) 制約を課す.他方,もう一つのグラフに対しては,正規化ラプラシアンによって得られる距離空間において局所密度を考慮した形でグラフを形成し,そのグラフにおいてクリークをなすことを要請する.k-Plex もクリークも共に単調性を持つことから,2つの制約を同時に満たす解頂点集合を高速に列挙できるエンジンをクリーク全列挙エンジンに習って設計できることを示す.
- 2013-02-20
著者
-
富田 悦次
Department Of Commucations And Systems Engineering The University Of Electro-communications
-
富田 悦次
電気通信大学|中央大学研究開発機構
関連論文
- 最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 準同型写像によって拡張されたある言語クラスに対する正例からの極限同定
- 実時間空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定(オートマトン・言語理論)
- 正則言語のある部分クラスに対する正の例からの多項式時間極限同定
- 最大クリーク抽出アルゴリズムの共有メモリ型並列計算機上での並列化
- 極大クリーク全列挙アルゴリズムを用いた企業コミュニティ理解
- 極大クリーク全列挙アルゴリズムを用いた企業コミュニティ理解
- ある種の有限状態変換器に対する多項式時間極限同定
- 実時間空スタック受理式決定性限定ワンカウンター変換器の多項式時間等価性判定アルゴリズム
- ε-推移を許したある決定性プッシュダウン変換器対の等価性判定(オートマトン・言語理論)
- ハイパーグラフを対象とした最大クリーク抽出の分枝限定アルゴリズム(セッション6)
- クラスタリングとBoostingを用いた高速、高精度な映像自己診断方式の提案
- 極大クリーク全列挙アルゴリズムCLIQUESを基にした極大2部クリーク全列挙アルゴリズム(セッション4)
- 極大クリーク全列挙アルゴリズムCLIQUESを基にした極大2部クリーク全列挙アルゴリズム(セッション4)
- 極大クリーク全列挙アルゴリズムCLIQUESを基にした極大2部クリーク全列挙アルゴリズム
- 最大クリーク抽出のより高速な分枝限定アルゴリズム
- ε-推移を許したある決定性プッシュダウン変換機器対の等価性判定アルゴリズム(セッション4)
- 極大クリーク全列挙アルゴリズムCLIQUESを基にした極大2部クリーク全列挙アルゴリズム
- サイズの大きな極大クリークの効率的列挙アルゴリズム(セッション3)
- 最大クリーク抽出アルゴリズムの効率化と実験的評価・解析(セッション3)
- 最大クリ-ク抽出の効率化手法とその実験的評価
- 正の例から極限同定可能な言語クラスを拡張する統一的アルゴリズム
- 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
- 単純でより高速な最大クリーク抽出アルゴリズム
- 制約付きプロファイルアライメント(文字列アルゴリズム)
- グラフ彩色問題における確率アルゴリズムとハイブリッドアルゴリズム
- グラフの近似彩色を行う確率アルゴリズム
- 質問と正の反例による正則言語の多項式時間学習 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 質問と初期情報による文法推論に関する一考察
- 構造反例付き等価性質問を用いた単純決定性言語の多項式時間MAT学習
- 単純決定性言語の質問による多項式時間学習について
- 単純決定性言語のある部分族に対する多項式時間MAT学習
- 構造反例付き等価性質問を用いた単純決定性言語の多項式時間MAT学習
- 質問と反例による単純決定性言語の多項式時間学習を可能とさせる十分条件
- 最大クリークを抽出するO(2^)-時間の多項式領域アルゴリズム
- 最大クリークを抽出する時間計算量O(2^)の多項式領域アルゴリズム
- 最大クリークを抽出する単純なアルゴリズムの最大次数4のグラフにおける計算量
- The Extended Equivalence Problem for a Class WSP of Non-Real-Time DPDA's : The Detailed Proofs
- The Extended Equivalence Problem for a Class WSP of Non-Real-Time DPDA′s--The Detailed Proofs
- ある非実時間決定性プッシュダウン変換器対の等価性判定(技術談話室)
- 分岐アルゴリズムによるDPDAの拡張等価性判定の一結果(技術談話室)
- D-1-3 巡回セールスマン問題に対する確率及び遺伝的ハイブリッドアルゴリズムとその実験的評価
- 最大クリーク抽出に基づく向きの変化に依存しない人物の顔検出法
- NetMCQ: a distributed exact maximum clique solver (数理モデル化と問題解決 バイオ情報学)
- 新しい計算パラダイム
- 節点重み最大クリーク抽出アルゴリズムと実験的評価
- 節点重み最大クリーク抽出に基づく量子回路の深さ最小化 (計算機科学基礎理論の新展開)
- 節点重み最大クリーク抽出アルゴリズム (計算機科学基礎理論の新展開)
- 最大クリーク抽出に基づく画像からの対象検出(クリーク問題と応用)
- 新たな手法に基づく最大クリーク抽出の効率化
- 最大クリーク問題の多項式時間的可解性の更なる改良結果 (コンピュテーション)
- 正の例から極限同定可能な言語クラスの統一的拡張手法 (小特集「学習と発見の計算理論」セッション)
- 最大クリーク問題の多項式時間的可解性の新たな結果
- 極大クリーク全列挙アルゴリズムの実験的比較評価(アルゴリズム一般)
- LA-007 最大クリーク抽出のより高速なアルゴリズム(A. モデル・アルゴリズム・プログラミング)
- 空スタック受理式決定性1カウンタオートマトンのある部分クラスに対する正の例からの多項式時間極眼同定
- 最大クリーク抽出アルゴリズムの高速化と解析・評価
- あるノイズモデルにおけるブール関数学習について
- 最小支配集合問題の近似解抽出アルゴリズム(アルゴリズム一般)
- 最小支配集合問題の近似解抽出アルゴリズム
- [電子情報通信学会フェロー受賞記念講演]オートマトン・言語理論・学習理論と組合せ最適化の研究及び教育
- オートマトン・言語理論・学習理論と組合せ最適化の研究及び教育
- 最大クリークを抽出するより効率的な分枝限定アルゴリズム
- 大局的に構造を取らない配列集合の抽出方法
- 「最大クリーク問題の近似解法に関するコメント」について
- 近似最大クリークを抽出する確率アルゴリズムとその実験的評価
- 実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 質問および代表的な記号列集合を用いた単純決定性言語の多項式時間学習
- 最大クリーク問題の多項式時間的可解性について (計算機科学とアルゴリズムの数理的基礎とその応用)
- 枝重み最大クリーク抽出アルゴリズムと実験的評価(クリーク問題と応用)
- ある種のカウンタに対する正の例からの多項式時間極限同定
- 最大クリーク問題の多項式時間的可解性の更なる改良結果
- 巡回セールスマン問題に対する確率・遺伝的ハイブリッドアルゴリズム
- リカレントネットワークを用いた連続音声認識
- 近似最大クリ-クを抽出する多項式時間アルゴリズムとその実験的評価
- 組合せ最適化手法によるシュードノット構造を含んだRNAの二次構造予測
- 最大重みクリーク抽出アルゴリズムのRNAの二次構造予測への適用
- 最大重みクリークの近似抽出解法によるRNAの二次構造予測
- 最大クリーク抽出アルゴリズムの実験的評価(クリーク問題と応用)
- 正則言語の部分クラスに対する正の例からの多項式時間極限同定
- グラフ彩色問題の厳密解アルゴリズム
- 分枝限定法を用いた最大クリーク抽出アルゴリズムの効率化
- 正則言語のある部分クラスに対する正の例からの多項式時間極限同定
- 確率アルゴリズムに基づいた支配集合問題の近似解法
- 最大重みクリークの効率的抽出アルゴリズムとその評価
- 最大クリーク抽出アルゴリズムの効率化とその評価
- Dominating Set問題に対する分枝限定アルゴリズムとその実験的評価
- 最大重みクリーク抽出アルゴリズムの効率化
- 正則言語のある部分族に対する正の例からの多項式時間極限同定
- 単純決定性プッシュダウンオ-トマトンの等価性判定を行う直接的分岐アルゴリズム
- 諸受理方式による決定性カウンタの言語クラスについて
- 整数重みグラフの最大重みクリーク抽出アルゴリズム
- 最大クリークを抽出する単純で効率的な分枝限定アルゴリズムと実験的評価
- 近似彩色を用いた単純な最大重みクリーク抽出アルゴリズム
- 最大クリークを抽出する単純で効率的な分枝限定手法
- 最大クリーク問題の多項式時間的可解性の更なる改良結果(情報・システム基礎)
- 最大クリーク問題の多項式時間的可解性の拡張
- 最大クリーク問題の多項式時間的可解性の拡張の改良 (Theoretical Foundations of Computing)
- 最大クリーク問題の多項式時間的可解性の拡張(情報・システム基礎)
- 疑似独立集合制約と正規化カットを用いたグラフの構造比較