  To promote viral marketing, major social platforms (e.g., Facebook
Marketplace and Pinduoduo) repeatedly select and invite different users (as
seeds) in online social networks to share fresh information about a product or
service with their friends. Thereby, we are motivated to optimize a multi-stage
seeding process of viral marketing in social networks and adopt the recent
notions of the peak and the average age of information (AoI) to measure the
timeliness of promotion information received by network users. Our problem is
different from the literature on information diffusion in social networks,
which limits to one-time seeding and overlooks AoI dynamics or information
replacement over time. As a critical step, we manage to develop closed-form
expressions that characterize and trace AoI dynamics over any social network.
For the peak AoI problem, we first prove the NP-hardness of our multi-stage
seeding problem by a highly non-straightforward reduction from the dominating
set problem, and then present a new polynomial-time algorithm that achieves
good approximation guarantees (e.g., less than 2 for linear network topology).
To minimize the average AoI, we also prove that our problem is NP-hard by
properly reducing it from the set cover problem. Benefiting from our two-side
bound analysis on the average AoI objective, we build up a new framework for
approximation analysis and link our problem to a much simplified sum-distance
minimization problem. This intriguing connection inspires us to develop another
polynomial-time algorithm that achieves a good approximation guarantee.
Additionally, our theoretical results are well corroborated by experiments on a
real social network.
