論文の概要: Community detection using low-dimensional network embedding algorithms
- arxiv url: http://arxiv.org/abs/2111.05267v1
- Date: Thu, 4 Nov 2021 14:57:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-14 15:12:36.482599
- Title: Community detection using low-dimensional network embedding algorithms
- Title（参考訳）: 低次元ネットワーク埋め込みアルゴリズムを用いたコミュニティ検出
- Authors: Aman Barot and Shankar Bhamidi and Souvik Dhara
- Abstract要約: 我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。
固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
- 参考スコア（独自算出の注目度）: 1.052782170493037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the increasing relevance of large networks in important areas such as
the study of contact networks for spread of disease, or social networks for
their impact on geopolitics, it has become necessary to study machine learning
tools that are scalable to very large networks, often containing millions of
nodes. One major class of such scalable algorithms is known as network
representation learning or network embedding. These algorithms try to learn
representations of network functionals (e.g.~nodes) by first running multiple
random walks and then using the number of co-occurrences of each pair of nodes
in observed random walk segments to obtain a low-dimensional representation of
nodes on some Euclidean space. The aim of this paper is to rigorously
understand the performance of two major algorithms, DeepWalk and node2vec, in
recovering communities for canonical network models with ground truth
communities. Depending on the sparsity of the graph, we find the length of the
random walk segments required such that the corresponding observed
co-occurrence window is able to perform almost exact recovery of the underlying
community assignments. We prove that, given some fixed co-occurrence window,
node2vec using random walks with a low non-backtracking probability can succeed
for much sparser networks compared to DeepWalk using simple random walks.
Moreover, if the sparsity parameter is low, we provide evidence that these
algorithms might not succeed in almost exact recovery. The analysis requires
developing general tools for path counting on random networks having an
underlying low-rank structure, which are of independent interest.
- Abstract（参考訳）: 病気の拡大のためのコンタクトネットワークや、地政学に影響を及ぼすソーシャルネットワークなど、重要な分野における大規模ネットワークの関連性が高まっているため、非常に大規模なネットワークにスケーラブルで、数百万のノードを含む機械学習ツールを研究する必要がある。
このようなスケーラブルなアルゴリズムの1つの主要なクラスは、ネットワーク表現学習またはネットワーク埋め込みとして知られている。
これらのアルゴリズムは、まず複数のランダムウォークを実行し、観察されたランダムウォークセグメント内の各ノードの共起数を使用して、いくつかのユークリッド空間上のノードの低次元表現を得ることにより、ネットワーク機能(例えば、ノード)の表現を学習しようとする。
本研究の目的は,DeepWalk と node2vec の2つの主要なアルゴリズムの性能を厳格に把握することである。
グラフのスパーシティによっては、観察された共起ウィンドウが基礎となるコミュニティの割り当てをほぼ正確にリカバリできるように、必要なランダムウォークセグメントの長さを見出すことができる。
一定の共起ウィンドウがあれば、単純なランダムウォークを用いたディープウォークと比較して、非バックトラック確率の低いランダムウォークを用いたnode2vecは、多くのスパルサーネットワークで成功する。
さらに、疎度パラメータが低い場合、これらのアルゴリズムがほぼ正確なリカバリに成功しないことを示す。
この分析には、独立した関心を持つ低ランク構造を持つランダムネットワークのパスカウントのための一般的なツールの開発が必要である。
関連論文リスト
- Strong and Weak Random Walks on Signed Networks [4.739812980667592]
本稿では,2つ以上のコミュニティを持つネットワークの構造を捉えることのできる,署名付きネットワークランダムウォークを提案する。
このウォークによって類似性行列が生成され、ノードを対角的なコミュニティにクラスタリングすることができる。
弱い歩行に基づく類似性行列は、教師なしおよび半自明なクラスタリングの両方に利用できることを示す。
論文 参考訳（メタデータ） (2024-06-12T09:36:20Z) - Sifting out communities in large sparse networks [2.666294200266662]
大規模ネットワークにおけるクラスタリングの結果の質を定量化するための直感的な客観的関数を導入する。
この領域に特に適したコミュニティを特定するために,2段階の手法を用いる。
数万のノードからなる大規模ネットワークにおける複雑な遺伝的相互作用を同定する。
論文 参考訳（メタデータ） (2024-05-01T18:57:41Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
ドメイン適応型ハッシュ学習はコンピュータビジョンコミュニティでかなりの成功を収めた。
UDAHと呼ばれるネットワークのための教師なしドメイン適応型ハッシュ学習手法を開発した。
論文 参考訳（メタデータ） (2021-08-20T12:09:38Z) - Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
我々は、高密度ネットワークグラフ上のランダムウォーキングとして、人工ニューラルネットワークを生成する。
このようなネットワークはスクラッチからスパースを訓練することができ、高密度ネットワークをトレーニングし、その後圧縮する高価な手順を避けることができる。
我々は,低差分シーケンスで生成された人工ニューラルネットワークが,より低い計算複雑性で,密度の高いニューラルネットワークの到達範囲内で精度を達成できることを実証した。
論文 参考訳（メタデータ） (2021-03-05T08:45:43Z) - Consistency of random-walk based network embedding algorithms [13.214230533788932]
node2vecアルゴリズムとDeepWalkアルゴリズムを行列ファクタリゼーションの観点から検討する。
その結果,観測ネットワークの幅,ランダムウォークのウィンドウサイズ,ノード2vec/DeepWalk埋め込みの収束率との微妙な相互作用が示唆された。
論文 参考訳（メタデータ） (2021-01-18T22:49:22Z) - Inductive Graph Embeddings through Locality Encodings [0.42970700836450487]
ドメイン依存のノード/エッジ属性を使わずに,大規模ネットワークにインダクティブネットワークを組み込むことの問題点を考察する。
本稿では,学習アルゴリズムの基盤として,基本的定義済みの局所符号化を用いることを提案する。
本手法は,役割検出,リンク予測,ノード分類などのタスクにおける最先端性能を実現する。
論文 参考訳（メタデータ） (2020-09-26T13:09:11Z) - Sketch-based community detection in evolving networks [15.512086254435788]
時間変化ネットワークにおけるコミュニティ検出のアプローチを検討する。
このアプローチの中心となるのは、完全なネットワークの各スナップショットにある重要なコミュニティ構造をキャプチャする、小さなスケッチグラフを維持することだ。
すべての処理を並列に処理できるコミュニティ検出アルゴリズムを定式化する。
論文 参考訳（メタデータ） (2020-09-24T17:32:57Z) - 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) - Detecting Communities in Heterogeneous Multi-Relational Networks:A
Message Passing based Approach [89.19237792558687]
コミュニティは、ソーシャルネットワーク、生物学的ネットワーク、コンピュータおよび情報ネットワークを含むネットワークの共通の特徴である。
我々は,全同種ネットワークのコミュニティを同時に検出する効率的なメッセージパッシングに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-06T17:36:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。