論文の概要: Jaccard-constrained dense subgraph discovery

• arxiv url: http://arxiv.org/abs/2308.15936v1
• Date: Wed, 30 Aug 2023 10:33:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-31 13:44:45.001308
• Title: Jaccard-constrained dense subgraph discovery
• Title（参考訳）: ジャカード制約された高密度サブグラフ発見
• Authors: Chamalee Wickrama Arachchi and Nikolaj Tatti
• Abstract要約: 大きい対のジャカード類似係数を持つ高密度部分グラフを探索する。 我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。
• 参考スコア（独自算出の注目度）: 2.4511852052357628
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding dense subgraphs is a core problem in graph mining with many applications in diverse domains. At the same time many real-world networks vary over time, that is, the dataset can be represented as a sequence of graph snapshots. Hence, it is natural to consider the question of finding dense subgraphs in a temporal network that are allowed to vary over time to a certain degree. In this paper, we search for dense subgraphs that have large pairwise Jaccard similarity coefficients. More formally, given a set of graph snapshots and a weight $\lambda$, we find a collection of dense subgraphs such that the sum of densities of the induced subgraphs plus the sum of Jaccard indices, weighted by $\lambda$, is maximized. We prove that this problem is NP-hard. To discover dense subgraphs with good objective value, we present an iterative algorithm which runs in $\mathcal{O}(n^2k^2 + m \log n + k^3 n)$ time per single iteration, and a greedy algorithm which runs in $\mathcal{O}(n^2k^2 + m \log n + k^3 n)$ time, where $k$ is the length of the graph sequence and $n$ and $m$ denote number of nodes and total number of edges respectively. We show experimentally that our algorithms are efficient, they can find ground truth in synthetic datasets and provide interpretable results from real-world datasets. Finally, we present a case study that shows the usefulness of our problem.
• Abstract（参考訳）: 密度の高い部分グラフを見つけることは、さまざまな領域で多くの応用を行うグラフマイニングの核となる問題である。 同時に、多くの現実世界のネットワークが時間とともに変化しており、データセットはグラフスナップショットのシーケンスとして表現できる。 したがって、時間とともに一定の程度まで変化することができる時間的ネットワークの中で密度の高い部分グラフを見つけるという問題を考えるのは自然である。 本稿では,ジャカード類似度係数の大きい高密度部分グラフを探索する。 より正式には、グラフスナップショットの集合と重み$\lambda$が与えられたとき、誘導された部分グラフの密度の和と、$\lambda$の重み付き Jaccard インデックスの和が最大になるような高密度な部分グラフの集合を見つける。 この問題がNPハードであることを証明する。 客観的な値の密接な部分グラフを見つけるために,1回の反復毎に$\mathcal{o}(n^2k^2 + m \log n + k^3 n)$で実行される反復アルゴリズムと$\mathcal{o}(n^2k^2 + m \log n + k^3 n)$ で実行されるgreedyアルゴリズムを示し,$k$はグラフ列の長さであり、$n$と$m$はそれぞれノード数と辺の総数を表す。 我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。 最後に,この問題の有用性を示すケーススタディを提案する。

関連論文リスト

• Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets [15.078359519557207]
  現実世界のグラフは世界規模でスパースであるが、高密度の「ポケット」が多数含まれている。 グラフマイニングの基本的な課題は、これらの密度の高い部分グラフを発見することである。 我々は、正規三角形リッチ(RTR)ファミリーの新しい定義を用いて、この問題の数学的定式化を行う。 証明可能なアルゴリズム RTRExtractor を設計し,任意の RTR 集合をカバーする RTR ファミリーを探索する。
  論文  参考訳（メタデータ） (2024-07-23T21:26:37Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。 我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。 我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
  論文  参考訳（メタデータ） (2021-06-02T02:58:35Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。