論文の概要: Influence Maximization (IM) in Complex Networks with Limited Visibility
Using Statistical Methods
- arxiv url: http://arxiv.org/abs/2208.13166v1
- Date: Sun, 28 Aug 2022 07:55:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-30 14:28:44.275258
- Title: Influence Maximization (IM) in Complex Networks with Limited Visibility
Using Statistical Methods
- Title（参考訳）: 統計的手法を用いた可視性に制限のある複雑ネットワークにおける影響最大化(IM)
- Authors: aeid Ghafouri, Seyed Hossein Khasteh, Seyed Omid Azarkasb
- Abstract要約: 影響文学(IM)問題はNP完全問題(NP完全問題)として知られており、時間内に解が存在しない。
この複雑さを改善するために提案された手法のほとんどは、グラフ全体が見えるという仮定に基づいている。
本研究では,リンク予測手法による現在の手法を擬似可視グラフに拡張する。
- 参考スコア（独自算出の注目度）: 2.320417845168326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A social network (SN) is a social structure consisting of a group
representing the interaction between them. SNs have recently been widely used
and, subsequently, have become suitable and popular platforms for product
promotion and information diffusion. People in an SN directly influence each
other's interests and behavior. One of the most important problems in SNs is to
find people who can have the maximum influence on other nodes in the network in
a cascade manner if they are chosen as the seed nodes of a network diffusion
scenario. Influential diffusers are people who, if they are chosen as the seed
set in a publishing issue in the network, that network will have the most
people who have learned about that diffused entity. This is a well-known
problem in literature known as influence maximization (IM) problem. Although it
has been proven that this is an NP-complete problem and does not have a
solution in polynomial time, it has been argued that it has the properties of
sub modular functions and, therefore, can be solved using a greedy algorithm.
Most of the methods proposed to improve this complexity are based on the
assumption that the entire graph is visible. However, this assumption does not
hold for many real-world graphs. This study is conducted to extend current
maximization methods with link prediction techniques to pseudo-visibility
graphs. To this end, a graph generation method called the exponential random
graph model (ERGM) is used for link prediction. The proposed method is tested
using the data from the Snap dataset of Stanford University. According to the
experimental tests, the proposed method is efficient on real-world graphs.
- Abstract（参考訳）: sn(social network)は、それらの間の相互作用を表すグループからなる社会構造である。
SNは近年広く使われており、その後製品プロモーションや情報拡散のプラットフォームとして広く普及している。
SNの人々はお互いの興味や行動に直接影響を与えます。
SNの最も重要な問題の1つは、ネットワーク拡散シナリオのシードノードとして選択された場合、ネットワーク内の他のノードに最大限の影響を持つことができる人を見つけることである。
影響力のあるディフューザーは、もしそれがネットワークの出版号のシードセットに選ばれれば、その拡散したエンティティについて学んだ人の大半を持つだろう。
これは、影響最大化(IM)問題として知られる文学におけるよく知られた問題である。
これはnp完全問題であり、多項式時間では解がないことが証明されているが、それは部分モジュラー関数の性質を持ち、したがって欲張りなアルゴリズムを使って解くことができると論じられている。
この複雑さを改善するために提案された手法のほとんどは、グラフ全体が見えるという仮定に基づいている。
しかし、この仮定は多くの実世界のグラフには当てはまらない。
本研究では,リンク予測手法による電流最大化手法を擬似可視グラフに拡張する。
この目的のために,指数ランダムグラフモデル (ERGM) と呼ばれるグラフ生成手法がリンク予測に用いられている。
スタンフォード大学のsnapデータセットのデータを用いて,提案手法を検証した。
実験によると,提案手法は実世界のグラフ上で効率的である。
関連論文リスト
- Online Learning Of Expanding Graphs [14.952056744888916]
本稿では,信号ストリームからグラフを拡張するためのオンラインネットワーク推論の問題に対処する。
ネットワークに加入したばかりのノードや,それまでのノードに対して,さまざまなタイプの更新を可能にする戦略を導入する。
論文 参考訳（メタデータ） (2024-09-13T09:20:42Z) - The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。
観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。
さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
論文 参考訳（メタデータ） (2024-06-18T12:16:00Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Neural Graph Revealers [2.2721854258621064]
確率的グラフモデルとスパースグラフリカバリ手法を効率的にマージするために,NGR(Neural Graph Revealers)を提案する。
NGRはニューラルネットワークを「ガラス箱」、より具体的にはマルチタスク学習フレームワークとみなしている。
ガウス図形モデルとCenters for Disease Control and Preventionによるマルチモーダル乳幼児死亡データから,スパースグラフの復元と確率的推定を行った。
論文 参考訳（メタデータ） (2023-02-27T08:40:45Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。
IID(non-graph)データをGNNに簡単に組み込むことはできない。
本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-16T22:46:33Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - How hard is to distinguish graphs with graph neural networks? [32.09819774228997]
本研究では,メッセージパッシングモデル(MPNN)におけるグラフアイソモーフィズムの分類変種に対する硬度結果の導出を行う。
MPNNは、今日のグラフニューラルネットワークの大部分を包含しており、ノードにユニークな特徴が与えられた場合、普遍的である。
12のグラフ分類タスクと420のネットワークを含む実証的研究は、実際の性能と理論的予測の間に強い整合性を示す。
論文 参考訳（メタデータ） (2020-05-13T22:28:46Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。