論文の概要: A Nearly-Linear Time Algorithm for Minimizing Risk of Conflict in Social
Networks
- arxiv url: http://arxiv.org/abs/2301.05466v1
- Date: Fri, 13 Jan 2023 10:32:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-19 13:36:44.304890
- Title: A Nearly-Linear Time Algorithm for Minimizing Risk of Conflict in Social
Networks
- Title（参考訳）: ソーシャルネットワークにおける衝突リスク最小化のための近似時間アルゴリズム
- Authors: Liwang Zhu and Zhongzhi Zhang
- Abstract要約: 本研究では,少数のノードの初期意見を変更することで,ソーシャルネットワークにおける競合のリスクを最小限に抑えることの課題について検討する。
特に、高速なネットワークは200万以上のノードを持つ大規模ネットワークにスケールし、最大20タイムのスピードアップを実現している。
- 参考スコア（独自算出の注目度）: 11.244268226976478
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Concomitant with the tremendous prevalence of online social media platforms,
the interactions among individuals are unprecedentedly enhanced. People are
free to interact with acquaintances, express and exchange their own opinions
through commenting, liking, retweeting on online social media, leading to
resistance, controversy and other important phenomena over controversial social
issues, which have been the subject of many recent works. In this paper, we
study the problem of minimizing risk of conflict in social networks by
modifying the initial opinions of a small number of nodes. We show that the
objective function of the combinatorial optimization problem is monotone and
supermodular. We then propose a na\"{\i}ve greedy algorithm with a $(1-1/e)$
approximation ratio that solves the problem in cubic time. To overcome the
computation challenge for large networks, we further integrate several
effective approximation strategies to provide a nearly linear time algorithm
with a $(1-1/e-\epsilon)$ approximation ratio for any error parameter
$\epsilon>0$. Extensive experiments on various real-world datasets demonstrate
both the efficiency and effectiveness of our algorithms. In particular, the
fast one scales to large networks with more than two million nodes, and
achieves up to $20\times$ speed-up over the state-of-the-art algorithm.
- Abstract（参考訳）: オンラインソーシャルメディアプラットフォームが急速に普及している中で、個人間の交流は前例のないほど強化されている。
人々は知り合いと自由に対話し、コメント、好み、リツイートを通じて自分の意見を交換し、議論を呼んでいる社会問題に対する抵抗、論争、その他の重要な現象を招き、近年の多くの著作の主題となっている。
本稿では,少数のノードの初期の意見を変更することで,ソーシャルネットワークにおける衝突のリスクを最小化する問題について検討する。
組合せ最適化問題の目的関数は単調かつ超モジュラーであることを示す。
次に,この問題を立方時間で解く近似比(1-1/e)$のna\"{\i}ve greedyアルゴリズムを提案する。
大規模ネットワークの計算課題を克服するため, 誤差パラメータ$\epsilon>0$に対して$(1-1/e-\epsilon)$近似比のほぼ線形時間アルゴリズムを提供するために, いくつかの効率的な近似戦略を統合する。
様々な実世界のデータセットに対する大規模な実験は、アルゴリズムの効率性と有効性を示している。
特にfast oneは、200万以上のノードを持つ大規模ネットワークにスケールし、最先端アルゴリズムよりも最大20\times$のスピードアップを実現している。
関連論文リスト
- Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
論文 参考訳（メタデータ） (2023-09-09T13:54:34Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - FastCover: An Unsupervised Learning Framework for Multi-Hop Influence
Maximization in Social Networks [39.86798194955807]
ソーシャルネットワークで影響力のあるユーザーを見つけることは、多くの有用なアプリケーションにおいて根本的な問題である。
本稿では,IM の問題を予算制約付き d-hop 支配集合問題 (kdDSP) に還元する。
我々は、効率的な欲求戦略を教師なしで学習することでkdDSPを解決するために、統合機械学習(ML)フレームワークであるFastCoverを提案する。
FastCoverは、GNNの1つの前方伝播で計算されたノードのスコアから設定されたシード全体を決定する。
論文 参考訳（メタデータ） (2021-10-31T10:49:21Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Maximizing Influence of Leaders in Social Networks [15.05158252504978]
我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。
提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
論文 参考訳（メタデータ） (2021-06-11T02:31:46Z) - Online Adversarial Attacks [57.448101834579624]
我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。
まず、オンライン脅威モデルの決定論的変種を厳格に分析する。
このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
論文 参考訳（メタデータ） (2021-03-02T20:36:04Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。