Search

Let H be a graph possibly with loops and G be a multigraph without loops. An H-coloring of G is a function c : E (G) → V (H) . We will say that G is an H-colored multigraph, whenever we are taking a fixed H-coloring of G. The set of all the edges with end vertices u and v will be denoted by E uv . We will say that W = (v 0 , e 0 1 , ... , e 0 k 0 , v 1 , e 1 1 , ... , e 1 k 1 , v 2 , ... , v n - 1 , e n - 1 1 , ... , e n - 1 k n - 1 , v n) , where for each i in { 0 , ... , n - 1 } , k i ≥ 1 and e i j ∈ E v i v i + 1 for every j ∈ { 1 , ... , k i } , is a dynamic H-walk iff c (e i k i) c (e i + 1 1) is an edge in H, for each i ∈ { 0 , ... , n - 2 } . We will say that a dynamic H-walk is a closed dynamic H-walk whenever v 0 = v n and c (e n - 1 k n - 1 ) c (e 0 1) is an edge in H. Moreover, a closed dynamic H-walk is called dynamic H-cycle whenever v i ≠ v j , for every { i , j } ⊆ { 0 , ... , v n - 1 } . In particular, a dynamic H-walk is an H-walk whenever k i = 1 , for every i ∈ { 0 , ... , n - 1 } , and when H is a complete graph without loops, an H-walk is well known as a properly colored walk. In this work, we study the existence and length of dynamic H-cycles, dynamic H-trails and dynamic H-paths in H-colored multigraphs. To accomplish this, we introduce a new concept of color degree, namely, the dynamic degree, which allows us to extend some classic results, as Ore's Theorem, for H-colored multigraphs. Also, we give sufficient conditions for the existence of hamiltonian dynamic H-cycles in H-colored multigraphs, and as a consequence, we obtain sufficient conditions for the existence of properly colored hamiltonian cycle in edge-colored multigraphs, with at least c ≥ 3 colors. [ABSTRACT FROM AUTHOR]

Let G be a graph which may have multiple edges but no loops, μ G (v) be the multiplicity of G (which is the maximum among the numbers of edges between v and the other vertex on G), and a and b be any two functions, s.t. a , b : V (G) → N \ { 0 , 1 } . A theta is a graph made of three internally vertex-disjoint chordless paths P 1 = x - ⋯ - y , P 2 = x - ⋯ - y , P 3 = x - ⋯ - y of length at least two and no edges exist between P i and P j ( i ≠ j , i , j ∈ { 1 , 2 , 3 } ) except the three edges incident to x and the three edges incident to y. For a partition (X, Y) of V(G), and any x ∈ X , y ∈ Y , let d X (x) denote by the degree of x in G[X], and d Y (y) be defined similarly. In this paper, we show that a graph G admits a partition (A, B) such that d A (x) ≥ a (x) for any x ∈ A and d B (y) ≥ b (y) for any y ∈ B if G is H -free and d G (v) ≥ a + b + 2 μ G (v) - 3 for any vertex v ∈ V (G) , where for each member H ∈ H , the underlying of H belongs to {triangle, wheel, theta}. [ABSTRACT FROM AUTHOR]

Accurate and timely traffic flow predictions are essential for effective traffic management and congestion reduction. However, most traditional prediction methods often fail to capture the complex dynamics and correlations within traffic flows due to insufficient processing of spatiotemporal data. Specifically, these methods struggle to integrate and analyze the multi-layered spatial and temporal interactions inherent in traffic data, leading to suboptimal prediction accuracy and robustness. To address this limitation, this paper presents a Multi-Graph Structures and Hypergraph Convolutional Network (MGHCN) that combines diverse graphs and hypergraphs. The MGHCN simplifies the predictive framework by integrating key components that improve its robustness and accuracy. One of the most critical components is the dual hypergraph structure, which captures edge correlations by converting traditional graph edges into hypergraph nodes. To better capture the spatiotemporal correlation of traffic data, a Graph Convolutional Network (GCN) is employed to analyze these hypergraphs in depth. Finally, a novel adjacency matrix and a dynamic graph module are used to accurately simulate interactions between spatiotemporal features, thereby enhancing the accuracy and robustness of predictions. Experimental validation on four distinct real-world traffic datasets shows that MGHCN outperforms existing state-of-the-art traffic prediction methods. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Computer Engineering & Applications is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Social network extensions of Heider's balance theory have led to a plethora of adaptations, often inconsistent with Heider and each other. We present a general model that permits the description and testing of specific balance theoretic predictions as Heider had originally proposed them. We formulate balance statements as a comparison of two conditional probabilities of a tie: Ego-qAlter , conditioned on 2-path relations Ego-rX-sAlter vs. their counterfactual negation, ¬(Ego-rX-sAlter). Here q, r and s, are indices that identify elements in a set of mutually exclusive and exhaustive relations in a multigraph (their sum produces a complete graph). This relaxes the dichotomous assumption of a signed graph. We identify neutral ties distinctive from negative and positive ties and convert the underlying signed graph into a restricted multigraph. The point-biserial correlations of relation q with the count of 2-paths (through relations r and s) describe the difference in conditional probabilities, or the prevalence for any stipulated balance configuration. In total 18 such unique balance correlations are identified for any trichotomous multigraph, although 27 theoretical statements exist. Two major advantages of balance correlations are: direct comparison between any two correlations over time, even if network sizes and densities differ; and the evaluation of specific balanced and unbalanced behaviors and predictions. We apply the model to a large data set consisting of friendly vs hostile relations between countries from 1816 to 2007. We find strong evidence for one of the balance statements, and virtually no evidence for unbalanced predictions. However, there is ample stable evidence that "neutral" ties are important in balancing the relations among nations. Results suggest that prevalence of balance-driven behavior varies over time. Indeed, other behaviors may prevail in certain eras. [ABSTRACT FROM AUTHOR]

This paper studies the N-player gambler's ruin problem where two players are involved in an even-money bet during each round. The objective is to solve for each player's final placing probabilities given their initial wealths, as well as the expected time until ruin. Multigraphs were constructed to model the transitions between chip states. Linear systems were constructed based on these graphs. Solutions for the placing probabilities of each player were obtained using these linear systems. A numerical algorithm is developed to solve the general N-player gambler's ruin for any positive integer chip total. Expected time until ruin for any initial state can be solved using absorbing Markov chains. The solution leads to exact values and equities in this model depend on the exact number, not just proportion, of chips each player holds. Compared with the usual lattice model, the multigraph model uses smaller matrices in computations, yielding considerable savings in the number of operations and program run time. [ABSTRACT FROM AUTHOR]

Crossword puzzles lend themselves to mathematical inquiry. Several authors have already described the arrangement of crossword grids and associated combinatorics of answer numbers [Fer14] [Fer20] [McS16]. In this paper, we present a new graph-theoretic representation of crossword puzzle grid designs and describe the mathematical conditions placed on these graphs by well-known crossword construction conventions. [ABSTRACT FROM AUTHOR]

In the field of research into vessel type recognition utilizing trajectory data, researchers have primarily concentrated on developing models based on trajectory sequences to extract the relevant information. However, this approach often overlooks the crucial significance of the spatial dependency relationships among trajectory points, posing challenges for comprehensively capturing the intricate features of vessel travel patterns. To address this limitation, our study introduces a novel multi-graph fusion representation method that integrates both trajectory sequences and dependency relationships to optimize the task of vessel type recognition. The proposed method initially extracts the spatiotemporal features and behavioral semantic features from vessel trajectories. By utilizing these behavioral semantic features, the key nodes within the trajectory that exhibit dependencies are identified. Subsequently, graph structures are constructed to represent the intricate dependencies between these nodes and the sequences of trajectory points. These graph structures are then processed through graph convolutional networks (GCNs), which integrate various sources of information within the graphs to obtain behavioral representations of vessel trajectories. Finally, these representations are applied to the task of vessel type recognition for experimental validation. The experimental results indicate that this method significantly enhances vessel type recognition performance when compared to other baseline methods. Additionally, ablation experiments have been conducted to validate the effectiveness of each component of the method. This innovative approach not only delves deeply into the behavioral representations of vessel trajectories but also contributes to advancements in intelligent water traffic control. [ABSTRACT FROM AUTHOR]

Major Depressive Disorder (MDD) is an affective disorder that can lead to persistent sadness and a decline in the quality of life, increasing the risk of suicide. Utilizing multimodal data such as electroencephalograms and patient interview audios can facilitate the timely detection of MDD. However, existing depression detection methods either consider only a single modality or do not fully account for the differences and similarities between modalities in multimodal approaches, potentially overlooking the latent information inherent in various modal data. To address these challenges, we propose EMO-GCN, a multimodal depression detection method based on an adaptive multi-graph neural network. By employing graph-based methods to model data from various modalities and extracting features from them, the potential correlations between modalities are uncovered. The model's performance on the MODMA dataset is outstanding, achieving an accuracy (ACC) of 96.30%. Ablation studies further confirm the effectiveness of the model's individual components.The experimental results of EMO-GCN demonstrate the application prospects of graph-based multimodal analysis in the field of mental health, offering new perspectives for future research. [ABSTRACT FROM AUTHOR]

We prove the inequality λ k ≤ d k + d k − 1 for all the eigenvalues λ 1 ≤ λ 2 ≤ ⋯ ≤ λ n of the Kirchhoff matrix K of a finite simple graph or quiver with vertex degrees d 1 ≤ d 2 ≤ ⋯ ≤ d n and assuming d 0 = 0. Without multiple connections, the inequality λ k ≥ max (0 , d k − (n − k)) holds. A consequence in the finite simple graph or multi-graph case is that the pseudo determinant Det (K) counting the number of rooted spanning trees has an upper bound 2 n ∏ k = 1 n d k and that det (1 + K) counting the number of rooted spanning forests has an upper bound ∏ k = 1 n (1 + 2 d k). [ABSTRACT FROM AUTHOR]

Vehicle detection is an important part of modern intelligent transportation systems. At present, complex deep learning algorithms are often used for vehicle detection and tracking, but high-precision detection results are often obtained at the cost of time, and the existing research rarely considers optimization algorithms for vehicle information. Based on this, we propose an efficient method for vehicle detection in multi-graph mode and optimization method considering multi-section tracking based on geographic similarity. In this framework, we design a vehicle extraction method based on multi-graph mode and a vehicle detection technology based on traffic flow characteristics, which can cope with the challenge of vehicle detection under an unstable environment. Further, a multi-section tracking optimization technology based on geographic similarity at a high video frame rate is proposed, which can efficiently identify lane change behavior and match, track, and optimize vehicles. Experiments are carried out on several road sections, and the model performance and optimization effect are analyzed. The experimental results show that the vehicle detection and optimization algorithm proposed in this paper has the best effect and high detection accuracy and robustness. The average results of R e c a l l , P r e c i s i o n , and F 1 are 0.9715, 0.979, and 0.9752, respectively, all of which are above 0.97, showing certain competitiveness in the field of vehicle detection. [ABSTRACT FROM AUTHOR]

Timely and accurate traffic flow prediction is crucial for stabilizing road conditions, reducing environmental pollution, and mitigating economic losses. While current graph convolution methods have achieved certain results, they do not fully leverage the true advantages of graph convolution. There is still room for improvement in simultaneously addressing multi-graph convolution, optimizing graphs, and simulating road conditions. Based on this, this paper proposes MSA-GCN: Multistage Spatio-Temporal Aggregation Graph Convolutional Networks for Traffic Flow Prediction. This method overcomes the aforementioned issues by dividing the process into different stages and achieves promising prediction results. In the first stage, we construct a latent similarity adjacency matrix and address the randomness interference features in similarity features through two optimizations using the proposed ConvGRU Attention Layer (CGAL module) and the Causal Similarity Capture Module (CSC module), which includes Granger causality tests. In the second stage, we mine the potential correlation between roads using the Correlation Completion Module (CC module) to create a global correlation adjacency matrix as a complement for potential correlations. In the third stage, we utilize the proposed Auto-LRU autoencoder to pre-train various weather features, encoding them into the model's prediction process to enhance its ability to simulate the real world and improve interpretability. Finally, in the fourth stage, we fuse these features and use a Bidirectional Gated Recurrent Unit (BiGRU) to model time dependencies, outputting the prediction results through a linear layer. Our model demonstrates a performance improvement of 29.33%, 27.03%, and 23.07% on three real-world datasets (PEMSD8, LOSLOOP, and SZAREA) compared to advanced baseline methods, and various ablation experiments validate the effectiveness of each stage and module. [ABSTRACT FROM AUTHOR]

The increase in motorized vehicles in cities and the inefficient use of parking spaces have exacerbated parking difficulties in cities. To effectively improve the utilization rate of parking spaces, it is necessary to accurately predict future parking demand. This paper proposes a deep learning model based on multi-graph convolutional Transformer, which captures geographic spatial features through a Multi-Graph Convolutional Network (MGCN) module and mines temporal feature patterns using a Transformer module to accurately predict future multi-step parking demand. The model was validated using historical parking transaction volume data from all on-street parking lots in Nanshan District, Shenzhen, from September 2018 to March 2019, and its superiority was verified through comparative experiments with benchmark models. The results show that the MGCN–Transformer model has a MAE, RMSE, and R2 error index of 0.26, 0.42, and 95.93%, respectively, in the multi-step prediction task of parking demand, demonstrating its superior predictive accuracy compared to other benchmark models. [ABSTRACT FROM AUTHOR]

Identifying the region's functionalities and what the specific Point-of-Interest (POI) needs is essential for effective urban planning. However, due to the diversified and ambiguity nature of urban regions, there are still some significant challenges to be resolved in urban POI demand analysis. To this end, we propose a novel framework, in which Region-of-Interest Demand Modeling is enhanced through the graph representation learning, namely Variational Multi-graph Auto-encoding Fusion, aiming to effectively predict the ROI demand from both the POI level and category level. Specifically, we first divide the urban area into spatially differentiated neighborhood regions, extract the corresponding multi-dimensional natures, and then generate the Spatial-Attributed Region Graph (SARG). After that, we introduce an unsupervised multi-graph based variational auto-encoder to map regional profiles of SARG into latent space, and further retrieve the dynamic latent representations through probabilistic sampling and global fusing. Additionally, during the training process, a spatio-temporal constrained Bayesian algorithm is adopted to infer the destination POIs. Finally, extensive experiments are conducted on real-world dataset, which demonstrate our model significantly outperforms state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

In this paper, we obtain a combinatorial expression for the Perron root and eigenvectors of a non-negative integer matrix using techniques from symbolic dynamics. We associate such a matrix with a multigraph and consider the edge shift corresponding to it. This gives rise to a collection of forbidden words F which correspond to the non-existence of an edge between two vertices, and a collection of repeated words R with multiplicities which correspond to multiple edges between two vertices. In general, for given collections F of forbidden words and R of repeated words with pre-assigned multiplicities, we construct a generalized language as a multiset. A combinatorial expression that enumerates the number of words of fixed length in this generalized language gives the Perron root and eigenvectors of the adjacency matrix. We also obtain conditions under which such a generalized language is a language of an edge shift. [ABSTRACT FROM AUTHOR]

For a class D of drawings of loopless (multi‐)graphs in the plane, a drawing D∈D is saturated when the addition of any edge to D results in D′∉D—this is analogous to saturated graphs in a graph class as introduced by Turán and Erdős, Hajnal, and Moon. We focus on k‐planar drawings, that is, graphs drawn in the plane where each edge is crossed at most k times, and the classes D of all k‐planar drawings obeying a number of restrictions, such as having no crossing incident edges, no pair of edges crossing more than once, or no edge crossing itself. While saturated k‐planar drawings are the focus of several prior works, tight bounds on how sparse these can be are not well understood. We establish a generic framework to determine the minimum number of edges among all n‐vertex saturated k‐planar drawings in many natural classes. For example, when incident crossings, multicrossings and selfcrossings are all allowed, the sparsest n‐vertex saturated k‐planar drawings have 2k−(kmod2)(n−1) edges for any k≥4, while if all that is forbidden, the sparsest such drawings have 2(k+1)k(k−1)(n−1) edges for any k≥6. [ABSTRACT FROM AUTHOR]

Over the last few years, network science has proved to be useful in modelling a variety of complex systems, composed of a large number of interconnected units. The intricate pattern of interactions often allows the system to achieve complex tasks, such as synchronization or collective motions. In this regard, the interplay between network structure and dynamics has long been recognized as a cornerstone of network science. Among dynamical processes, random walks are undoubtedly among the most studied stochastic processes. While traditionally, the random walkers are assumed to be independent, this assumption breaks down if nodes are endowed with a finite carrying capacity, a feature shared by many real-life systems. Recently, a class of nonlinear diffusion processes accounting for the finite carrying capacities of the nodes was introduced. The stationary nodes densities were shown to be nonlinearly correlated with the nodes degrees, allowing to uncover the network structure by performing a few measurements of the stationary density at the level of a single arbitrary node and by solving an inverse problem. In this work, we extend this class of nonlinear diffusion processes to the case of multigraphs, in which links between nodes carry distinct attributes. Assuming the knowledge of the pattern of interactions associated with one type of links, we show how the degree distribution of the whole multigraph can be reconstructed. The effectiveness of the reconstruction algorithm is demonstrated through simulations on various multigraph topologies. [ABSTRACT FROM AUTHOR]

Studies on human mobility from abundant trajectory data have become more and more popular with the development of location-based services. Prediction for locations people may visit in the future is a significant task, helping to make visiting recommendations and manage traffic conditions. Different from other time series prediction tasks, location prediction is temporally dependent as well as spatial-aware. In this paper, we propose a novel multi-graph attention network with sequence-to-sequence structures based on spatial–temporal long short-term memory to predict future locations. Specifically, we build three graphs with movements in geographic space and apply graph attention networks to explore the latent spatial associations among geographic regions. Additionally, we come up with spatial–temporal long short-term memory and use it to establish a sequence-to-sequence framework, which collects the temporal dependence as well as some spatial information from history trajectories. The predictions of future location are finally made by aggregating spatial–temporal contexts. [ABSTRACT FROM AUTHOR]

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds. [ABSTRACT FROM AUTHOR]

The prediction of bike-sharing demand plays a pivotal role in the optimization of intelligent transportation systems, particularly amidst the COVID-19 pandemic, which has significantly altered travel behaviors and demand dynamics. In this study, we examine various spatiotemporal influencing factors associated with bike-sharing and propose the Local-Global Dynamic Multi-Graph Convolutional Network (LGDMGCN) model, driven by multi-source data, for multi-step prediction of station-level bike-sharing demand. In the temporal dimension, we dynamically model temporal dependencies by incorporating multiple sources of time semantic features such as confirmed COVID-19 cases, weather conditions, and holidays. Additionally, we integrate a time attention mechanism to better capture variations over time. In the spatial dimension, we consider factors related to the addition or removal of stations and utilize spatial semantic features, such as urban points of interest and station locations, to construct dynamic multi-graphs. The model utilizes a local-global structure to capture spatial dependencies among individual bike-sharing stations and all stations collectively. Experimental results, obtained through comparisons with baseline models on the same dataset and conducting ablation studies, demonstrate the feasibility and effectiveness of the proposed model in predicting bike-sharing demand. [ABSTRACT FROM AUTHOR]

To mitigate the negative effects of freight vehicles on urban areas, many cities have implemented road accessibility restrictions, including limited traffic zones, which restrict access to specific areas during certain times of the day. Implementing these zones creates a tradeoff between the delivery cost and time, even under the assumption of equal traversal time and travel cost. Consequently, the planners in charge of vehicle routing need to work with graphs containing information on all Pareto-optimal paths. Inspired by these changes in city logistics and the resulting computational challenges, we study the vehicle routing problem with access restrictions, where some streets are closed to traffic within a given time period. We formulate this problem using workday variables and propose two branch and price algorithms based on the underlying road network and multigraph. The results of our computational experiments demonstrate the effectiveness of the proposed algorithms, solving instances with up to 100 nodes and 33 customers, and underline the importance of considering alternative paths in reducing costs. Funding: This work was supported by KU Leuven [C14/22/026]. [ABSTRACT FROM AUTHOR]

We study the asymptotic growth rate of the labels of high-degree vertices in weighted recursive graphs (WRGs) when the weights are independent, identically distributed, almost surely bounded random variables, and as a result confirm a conjecture by Lodewijks and Ortgiese ('The maximal degree in random recursive graphs with random weights', preprint, 2020). WRGs are a generalisation of the random recursive tree and directed acyclic graph models, in which vertices are assigned vertex-weights and where new vertices attach to $m\in\mathbb{N}$ predecessors, each selected independently with a probability proportional to the vertex-weight of the predecessor. Prior work established the asymptotic growth rate of the maximum degree of the WRG model, and here we show that there exists a critical exponent $\mu_m$ such that the typical label size of the maximum-degree vertex equals $n^{\mu_m(1+o(1))}$ almost surely as n , the size of the graph, tends to infinity. These results extend results on the asymptotic behaviour of the location of the maximum degree, formerly only known for the random recursive tree model, to the more general weighted multigraph case of the WRG model. Moreover, for the weighted recursive tree model, that is, the WRG model with $m=1$ , we prove the joint convergence of the rescaled degree and label of high-degree vertices under additional assumptions on the vertex-weight distribution, and also extend results on the growth rate of the maximum degree obtained by Eslava, Lodewijks, and Ortgiese (Stoch. Process. Appl. 158 , 2023). [ABSTRACT FROM AUTHOR]

Background: The rise of network pharmacology has led to the widespread use of network-based computational methods in predicting drug target interaction (DTI). However, existing DTI prediction models typically rely on a limited amount of data to extract drug and target features, potentially affecting the comprehensiveness and robustness of features. In addition, although multiple networks are used for DTI prediction, the integration of heterogeneous information often involves simplistic aggregation and attention mechanisms, which may impose certain limitations. Results: MSH-DTI, a deep learning model for predicting drug-target interactions, is proposed in this paper. The model uses self-supervised learning methods to obtain drug and target structure features. A Heterogeneous Interaction-enhanced Feature Fusion Module is designed for multi-graph construction, and the graph convolutional networks are used to extract node features. With the help of an attention mechanism, the model focuses on the important parts of different features for prediction. Experimental results show that the AUROC and AUPR of MSH-DTI are 0.9620 and 0.9605 respectively, outperforming other models on the DTINet dataset. Conclusion: The proposed MSH-DTI is a helpful tool to discover drug-target interactions, which is also validated through case studies in predicting new DTIs. [ABSTRACT FROM AUTHOR]

This paper is a continuation of Ref. 7. In this paper, we give an explicit construction of a non-Bichon type co-action on a multigraph that is, it preserves quantum symmetry of (V,E) in our sense but not always in Bichon’s sense.2 This construction itself is motivated from automorphisms of quantum graphs. [ABSTRACT FROM AUTHOR]

Summary: Passenger flow prediction is an important part of daily metro operation, and its accuracy affects the deployment of train resources management. Due to the complex spatiotemporal correlation characteristics of metro passenger flow, it is necessary to describe it to improve the accuracy of passenger flow prediction. However, the existing models mainly construct the weight matrix based on the static graph and the similarity between stations when describing the spatial correlation of station passenger flow but ignore the time‐varying characteristics of the spatial correlation of station passenger flow. To address this problem, this study introduces a dynamic multi‐graph and multidimensional attention spatiotemporal model. Specifically, the Graph Convolutional Neural Network combined with dynamic multigraph extracts spatial features and the Gated Recurrent Unit extracts temporal features of passenger flow. The multidimensional attention can obtain the spatiotemporal correlation of passenger flow data by assigning weights to them. Finally, this model has been used to conduct experiments on Beijing metro passenger flow datasets with time granularity of 10 and 15 min. The result indicates that the DGMANN model outperforms state‐of‐the‐art other deep learning methods in passenger flow prediction. In addition, the effectiveness of its key submodules has been verified through ablation experiments. [ABSTRACT FROM AUTHOR]

Diagnosing individuals with autism spectrum disorder (ASD) accurately faces great challenges in clinical practice, primarily due to the data's high heterogeneity and limited sample size. To tackle this issue, the authors constructed a deep graph convolutional network (GCN) based on variable multi‐graph and multimodal data (VMM‐DGCN) for ASD diagnosis. Firstly, the functional connectivity matrix was constructed to extract primary features. Then, the authors constructed a variable multi‐graph construction strategy to capture the multi‐scale feature representations of each subject by utilising convolutional filters with varying kernel sizes. Furthermore, the authors brought the non‐imaging information into the feature representation at each scale and constructed multiple population graphs based on multimodal data by fully considering the correlation between subjects. After extracting the deeper features of population graphs using the deep GCN(DeepGCN), the authors fused the node features of multiple subgraphs to perform node classification tasks for typical control and ASD patients. The proposed algorithm was evaluated on the Autism Brain Imaging Data Exchange I (ABIDE I) dataset, achieving an accuracy of 91.62% and an area under the curve value of 95.74%. These results demonstrated its outstanding performance compared to other ASD diagnostic algorithms. [ABSTRACT FROM AUTHOR]

We study the minimum number of maximum matchings in a bipartite multigraph G $G$ with parts X $X$ and Y $Y$ under various conditions, refining the well‐known lower bound due to M. Hall. When ∣X∣=n $| X| =n$, every vertex in X $X$ has degree at least k $k$, and every vertex in X $X$ has at least r $r$ distinct neighbors, the minimum is r!(k−r+1) $r!(k-r+1)$ when n≥r $n\ge r$ and is [r+n(k−r)]∏i=1n−1(r−i) $[r+n(k-r)]{\prod }_{i=1}^{n-1}(r-i)$ when n≤r $n\le r$. When every vertex has at least two neighbors and ∣Y∣−∣X∣=t≥0 $| Y| -| X| =t\ge 0$, the minimum is [(n−1)t+2+b](t+1) $[(n-1)t+2+b](t+1)$, where b=∣E(G)∣−2(n+t) $b=| E(G)| -2(n+t)$. We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions. [ABSTRACT FROM AUTHOR]

Let G be a simple, undirected and connected graph. A subset S ⊆ V (G) is a geodetic cover of G if IG[S] = V (G), where IG[S] is the set of all vertices of G lying on any geodesic between two vertices in S. A geodetic cover S of G is a closed geodetic cover if the vertices in S are sequentially selected as follows: Select a vertex v1 and let S1 = {v1}. If G is nontrivial, select a vertex v2 ̸= v1 and let S2 = {v1, v2}. Where possible, for i ≥ 3, successively select vertex vi ∈/ IG[Si−1] and let Si = {v1, v2, ..., vi}. Then there exists a positive integer k such thatSk = S. A geodetic cover S of G is a geodetic hop dominating set if every vertex in V (G) \ S is of distance 2 from a vertex in S. A geodetic hop dominating set S is a closed geodetic hop dominating set if S is a closed geodetic cover of G. The minimum cardinality of a (closed) geodetic hop dominating set of G is the (closed) geodetic hop domination number of G. This study initiates the study of the closed geodetic hop domination. First, it characterizes all graphs G of order n whose closed geodetic hop domination numbers are 2 or n, and determines the closed geodetic hop domination number of paths, cycles and multigraphs. Next, it shows that any positive integers a and b with 2 ≤ a ≤ b are realizable as the closed geodetic number and closed geodetic hop domination number of a connected graph. Also, every positive integer n, m and k with 4 ≤ m ≤ k and 2k−m+2 ≤ n are realizable as the order, geodetic hop domination number and closed geodetic hop domination number, respectively of a connected graph. Furthermore, the study characterizes the closed geodetic hop dominating sets of graphs resulting from the join, corona and edge corona of graphs. [ABSTRACT FROM AUTHOR]

That the activities of organisms influence their surrounding ecological communities, and the environment, has long been appreciated by palaeontologists, as has the role of these activities on both ecological and evolutionary processes. Spillover effects extend the range of ecosystem‐engineering through ecological networks, generating network effects that because of their non‐trophic nature can be challenging to track. Moreover, the cumulative effect of organismal activities can persist far beyond the lifespan of individual organisms, producing ecological inheritances that influence macroecological and macroevolutionary dynamics. This contribution surveys macroevolutionary patterns arising from ecosystem engineering, their potential contribution to evolutionary radiations, and the significance of ecosystem engineering as a public good in the success of evolutionary innovations. Anecdotally, such activities appear to have made important contributions, but considerable work is required for more rigorous understanding. I describe two challenges: the need for palaeontologists to collect abundance data in a way that facilitates comparative study, and the importance of more robust models of ecological (not just trophic) networks involving multigraphs and hypergraphs. [ABSTRACT FROM AUTHOR]

Traditional load prediction methods are unable to effectively predict the loads according to the spatial topology of each electricity consumer in neighboring areas and the load dependency correlations. In order to further improve the load prediction accuracy of each consumer in the region, this paper proposes a shortterm prediction method of electric load based on multi-graph convolutional network. First, the input data are selected with maximum information coefficient method by integrating multi-dimensional information such as load, weather, electricity price and date in the areas. Then, a gated convolutional network is used as a temporal convolutional layer to capture the temporal features of the loads. Moreover, a physical-virtual multi-graph convolutional network is constructed based on the spatial location of each consumer as well as load dependencies to capture the different evolutionary correlations of each spatial load. Comparative studies have validated the effectiveness of the proposed model in improving the prediction accuracy of power loads for each consumer. [ABSTRACT FROM AUTHOR]

The ongoing COVID-19 pandemic continues to pose significant challenges worldwide, despite widespread vaccination. Researchers are actively exploring antiviral treatments to assess their efficacy against emerging virus variants. The aim of the study is to employ M-polynomial, neighborhood M-polynomial approach and QSPR/QSAR analysis to evaluate specific antiviral drugs including Lopinavir, Ritonavir, Arbidol, Thalidomide, Chloroquine, Hydroxychloroquine, Theaflavin and Remdesivir. Utilizing degree-based and neighborhood degree sum-based topological indices on molecular multigraphs reveals insights into the physicochemical properties of these drugs, such as polar surface area, polarizability, surface tension, boiling point, enthalpy of vaporization, flash point, molar refraction and molar volume are crucial in predicting their efficacy against viruses. These properties influence the solubility, permeability, and bio availability of the drugs, which in turn affect their ability to interact with viral targets and inhibit viral replication. In QSPR analysis, molecular multigraphs yield notable correlation coefficients exceeding those from simple graphs: molar refraction (MR) (0.9860), polarizability (P) (0.9861), surface tension (ST) (0.6086), molar volume (MV) (0.9353) using degree-based indices, and flash point (FP) (0.9781), surface tension (ST) (0.7841) using neighborhood degree sum-based indices. QSAR models, constructed through multiple linear regressions (MLR) with a backward elimination approach at a significance level of 0.05, exhibit promising predictive capabilities highlighting the significance of the biological activity I C 50 (Half maximal inhibitory concentration). Notably, the alignment of predicted and observed values for Remdesivir's with obs p I C 50 = 6.01 ,pred p I C 50 = 6.01 ( p I C 50 represents the negative logarithm of I C 50 ) underscores the accuracy of multigraph-based QSAR analysis. The primary objective is to showcase the valuable contribution of multigraphs to QSPR and QSAR analyses, offering crucial insights into molecular structures and antiviral properties. The integration of physicochemical applications enhances our understanding of factors influencing antiviral drug efficacy, essential for combating emerging viral strains effectively. [ABSTRACT FROM AUTHOR]

This study presents an in‐depth inquiry into estimating ADME properties for promising anticancer drugs, particularly amino acid‐based alkylating agents, through ev‐ve degree topological indices and QSPR analysis. The aim of the study is to compare multigraph modeling to simple graph modeling in estimating six ADME properties. Results demonstrate that multigraph modeling's superior performance, with notable high correlations such as r=0.926$$ r=0.926 $$ for maximum passive absorption (MPA) using the M‐ev index, compared to simple graph modeling's r=0.68$$ r=0.68 $$ with the M2$$ {M}_2 $$‐ev index. This emphasizes the need for sophisticated modeling techniques in drug development. The primary objective is to compare multigraph and simple graph modeling using topological structure descriptors, followed by QSPR analysis to determine the better approach in estimating ADME properties. MCDM weight allocation techniques validate correlation values, enhancing understanding of estimators and identifying potential drugs. This underscores the importance of considering various MCDM methods and weight allocation approaches for reliable decision‐making in healthcare contexts. [ABSTRACT FROM AUTHOR]

Graph semi-supervised learning (GSSL) plays an important role in semi-supervised classification by leveraging the similarity of graph topology and convex optimization with Laplacian-based regularization. Current approaches mainly focus on data representation in the Euclidean space and solely rely on a single graph structure, ignoring the underlined manifold-valued structure of the data. To this end, we propose a novel manifold-based multi-graph embedding (M2GE), which explicitly learns representations on both Riemannian manifold and Euclidean space in the embedding learning process. Incorporating multi-graph structure, the rich and varied features are used by M2GE to more fully capture categorical information, where the heterogeneous spatial representations from manifold are complementary. Extensive experimental results on three popular benchmarks verify demonstrate the superiority of our method over state-of-the art competitors. • A novel manifold-based multi-graph embedding (M2GE) is proposed for semi-supervised classification. • Multi-sampling augmentation is employed to improve the generalization of the model. • M2GE effectively improves the accuracy rate of the semi-supervised classification. [ABSTRACT FROM AUTHOR]

Unsupervised salient object detection is an important task in many real-world scenarios where pixel-wise label information is of scarce availability. Despite its significance, this problem remains rarely explored, with a few works that consider unsupervised salient object detection methods based on the fused graph from the sum fusion of multiple deep feature similarity matrices. However, these methods ignore the interrelation of the low-level feature similarity matrices and the high-level semantic similarity matrice, which degrades the quality of the fused graph. In this article, we propose a semantic-consistency-guided multi-graph fusion learning algorithm for unsupervised saliency detection, where the consistency and inconsistency between multiple low-level feature similarity matrices and the high-level semantic similarity matrice are explored to promote the robustness and quality of the fused graph. In the first stage, a semantic-consistency-guided multi-graph fusion learning method is proposed to exploit consistency and inconsistency of multiple low-level deep features and the high-level semantic feature. The semantic-consistency-guided similarity matrices are computed for preliminary saliency ranking. In the following saliency refinement stage, the semantic-enhanced similarity matrices are built by the cross diffusion to fuse the multiple low-level deep features and the high semantic deep feature. Based on the semantic-enhanced similarity matrices, the refinement saliency maps are calculated in a semantic-enhanced cellular automata manner. Furthermore, the final ensemble stage of the large margin semi-supervised classification views the preliminary ranking results and refinement results as features, adopts the large margin graphs for saliency ensemble. Extensive evaluations over four benchmark datasets show that the proposed unsupervised method performs favorably against the state-of-the-art approaches and is competitive with some supervised deep learning-based methods. [ABSTRACT FROM AUTHOR]

Predicting terrorism risk is crucial for formulating detailed counter‐strategies. However, this task is challenging mainly because the risk of the concerned potential victim is not isolated. Terrorism risk has a spatiotemporal interprovincial contagious characteristic. The risk diffusion mechanism comes from three possibilities: cross‐provincial terrorist attacks, internal and external echoes, and internal self‐excitation. This study proposed a novel spatiotemporal graph convolutional network (STGCN)‐based extension method to capture the complex and multidimensional non‐Euclidean relationships between different provinces and forecast the daily risks. Specifically, three graph structures were constructed to represent the contagious process between provinces: the distance graph, the province‐level root cause similarity graph, and the self‐excited graph. The long short‐term memory and self‐attention layers were extended to STGCN for capturing context‐dependent temporal characters. At the same time, the one‐dimensional convolutional neural network kernel with the gated linear unit inside the classical STGCN can model single‐node‐dependent temporal features, and the spectral graph convolution modules can capture spatial features. The experimental results on Afghanistan terrorist attack data from 2005 to 2020 demonstrate the effectiveness of the proposed extended STGCN method compared to other machine learning prediction models. Furthermore, the results illustrate the crucial of capturing comprehensive spatiotemporal correlation characters among provinces. Based on this, this article provides counter‐terrorism management insights on addressing the long‐term root causes of terrorism risk and performing short‐term situational prevention. [ABSTRACT FROM AUTHOR]

With the development of deep learning, deep neural methods have been introduced to boost the performance of Collaborative Filtering (CF) models. However, most of the models rely solely on the user-item heterogeneous graph and only implicitly capture homogenous information, which limits their performance improvement. Although some state-of-the-art methods try to utilize additional graphs to make up, they either merely aggregate the information of multiple graphs in the step of initial embedding or only merge different multi-graph information in the step of final embedding. Such one-time multi-graph integration leads to the loss of interactive and topological information in the intermediate process of propagation. This paper proposes a novel Multi-Graph iterative fusion Recommendation Framework (MGRF) for CF recommendation. The core components are dual information crossing interaction and multi-graph fusing propagation. The former enables repeated feature crossing between heterogeneous nodes throughout the whole embedding process. The latter repeatedly integrates homogeneous nodes as well as their topological relationships based on the constructed user-user and itemitem graphs. Thus, MGRF can improve the embedding quality by iteratively fusing user-item heterogeneous graph, user-user and item-item homogeneous graphs. Extensive experiments on three public benchmarks demonstrate the effectiveness of MGRF, which outperforms state-of-the-art baselines in terms of Recall and NDCG. [ABSTRACT FROM AUTHOR]

Software quality is key to the success of software systems. Modern software systems are growing in their worth based on industry needs and becoming more complex, which inevitably increases the possibility of more defects in software systems. Software repairing is time‐consuming, especially locating the source files related to specific software defect reports. To locate defective source files more quickly and accurately, automated software defect location technology is generated and has a huge application value. The existing deep learning‐based software defect location method focuses on extracting the semantic correlation between the source file and the corresponding defect reports. However, the extensive code structure information contained in the source files is ignored. To this end, we propose a software defect location method, namely, multi‐graph learning‐based software defect location (MGSDL). By extracting the program dependency graphs for functions, each source file is converted into a graph bag containing multiple graphs (i.e., multi‐graph). Further, a multi‐graph learning method is proposed, which learns code structure information from multi‐graph to establish the semantic association between source files and software defect reports. Experiments' results on four publicly available datasets, AspectJ, Tomcat, Eclipse UI, and SWT, show that MGSDL improves on average 3.88%, 5.66%, 13.23%, 9.47%, and 3.26% over the competitive methods in five evaluation metrics, rank@10, rank@5, MRR, MAP, and AUC, respectively. [ABSTRACT FROM AUTHOR]

Stock price prediction is considered a classic and challenging task, with the potential to aid traders in making more profitable trading decisions. Significant improvements in stock price prediction methods based on deep learning have been observed in recent years. However, most existing methods are reliant solely on historical stock price data for predictions, resulting in the inability to capture market dynamics beyond price indicators, thus limiting their performance to some extent. Therefore, combining social media text with historical stock price information has proposed a novel stock price prediction method, known as the Deep Cross-Modal Information Fusion Network (DCIFNet). The process is initiated by DCIFNet, which employs temporal convolution processes to encode stock prices and Twitter content. This ensures that each element has sufficient information about its surrounding components. Following this, the outcomes are inputted into a cross-modal fusion structure based on transformers to enhance the integration of crucial information from stock prices and Twitter content. Lastly, a multi-graph convolution attention network is introduced to depict the relationships between different stocks from diverse perspectives. This facilitates the more effective capturing of industry affiliations, Wikipedia references, and associated relationships among linked stocks, ultimately leading to an enhancement in stock price prediction accuracy. Trend prediction and simulated trading experiments are conducted on high-frequency trading datasets spanning nine different industries. Comparative assessments with the Multi-Attention Network for Stock Prediction (MANGSF) method, as well as ablation experiments, confirm the effectiveness of the DCIFNet approach, resulting in an accuracy rate of 0.6309, a marked improvement compared to representative methods in the field. [ABSTRACT FROM AUTHOR]

We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k, one can in randomized k(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(G)}{2}\) such that the following holds: for every inclusion-wise minimal st-cut Z in G of cardinality at most k, Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2-(k log k). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2-(k log k) instead of 2-(k4 log k)), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st-Cut problem can be solved in randomized FPT time 2(k log k)(|V(G)|+|E(G)|) on undirected graphs. [ABSTRACT FROM AUTHOR]

Wang and Yu (2022) prove an enhanced version of the Erdős–Lovász Tihany conjecture for line graphs of multigraphs. That is, let s , t and ℓ be arbitrary integers with t ≥ s ≥ 3. 5 ℓ + 2 , ℓ ≥ 0. If the line graph L (G) of some multigraph G has chromatic number s + t − 1 > ω (L (G)) , then there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + ℓ. In this paper, for integers s and t with t ≥ s ≥ 7 , we prove that for each line graph L (G) with χ (L (G)) = s + t − 1 ≥ ω (L (G)) , there is a partition (S , T) of the vertex set V (L (G)) such that χ (L (G) [ S ]) ≥ s and χ (L (G) [ T ]) ≥ t + 2 , which slightly improves the recent result of Wang and Yu (2022) for ℓ = 2. [ABSTRACT FROM AUTHOR]

Let $\ell $ be a prime number. The Iwasawa theory of multigraphs is the systematic study of growth patterns in the number of spanning trees in abelian $\ell $ -towers of multigraphs. In this context, growth patterns are realized by certain analogs of Iwasawa invariants, which depend on the prime $\ell $ and the abelian $\ell $ -tower of multigraphs. We formulate and study statistical questions about the behavior of the Iwasawa $\mu $ and $\lambda $ invariants. [ABSTRACT FROM AUTHOR]

A graphoid is a mixed multigraph with multiple directed and/or undirected edges, loops, and semiedges. A covering projection of graphoids is an onto mapping between two graphoids such that at each vertex, the mapping restricts to a local bijection on incoming edges and outgoing edges. Naturally, as it appears, this definition displays unusual behaviour since the projection of the corresponding underlying graphs is not necessarily a graph covering. Yet, it is still possible to grasp such coverings algebraically in terms of the action of the fundamental monoid and combinatorially in terms of voltage assignments on arcs. In the present paper, the existence theorem is formulated and proved in terms of the action of the fundamental monoid. A more conventional formulation in terms of the weak fundamental group is possible because the action of the fundamental monoid is permutational. The standard formulation in terms of the fundamental group holds for a restricted class of coverings, called homogeneous. Further, the existence of the universal covering and the problems related to decomposing regular coverings via regular coverings are studied in detail. It is shown that with mild adjustments in the formulation, all the analogous theorems that hold in the context of graphs are still valid in this wider setting. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]