An official website of the United States government
Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomesPSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of asingleedge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs.
more »
« less
Integrability of generalised skew-symmetric replicator equations via graph embeddings
Abstract It is known that there is a one-to-one mapping between oriented directed graphs and zero-sum replicator dynamics (Lotka–Volterra equations) and that furthermore these dynamics are Hamiltonian in an appropriately defined nonlinear Poisson bracket. In this paper, we investigate the problem of determining whether these dynamics are Liouville–Arnold integrable, building on prior work in graph decloning by Evripidouet al(2022J. Phys. A: Math. Theor.55325201) and graph embedding by Paik and Griffin (2024Phys. Rev.E107L052202). Using the embedding procedure from Paik and Griffin, we show (with certain caveats) that when a graph producing integrable dynamics is embedded in another graph producing integrable dynamics, the resulting graph structure also produces integrable dynamics. We also construct a new family of graph structures that produces integrable dynamics that does not arise either from embeddings or decloning. We use these results, along with numerical methods, to classify the dynamics generated by almost all oriented directed graphs on six vertices, with three hold-out graphs that generate integrable dynamics and are not part of a natural taxonomy arising from known families and graph operations. These hold-out graphs suggest more structure is available to be found. Moreover, the work suggests that oriented directed graphs leading to integrable dynamics may be classifiable in an analogous way to the classification of finite simple groups, creating the possibility that there is a deep connection between integrable dynamics and combinatorial structures in graphs.
more »
« less
- Award ID(s):
- 1932991
- PAR ID:
- 10559855
- Publisher / Repository:
- IOP Publishing
- Date Published:
- Journal Name:
- Journal of Physics A: Mathematical and Theoretical
- Volume:
- 58
- Issue:
- 1
- ISSN:
- 1751-8113
- Format(s):
- Medium: X Size: Article No. 015701
- Size(s):
- Article No. 015701
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Recently, graph neural network (GNN)-based algorithms were proposed to solve a variety of combinatorial optimization problems [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)]. GNN was tested in particular on randomly generated instances of these problems. The publication [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)] stirred a debate whether the GNN-based method was adequately benchmarked against best prior methods. In particular, critical commentaries [M. C. Angelini, F. Ricci-Tersenghi,Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher,Nat. Mach. Intell.5, 24–25 (2023)] point out that a simple greedy algorithm performs better than the GNN. We do not intend to discuss the merits of arguments and counterarguments in these papers. Rather, in this note, we establish a fundamental limitation for running GNN on random instances considered in these references, for a broad range of choices of GNN architecture. Specifically, these barriers hold when the depth of GNN does not scale with graph size (we note that depth 2 was used in experiments in [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber,Nat. Mach. Intell.4, 367–377 (2022)]), and importantly, these barriers hold regardless of any other parameters of GNN architecture. These limitations arise from the presence of the overlap gap property (OGP) phase transition, which is a barrier for many algorithms, including importantly local algorithms, of which GNN is an example. At the same time, some algorithms known prior to the introduction of GNN provide best results for these problems up to the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this, we side with the conclusions made in [M. C. Angelini, F. Ricci-Tersenghi,Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher,Nat. Mach. Intell.5, 24–25 (2023)].more » « less
-
Directed graphs have been widely used in Community Question Answering services (CQAs) to model asymmetric relationships among different types of nodes in CQA graphs, e.g., question, answer, user. Asymmetric transitivity is an essential property of directed graphs, since it can play an important role in downstream graph inference and analysis. Question difficulty and user expertise follow the characteristic of asymmetric transitivity. Maintaining such properties, while reducing the graph to a lower dimensional vector embedding space, has been the focus of much recent research. In this paper, we tackle the challenge of directed graph embedding with asymmetric transitivity preservation and then leverage the proposed embedding method to solve a fundamental task in CQAs: how to appropriately route and assign newly posted questions to users with the suitable expertise and interest in CQAs. The technique incorporates graph hierarchy and reachability information naturally by relying on a nonlinear transformation that operates on the core reachability and implicit hierarchy within such graphs. Subsequently, the methodology levers a factorization-based approach to generate two embedding vectors for each node within the graph, to capture the asymmetric transitivity. Extensive experiments show that our framework consistently and significantly outperforms the state-of-the-art baselines on three diverse realworld tasks: link prediction, and question difficulty estimation and expert finding in online forums like Stack Exchange. Particularly, our framework can support inductive embedding learning for newly posted questions (unseen nodes during training), and therefore can properly route and assign these kinds of questions to experts in CQAs.more » « less
-
ter Beek, Maurice; Koutny, Maciej; Rozenberg, Grzegorz (Ed.)For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices.more » « less
-
Recent spectral graph sparsificationresearch aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly linear time numerical and graph algorithms. However, there is very limited progress in the spectral sparsification of directed graphs. In this work, we prove the existence of nearly linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors.more » « less
