To see the other types of publications on this topic, follow the link: Graph dynamics.
Journal articles on the topic 'Graph dynamics'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Graph dynamics.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Huang, Xueqin, Xianqiang Zhu, Xiang Xu, Qianzhen Zhang, and Ailin Liang. "Parallel Learning of Dynamics in Complex Systems." Systems 10, no. 6 (2022): 259. http://dx.doi.org/10.3390/systems10060259.
Full textAbstract:
Dynamics always exist in complex systems. Graphs (complex networks) are a mathematical form for describing a complex system abstractly. Dynamics can be learned efficiently from the structure and dynamics state of a graph. Learning the dynamics in graphs plays an important role in predicting and controlling complex systems. Most of the methods for learning dynamics in graphs run slowly in large graphs. The complexity of the large graph’s structure and its nonlinear dynamics aggravate this problem. To overcome these difficulties, we propose a general framework with two novel methods in this paper, the Dynamics-METIS (D-METIS) and the Partitioned Graph Neural Dynamics Learner (PGNDL). The general framework combines D-METIS and PGNDL to perform tasks for large graphs. D-METIS is a new algorithm that can partition a large graph into multiple subgraphs. D-METIS innovatively considers the dynamic changes in the graph. PGNDL is a new parallel model that consists of ordinary differential equation systems and graph neural networks (GNNs). It can quickly learn the dynamics of subgraphs in parallel. In this framework, D-METIS provides PGNDL with partitioned subgraphs, and PGNDL can solve the tasks of interpolation and extrapolation prediction. We exhibit the universality and superiority of our framework on four kinds of graphs with three kinds of dynamics through an experiment.
2
Li, Jintang, Zhouxin Yu, Zulun Zhu, et al. "Scaling Up Dynamic Graph Representation Learning via Spiking Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 7 (2023): 8588–96. http://dx.doi.org/10.1609/aaai.v37i7.26034.
Full textAbstract:
Recent years have seen a surge in research on dynamic graph representation learning, which aims to model temporal graphs that are dynamic and evolving constantly over time. However, current work typically models graph dynamics with recurrent neural networks (RNNs), making them suffer seriously from computation and memory overheads on large temporal graphs. So far, scalability of dynamic graph representation learning on large temporal graphs remains one of the major challenges. In this paper, we present a scalable framework, namely SpikeNet, to efficiently capture the temporal and structural patterns of temporal graphs. We explore a new direction in that we can capture the evolving dynamics of temporal graphs with spiking neural networks (SNNs) instead of RNNs. As a low-power alternative to RNNs, SNNs explicitly model graph dynamics as spike trains of neuron populations and enable spike-based propagation in an efficient way. Experiments on three large real-world temporal graph datasets demonstrate that SpikeNet outperforms strong baselines on the temporal node classification task with lower computational costs. Particularly, SpikeNet generalizes to a large temporal graph (2.7M nodes and 13.9M edges) with significantly fewer parameters and computation overheads.
3
Zhang, Lei, Zhiqian Chen, Chang-Tien Lu, and Liang Zhao. "From “Dynamics on Graphs” to “Dynamics of Graphs”: An Adaptive Echo-State Network Solution (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (2022): 13111–12. http://dx.doi.org/10.1609/aaai.v36i11.21692.
Full textAbstract:
Many real-world networks evolve over time, which results in dynamic graphs such as human mobility networks and brain networks. Usually, the “dynamics on graphs” (e.g., node attribute values evolving) are observable, and may be related to and indicative of the underlying “dynamics of graphs” (e.g., evolving of the graph topology). Traditional RNN-based methods are not adaptive or scalable for learn- ing the unknown mappings between two types of dynamic graph data. This study presents a AD-ESN, and adaptive echo state network that can automatically learn the best neural net- work architecture for certain data while keeping the efficiency advantage of echo state networks. We show that AD-ESN can successfully discover the underlying pre-defined map- ping function and unknown nonlinear map-ping between time series and graphs.
4
Ahmed Mouhamadou WADE. "Tight bounds on exploration of constantly connected cacti-paths." World Journal of Advanced Research and Reviews 12, no. 1 (2021): 355–61. http://dx.doi.org/10.30574/wjarr.2021.12.1.0534.
Full textAbstract:
In this paper, we study the necessary and sufficient time to explore constantly connected dynamics graphs by a mobile entity (agent). A dynamic graph is constantly connected if for each time units, there exists a stable connected spanning tree [10]. We focus on the case where the underlying graph is a cactus-path (graph reduced to a path of k rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that 5n - Θ(1) time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path 〖Ch〗_(2,n) (composed of two same size ringsn). The upper bound is generalized on dynamic graphs based on cacti-paths with k rings. We show that for any constantly connected dynamic graph of size N based on a cactus-path, 4N -max{n_1,n_k} -3k -3 time units are sufficient to explore the graph, with k the length of the path, N=∑_(i=1)^k▒n_i -k+1 the size of the dynamic graph and n_i the size of the ring which is at position i starting from left to right.
5
Di Ianni, Miriam. "Game of Life-like Opinion Dynamics: Generalizing the Underpopulation Rule." AppliedMath 3, no. 1 (2022): 10–36. http://dx.doi.org/10.3390/appliedmath3010002.
Full textAbstract:
Graph dynamics for a node-labeled graph is a set of updating rules describing how the labels of each node in the graph change in time as a function of the global set of labels. The underpopulation rule is graph dynamics derived by simplifying the set of rules constituting the Game of Life. It is known that the number of label configurations met by a graph during the dynamic process defined by such rule is bounded by a polynomial in the size of the graph if the graph is undirected. As a consequence, predicting the labels evolution is an easy problem (i.e., a problem in P) in such a case. In this paper, the generalization of the underpopulation rule to signed and directed graphs is studied. It is here proved that the number of label configurations met by a graph during the dynamic process defined by any so generalized underpopulation rule is still bounded by a polynomial in the size of the graph if the graph is undirected and structurally balanced, while it is not bounded by any polynomial in the size of the graph if the graph is directed although unsigned unless P = PSpace.
6
Mouhamadou Wade, Ahmed. "EXPLORATION WITH RETURN OF HIGHLY DYNAMIC NETWORKS." International Journal of Advanced Research 9, no. 10 (2021): 315–19. http://dx.doi.org/10.21474/ijar01/13550.
Full textAbstract:
In this paper, we study the necessary and sufficient time to explore with return constantly connected dynamic networks modelled by a dynamic graphs. Exploration with return consists, for an agent operating in a dynamic graph, of visiting all the vertices of the graph and returning to the starting vertex. We show that for constantly connected dynamic graphs based on a ring of sizen,3n-4 time units are necessary and sufficient to explore it. Assuming that the agent knows the dynamics of the graph.
7
Chen, Haiyan, and Fuji Zhang. "Spectral Dynamics of Graph Sequences Generated by Subdivision and Triangle Extension." Electronic Journal of Linear Algebra 32 (February 6, 2017): 454–63. http://dx.doi.org/10.13001/1081-3810.3583.
Full textAbstract:
For a graph G and a unary graph operation X, there is a graph sequence \G_k generated by G_0=G and G_{k+1}=X(G_k). Let Sp({G_k}) denote the set of normalized Laplacian eigenvalues of G_k. The set of limit points of \bigcup_{k=0}^\infty Sp(G_k)$, $\liminf_{k\rightarrow\infty}Sp(G_k) and $\limsup_{k\rightarrow \infty}Sp(G_k)$ are considered in this paper for graph sequences generated by two operations: subdivision and triangle extension. It is obtained that the spectral dynamic of graph sequence generated by subdivision is determined by a quadratic function, which is closely related to the the well-known logistic map; while that generated by triangle extension is determined by a linear function. By using the knowledge of dynamic system, the spectral dynamics of graph sequences generated by these two operations are characterized. For example, it is found that, for any initial non-trivial graph $G$, chaos takes place in the spectral dynamics of iterated subdivision graphs, and the set of limit points is the entire closed interval [0,2].
8
Chen, Lanlan, Kai Wu, Jian Lou, and Jing Liu. "Signed Graph Neural Ordinary Differential Equation for Modeling Continuous-Time Dynamics." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (2024): 8292–301. http://dx.doi.org/10.1609/aaai.v38i8.28670.
Full textAbstract:
Modeling continuous-time dynamics constitutes a foundational challenge, and uncovering inter-component correlations within complex systems holds promise for enhancing the efficacy of dynamic modeling. The prevailing approach of integrating graph neural networks with ordinary differential equations has demonstrated promising performance. However, they disregard the crucial signed information potential on graphs, impeding their capacity to accurately capture real-world phenomena and leading to subpar outcomes. In response, we introduce a novel approach: a signed graph neural ordinary differential equation, adeptly addressing the limitations of miscapturing signed information. Our proposed solution boasts both flexibility and efficiency. To substantiate its effectiveness, we seamlessly integrate our devised strategies into three preeminent graph-based dynamic modeling frameworks: graph neural ordinary differential equations, graph neural controlled differential equations, and graph recurrent neural networks. Rigorous assessments encompass three intricate dynamic scenarios from physics and biology, as well as scrutiny across four authentic real-world traffic datasets. Remarkably outperforming the trio of baselines, empirical results underscore the substantial performance enhancements facilitated by our proposed approach. Our code can be found at https://github.com/beautyonce/SGODE.
9
Fahrenthold, E. P., and J. D. Wargo. "Lagrangian Bond Graphs for Solid Continuum Dynamics Modeling." Journal of Dynamic Systems, Measurement, and Control 116, no. 2 (1994): 178–92. http://dx.doi.org/10.1115/1.2899209.
Full textAbstract:
The limitations of existing continuum bond graph modeling techniques have effectively precluded their use in large order problems, where nonrepetitive graph structures and causal patterns are normally present. As a result, despite extensive publication of bond graph models for continuous systems simulations, bond graph methods have not offered a viable alternative to finite element analysis for the vast majority of practical problems. However, a new modeling approach combining Lagrangian (mass fixed) bond graphs with a selected finite element discretization scheme allows for direct simulation of a wide range of large order solid continuum dynamics problems. With appropriate modifications, including the use of Eulerian (space fixed) bond graphs, the method may be extended to include fluid dynamics modeling.
10
Chen, Libin, Luyao Wang, Chengyi Zeng, Hongfu Liu, and Jing Chen. "DHGEEP: A Dynamic Heterogeneous Graph-Embedding Method for Evolutionary Prediction." Mathematics 10, no. 22 (2022): 4193. http://dx.doi.org/10.3390/math10224193.
Full textAbstract:
Current graph-embedding methods mainly focus on static homogeneous graphs, where the entity type is the same and the topology is fixed. However, in real networks, such as academic networks and shopping networks, there are typically various types of nodes and temporal interactions. The dynamical and heterogeneous components of graphs in general contain abundant information. Currently, most studies on dynamic graphs do not sufficiently consider the heterogeneity of the network in question, and hence the semantic information of the interactions between heterogeneous nodes is missing in the graph embeddings. On the other hand, the overall size of the network tends to accumulate over time, and its growth rate can reflect the ability of the entire network to generate interactions of heterogeneous nodes; therefore, we developed a graph dynamics model to model the evolution of graph dynamics. Moreover, the temporal properties of nodes regularly affect the generation of temporal interaction events with which they are connected. Thus, we developed a node dynamics model to model the evolution of node connectivity. In this paper, we propose DHGEEP, a dynamic heterogeneous graph-embedding method based on the Hawkes process, to predict the evolution of dynamic heterogeneous networks. The model considers the generation of temporal events as an effect of historical events, introduces the Hawkes process to simulate this evolution, and then captures semantic and structural information based on the meta-paths of temporal heterogeneous nodes. Finally, the graph-level dynamics of the network and the node-level dynamics of each node are integrated into the DHGEEP framework. The embeddings of the nodes are automatically obtained by minimizing the value of the loss function. Experiments were conducted on three downstream tasks, static link prediction, temporal event prediction for homogeneous nodes, and temporal event prediction for heterogeneous nodes, on three datasets. Experimental results show that DHGEEP achieves excellent performance in these tasks. In the most significant task, temporal event prediction of heterogeneous nodes, the values of precision@2 and recall@2 can reach 30.23% and 10.48% on the AMiner dataset, and reach 4.56% and 1.61% on the DBLP dataset, so that our method is more accurate at predicting future temporal events than the baseline.
11
Arrighi, Pablo, and Gilles Dowek. "Causal graph dynamics." Information and Computation 223 (February 2013): 78–93. http://dx.doi.org/10.1016/j.ic.2012.10.019.
Full text
12
SAXENA, NITIN, SIMONE SEVERINI, and IGOR E. SHPARLINSKI. "PARAMETERS OF INTEGRAL CIRCULANT GRAPHS AND PERIODIC QUANTUM DYNAMICS." International Journal of Quantum Information 05, no. 03 (2007): 417–30. http://dx.doi.org/10.1142/s0219749907002918.
Full textAbstract:
The intention of the paper is to move a step towards a classification of network topologies that exhibit periodic quantum dynamics. We show that the evolution of a quantum system whose hamiltonian is identical to the adjacency matrix of a circulant graph is periodic if and only if all eigenvalues of the graph are integers (that is, the graph is integral). Motivated by this observation, we focus on relevant properties of integral circulant graphs. Specifically, we bound the number of vertices of integral circulant graphs in terms of their degree, characterize bipartiteness and give exact bounds for their diameter. Additionally, we prove that circulant graphs with odd order do not allow perfect state transfer.
13
Mai, Weimin, Junxin Chen, and Xiang Chen. "Time-Evolving Graph Convolutional Recurrent Network for Traffic Prediction." Applied Sciences 12, no. 6 (2022): 2842. http://dx.doi.org/10.3390/app12062842.
Full textAbstract:
Accurate traffic prediction is crucial to the construction of intelligent transportation systems. This task remains challenging because of the complicated and dynamic spatiotemporal dependency in traffic networks. While various graph-based spatiotemporal networks have been proposed for traffic prediction, most of them rely on predefined graphs from different views or static adaptive matrices. Some implicit dynamics of inter-node dependency may be neglected, which limits the performance of prediction. To address this problem and make more accurate predictions, we propose a traffic prediction model named Time-Evolving Graph Convolution Recurrent Network (TEGCRN), which takes advantage of time-evolving graph convolution to capture the dynamic inter-node dependency adaptively at different time slots. Specifically, we first propose a tensor-composing method to generate adaptive time-evolving adjacency graphs. Based on these time-evolving graphs and a predefined distance-based graph, a graph convolution module with mix-hop operation is applied to extract comprehensive inter-node information. Then the resulting graph convolution module is integrated into the Recurrent Neural Network structure to form an general predicting model. Experiments on two real-world traffic datasets demonstrate the superiority of TEGCRN over multiple competitive baseline models, especially in short-term prediction, which also verifies the effectiveness of time-evolving graph convolution in capturing more comprehensive inter-node dependency.
14
Sun, Li, Zhongbao Zhang, Jiawei Zhang, et al. "Hyperbolic Variational Graph Neural Network for Modeling Dynamic Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 5 (2021): 4375–83. http://dx.doi.org/10.1609/aaai.v35i5.16563.
Full textAbstract:
Learning representations for graphs plays a critical role in a wide spectrum of downstream applications. In this paper, we summarize the limitations of the prior works in three folds: representation space, modeling dynamics and modeling uncertainty. To bridge this gap, we propose to learn dynamic graph representations in hyperbolic space, for the first time, which aims to infer stochastic node representations. Working with hyperbolic space, we present a novel Hyperbolic Variational Graph Neural Network, referred to as HVGNN. In particular, to model the dynamics, we introduce a Temporal GNN (TGNN) based on a theoretically grounded time encoding approach. To model the uncertainty, we devise a hyperbolic graph variational autoencoder built upon the proposed TGNN to generate stochastic node representations of hyperbolic normal distributions. Furthermore, we introduce a reparameterisable sampling algorithm for the hyperbolic normal distribution to enable the gradient-based learning of HVGNN. Extensive experiments show that HVGNN outperforms state-of-the-art baselines on real-world datasets.
15
Yang, Yu, An Wang, Hua Wang, Wei-Ting Zhao, and Dao-Qiang Sun. "On Subtrees of Fan Graphs, Wheel Graphs, and “Partitions” of Wheel Graphs under Dynamic Evolution." Mathematics 7, no. 5 (2019): 472. http://dx.doi.org/10.3390/math7050472.
Full textAbstract:
The number of subtrees, or simply the subtree number, is one of the most studied counting-based graph invariants that has applications in many interdisciplinary fields such as phylogenetic reconstruction. Motivated from the study of graph surgeries on evolutionary dynamics, we consider the subtree problems of fan graphs, wheel graphs, and the class of graphs obtained from “partitioning” wheel graphs under dynamic evolution. The enumeration of these subtree numbers is done through the so-called subtree generation functions of graphs. With the enumerative result, we briefly explore the extremal problems in the corresponding class of graphs. Some interesting observations on the behavior of the subtree number are also presented.
16
Zhu, Jiawei, Bo Li, Zhenshi Zhang, Ling Zhao, and Haifeng Li. "High-Order Topology-Enhanced Graph Convolutional Networks for Dynamic Graphs." Symmetry 14, no. 10 (2022): 2218. http://dx.doi.org/10.3390/sym14102218.
Full textAbstract:
Understanding the evolutionary mechanisms of dynamic graphs is crucial since dynamic is a basic characteristic of real-world networks. The challenges of modeling dynamic graphs are as follows: (1) Real-world dynamics are frequently characterized by group effects, which essentially emerge from high-order interactions involving groups of entities. Therefore, the pairwise interactions revealed by the edges of graphs are insufficient to describe complex systems. (2) The graph data obtained from real systems are often noisy, and the spurious edges can interfere with the stability and efficiency of models. To address these issues, we propose a high-order topology-enhanced graph convolutional network for modeling dynamic graphs. The rationale behind it is that the symmetric substructure in a graph, called the maximal clique, can reflect group impacts from high-order interactions on the one hand, while not being readily disturbed by spurious links on the other hand. Then, we utilize two independent branches to model the distinct influence mechanisms of the two effects. Learnable parameters are used to tune the relative importance of the two effects during the process. We conduct link predictions on real-world datasets, including one social network and two citation networks. Results show that the average improvements of the high-order enhanced methods are 68%, 15%, and 280% over the corresponding backbones across datasets. The ablation study and perturbation analysis validate the effectiveness and robustness of the proposed method. Our research reveals that high-order structures provide new perspectives for studying the dynamics of graphs and highlight the necessity of employing higher-order topologies in the future.
17
Pan, Liming, Cheng Shi, and Ivan Dokmanic. "A Graph Dynamics Prior for Relational Inference." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 13 (2024): 14508–16. http://dx.doi.org/10.1609/aaai.v38i13.29366.
Full textAbstract:
Relational inference aims to identify interactions between parts of a dynamical system from the observed dynamics. Current state-of-the-art methods fit the dynamics with a graph neural network (GNN) on a learnable graph. They use one-step message-passing GNNs---intuitively the right choice since non-locality of multi-step or spectral GNNs may confuse direct and indirect interactions. But the effective interaction graph depends on the sampling rate and it is rarely localized to direct neighbors, leading to poor local optima for the one-step model. In this work, we propose a graph dynamics prior (GDP) for relational inference. GDP constructively uses error amplification in non-local polynomial filters to steer the solution to the ground-truth graph. To deal with non-uniqueness, GDP simultaneously fits a ``shallow'' one-step model and a polynomial multi-step model with shared graph topology. Experiments show that GDP reconstructs graphs far more accurately than earlier methods, with remarkable robustness to under-sampling. Since appropriate sampling rates for unknown dynamical systems are not known a priori, this robustness makes GDP suitable for real applications in scientific machine learning. Reproducible code is available at https://github.com/DaDaCheng/GDP.
18
PREVITE, JOSEPH P. "Graph substitutions." Ergodic Theory and Dynamical Systems 18, no. 3 (1998): 661–85. http://dx.doi.org/10.1017/s0143385798108234.
Full textAbstract:
In 1984, Gromov (see [4] and [6]) introduced the idea of subdividing a ‘branching’ polyhedron into smaller cells and replacing these cells by more complex objects, reminiscent of the growth of multicellular organisms in biology. The simplest situation of this kind is a graph substitution which replaces certain subgraphs in a graph $G$ by bigger finite graphs. The most basic graph substitution is a vertex replacement rule which replaces certain vertices of $G$ with finite graphs. This paper develops a framework for studying vertex replacements and discusses the asymptotic behavior of iterated vertex replacements, the limit objects, and the induced dynamics on the space of infinite graphs from the viewpoint of geometry and dynamical systems.
19
Nair, Aditya G., and Kunihiko Taira. "Network-theoretic approach to sparsified discrete vortex dynamics." Journal of Fluid Mechanics 768 (March 10, 2015): 549–71. http://dx.doi.org/10.1017/jfm.2015.97.
Full textAbstract:
We examine discrete vortex dynamics in two-dimensional flow through a network-theoretic approach. The interaction of the vortices is represented with a graph, which allows the use of network-theoretic approaches to identify key vortex-to-vortex interactions. We employ sparsification techniques on these graph representations based on spectral theory to construct sparsified models and evaluate the dynamics of vortices in the sparsified set-up. Identification of vortex structures based on graph sparsification and sparse vortex dynamics is illustrated through an example of point-vortex clusters interacting amongst themselves. We also evaluate the performance of sparsification with increasing number of point vortices. The sparsified-dynamics model developed with spectral graph theory requires a reduced number of vortex-to-vortex interactions but agrees well with the full nonlinear dynamics. Furthermore, the sparsified model derived from the sparse graphs conserves the invariants of discrete vortex dynamics. We highlight the similarities and differences between the present sparsified-dynamics model and reduced-order models.
20
Chen, Lei, Jing Zhang, and Li-Jun Cai. "Overlapping community detection based on link graph using distance dynamics." International Journal of Modern Physics B 32, no. 03 (2018): 1850015. http://dx.doi.org/10.1142/s0217979218500157.
Full textAbstract:
The distance dynamics model was recently proposed to detect the disjoint community of a complex network. To identify the overlapping structure of a network using the distance dynamics model, an overlapping community detection algorithm, called L-Attractor, is proposed in this paper. The process of L-Attractor mainly consists of three phases. In the first phase, L-Attractor transforms the original graph to a link graph (a new edge graph) to assure that one node has multiple distances. In the second phase, using the improved distance dynamics model, a dynamic interaction process is introduced to simulate the distance dynamics (shrink or stretch). Through the dynamic interaction process, all distances converge, and the disjoint community structure of the link graph naturally manifests itself. In the third phase, a recovery method is designed to convert the disjoint community structure of the link graph to the overlapping community structure of the original graph. Extensive experiments are conducted on the LFR benchmark networks as well as real-world networks. Based on the results, our algorithm demonstrates higher accuracy and quality than other state-of-the-art algorithms.
21
SARKAR, Prosanta, Sourav MONDAL, Nilanjan DE, and Anita PAL. "(a,b)- Zagreb index of some special graph." Revue Roumaine de Chimie 65, no. 11 (2021): 1045–55. http://dx.doi.org/10.33224/rrch.2020.65.11.09.
Full textAbstract:
In the past few years, graph theory has emerged as one of the most powerful mathematical tools to model many types of relations and process dynamics in computer science, biological and social systems. Generally, a graph is depicted as a set of nodes which is called vertices connected by lines are called edges. A topological index is the numerical parameter of a graph that characterizes its topology and it is usually graph invariant. In this paper, we compute some important classes vertex degree-based graph invariants using the Zagreb index of some special graphs such as the co-normal product of graphs, concentric wheels graph and intersection graph.
22
Raberto, Marco, Fabio Rapallo, and Enrico Scalas. "Semi-Markov Graph Dynamics." PLoS ONE 6, no. 8 (2011): e23370. http://dx.doi.org/10.1371/journal.pone.0023370.
Full text
23
Mariumuthu, G., and M. S. Saraswathy. "Dynamics of Boundary Graphs." Journal of Scientific Research 5, no. 3 (2013): 447–55. http://dx.doi.org/10.3329/jsr.v5i3.14866.
Full textAbstract:
In a graph G, the distance d(u,v) between a pair of vertices u and v is the length of a shortest path joining them. A vertex v is a boundary vertex of a vertex u if for all The boundary graph B(G) based on a connected graph G is a simple graph which has the vertex set as in G. Two vertices u and v are adjacent in B(G) if either u is a boundary of v or v is a boundary of u. If G is disconnected, then each vertex in a component is adjacent to all other vertices in the other components and is adjacent to all of its boundary vertices within the component. Given a positive integer m, the mth iterated boundary graph of G is defined as A graph G is periodic if for some m. A graph G is said to be an eventually periodic graph if there exist positive integers m and k >0 such that We give the necessary and sufficient condition for a graph to be eventually periodic. Keywords: Boundary graph; Periodic graph. © 2013 JSR Publications. ISSN: 2070-0237 (Print); 2070-0245 (Online). All rights reserved. doi: http://dx.doi.org/10.3329/jsr.v5i3.14866 J. Sci. Res. 5 (3), xxx-xxx (2013)
24
Bai, Wenjun. "Smoothness Harmonic: A Graph-Based Approach to Reveal Spatiotemporal Patterns of Cortical Dynamics in fMRI Data." Applied Sciences 13, no. 12 (2023): 7130. http://dx.doi.org/10.3390/app13127130.
Full textAbstract:
Despite fMRI data being interpreted as time-varying graphs in graph analysis, there has been more emphasis on learning sophisticated node embeddings and complex graph structures rather than providing a macroscopic description of cortical dynamics. In this paper, I introduce the notion of smoothness harmonics to capture the slowly varying cortical dynamics in graph-based fMRI data in the form of spatiotemporal smoothness patterns. These smoothness harmonics are rooted in the eigendecomposition of graph Laplacians, which reveal how low-frequency-dominated fMRI signals propagate across the cortex and through time. We showcase their usage in a real fMRI dataset to differentiate the cortical dynamics of children and adults while also demonstrating their empirical merit over the static functional connectomes in inter-subject and between-group classification analyses.
25
Chayes, Jennifer. "Mathematics of Web science: structure, dynamics and incentives." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371, no. 1987 (2013): 20120377. http://dx.doi.org/10.1098/rsta.2012.0377.
Full textAbstract:
Dr Chayes’ talk described how, to a discrete mathematician, ‘all the world’s a graph, and all the people and domains merely vertices’. A graph is represented as a set of vertices V and a set of edges E, so that, for instance, in the World Wide Web, V is the set of pages and E the directed hyperlinks; in a social network, V is the people and E the set of relationships; and in the autonomous system Internet, V is the set of autonomous systems (such as AOL, Yahoo! and MSN) and E the set of connections. This means that mathematics can be used to study the Web (and other large graphs in the online world) in the following way: first, we can model online networks as large finite graphs; second, we can sample pieces of these graphs; third, we can understand and then control processes on these graphs; and fourth, we can develop algorithms for these graphs and apply them to improve the online experience.
26
XING, CHANGMING, and LIN YANG. "RANDOM WALKS IN HETEROGENEOUS WEIGHTED PSEUDO-FRACTAL WEBS WITH THE SAME WEIGHT SEQUENCE." Fractals 27, no. 06 (2019): 1950089. http://dx.doi.org/10.1142/s0218348x19500890.
Full textAbstract:
Intuitively, link weight could affect the dynamics of the network. However, the theoretical research on the effects of link weight on network dynamics is still rare. In this paper, we present two heterogeneous weighted pseudo-fractal webs controlled by two weight parameters [Formula: see text] and [Formula: see text] ([Formula: see text]). Both graph models are scale-free deterministic graphs, and they have the same weight sequence when [Formula: see text] and [Formula: see text] are fixed. Based on their self-similar graph structure, we study the effect of heterogeneous weight on the random walks in graph with scale-free characteristics. We obtain analytically the average trapping time (ATT) for biased random walks in graphs with a trap located at a fixed node. Analyzing and comparing the obtained solutions, we find that in the large graph limit, the ATT for both graph models all grow as a power function of the graph size (number of nodes) with the exponent [Formula: see text] dependents on the ratio of parameters [Formula: see text] and [Formula: see text], but their exponents [Formula: see text] are not the same, one gets the minimum when [Formula: see text], while the other gets the maximum. Furthermore, the average weighted shortest path length (AWSPL) to the trap is calculated for both graph models, respectively. We show that when the graph size tends to infinity, their AWSPL grows unbounded with the graph size for most parameters. We hope that these results could help people understand the impact of heterogeneous weight on network dynamics.
27
Xu, Chunyan, Rong Liu, Tong Zhang, Zhen Cui, Jian Yang, and Chunlong Hu. "Dual-Stream Structured Graph Convolution Network for Skeleton-Based Action Recognition." ACM Transactions on Multimedia Computing, Communications, and Applications 17, no. 4 (2021): 1–22. http://dx.doi.org/10.1145/3450410.
Full textAbstract:
In this work, we propose a dual-stream structured graph convolution network ( DS-SGCN ) to solve the skeleton-based action recognition problem. The spatio-temporal coordinates and appearance contexts of the skeletal joints are jointly integrated into the graph convolution learning process on both the video and skeleton modalities. To effectively represent the skeletal graph of discrete joints, we create a structured graph convolution module specifically designed to encode partitioned body parts along with their dynamic interactions in the spatio-temporal sequence. In more detail, we build a set of structured intra-part graphs, each of which can be adopted to represent a distinctive body part (e.g., left arm, right leg, head). The inter-part graph is then constructed to model the dynamic interactions across different body parts; here each node corresponds to an intra-part graph built above, while an edge between two nodes is used to express these internal relationships of human movement. We implement the graph convolution learning on both intra- and inter-part graphs in order to obtain the inherent characteristics and dynamic interactions, respectively, of human action. After integrating the intra- and inter-levels of spatial context/coordinate cues, a convolution filtering process is conducted on time slices to capture these temporal dynamics of human motion. Finally, we fuse two streams of graph convolution responses in order to predict the category information of human action in an end-to-end fashion. Comprehensive experiments on five single/multi-modal benchmark datasets (including NTU RGB+D 60, NTU RGB+D 120, MSR-Daily 3D, N-UCLA, and HDM05) demonstrate that the proposed DS-SGCN framework achieves encouraging performance on the skeleton-based action recognition task.
28
Changaival, Boonyarit, Martin Rosalie, Grégoire Danoy, Kittichai Lavangnananda, and Pascal Bouvry. "Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics." International Journal of Bifurcation and Chaos 27, no. 14 (2017): 1750215. http://dx.doi.org/10.1142/s0218127417502157.
Full textAbstract:
Graph Traversal algorithms can find their applications in various fields such as routing problems, natural language processing or even database querying. The exploration can be considered as a first stepping stone into knowledge extraction from the graph which is now a popular topic. Classical solutions such as Breadth First Search (BFS) and Depth First Search (DFS) require huge amounts of memory for exploring very large graphs. In this research, we present a novel memoryless graph traversal algorithm, Chaotic Traversal (CHAT) which integrates chaotic dynamics to traverse large unknown graphs via the Lozi map and the Rössler system. To compare various dynamics effects on our algorithm, we present an original way to perform the exploration of a parameter space using a bifurcation diagram with respect to the topological structure of attractors. The resulting algorithm is an efficient and nonresource demanding algorithm, and is therefore very suitable for partial traversal of very large and/or unknown environment graphs. CHAT performance using Lozi map is proven superior than the, commonly known, Random Walk, in terms of number of nodes visited (coverage percentage) and computation time where the environment is unknown and memory usage is restricted.
29
Genova, Daniela, Hendrik Jan Hoogeboom, and Nataša Jonoska. "Companions and an Essential Motion of a Reaction System." Fundamenta Informaticae 175, no. 1-4 (2020): 187–99. http://dx.doi.org/10.3233/fi-2020-1953.
Full textAbstract:
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.
30
AN HUEF, ASTRID, MARCELO LACA, IAIN RAEBURN, and AIDAN SIMS. "KMS states on the -algebras of reducible graphs." Ergodic Theory and Dynamical Systems 35, no. 8 (2014): 2535–58. http://dx.doi.org/10.1017/etds.2014.52.
Full textAbstract:
We consider the dynamics on the $C^{\ast }$-algebras of finite graphs obtained by lifting the gauge action to an action of the real line. Enomoto, Fujii and Watatani [KMS states for gauge action on ${\mathcal{O}}_{A}$. Math. Japon.29 (1984), 607–619] proved that if the vertex matrix of the graph is irreducible, then the dynamics on the graph algebra admits a single Kubo–Martin–Schwinger (KMS) state. We have previously studied the dynamics on the Toeplitz algebra, and explicitly described a finite-dimensional simplex of KMS states for inverse temperatures above a critical value. Here we study the KMS states for graphs with reducible vertex matrix, and for inverse temperatures at and below the critical value. We prove a general result which describes all the KMS states at a fixed inverse temperature, and then apply this theorem to a variety of examples. We find that there can be many patterns of phase transition, depending on the behaviour of paths in the underlying graph.
31
Blachowski, B., and W. Gutkowski. "Graph based discrete optimization in structural dynamics." Bulletin of the Polish Academy of Sciences: Technical Sciences 62, no. 1 (2014): 91–102. http://dx.doi.org/10.2478/bpasts-2014-0011.
Full textAbstract:
Abstract In this study, a relatively simple method of discrete structural optimization with dynamic loads is presented. It is based on a tree graph, representing discrete values of the structural weight. In practical design, the number of such values may be very large. This is because they are equal to the combination numbers, arising from numbers of structural members and prefabricated elements. The starting point of the method is the weight obtained from continuous optimization, which is assumed to be the lower bound of all possible discrete weights. Applying the graph, it is possible to find a set of weights close to the continuous solution. The smallest of these values, fulfilling constraints, is assumed to be the discrete minimum weight solution. Constraints can be imposed on stresses, displacements and accelerations. The short outline of the method is presented in Sec. 2. The idea of discrete structural optimization by means of graphs. The knowledge needed to apply the method is limited to the FEM and graph representation. The paper is illustrated with two examples. The first one deals with a transmission tower subjected to stochastic wind loading. The second one with a composite floor subjected to deterministic dynamic forces, coming from the synchronized crowd activities, like dance or aerobic.
32
Faizliev, Alexey, Vladimir Balash, Vladimir Petrov, Alexey Grigoriev, Dmitriy Melnichuk, and Sergei Sidorov. "Stability Analysis of Company Co-Mention Network and Market Graph Over Time Using Graph Similarity Measures." Journal of Open Innovation: Technology, Market, and Complexity 5, no. 3 (2019): 55. http://dx.doi.org/10.3390/joitmc5030055.
Full textAbstract:
The aim of the paper is to provide an analysis of news and financial data using their network representation. The formation of network structures from data sources is carried out using two different approaches: by building the so-called market graph in which nodes represent financial assets (e.g., stocks) and the edges between nodes stand for the correlation between the corresponding assets, by constructing a company co-mention network in which any two companies are connected by an edge if a news item mentioning both companies has been published in a certain period of time. Topological changes of the networks over the period 2005–2010 are investigated using the sliding window of six-month duration. We study the stability of the market graph and the company co-mention network over time and establish which of the two networks was more stable during the period. In addition, we examine the impact of the crisis of 2008 on the stability of the market graph as well as the company co-mention network. The networks that are considered in this paper and that are the objects of our study (the market graph and the company co-mention network) have a non-changing set of nodes (companies), and can change over time by adding/removing links between these nodes. Different graph similarity measures are used to evaluate these changes. If a network is stable over time, a measure of similarity between two graphs constructed for two different time windows should be close to zero. If there was a sharp change between the graphs constructed for two adjacent periods, then this should lead to a sharp increase in the value of the similarity measure between these two graphs. This paper uses the graph similarity measures which were proposed relatively recently. In addition, to estimate how the networks evolve over time we exploit QAP (Quadratic Assignment Procedure). While there is a sufficient amount of works studying the dynamics of graphs (including the use of graph similarity metrics), in this paper the company co-mention network dynamics is examined both individually and in comparison with the dynamics of market graphs for the first time.
33
Huang, Yicong, and Zhuliang Yu. "Representation Learning for Dynamic Functional Connectivities via Variational Dynamic Graph Latent Variable Models." Entropy 24, no. 2 (2022): 152. http://dx.doi.org/10.3390/e24020152.
Full textAbstract:
Latent variable models (LVMs) for neural population spikes have revealed informative low-dimensional dynamics about the neural data and have become powerful tools for analyzing and interpreting neural activity. However, these approaches are unable to determine the neurophysiological meaning of the inferred latent dynamics. On the other hand, emerging evidence suggests that dynamic functional connectivities (DFC) may be responsible for neural activity patterns underlying cognition or behavior. We are interested in studying how DFC are associated with the low-dimensional structure of neural activities. Most existing LVMs are based on a point process and fail to model evolving relationships. In this work, we introduce a dynamic graph as the latent variable and develop a Variational Dynamic Graph Latent Variable Model (VDGLVM), a representation learning model based on the variational information bottleneck framework. VDGLVM utilizes a graph generative model and a graph neural network to capture dynamic communication between nodes that one has no access to from the observed data. The proposed computational model provides guaranteed behavior-decoding performance and improves LVMs by associating the inferred latent dynamics with probable DFC.
34
Sun, Mengzhu, Xi Zhang, Jiaqi Zheng, and Guixiang Ma. "DDGCN: Dual Dynamic Graph Convolutional Networks for Rumor Detection on Social Media." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (2022): 4611–19. http://dx.doi.org/10.1609/aaai.v36i4.20385.
Full textAbstract:
Detecting rumors on social media has become particular important due to the rapid dissemination and adverse impacts on our lives. Though a set of rumor detection models have exploited the message propagation structural or temporal information, they seldom model them altogether to enjoy the best of both worlds. Moreover, the dynamics of knowledge information associated with the comments are not involved, either. To this end, we propose a novel Dual-Dynamic Graph Convolutional Networks, termed as DDGCN, which can model the dynamics of messages in propagation as well as the dynamics of the background knowledge from Knowledge graphs in one unified framework. Specifically, two Graph Convolutional Networks are adopted to capture the above two types of structure information at different time stages, which are then combined with a temporal fusing unit. This allows for learning the dynamic event representations in a more fine-grained manner, and incrementally aggregating them to capture the cascading effect for better rumor detection. Extensive experiments on two public real-world datasets demonstrate that our proposal yields significant improvements compared to strong baselines and can detect rumors at early stages.
35
Mosterman, P. J. "HYBRSIM—a modelling and simulation environment for hybrid bond graphs." Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 216, no. 1 (2002): 35–46. http://dx.doi.org/10.1243/0959651021541417.
Full textAbstract:
Bond graphs are a powerful formalism to model continuous dynamics of physical systems. Hybrid bond graphs introduce an ideal switching element, the controlled junction, to approximate continuous behaviour that is too complex for numerical analysis (e.g. because of non-linearities or steep gradients). HYBRSIM is a tool for hybrid bond graph modelling and simulation implemented in Java and is documented in this paper. It performs event detection and location based on a bisectional search, handles run-time causality changes, including derivative causality, performs physically consistent (re-)initialization and supports two types of event iteration because of dynamic coupling. It exports hybrid bond graph models in Java and C/C++ code that includes discontinuities as switched equations (i.e. pre-enumeration is not required).
36
Pan, Zhiqiang, Wanyu Chen, and Honghui Chen. "Dynamic Graph Learning for Session-Based Recommendation." Mathematics 9, no. 12 (2021): 1420. http://dx.doi.org/10.3390/math9121420.
Full textAbstract:
Session-based recommendation (SBRS) aims to make recommendations for users merely based on the ongoing session. Existing GNN-based methods achieve satisfactory performance by exploiting the pair-wise item transition pattern; however, they ignore the temporal evolution of the session graphs over different time-steps. Moreover, the widely applied cross-entropy loss with softmax in SBRS faces the serious overfitting problem. To deal with the above issues, we propose dynamic graph learning for session-based recommendation (DGL-SR). Specifically, we design a dynamic graph neural network (DGNN) to simultaneously take the graph structural information and the temporal dynamics into consideration for learning the dynamic item representations. Moreover, we propose a corrective margin softmax (CMS) to prevent overfitting in the model optimization by correcting the gradient of the negative samples. Comprehensive experiments are conducted on two benchmark datasets, that is, Diginetica and Gowalla, and the experimental results show the superiority of DGL-SR over the state-of-the-art baselines in terms of Recall@20 and MRR@20, especially on hitting the target item in the recommendation list.
37
Samanta, B., and A. Mukherjee. "Analysis of Acoustoelastic Systems Using Modal Bond Graphs." Journal of Dynamic Systems, Measurement, and Control 112, no. 1 (1990): 108–15. http://dx.doi.org/10.1115/1.2894126.
Full textAbstract:
A procedure is presented to study the dynamics of acoustoelastic systems within the framework of bond graph technique. The substructures, acoustic and structural, are modeled individually in form of bond graphs that are coupled through suitable elements satisfying the conditions at the interfaces. From this bond graph a second stage modal decomposition is performed to represent the overall system in yet another bond graph that can be analyzed to obtain the overall system dynamics. The scope for two-stage modal truncation makes the procedure suitable for analyzing acoustoelastic systems that are “stiff” in nature due to the wide range of their natural frequencies. The procedure is illustrated by suitable examples.
38
Parmelee, Caitlyn, Samantha Moore, Katherine Morrison, and Carina Curto. "Core motifs predict dynamic attractors in combinatorial threshold-linear networks." PLOS ONE 17, no. 3 (2022): e0264456. http://dx.doi.org/10.1371/journal.pone.0264456.
Full textAbstract:
Combinatorial threshold-linear networks (CTLNs) are a special class of inhibition-dominated TLNs defined from directed graphs. Like more general TLNs, they display a wide variety of nonlinear dynamics including multistability, limit cycles, quasiperiodic attractors, and chaos. In prior work, we have developed a detailed mathematical theory relating stable and unstable fixed points of CTLNs to graph-theoretic properties of the underlying network. Here we find that a special type of fixed points, corresponding to core motifs, are predictive of both static and dynamic attractors. Moreover, the attractors can be found by choosing initial conditions that are small perturbations of these fixed points. This motivates us to hypothesize that dynamic attractors of a network correspond to unstable fixed points supported on core motifs. We tested this hypothesis on a large family of directed graphs of size n = 5, and found remarkable agreement. Furthermore, we discovered that core motifs with similar embeddings give rise to nearly identical attractors. This allowed us to classify attractors based on structurally-defined graph families. Our results suggest that graphical properties of the connectivity can be used to predict a network’s complex repertoire of nonlinear dynamics.
39
Gustafson, Karl, and Robert Hartman. "Graph Theory and Fluid Dynamics." SIAM Journal on Algebraic Discrete Methods 6, no. 4 (1985): 643–56. http://dx.doi.org/10.1137/0606064.
Full text
40
Collins, Pieter, and Kevin A. Mitchell. "Graph Duality in Surface Dynamics." Journal of Nonlinear Science 29, no. 5 (2019): 2103–35. http://dx.doi.org/10.1007/s00332-019-09549-0.
Full text
41
Amorim, Tiago de Albuquerque, and Miriam Manoel. "The realisation of admissible graphs for coupled vector fields." Nonlinearity 37, no. 1 (2023): 015004. http://dx.doi.org/10.1088/1361-6544/ad0ca4.
Full textAbstract:
Abstract In a coupled network cells can interact in several ways. There is a vast literature from the last 20 years that investigates this interacting dynamics under a graph theory formalism, namely as a graph endowed with an input-equivalence relation on the set of vertices that enables a characterisation of the admissible vector fields that rules the network dynamics. The present work goes in the direction of answering an inverse problem: for n ⩾ 2 , any mapping on R n can be realised as an admissible vector field for some graph with the number of vertices depending on (but not necessarily equal to) n. Given a mapping, we present a procedure to construct all non-equivalent admissible graphs, up to the appropriate equivalence relation. We also give an upper bound for the number of such graphs. As a consequence, invariant subspaces under the vector field can be investigated as the locus of synchrony states supported by an admissible graph, in the sense that a suitable graph can be chosen to realise couplings with more (or less) synchrony than another graph admissible to the same vector field. The approach provides in particular a systematic investigation of occurrence of chimera states in a network of van der Pol identical oscillators.
42
Niehaus, Jens, Christian Igel, and Wolfgang Banzhaf. "Reducing the Number of Fitness Evaluations in Graph Genetic Programming Using a Canonical Graph Indexed Database." Evolutionary Computation 15, no. 2 (2007): 199–221. http://dx.doi.org/10.1162/evco.2007.15.2.199.
Full textAbstract:
In this paper we describe the genetic programming system GGP operating on graphs and introduce the notion of graph isomorphisms to explain how they influence the dynamics of GP. It is shown empirically how fitness databases can improve the performance of GP and how mapping graphs to a canonical form can increase these improvements by saving considerable evaluation time.
43
Tang, Jin Yuan, Hai Feng Chen, and Si Yu Chen. "A Nonlinear Dynamics Bond Graph Model of Gear Transmission." Advanced Materials Research 139-141 (October 2010): 933–37. http://dx.doi.org/10.4028/www.scientific.net/amr.139-141.933.
Full textAbstract:
A nonlinear dynamics bond graph model of gear pair is established including the time-varying stiffness, transmission error and tooth surface friction. A capacitive component C is introduced to represent the loads and tooth elastic deformation while introducing the concept of switched power junctions (SPJ) to describe time-varying gear mesh stiffness with clearance, and flow Sf represents the influences of the gear transmission error on the system dynamic equations. The tooth surface friction bond graph model involving the relationship of the relative velocity and the direction of friction are developed. According to the causal relations and the power flow, the state-space equations of the gear bond graph model are obtained. Research results show that bond graph modeling method can solve the modeling problem of the gear nonlinear dynamics.
44
LEFÈVRE, JACQUES. "POSSIBILITY OF REVERSIBLE CHEMO-MECHANICAL COUPLING IN CARDIAC MUSCLE: A BOND GRAPH APPROACH." Journal of Biological Systems 03, no. 03 (1995): 645–52. http://dx.doi.org/10.1142/s0218339095000599.
Full textAbstract:
Current models of cardiac dynamics include a time-varying spring generating the pumping power. They ignore therefore the chemo-mechanical process of transduction. We present a new model, based on the bond graph notion of a two-port capacity which represents this transduction and is compatible with the dynamic spring idea. In addition to showing the power of bond graphs, our model suggests that the transduction is reversible and length-dependent.
45
Dworzanski, Leonid Wladimirovich. "Overapproximation of the Number of Active Timers in Timed-Arc Petri Nets Using DP-Systems." Proceedings of the Institute for System Programming of the RAS 34, no. 5 (2022): 183–94. http://dx.doi.org/10.15514/ispras-2022-34(5)-12.
Full textAbstract:
Timed-arcs Petri nets are a time extension of Petri nets that allows assigning clocks to tokens. System of dynamic points on a metric graph (DP-systems) is another dynamical model that is studied in discrete geometry dynamics; DP-system combines continuous time and discrete branching events and used, for example, in study of localized Gaussian wave packets scattering on thin structures. In recent works, asymptotic estimates of the growth of the number of points in dynamic systems on metric graphs were obtained. In this paper, we provide a mean to overapproximate the number of different values of timers for a subclass of timed-arc Petri nets by constructing a system of dynamic points on a metric graph and prove overapproximation of the number of timer values by the number of points in the system of dynamic points.
46
VISHVESHWARA, SARASWATHI, K. V. BRINDA, and N. KANNAN. "PROTEIN STRUCTURE: INSIGHTS FROM GRAPH THEORY." Journal of Theoretical and Computational Chemistry 01, no. 01 (2002): 187–211. http://dx.doi.org/10.1142/s0219633602000117.
Full textAbstract:
The sequence and structure of a large body of proteins are becoming increasingly available. It is desirable to explore mathematical tools for efficient extraction of information from such sources. The principles of graph theory, which was earlier applied in fields such as electrical engineering and computer networks are now being adopted to investigate protein structure, folding, stability, function and dynamics. This review deals with a brief account of relevant graphs and graph theoretic concepts. The concepts of protein graph construction are discussed. The manner in which graphs are analyzed and parameters relevant to protein structure are extracted, are explained. The structural and biological information derived from protein structures using these methods is presented.
47
Bougueroua, Sana, Marie Bricage, Ylène Aboulfath, Dominique Barth, and Marie-Pierre Gaigeot. "Algorithmic Graph Theory, Reinforcement Learning and Game Theory in MD Simulations: From 3D Structures to Topological 2D-Molecular Graphs (2D-MolGraphs) and Vice Versa." Molecules 28, no. 7 (2023): 2892. http://dx.doi.org/10.3390/molecules28072892.
Full textAbstract:
This paper reviews graph-theory-based methods that were recently developed in our group for post-processing molecular dynamics trajectories. We show that the use of algorithmic graph theory not only provides a direct and fast methodology to identify conformers sampled over time but also allows to follow the interconversions between the conformers through graphs of transitions in time. Examples of gas phase molecules and inhomogeneous aqueous solid interfaces are presented to demonstrate the power of topological 2D graphs and their versatility for post-processing molecular dynamics trajectories. An even more complex challenge is to predict 3D structures from topological 2D graphs. Our first attempts to tackle such a challenge are presented with the development of game theory and reinforcement learning methods for predicting the 3D structure of a gas-phase peptide.
48
Lee, Jong-whi, and Jinhong Jung. "Time-Aware Random Walk Diffusion to Improve Dynamic Graph Learning." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 7 (2023): 8473–81. http://dx.doi.org/10.1609/aaai.v37i7.26021.
Full textAbstract:
How can we augment a dynamic graph for improving the performance of dynamic graph neural networks? Graph augmentation has been widely utilized to boost the learning performance of GNN-based models. However, most existing approaches only enhance spatial structure within an input static graph by transforming the graph, and do not consider dynamics caused by time such as temporal locality, i.e., recent edges are more influential than earlier ones, which remains challenging for dynamic graph augmentation. In this work, we propose TiaRa (Time-aware Random Walk Diffusion), a novel diffusion-based method for augmenting a dynamic graph represented as a discrete-time sequence of graph snapshots. For this purpose, we first design a time-aware random walk proximity so that a surfer can walk along the time dimension as well as edges, resulting in spatially and temporally localized scores. We then derive our diffusion matrices based on the time-aware random walk, and show they become enhanced adjacency matrices that both spatial and temporal localities are augmented. Throughout extensive experiments, we demonstrate that TiaRa effectively augments a given dynamic graph, and leads to significant improvements in dynamic GNN models for various graph datasets and tasks.
49
Lin, Zhe, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Zhihong Tian. "Hierarchical core maintenance on large dynamic graphs." Proceedings of the VLDB Endowment 14, no. 5 (2021): 757–70. http://dx.doi.org/10.14778/3446095.3446099.
Full textAbstract:
The model of k -core and its decomposition have been applied in various areas, such as social networks, the world wide web, and biology. A graph can be decomposed into an elegant k -core hierarchy to facilitate cohesive subgraph discovery and network analysis. As many real-life graphs are fast evolving, existing works proposed efficient algorithms to maintain the coreness value of every vertex against structure changes. However, the maintenance of the k -core hierarchy in existing studies is not complete because the connections among different k -cores in the hierarchy are not considered. In this paper, we study hierarchical core maintenance which is to compute the k -core hierarchy incrementally against graph dynamics. The problem is challenging because the change of hierarchy may be large and complex even for a slight graph update. In order to precisely locate the area affected by graph dynamics, we conduct in-depth analyses on the structural properties of the hierarchy, and propose well-designed local update techniques. Our algorithms significantly outperform the baselines on runtime by up to 3 orders of magnitude, as demonstrated on 10 real-world large graphs.
50
Ayala-Jaimes, Gerardo, Gilberto Gonzalez-Avalos, Noe Barrera Gallegos, Aaron Padilla Garcia, and Juancarlos Méndez-Barriga. "Direct Determination of Reduced Models of a Class of Singularly Perturbed Nonlinear Systems on Three Time Scales in a Bond Graph Approach." Symmetry 14, no. 1 (2022): 104. http://dx.doi.org/10.3390/sym14010104.
Full textAbstract:
One of the most important features in the analysis of the singular perturbation methods is the reduction of models. Likewise, the bond graph methodology in dynamic system modeling has been widely used. In this paper, the bond graph modeling of nonlinear systems with singular perturbations is presented. The class of nonlinear systems is the product of state variables on three time scales (fast, medium, and slow). Through this paper, the symmetry of mathematical modeling and graphical modeling can be established. A main characteristic of the bond graph is the application of causality to its elements. When an integral causality is assigned to the storage elements that determine the state variables, the dynamic model is obtained. If the storage elements of the fast dynamics have a derivative causality and the storage elements of the medium and slow dynamics an integral causality is assigned, a reduced model is obtained, which consists of a dynamic model for the medium and slow time scales and a stationary model of the fast time scale. By applying derivative causality to the storage elements of the fast and medium dynamics and an integral causality to the storage elements of the slow dynamics, the quasi-steady-state model for the slow dynamics is obtained and stationary models for the fast and medium dynamics are defined. The exact and reduced models of singularly perturbed systems can be interpreted as another symmetry in the development of this paper. Finally, the proposed methodology was applied to a system with three time scales in a bond graph approach, and simulation results are shown in order to indicate the effectiveness of the proposed methodology.