Local Probability Solution Based Immune Genetic Influence Maximization Algorithm
The problem of influence maximization is to select a small number of users in a complex social network to maximize the diffusion of influence under a specific propagation model. The greedy Monte Carlo simulation approach theoretically guarantees a near-optimal solution, but it is very inefficient. A...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press
2020-05-01
|
| Series: | Jisuanji kexue yu tansuo |
| Subjects: | |
| Online Access: | http://fcst.ceaj.org/CN/abstract/abstract2191.shtml |
| _version_ | 1830517962158637056 |
|---|---|
| author | QIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping |
| author_facet | QIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping |
| author_sort | QIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping |
| collection | DOAJ |
| description | The problem of influence maximization is to select a small number of users in a complex social network to maximize the diffusion of influence under a specific propagation model. The greedy Monte Carlo simulation approach theoretically guarantees a near-optimal solution, but it is very inefficient. Although many heuristics appro-aches have been developed without any theoretical guarantee, they greatly reduce the quality of the solution. In order to solve this problem, this paper presents a local probabilistic solution strategy to calculate the in uence spread of a node set. The performance of this strategy is similar to Monte Carlo simulation. And this paper proposes immune genetic algorithm based influence maximization. Experiments on four real datasets demonstrate the efficiency of the proposed algorithm in solving the influence maximization problem. In terms of influence spread, it has extremely similar performance with the current best performing CELF (cost-effective lazy forward) algorithm, and the running time is about 5 orders of magnitude faster than CELF algorithm. |
| first_indexed | 2024-12-22T04:10:08Z |
| format | Article |
| id | doaj.art-fcf4a33938e74279bcab7c88fc1a8c30 |
| institution | Directory Open Access Journal |
| issn | 1673-9418 |
| language | zho |
| last_indexed | 2024-12-22T04:10:08Z |
| publishDate | 2020-05-01 |
| publisher | Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press |
| record_format | Article |
| series | Jisuanji kexue yu tansuo |
| spelling | doaj.art-fcf4a33938e74279bcab7c88fc1a8c302022-12-21T18:39:33ZzhoJournal of Computer Engineering and Applications Beijing Co., Ltd., Science PressJisuanji kexue yu tansuo1673-94182020-05-0114578379110.3778/j.issn.1673-9418.1905010Local Probability Solution Based Immune Genetic Influence Maximization AlgorithmQIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping01. School of Computer Science and Technology, Anhui University, Hefei 230601, China 2. Center of Information Support & Assurance Technology, Anhui University, Hefei 230601, ChinaThe problem of influence maximization is to select a small number of users in a complex social network to maximize the diffusion of influence under a specific propagation model. The greedy Monte Carlo simulation approach theoretically guarantees a near-optimal solution, but it is very inefficient. Although many heuristics appro-aches have been developed without any theoretical guarantee, they greatly reduce the quality of the solution. In order to solve this problem, this paper presents a local probabilistic solution strategy to calculate the in uence spread of a node set. The performance of this strategy is similar to Monte Carlo simulation. And this paper proposes immune genetic algorithm based influence maximization. Experiments on four real datasets demonstrate the efficiency of the proposed algorithm in solving the influence maximization problem. In terms of influence spread, it has extremely similar performance with the current best performing CELF (cost-effective lazy forward) algorithm, and the running time is about 5 orders of magnitude faster than CELF algorithm.http://fcst.ceaj.org/CN/abstract/abstract2191.shtmlsocial networkin uence maximizationmonte carlo simulationimmune genetic |
| spellingShingle | QIAN Fulan, XU Tao, ZHAO Shu, ZHANG Yanping Local Probability Solution Based Immune Genetic Influence Maximization Algorithm Jisuanji kexue yu tansuo social network in uence maximization monte carlo simulation immune genetic |
| title | Local Probability Solution Based Immune Genetic Influence Maximization Algorithm |
| title_full | Local Probability Solution Based Immune Genetic Influence Maximization Algorithm |
| title_fullStr | Local Probability Solution Based Immune Genetic Influence Maximization Algorithm |
| title_full_unstemmed | Local Probability Solution Based Immune Genetic Influence Maximization Algorithm |
| title_short | Local Probability Solution Based Immune Genetic Influence Maximization Algorithm |
| title_sort | local probability solution based immune genetic influence maximization algorithm |
| topic | social network in uence maximization monte carlo simulation immune genetic |
| url | http://fcst.ceaj.org/CN/abstract/abstract2191.shtml |
| work_keys_str_mv | AT qianfulanxutaozhaoshuzhangyanping localprobabilitysolutionbasedimmunegeneticinfluencemaximizationalgorithm |