Effective submodularity of influence maximization on temporal networks

Abstract

We study influence maximization on temporal networks. This is a special setting where the influence function is not submodular, and there is no optimality guarantee for solutions achieved via greedy optimization. We perform an exhaustive analysis on both real and synthetic networks. We show that the influence function of randomly sampled sets of seeds often violates the necessary conditions for submodularity. However, when sets of seeds are selected according to the greedy optimization strategy, the influence function behaves effectively as a submodular function. Specifically, violations of the necessary conditions for submodularity are never observed in real networks, and only rarely in synthetic ones. The direct comparison with exact solutions obtained via brute-force search indicate that the greedy strategy provides approximate solutions that are well within the optimality gap guaranteed for strictly submodular functions. Greedy optimization appears therefore an effective strategy for the maximization of influence on temporal networks.

arXiv comment12 pages, 10 figures, 3 tables

References in corpus (20)

• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• Temporal Networks
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• High-resolution measurements of face-to-face contact patterns in a primary school
• What's in a crowd? Analysis of face-to-face behavioral networks
• Activity driven modeling of time varying networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
• Contact patterns among high school students
• Can co-location be used as a proxy for face-to-face contacts?
• Mitigation of infectious disease at school: targeted class closure vs school closure
• Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers
• Analytical computation of the epidemic threshold on temporal networks
• Seed Selection for Spread of Influence in Social Networks: Temporal vs. Static Approach
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Influence maximization on temporal networks
• Effective Influence Spreading in Temporal Networks with Sequential Seeding