論文の概要: A Census-Based Genetic Algorithm for Target Set Selection Problem in Social Networks
- arxiv url: http://arxiv.org/abs/2410.02011v1
- Date: Wed, 2 Oct 2024 20:21:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 09:34:57.626880
- Title: A Census-Based Genetic Algorithm for Target Set Selection Problem in Social Networks
- Title（参考訳）: ソーシャルネットワークにおける目標設定問題に対するセンサスに基づく遺伝的アルゴリズム
- Authors: Md. Samiur Rahman, Mohammad Shamim Ahsan, Tim Chen, Vijayakumar Varadarajan,
- Abstract要約: 本稿では,TSS問題に対する「国勢調査に基づく遺伝的アルゴリズム」という新しいアプローチを提案する。
このアルゴリズムでは、人口統計の考え方を用いて、人口の個々の情報を収集し、保存する。
本論文では,本論文から14個の実生活ソーシャルネットワークインスタンスの大規模グラフ上で提案アルゴリズムを実行する。
- 参考スコア（独自算出の注目度）: 0.46498278084317696
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the Target Set Selection (TSS) Problem in social networks, a fundamental problem in viral marketing. In the TSS problem, a graph and a threshold value for each vertex of the graph are given. We need to find a minimum size vertex subset to "activate" such that all graph vertices are activated at the end of the propagation process. Specifically, we propose a novel approach called "a census-based genetic algorithm" for the TSS problem. In our algorithm, we use the idea of a census to gather and store information about each individual in a population and collect census data from the individuals constructed during the algorithm's execution so that we can achieve greater diversity and avoid premature convergence at locally optimal solutions. We use two distinct census information: (a) for each individual, the algorithm stores how many times it has been identified during the execution (b) for each network node, the algorithm counts how many times it has been included in a solution. The proposed algorithm can also self-adjust by using a parameter specifying the aggressiveness employed in each reproduction method. Additionally, the algorithm is designed to run in a parallelized environment to minimize the computational cost and check each individual's feasibility. Moreover, our algorithm finds the optimal solution in all cases while experimenting on random graphs. Furthermore, we execute the proposed algorithm on 14 large graphs of real-life social network instances from the literature, improving around 9.57 solution size (on average) and 134 vertices (in total) compared to the best solutions obtained in previous studies.
- Abstract（参考訳）: 本稿では,ソーシャル・ネットワークにおけるターゲット・セット・セレクション(TSS)問題について考察する。
TSS問題では、グラフの各頂点に対するグラフとしきい値が与えられる。
伝播過程の最後に全てのグラフ頂点が活性化されるように、最小サイズの頂点部分集合を「活性化する」必要がある。
具体的には,TSS問題に対する「国勢調査に基づく遺伝的アルゴリズム」と呼ばれる新しいアプローチを提案する。
本アルゴリズムでは,集団内の各個体の情報を収集・保存し,アルゴリズムの実行中に構築した個体の国勢調査データを収集することで,より多様性を増し,局所最適解における早期収束を回避する。
私たちは2つの異なる国勢調査情報を使用します。
a) 各個体について、その実行中に何回特定されたかをアルゴリズムが記憶する
b) 各ネットワークノードに対して、解に何回含まれたかをアルゴリズムがカウントする。
提案アルゴリズムは、各再生法で用いられる攻撃性を指定するパラメータを用いて自己調整することもできる。
さらに、計算コストを最小化し、個々の実現可能性をチェックするために、並列化された環境で実行されるように設計されている。
さらに,提案アルゴリズムは,ランダムグラフ上で実験しながら,すべてのケースにおいて最適解を求める。
さらに,本論文では,14個の実生活ソーシャルネットワークインスタンスのグラフ上で提案アルゴリズムを実行し,従来研究で得られた最良の解と比較して,平均9.57の解サイズと134の頂点を改良した。
関連論文リスト
- Parallel Algorithms for Median Consensus Clustering in Complex Networks [3.7474428734943532]
我々は,グラフの多数の異なるクラスタリングソリューションのコンセンサスを求めるアルゴリズムを開発した。
我々のアルゴリズムはグラフ構造を考慮に入れ、他の手法よりもはるかに高速な品質の解を求める。
並列アルゴリズムは,64コアを大規模実世界のグラフに利用することにより,35倍の高速化を実現する。
論文 参考訳（メタデータ） (2024-08-21T04:27:57Z) - Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。
特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
論文 参考訳（メタデータ） (2024-02-04T03:03:27Z) - CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
論文 参考訳（メタデータ） (2022-08-01T17:34:07Z) - The Neural-Prediction based Acceleration Algorithm of Column Generation
for Graph-Based Set Covering Problems [20.1479227701035]
グラフに基づく集合被覆問題の解法として,ニューラル予測(CG-P)を用いたカラム生成アルゴリズムを提案する。
グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジの最終解に含まれる確率を予測する。
鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2022-07-04T13:46:59Z) - Degree-Based Random Walk Approach for Graph Embedding [0.0]
計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。
提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
論文 参考訳（メタデータ） (2021-10-21T19:16:16Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。