A QUBO formulation for top-$\tau$ eigencentrality nodes

• URL: http://arxiv.org/abs/2105.00172v4
• Date: Sun, 10 Jul 2022 01:44:14 GMT
• Title: A QUBO formulation for top-$\tau$ eigencentrality nodes
• Authors: Prosper D. Akrobotu, Tamsin E. James, Christian F. A. Negre, and Susan M. Mniszewski
• Abstract summary: We lay the foundations for solving the eigencentrality problem of ranking the importance of the nodes of a network with scores from the eigenvector of the network. The problem is reformulated as a quadratic unconstrained binary optimization (QUBO) that can be solved on both quantum architectures. The results focus on correctly identifying a given number of the most important nodes in numerous networks given by the sparse vector solution of our QUBO formulation of the problem of identifying the top-$tau$ highest eigencentrality nodes in a network on both the D-Wave and IBM quantum computers.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The efficient calculation of the centrality or "hierarchy" of nodes in a network has gained great relevance in recent years due to the generation of large amounts of data. The eigenvector centrality (aka eigencentrality) is quickly becoming a good metric for centrality due to both its simplicity and fidelity. In this work we lay the foundations for solving the eigencentrality problem of ranking the importance of the nodes of a network with scores from the eigenvector of the network, using quantum computational paradigms such as quantum annealing and gate-based quantum computing. The problem is reformulated as a quadratic unconstrained binary optimization (QUBO) that can be solved on both quantum architectures. The results focus on correctly identifying a given number of the most important nodes in numerous networks given by the sparse vector solution of our QUBO formulation of the problem of identifying the top-$\tau$ highest eigencentrality nodes in a network on both the D-Wave and IBM quantum computers

Related papers

• Core-Intermediate-Peripheral Index: Factor Analysis of Neighborhood and Shortest Paths-based Centrality Metrics [0.0]
  We propose a novel measure called the Core- Intermediate-Peripheral (CIP) Index to capture the extent with which a node could play the role of a core node. We test our approach on a diverse suite of 12 complex real-world networks.
  arXiv  Detail & Related papers  (2023-10-10T06:52:20Z)
• A Control Architecture for Entanglement Generation Switches in Quantum Networks [1.0282274843007797]
  Entanglement between quantum network nodes is often produced using intermediary devices - such as heralding stations - as a resource. Here, we propose a cost-effective architecture to connect many quantum network nodes via a central quantum network hub called an Entanglement Generation Switch (EGS) The EGS allows multiple quantum nodes to be connected at a fixed resource cost, by sharing the resources needed to make entanglement.
  arXiv  Detail & Related papers  (2023-09-05T10:06:48Z)
• Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing [52.402550431781805]
  Decentralized federated learning (DFL) has gained popularity due to its practicality across various applications. Compared to the centralized version, training a shared model among a large number of nodes in DFL is more challenging. We develop a novel algorithm based on the framework of the inexact alternating direction method (iADM)
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• Network Centralities in Quantum Entanglement Distribution due to User Preferences [5.243460995467895]
  This paper studies the centralities of the network when the link layer topology of entanglements is driven by usage patterns of peer-to-peer connections. It shows that the edge centralities (measured as usage of individual edges during entanglement distribution) of the entangled graph follow power law distributions. These findings will help in quantum resource management, e.g., quantum technology with high reliability and lower decoherence time may be allocated to edges with high centralities.
  arXiv  Detail & Related papers  (2023-08-16T07:00:09Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• Identifying Influential Nodes in Two-mode Data Networks using Formal Concept Analysis [0.0]
  Bi-face (BF) is a new bipartite centrality measurement for identifying important nodes in two-mode networks. Unlike off-the shelf centrality indices, it quantifies how a node has a cohesive-substructure influence on its neighbour nodes via bicliques. Our experiments on several real-world and synthetic networks show the efficiency of BF over existing prominent bipartite centrality measures.
  arXiv  Detail & Related papers  (2021-09-07T23:57:05Z)
• Quantum Federated Learning with Quantum Data [87.49715898878858]
  Quantum machine learning (QML) has emerged as a promising field that leans on the developments in quantum computing to explore large complex machine learning problems. This paper proposes the first fully quantum federated learning framework that can operate over quantum data and, thus, share the learning of quantum circuit parameters in a decentralized manner.
  arXiv  Detail & Related papers  (2021-05-30T12:19:27Z)
• Entanglement Rate Optimization in Heterogeneous Quantum Communication Networks [79.8886946157912]
  Quantum communication networks are emerging as a promising technology that could constitute a key building block in future communication networks in the 6G era and beyond. Recent advances led to the deployment of small- and large-scale quantum communication networks with real quantum hardware. In quantum networks, entanglement is a key resource that allows for data transmission between different nodes.
  arXiv  Detail & Related papers  (2021-05-30T11:34:23Z)
• Approximating Network Centrality Measures Using Node Embedding and Machine Learning [0.0]
  We propose an approach for efficiently approximating node centralities for large networks using Neural Networks and Graph Embedding techniques. Our proposed model, entitled Network Centrality Approximation using Graph Embedding (NCA-GE), uses the adjacency matrix of a graph and a set of features for each node. NCA-GE has a time complexity of $O(|E|)$, $E$ being the set of edges of a graph, making it suitable for large networks.
  arXiv  Detail & Related papers  (2020-06-29T21:19:40Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
  We consider a decentralized learning problem where data points are distributed among computing nodes communicating over a directed graph. As the model size gets large, decentralized learning faces a major bottleneck that is the communication load due to each node transmitting messages (model updates) to its neighbors. We propose the quantized decentralized learning algorithm over directed graphs that is based on the push-sum algorithm in decentralized consensus optimization.
  arXiv  Detail & Related papers  (2020-02-23T18:25:39Z)

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.