Budget-aware local influence iterative algorithm for efficient influence maximization in social networks

Area of Science:

• Social Network Analysis
• Computational Social Science
• Information Science

Background:

• The budgeted influence maximization (BIM) problem seeks optimal seed nodes within budget constraints.
• Existing BIM algorithms struggle to balance speed and accuracy.
• A refined cost model and efficient algorithm are needed for practical BIM applications.

Purpose of the Study:

• To develop an efficient algorithm for the budgeted influence maximization (BIM) problem.
• To propose a refined cost model based on empirical social media data.
• To enhance the balance between timeliness and effectiveness in influence maximization.

Main Methods:

• Developed a refined cost model using empirical analysis of Weibo quote data.
• Introduced the budget-aware local influence iterative (BLII) algorithm, a proxy-based approach.
• Approximated global influence using one-hop influence and managed overlap via iterative updates.

Main Results:

• The BLII algorithm demonstrated superior effectiveness and efficiency in comparative experiments.
• BLII outperformed other proxy-based algorithms by 20%-255% in influence spread.
• Achieved 96% improvement over the state-of-the-art simulation-based approach with reasonable running time.

Conclusions:

• The proposed cost model and BLII algorithm offer novel insights for BIM problems.
• BLII provides a potent and efficient tool for identifying seed nodes in budgeted influence maximization.
• The study addresses the critical need for timely and effective solutions in network influence analysis.