Fast and error-adaptive influence maximization based on count-distinct sketches

Warning The system is temporarily closed to updates for reporting purpose.

Göktürk, Gökhan and Kaya, Kamer (2024) Fast and error-adaptive influence maximization based on count-distinct sketches. Information Sciences, 655 . ISSN 0020-0255 (Print) 1872-6291 (Online)

Full text not available from this repository. (Request a copy)

Abstract

Influence maximization (IM) is the problem of finding a seed vertex set that maximizes the expected number of vertices influenced under a given diffusion model. Due to the NP-Hardness of finding an optimal seed set, high-quality yet expensive approximation algorithms have been frequently used. In addition, lightweight, sketch-based approaches, which do not step-by-step simulate the influence process, have been proposed in the literature to cope with the scale of today's networks. In this work, we describe a fast, error-adaptive approach that leverages Count-Distinct sketches and hash-based fused sampling to avoid step-by-step simulations and estimate the number of influenced vertices throughout a diffusion. Furthermore, for faster estimations, the sketches of a vertex for consecutive simulations are stored adjacently in memory. This allows the proposed algorithm to estimate the number of influenced vertices for multiple simulations at once. For faster processing, the proposed method automatically rebuilds the sketches after observing estimation errors above a given threshold. Our experimental results show that the proposed algorithm yields seed sets with comparable quality while being up to 3,337× faster than a state-of-the-art, high-quality influence maximization algorithm. In addition, it is up to 63× faster than a sketch-based approach while producing seed sets with 2%–10% better influence scores.
Item Type: Article
Uncontrolled Keywords: Count-Distinct sketch; Error-adaptive cardinality estimation; Graph processing; Influence maximization
Divisions: Center of Excellence in Data Analytics
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 08 Jun 2024 12:17
Last Modified: 08 Jun 2024 12:17
URI: https://research.sabanciuniv.edu/id/eprint/49038

Actions (login required)

View Item
View Item