Abstract
Concerning the limited influence scope and high time complexity of existing influence maximization algorithms in social networks, a k-core filtered algorithm based on independent cascade model was proposed. Firstly, an existing influence maximization algorithm was introduced, its rank of nodes does not depend on the entire network. Secondly, pretraining was carried out to find the value of k which has the best optimization effect on existing algorithms but has no relation with the number of selected seeds. Finally, the nodes and edges that do not belong to the k-core subgraph were filtered by computing the k-core of the graph, then the existing influence maximization algorithms were applied on the k-core subgraph,thus reducing computational complexity. Several experiments were conducted on datasets with different scale to prove that the k-core filtered algorithm has different optimization effects on different influence maximization algorithms. After combined with k-core filtered algorithm, compared with the original Prefix excluding Maximum Influence Arborescence( PMIA) algorithm,the influence range is increased by 13. 89% and the execution time is reduced by as much as 8. 34%; compared with the original Core Covering Algorithm( CCA), the influence range has no obvious difference and the execution time is reduced by as much as 28. 5%; compared with the original Out Degree algorithm, the influence range is increased by 21. 81% and the execution time is reduced by as much as 26. 96%; compared with the original Random algorithm, the influence range is increased by 71. 99% and the execution time is reduced by as much as 24. 21%. Furthermore, a new influence maximization algorithm named GIMS( General Influence Maximization in Social network) was proposed. Compared with PIMA and Influence Rank Influence Estimation( IRIE), it has wider influence range while still keeping execution time at second level. When it was combined with k-core filtered algorithm, the influence range and execution time do not have significant change. The experimiental results show that k-core filtered algorithm can effectively increase the influence ranges of existing algorithms and reduce their execution times; in addition, the proposed GIMS algorithm has wider influence range and better efficiency, and it is more robust.
| Translated title of the contribution | k-core filtered influence maximization algorithms in social networks |
|---|---|
| Original language | Chinese |
| Pages (from-to) | 464-470 |
| Number of pages | 7 |
| Journal | Journal of Computer Applications |
| Volume | 38 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1 Feb 2018 |
Funding
国家自然科学基金资助项目(61502349);湖北省自然科学基金资助项目(2015CFB339);苏州市科技发展项目(SYG201442).
Indexed by
- CSCD
Fingerprint
Dive into the research topics of 'k-core filtered influence maximization algorithms in social networks'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver