HNoF: A Neighbors-of-Friends Heuristic for Influence Maximization in Social Networks

Influence maximization (IM) seeks a set of k seed users that maximizes the expected spread of influence in a social network. Because IM is NP-hard and computing the spread is #P-hard, simulation-based greedy algorithms achieve near-optimal spread but scale poorly, whereas fast heuristics often sacrifice much of the achievable spread. This paper proposes HNoF (Heuristic based on Neighbors of Friends), a greedy heuristic that restricts candidates to the two-hop neighbors of the current seed that are not its direct friends and ranks them by their marginal gain in the Expected Diffusion Value (EDV), a closed-form one-hop approximation of spread under the Independent Cascade (IC) model. This restriction prunes most of the graph at each iteration, and the EDV score replaces Monte Carlo simulation during seed selection. A derived closed-form expression for the EDV marginal gain shows how HNoF penalizes overlapping neighborhoods. HNoF was compared with General Greedy, LIR, SAEDV and DDSE on four real-world networks (NetHEPT, NetPHY, Epinions۱ and Slashdot۰۹۰۲) under the IC model (p = ۰.۰۱, k = ۵–۵۰). On the two collaboration networks, it came within about ۱–۴% of the spread of General Greedy at k = ۵۰ while running roughly four orders of magnitude faster. On all four networks, it achieved the largest spread among the scalable methods, exceeding DDSE by about ۱–۶%, although at a higher running time than DDSE and SAEDV on the largest networks. Combining a locality-constrained candidate set with an analytical spread estimate thus offers a favorable balance between spread and efficiency.

کلیدواژه ها:

influence maximization ، Social Networks ، Viral Marketing ، independent cascade model ، Expected Diffusion Value ، information diffusion ، Greedy Heuristics