Budget-aware Influence Maximization in Social Networks
The influence maximization of social networks is a crucial problem in the field of network science, which has wide applications from advertising to public opinion control.This problem refers to selecting a set of source nodes in a social graph to achieve the greatest influence under a certain propag...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial office of Computer Science
2022-04-01
|
| Series: | Jisuanji kexue |
| Subjects: | |
| Online Access: | https://www.jsjkx.com/fileup/1002-137X/PDF/1002-137X-2022-49-4-100.pdf |
| _version_ | 1818535732056162304 |
|---|---|
| author | ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng |
| author_facet | ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng |
| author_sort | ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng |
| collection | DOAJ |
| description | The influence maximization of social networks is a crucial problem in the field of network science, which has wide applications from advertising to public opinion control.This problem refers to selecting a set of source nodes in a social graph to achieve the greatest influence under a certain propagation model.Since the node selection problem is a typical NP-hard problem, it will encounter the combinatorial explosion when facing large-scale networks.Hence, in recent years, heuristic algorithms are ge-nerally adopted to obtain approximate solutions to the problems in acceptable time.However, the existing work rarely considers the cost of selected nodes, and hence the solutions obtained cannot meet the budget limitations in practical applications.This paper aims to solve the influence maximization problem of social networks under cost-constrained conditions.By fully considering the costs, we build a budget-aware influence maximization model and propose a node selection algorithm named community detection-based ant colony system (CDACS) to deal with it.First, in order to save the unnecessary expenditure coming from the redundant coverage of source nodes, we use the fast greedy modularity maximization algorithm to cluster the network, and introduce a cross-community walking factor in the state transition process of ants to enhance the global exploration ability of the ant colony on the network.Second, we specifically design a penalty-based evaluation function to guide the search towards budget-feasible region as well as developing new heuristic and pheromone forms to enhance the search efficiency.Experimental results on real datasets show that the CDACS algorithm enhances the traditional ant colony algorithm by achieving a 15% improvement in the average coverage rate and a 20% reduction in the running time overhead.Compared with other existing influence maximization algorithms, the coverage effect has also been significantly improved.Moreover, the reliability of the CDACS algorithm in cost control has been validated by experiments. |
| first_indexed | 2024-12-11T18:28:50Z |
| format | Article |
| id | doaj.art-7b7461a9789e4a29b659a27eb8fb8b9c |
| institution | Directory Open Access Journal |
| issn | 1002-137X |
| language | zho |
| last_indexed | 2024-12-11T18:28:50Z |
| publishDate | 2022-04-01 |
| publisher | Editorial office of Computer Science |
| record_format | Article |
| series | Jisuanji kexue |
| spelling | doaj.art-7b7461a9789e4a29b659a27eb8fb8b9c2022-12-22T00:54:59ZzhoEditorial office of Computer ScienceJisuanji kexue1002-137X2022-04-0149410010910.11896/jsjkx.210300228Budget-aware Influence Maximization in Social NetworksZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng0School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, ChinaThe influence maximization of social networks is a crucial problem in the field of network science, which has wide applications from advertising to public opinion control.This problem refers to selecting a set of source nodes in a social graph to achieve the greatest influence under a certain propagation model.Since the node selection problem is a typical NP-hard problem, it will encounter the combinatorial explosion when facing large-scale networks.Hence, in recent years, heuristic algorithms are ge-nerally adopted to obtain approximate solutions to the problems in acceptable time.However, the existing work rarely considers the cost of selected nodes, and hence the solutions obtained cannot meet the budget limitations in practical applications.This paper aims to solve the influence maximization problem of social networks under cost-constrained conditions.By fully considering the costs, we build a budget-aware influence maximization model and propose a node selection algorithm named community detection-based ant colony system (CDACS) to deal with it.First, in order to save the unnecessary expenditure coming from the redundant coverage of source nodes, we use the fast greedy modularity maximization algorithm to cluster the network, and introduce a cross-community walking factor in the state transition process of ants to enhance the global exploration ability of the ant colony on the network.Second, we specifically design a penalty-based evaluation function to guide the search towards budget-feasible region as well as developing new heuristic and pheromone forms to enhance the search efficiency.Experimental results on real datasets show that the CDACS algorithm enhances the traditional ant colony algorithm by achieving a 15% improvement in the average coverage rate and a 20% reduction in the running time overhead.Compared with other existing influence maximization algorithms, the coverage effect has also been significantly improved.Moreover, the reliability of the CDACS algorithm in cost control has been validated by experiments.https://www.jsjkx.com/fileup/1002-137X/PDF/1002-137X-2022-49-4-100.pdfsocial network|influence maximization|cost control|ant colony system|community clustering |
| spellingShingle | ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng Budget-aware Influence Maximization in Social Networks Jisuanji kexue social network|influence maximization|cost control|ant colony system|community clustering |
| title | Budget-aware Influence Maximization in Social Networks |
| title_full | Budget-aware Influence Maximization in Social Networks |
| title_fullStr | Budget-aware Influence Maximization in Social Networks |
| title_full_unstemmed | Budget-aware Influence Maximization in Social Networks |
| title_short | Budget-aware Influence Maximization in Social Networks |
| title_sort | budget aware influence maximization in social networks |
| topic | social network|influence maximization|cost control|ant colony system|community clustering |
| url | https://www.jsjkx.com/fileup/1002-137X/PDF/1002-137X-2022-49-4-100.pdf |
| work_keys_str_mv | AT zuoyuanlingongyuejiaochenweineng budgetawareinfluencemaximizationinsocialnetworks |