Neural Influence Estimator: Towards Real-time Solutions to Influence Blocking Maximization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910962278203392 |
|---|---|
| author | Chen, Wenjie Liu, Shengcai Ong, Yew-Soon Li, Zhuang Tang, Ke |
| author_facet | Chen, Wenjie Liu, Shengcai Ong, Yew-Soon Li, Zhuang Tang, Ke |
| contents | Real-time solutions to the influence blocking maximization (IBM) problems are crucial for promptly containing the spread of misinformation. However, achieving this goal is non-trivial, mainly because assessing the blocked influence of an IBM problem solution typically requires plenty of expensive Monte Carlo simulations (MCSs). This work presents a novel approach that enables solving IBM problems with hundreds of thousands of nodes and edges in seconds. The key idea is to construct a fast-to-evaluate surrogate model called neural influence estimator (NIE) offline as a substitute for the time-intensive MCSs, and then combine it with optimization algorithms to address IBM problems online. To this end, a learning problem is formulated to build the NIE that takes the false-and-true information instance as input, extracts features describing the topology and inter-relationship between two seed sets, and predicts the blocked influence. A well-trained NIE can generalize across different IBM problems given a social network, and can be readily combined with existing IBM optimization algorithms. The experiments on 25 IBM problems with up to millions of edges show that the NIE-based optimization method can be up to four orders of magnitude faster than MCSs-based optimization method to achieve the same optimization quality. Moreover, given a one-minute limit, the NIE-based method can solve IBM problems with up to hundreds of thousands of nodes, which is at least one order of magnitude larger than what can be solved by existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14012 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Neural Influence Estimator: Towards Real-time Solutions to Influence Blocking Maximization Chen, Wenjie Liu, Shengcai Ong, Yew-Soon Li, Zhuang Tang, Ke Neural and Evolutionary Computing Social and Information Networks Real-time solutions to the influence blocking maximization (IBM) problems are crucial for promptly containing the spread of misinformation. However, achieving this goal is non-trivial, mainly because assessing the blocked influence of an IBM problem solution typically requires plenty of expensive Monte Carlo simulations (MCSs). This work presents a novel approach that enables solving IBM problems with hundreds of thousands of nodes and edges in seconds. The key idea is to construct a fast-to-evaluate surrogate model called neural influence estimator (NIE) offline as a substitute for the time-intensive MCSs, and then combine it with optimization algorithms to address IBM problems online. To this end, a learning problem is formulated to build the NIE that takes the false-and-true information instance as input, extracts features describing the topology and inter-relationship between two seed sets, and predicts the blocked influence. A well-trained NIE can generalize across different IBM problems given a social network, and can be readily combined with existing IBM optimization algorithms. The experiments on 25 IBM problems with up to millions of edges show that the NIE-based optimization method can be up to four orders of magnitude faster than MCSs-based optimization method to achieve the same optimization quality. Moreover, given a one-minute limit, the NIE-based method can solve IBM problems with up to hundreds of thousands of nodes, which is at least one order of magnitude larger than what can be solved by existing methods. |
| title | Neural Influence Estimator: Towards Real-time Solutions to Influence Blocking Maximization |
| topic | Neural and Evolutionary Computing Social and Information Networks |
| url | https://arxiv.org/abs/2308.14012 |