論文の概要: Sketch-based community detection in evolving networks
- arxiv url: http://arxiv.org/abs/2009.11835v1
- Date: Thu, 24 Sep 2020 17:32:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-15 04:30:51.513440
- Title: Sketch-based community detection in evolving networks
- Title（参考訳）: 進化するネットワークにおけるスケッチに基づくコミュニティ検出
- Authors: Andre Beckus and George K. Atia
- Abstract要約: 時間変化ネットワークにおけるコミュニティ検出のアプローチを検討する。
このアプローチの中心となるのは、完全なネットワークの各スナップショットにある重要なコミュニティ構造をキャプチャする、小さなスケッチグラフを維持することだ。
すべての処理を並列に処理できるコミュニティ検出アルゴリズムを定式化する。
- 参考スコア（独自算出の注目度）: 15.512086254435788
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider an approach for community detection in time-varying networks. At
its core, this approach maintains a small sketch graph to capture the essential
community structure found in each snapshot of the full network. We demonstrate
how the sketch can be used to explicitly identify six key community events
which typically occur during network evolution: growth, shrinkage, merging,
splitting, birth and death. Based on these detection techniques, we formulate a
community detection algorithm which can process a network concurrently
exhibiting all processes. One advantage afforded by the sketch-based algorithm
is the efficient handling of large networks. Whereas detecting events in the
full graph may be computationally expensive, the small size of the sketch
allows changes to be quickly assessed. A second advantage occurs in networks
containing clusters of disproportionate size. The sketch is constructed such
that there is equal representation of each cluster, thus reducing the
possibility that the small clusters are lost in the estimate. We present a new
standardized benchmark based on the stochastic block model which models the
addition and deletion of nodes, as well as the birth and death of communities.
When coupled with existing benchmarks, this new benchmark provides a
comprehensive suite of tests encompassing all six community events. We provide
a set of numerical results demonstrating the advantages of our approach both in
run time and in the handling of small clusters.
- Abstract（参考訳）: 時間変化ネットワークにおけるコミュニティ検出のアプローチを検討する。
このアプローチの核となるのは、全ネットワークのスナップショットにある重要なコミュニティ構造を捉えるために、小さなスケッチグラフを維持することだ。
ネットワーク進化中に典型的に発生する6つの重要なコミュニティイベント – 成長、縮小、マージ、分割、誕生、死 — を明示的に識別するために、このスケッチをいかに利用できるかを示します。
これらの検出手法に基づいて,すべての処理を同時に処理できるコミュニティ検出アルゴリズムを定式化する。
スケッチベースのアルゴリズムで得られる利点の1つは、大きなネットワークの効率的なハンドリングである。
フルグラフにおけるイベントの検出は計算に高価である可能性があるが、スケッチの小さなサイズは変更を迅速に評価することができる。
第二の利点は、不均等サイズのクラスタを含むネットワークで発生する。
スケッチは、各クラスタに等しい表現が存在するように構成され、その結果、見積もりで小さなクラスタが失われる可能性が減少する。
本稿では,ノードの追加と削除,およびコミュニティの誕生と死をモデル化した確率ブロックモデルに基づく新しい標準ベンチマークを提案する。
既存のベンチマークと組み合わせることで、この新しいベンチマークは6つのコミュニティイベントすべてを含む包括的なテストスイートを提供する。
我々は、実行時と小さなクラスタの処理において、我々のアプローチの利点を示す数値的な結果のセットを提供する。
関連論文リスト
- Sifting out communities in large sparse networks [2.666294200266662]
大規模ネットワークにおけるクラスタリングの結果の質を定量化するための直感的な客観的関数を導入する。
この領域に特に適したコミュニティを特定するために,2段階の手法を用いる。
数万のノードからなる大規模ネットワークにおける複雑な遺伝的相互作用を同定する。
論文 参考訳（メタデータ） (2024-05-01T18:57:41Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Implicit models, latent compression, intrinsic biases, and cheap lunches
in community detection [0.0]
コミュニティ検出は、ネットワークをノードのクラスタに分割して、その大規模な構造を要約することを目的としている。
いくつかのコミュニティ検出手法は、確率的生成モデルを通じてクラスタリングの目的を明示的に導出する。
他の方法は記述的であり、特定のアプリケーションによって動機付けられた目的に応じてネットワークを分割する。
本稿では,コミュニティ検出対象,推論対象,記述対象とそれに対応する暗黙的ネットワーク生成モデルとを関連付けるソリューションを提案する。
論文 参考訳（メタデータ） (2022-10-17T15:38:41Z) - Community detection using low-dimensional network embedding algorithms [1.052782170493037]
我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。
固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
論文 参考訳（メタデータ） (2021-11-04T14:57:43Z) - Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
ドメイン適応型ハッシュ学習はコンピュータビジョンコミュニティでかなりの成功を収めた。
UDAHと呼ばれるネットワークのための教師なしドメイン適応型ハッシュ学習手法を開発した。
論文 参考訳（メタデータ） (2021-08-20T12:09:38Z) - Anomaly Detection on Attributed Networks via Contrastive Self-Supervised
Learning [50.24174211654775]
本論文では,アトリビュートネットワーク上の異常検出のためのコントラスト型自己監視学習フレームワークを提案する。
このフレームワークは、新しいタイプのコントラストインスタンスペアをサンプリングすることで、ネットワークデータからのローカル情報を完全に活用します。
高次元特性と局所構造から情報埋め込みを学習するグラフニューラルネットワークに基づくコントラスト学習モデルを提案する。
論文 参考訳（メタデータ） (2021-02-27T03:17:20Z) - On the use of local structural properties for improving the efficiency
of hierarchical community detection methods [77.34726150561087]
本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。
また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
論文 参考訳（メタデータ） (2020-09-15T00:16:12Z) - Community detection in networks using graph embeddings [0.615738282053772]
ベンチマークグラフ上のコミュニティを検出するために,いくつかのグラフ埋め込み手法をテストした。
埋め込み手法のパラメータが好適に選択された場合、性能は同等である。
この発見は、ネットワークを埋め込み、ポイントをグループ化する高い計算コストとともに、コミュニティ検出において、現在の埋め込み技術はネットワーククラスタリングアルゴリズムよりも改善されたものではないことを示唆している。
論文 参考訳（メタデータ） (2020-09-11T07:49:21Z) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳（メタデータ） (2020-06-28T23:09:27Z) - Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
グラフメタ学習フレームワーク - Graph Prototypeal Networks (GPN) を提案する。
GPNは、属性付きネットワーク上でテキストミータ学習を行い、ターゲット分類タスクを扱うための高度に一般化可能なモデルを導出する。
論文 参考訳（メタデータ） (2020-06-23T04:13:23Z) - Artificial Benchmark for Community Detection (ABCD): Fast Random Graph
Model with Community Structure [5.8010446129208155]
我々は、コミュニティ構造と、コミュニティサイズおよびコミュニティサイズの両方のパワー-法則分布を持つ代替のランダムグラフモデル、ABCD(Artificial Benchmark for Community Detection)を提供する。
ABCDは高速でシンプルで、ユーザーが純粋(独立)なコミュニティと、コミュニティ構造のないランダムなグラフの2つの極端間のスムーズな遷移を可能にするように、簡単に調整できる。
論文 参考訳（メタデータ） (2020-01-14T17:20:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。