Two-Phase Influence Maximization in Social Networks with Seed Nodes and Referral Incentives

• The problem of maximizing the spread of influence with a limited budget is central to social networks research. Most solution approaches available in the existing literature devote the entire budget towards triggering diffusion at seed nodes. This paper investigates the effect of splitting the budget across two different, sequential phases. In phase 1, we adopt the classical approach of initiating diffusion at a selected seed-set. In phase 2, we use the remaining budget to offer referral incentives. We formulate this problem and explore suitable ways to split the budget between the two phases, with detailed experiments on synthetic and real-world datasets. The principal findings from our study are: (a) when the budget is low, it is prudent to use the entire budget for phase 1; (b) when the budget is moderate to high, it is preferable to use much of the budget for phase 1, while allocating the remaining budget to phase 2; (c) in the presence of moderate to strict temporal constraints, phase 2 is not warranted; (d) if the temporal constraints are low or absent, phase 2 yields a decisive improvement in influence spread.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

TEKNIK OCH TEKNOLOGIER  -- Annan teknik -- Övrig annan teknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Other Engineering and Technologies -- Other Engineering and Technologies not elsewhere specified (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Publikations- och innehållstyp

kon (ämneskategori)

ref (ämneskategori)