Influence maximization based on partial network structure information: A comparative analysis on seed selection heuristics
Authors:
- 1 October 2017
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Modern Physics C
- Vol. 28 (10)
Abstract
In this study, the problem of seed selection is investigated. This problem is mainly treated as an optimization problem, which is proved to be NP-hard. There are several heuristic approaches in the literature which mostly use algorithmic heuristics. These approaches mainly focus on the trade-off between computational complexity and accuracy. Although the accuracy of algorithmic heuristics are high, they also have high computational complexity. Furthermore, in the literature, it is generally assumed that complete information on the structure and features of a network is available, which is not the case in most of the times. For the study, a simulation model is constructed, which is capable of creating networks, performing seed selection heuristics, and simulating diffusion models. Novel metric-based seed selection heuristics that rely only on partial information are proposed and tested using the simulation model. These heuristics use local information available from nodes in the synthetically created networks. The performances of heuristics are comparatively analyzed on three different network types. The results clearly show that the performance of a heuristic depends on the structure of a network. A heuristic to be used should be selected after investigating the properties of the network at hand. More importantly, the approach of partial information provided promising results. In certain cases, selection heuristics that rely only on partial network information perform very close to similar heuristics that require complete network data.Keywords
This publication has 13 references indexed in Scilit:
- One Step, Two Step, Network Step? Complementary Perspectives on Communication Flows in Twittered Citizen ProtestsSocial Science Computer Review, 2016
- Dissecting the Spirit of Gezi: Influence vs. Selection in the Occupy Gezi MovementSociological Science, 2015
- Identifying influential nodes in complex networksPhysica A: Statistical Mechanics and its Applications, 2012
- Seeding Strategies for Viral Marketing: An Empirical ComparisonJournal of Marketing, 2011
- Social Network Sensors for Early Detection of Contagious OutbreaksPLOS ONE, 2010
- Extracting influential nodes on a social network for information diffusionData Mining and Knowledge Discovery, 2009
- Emergence of Scaling in Random NetworksScience, 1999
- Power and Centrality: A Family of MeasuresAmerican Journal of Sociology, 1987
- Threshold Models of Collective BehaviorAmerican Journal of Sociology, 1978
- Centrality in social networks conceptual clarificationSocial Networks, 1978