Pack and Measure: An Effective Approach for Influence Propagation in Social Networks

• URL: http://arxiv.org/abs/2401.00525v1
• Date: Sun, 31 Dec 2023 15:51:33 GMT
• Title: Pack and Measure: An Effective Approach for Influence Propagation in Social Networks
• Authors: Faisal N. Abu-Khzam, Ghinwa Bou Matar and Sergio Thoumi
• Abstract summary: The Influence Maximization problem under the Independent Cascade model (IC) is considered. New seed-set selection methods are introduced based on the notions of a $d$-packing and centrality.
• Score: 0.3222802562733786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Influence Maximization problem under the Independent Cascade model (IC) is considered. The problem asks for a minimal set of vertices to serve as "seed set" from which a maximum influence propagation is expected. New seed-set selection methods are introduced based on the notions of a $d$-packing and vertex centrality. In particular, we focus on selecting seed-vertices that are far apart and whose influence-values are the highest in their local communities. Our best results are achieved via an initial computation of a $d$-Packing followed by selecting either vertices of high degree or high centrality in their respective closed neighborhoods. This overall "Pack and Measure" approach proves highly effective as a seed selection method.

Related papers

• Community Quality and Influence Maximization: An Empirical Study [0.0]
  Social networks play a vital role in applications such as viral marketing, epidemiology, product recommendation, and counter-terrorism.<n>A common approach, Cascade seed nodes, by first detecting disjoint communities and subsequently selecting representative nodes from these communities.<n>But whether the quality of detected communities consistently identifies the spread of influence under the Independent model remains unclear.<n>This paper addresses this question by extending a disjoint community detection method, termed $$-Hierarchical Clustering, to the influence problem under the Independent model.
  arXiv  Detail & Related papers  (2025-12-01T09:59:04Z)
• Less is More: Efficient Black-box Attribution via Minimal Interpretable Subset Selection [52.716143424856185]
  We propose LiMA (Less input is More faithful for Attribution), which reformulates the attribution of important regions as an optimization problem for submodular subset selection. LiMA identifies both the most and least important samples while ensuring an optimal attribution boundary that minimizes errors. Our method also outperforms the greedy search in attribution efficiency, being 1.6 times faster.
  arXiv  Detail & Related papers  (2025-04-01T06:58:15Z)
• Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
  Subset selection is a fundamental problem in optimization, which has a wide range of applications such as influence and sparse regression. Previous algorithms, including the greedy algorithm and evolutionary evolutionary POSS, either struggle in noisy environments or consume excessive computational resources. We propose a novel approach based on Pareto Optimization with Robust Evaluation for noisy subset selection (PORE), which maximizes a robust evaluation function and minimizes the subset size simultaneously.
  arXiv  Detail & Related papers  (2025-01-12T14:04:20Z)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  We propose a Deep Tree-based Retriever (DTR) for efficient recommendation. DTR frames the training task as a softmax-based multi-class classification over tree nodes at the same level. To mitigate the suboptimality induced by the labeling of non-leaf nodes, we propose a rectification method for the loss function.
  arXiv  Detail & Related papers  (2024-08-21T05:09:53Z)
• Less is More: Fewer Interpretable Region via Submodular Subset Selection [54.07758302264416]
  This paper re-models the above image attribution problem as a submodular subset selection problem. We construct a novel submodular function to discover more accurate small interpretation regions. For correctly predicted samples, the proposed method improves the Deletion and Insertion scores with an average of 4.9% and 2.5% gain relative to HSIC-Attribution.
  arXiv  Detail & Related papers  (2024-02-14T13:30:02Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• DQSSA: A Quantum-Inspired Solution for Maximizing Influence in Online Social Networks (Student Abstract) [17.756827206688364]
  Influence Maximization is the task of selecting optimal nodes maximising the influence spread in social networks. This study proposes a Discretized Quantum-based Salp Swarm Algorithm (DQSSA) for optimizing influence diffusion in social networks.
  arXiv  Detail & Related papers  (2023-11-30T16:23:44Z)
• IDEAL: Influence-Driven Selective Annotations Empower In-Context Learners in Large Language Models [66.32043210237768]
  This paper introduces an influence-driven selective annotation method. It aims to minimize annotation costs while improving the quality of in-context examples. Experiments confirm the superiority of the proposed method on various benchmarks.
  arXiv  Detail & Related papers  (2023-10-16T22:53:54Z)
• Importance-Weighted Offline Learning Done Right [16.4989952150404]
  We study the problem of offline policy optimization in contextual bandit problems. The goal is to learn a near-optimal policy based on a dataset of decision data collected by a suboptimal behavior policy. We show that a simple alternative approach based on the "implicit exploration" estimator of citet2015 yields performance guarantees that are superior in nearly all possible terms to all previous results.
  arXiv  Detail & Related papers  (2023-09-27T16:42:10Z)
• Understanding Influence Maximization via Higher-Order Decomposition [6.542119695695405]
  Influence Maximization (IM) has garnered considerable attention over the last couple of decades. This work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index. An IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes.
  arXiv  Detail & Related papers  (2022-07-16T04:44:16Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  We consider an adaptive version of content-dependent online influence problem where seed nodes are sequentially activated based on realtime feedback. Our algorithm maintains a network model estimate and selects seed adaptively, exploring the social network while improving the optimal policy optimistically.
  arXiv  Detail & Related papers  (2022-06-29T18:17:28Z)
• Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach (Extended Version) [73.59962178534361]
  We study an influence problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaign. We describe and compare two methods of contextual multi-armed bandits, with upper-confidence bounds on the remaining potential of influencers.
  arXiv  Detail & Related papers  (2022-01-13T22:06:10Z)
• Learning to maximize global influence from local observations [12.611900695498218]
  We study a family online influence problems where in a sequence of rounds $t=1,ldots,T$, a decision maker selects one from a large number of agents with the goal of maximizing influence. The goal of the decision maker is to select the sequence of agents in a way that the total number of influenced nodes in the network.
  arXiv  Detail & Related papers  (2021-09-24T11:59:44Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Influence Maximization Under Generic Threshold-based Non-submodular Model [1.5780411262109524]
  Concept of social influence is coined, where the goal is to select a number of most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. In this paper, we propose seed selection strategies using network graphical in a generalized threshold-based model, called influence barricade model, which is non-submodular. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence.
  arXiv  Detail & Related papers  (2020-12-18T16:14:49Z)
• Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback [15.533908352376853]
  We look for a set of $k$ nodes that maximize the expected number of nodes that are reached by an influence cascade. We show that the adaptivity gap is upper-bounded by $lceil nrceil $, where $n$ is the number of nodes in the graph. We also show that in 0-bounded graphs, i.e. undirected graphs, the adaptivity gap is at most $frac3e3e3-1approx 3.16$.
  arXiv  Detail & Related papers  (2020-06-27T14:43:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.