Large-scale influence maximization with the influence maximization benchmarker suite
| Autor: | Kurt Rothermel, Sukanya Bhowmik, Heiko Geppert |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Scheme (programming language)
Mathematical optimization Computer science Suite Scale (descriptive set theory) 02 engineering and technology Maximization Set (abstract data type) 020204 information systems 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing Proxy (statistics) Implementation computer computer.programming_language |
| Zdroj: | GRADES-NDA@SIGMOD |
| DOI: | 10.1145/3461837.3464510 |
| Popis: | Maximizing the influence of a fixed size seed set in a graph was investigated intensively in the past decade. Two very relevant questions are 1) how to solve the influence maximization problem on very large graphs within short time and 2) how to compare possible findings with the current state-of-the-art in a fair manner. To solve the first problem, proxy-based influence maximization strategies emerged. However, today's graphs became too large to be solved quickly for many well-established proxy strategies, since they do not scale to such large graphs. In this paper we propose 1) a novel update scheme for iterative influence maximization strategies named Update Approximation (UA) capable of large influence spreads within a few seconds on billion-scale graphs. Further, we present 2) a generic benchmark suite (Influence Maximization Benchmarker --- IMB) to implement and evaluate influence maximization strategies, alongside with implementations for several established strategies. IMB allows for easy to use benchmarks for further research by the community. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|