Viral Marketing in Social Networks with Competing Products

• URL: http://arxiv.org/abs/2312.15819v1
• Date: Mon, 25 Dec 2023 21:59:15 GMT
• Title: Viral Marketing in Social Networks with Competing Products
• Authors: Ahad N. Zehmakan, Xiaotian Zhou, Zhongzhi Zhang
• Abstract summary: We provide a time approximation algorithm for selecting red seed nodes in a network. Our experiments on various real-world and synthetic networks demonstrate that our proposed algorithm outperforms other algorithms. In particular, we prove several tight bounds on the convergence time in terms of different graph parameters, such as the number of nodes/edges, maximum out-degree and diameter.
• Score: 23.48809201078124
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider a directed network where each node is either red (using the red product), blue (using the blue product), or uncolored (undecided). Then in each round, an uncolored node chooses red (resp. blue) with some probability proportional to the number of its red (resp. blue) out-neighbors. What is the best strategy to maximize the expected final number of red nodes given the budget to select $k$ red seed nodes? After proving that this problem is computationally hard, we provide a polynomial time approximation algorithm with the best possible approximation guarantee, building on the monotonicity and submodularity of the objective function and exploiting the Monte Carlo method. Furthermore, our experiments on various real-world and synthetic networks demonstrate that our proposed algorithm outperforms other algorithms. Additionally, we investigate the convergence time of the aforementioned process both theoretically and experimentally. In particular, we prove several tight bounds on the convergence time in terms of different graph parameters, such as the number of nodes/edges, maximum out-degree and diameter, by developing novel proof techniques.

Related papers

• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  This paper proposes a hybrid variational quantum algorithm to solve the $k$-coloring problem of graph vertices. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring. We apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
  arXiv  Detail & Related papers  (2025-04-30T05:45:15Z)
• A Generalisation of Voter Model: Influential Nodes and Convergence Properties [5.4327243200369555]
  We introduce and study a generalisation of the voter model. We study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms.
  arXiv  Detail & Related papers  (2024-11-07T09:38:42Z)
• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  We introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth.
  arXiv  Detail & Related papers  (2024-06-18T12:16:00Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. We present a novel algorithmic approach to find a proper colouring of a graph with $d$ colours, if it exists.
  arXiv  Detail & Related papers  (2021-11-29T09:17:34Z)
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks [19.767938436958296]
  We propose a distributed, cubic-regularized Newton method for large-scale convex optimization over networks. We show a $O(k-3)$ convergence rate when the cost function is convex with Lipschitz gradient and Hessian, with $k$ being the number of iterations.
  arXiv  Detail & Related papers  (2020-07-07T15:38:47Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  We propose a novel pool-based Active Learning framework constructed on a sequential Graph Convolution Network (GCN) With a small number of randomly sampled images as seed labelled examples, we learn the parameters of the graph to distinguish labelled vs unlabelled nodes. We exploit these characteristics of GCN to select the unlabelled examples which are sufficiently different from labelled ones.
  arXiv  Detail & Related papers  (2020-06-18T00:55:10Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  We propose a framework to generate adversarial examples in one of the most challenging black-box settings. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples.
  arXiv  Detail & Related papers  (2020-03-13T20:03:01Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  This paper proposes a emphfully asynchronous scheme for the policy evaluation problem of distributed reinforcement learning (DisRL) over directed peer-to-peer networks. Without waiting for any other node of the network, each node can locally update its value function at any time by using (possibly delayed) information from its neighbors.
  arXiv  Detail & Related papers  (2020-03-01T08:12:08Z)
• Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
  We perform a massive evaluation of neural networks with architectures corresponding to random graphs of various types. We find that none of the classical numerical graph invariants by itself allows to single out the best networks. We also find that networks with primarily short-range connections perform better than networks which allow for many long-range connections.
  arXiv  Detail & Related papers  (2020-02-19T11:04:49Z)

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.