Influence maximization algorithm based on social network
The influence maximization (IM) problem asks for a group of seed users in a social network under a given propagation model, so that the information spread is maximized through these users.Existing algorithms have two main problems.Firstly, these algorithms were difficult to be applied in large-scale...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2022-08-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2022152/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841540003246637056 |
|---|---|
| author | Xuan WANG Yu ZHANG Junfeng ZHOU Ziyang CHEN |
| author_facet | Xuan WANG Yu ZHANG Junfeng ZHOU Ziyang CHEN |
| author_sort | Xuan WANG |
| collection | DOAJ |
| description | The influence maximization (IM) problem asks for a group of seed users in a social network under a given propagation model, so that the information spread is maximized through these users.Existing algorithms have two main problems.Firstly, these algorithms were difficult to be applied in large-scale social networks due to limited expected influence and high time complexity.Secondly, these algorithms were limited to specific propagation models and could only solve the IM problem under a single type of social network.When they were used in different types of networks, the effect was poor.In this regard, an efficient algorithm (MTIM) based on two classic propagation models and reverse influence sampling (RIS) was proposed.To verify the effectiveness of MTIM, experiments were conducted to compare MTIM with greedy algorithms such as IMM, TIM and PMC, and heuristic algorithms such as OneHop and Degree Discount on four real social networks.The results show that MTIM can return a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow><mo>(</mo> <mrow> <mn>1</mn><mo>−</mo><mfrac> <mn>1</mn> <mtext>e</mtext> </mfrac> <mo>−</mo><mi>ε</mi></mrow> <mo>)</mo></mrow></math></inline-formula> approximate solution, effectively expand the expected influence and significantly improve the efficiency. |
| format | Article |
| id | doaj-art-f0c5ddee3c274750a5af5fa7e7368e81 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2022-08-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-f0c5ddee3c274750a5af5fa7e7368e812025-01-14T06:28:59ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2022-08-014315116359392476Influence maximization algorithm based on social networkXuan WANGYu ZHANGJunfeng ZHOUZiyang CHENThe influence maximization (IM) problem asks for a group of seed users in a social network under a given propagation model, so that the information spread is maximized through these users.Existing algorithms have two main problems.Firstly, these algorithms were difficult to be applied in large-scale social networks due to limited expected influence and high time complexity.Secondly, these algorithms were limited to specific propagation models and could only solve the IM problem under a single type of social network.When they were used in different types of networks, the effect was poor.In this regard, an efficient algorithm (MTIM) based on two classic propagation models and reverse influence sampling (RIS) was proposed.To verify the effectiveness of MTIM, experiments were conducted to compare MTIM with greedy algorithms such as IMM, TIM and PMC, and heuristic algorithms such as OneHop and Degree Discount on four real social networks.The results show that MTIM can return a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow><mo>(</mo> <mrow> <mn>1</mn><mo>−</mo><mfrac> <mn>1</mn> <mtext>e</mtext> </mfrac> <mo>−</mo><mi>ε</mi></mrow> <mo>)</mo></mrow></math></inline-formula> approximate solution, effectively expand the expected influence and significantly improve the efficiency.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2022152/social networkinfluence maximizationseed setpropagation model |
| spellingShingle | Xuan WANG Yu ZHANG Junfeng ZHOU Ziyang CHEN Influence maximization algorithm based on social network Tongxin xuebao social network influence maximization seed set propagation model |
| title | Influence maximization algorithm based on social network |
| title_full | Influence maximization algorithm based on social network |
| title_fullStr | Influence maximization algorithm based on social network |
| title_full_unstemmed | Influence maximization algorithm based on social network |
| title_short | Influence maximization algorithm based on social network |
| title_sort | influence maximization algorithm based on social network |
| topic | social network influence maximization seed set propagation model |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2022152/ |
| work_keys_str_mv | AT xuanwang influencemaximizationalgorithmbasedonsocialnetwork AT yuzhang influencemaximizationalgorithmbasedonsocialnetwork AT junfengzhou influencemaximizationalgorithmbasedonsocialnetwork AT ziyangchen influencemaximizationalgorithmbasedonsocialnetwork |