Search

This work generalizes the recently introduced bubble entropy (BE) algorithm for univariate time series to graph and network analysis. In this paper, we introduce a modified method, called bubble entropy for graph signals (BEG), as an invaluable tool for detecting the irregularity of signals defined on graphs. Our algorithm is based on using the adjacency matrix to combine the signal values with the topology of the graph. Experiments on both synthetic and real data demonstrate the availability of the proposed measures in detecting the irregularity of graph signals and identifying topological changes in graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

The (k , r) -fan, denoted by F k , r , is the graph consisting of k copies of the complete graph K r which intersect in a single vertex. Desai et al. [7] proved that E X s p (n , F k , r) ⊆ E X (n , F k , r) for sufficiently large n , where E X s p (n , F k , r) and E X (n , F k , r) are the sets of n -vertex F k , r -free graphs with maximum spectral radius and maximum size, respectively. In this paper, the set E X s p (n , F k , r) is uniquely determined for n large enough. Let H s , t 1 , ... , t k be the graph consisting of s triangles and k odd cycles of lengths t 1 , ... , t k ≥ 5 intersecting in exactly one common vertex, denoted by H s , k for short. Li and Peng [12] showed that E X s p (n , H s , k) ⊆ E X (n , H s , k) for n large enough. In this paper, the set E X s p (n , H s , k) is uniquely characterized for sufficiently large n. [ABSTRACT FROM AUTHOR]

The comaximal graph Γ (R) of a commutative ring R is a simple graph with vertex set R and two distinct vertices u and v of Γ (R) are adjacent if and only if u R + v R = R. In this paper, we find the sharp bounds for the Sombor index for comaximal graphs of integer modulo ring ℤ n and give the corresponding extremal graphs. Also, we find the Sombor eigenvalues and the bounds for the Sombor energy of comaximal graphs of ℤ n . [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with λ as an eigenvalue (i.e. an eigenvalue of the adjacency matrix of G), and let H be a star complement for λ in G. Motivated by a controllability condition, we say that H is a strong star complement for λ if G and H have no eigenvalue in common. We explore this concept in the context of line graphs, exceptional graphs, strongly regular graphs and graphs with a prescribed star complement. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [ABSTRACT FROM AUTHOR]

This paper established the idea of minimum evdominating matrix of semigraph and calculated its energy. The minimum ev-dominating energy EmeD(G) of a semigraph G is the sum of the absolute values of the eigenvalues of the minimum ev-dominating matrix. Here some results are also derived in connection with the energy of minimum evdominating matrix. Some lower bounds are also established. [ABSTRACT FROM AUTHOR]

A graph is called unimodular if its adjacency matrix has determinant ± 1. This article provides a necessary and sufficient condition for a simple connected graph with a unique perfect matching to be unimodular. In particular, we give a complete characterization of bicyclic unimodular graphs with a unique perfect matching. Moreover, the possible values of the determinant of the adjacency matrix of unicyclic, bicyclic, and tricyclic graphs with a unique perfect matching are also provided in this article. For non-bipartite unicyclic graphs with a unique perfect matching, we address the problem of when the inverse of the corresponding adjacency matrix is diagonally similar to a non-negative matrix. A pseudo-unimodular graph is a singular graph whose product of non-zero eigenvalues of the corresponding adjacency matrix is ± 1. We supply a necessary and sufficient condition for a singular graph to be pseudo-unimodular. [ABSTRACT FROM AUTHOR]

Let (G, w) be a weighted graph with the adjacency matrix A. The group inverse of (G, w), denoted by (G # , w #) is the weighted graph with the weight w # (v i v j) of an edge v i v j in G # is defined as the ijth entry of A # , the group inverse of A. We study the group inverse of singular weighted trees. It is shown that if (T, w) is a singular weighted tree, then (T # , w #) is again a weighted tree if and only if (T, w) is a star tree, which in turn holds if and only if (T # , w #) is graph isomorphic to (T, w). A new class T w of weighted trees is introduced and studied here. It is shown that the group inverse of the adjacency matrix of a positively weighted tree in T w is signature similar to a non-negative matrix. [ABSTRACT FROM AUTHOR]

Let A(G) be the adjacency matrix of a simple connected undirected graph G. A graph G of order n is said to be non-singular (respectively singular) if A(G) is non-singular (respectively singular). The spectrum of a graph G is the set of all its eigenvalues denoted by spec(G). The antireciprocal (respectively reciprocal) eigenvalue property for a graph G can be defined as "Let G be a non-singular graph G if the negative reciprocal (respectively positive reciprocal) of each eigenvalue is likewise an eigenvalue of G, then G has anti-reciprocal (respectively reciprocal) eigenvalue property." Furthermore, a graph G is said to have strong anti-reciprocal eigenvalue property (resp. strong reciprocal eigenvalue property) if the eigenvalues and their negative (resp. positive) reciprocals are of same multiplicities. In this article, graphs satisfying anti-reciprocal eigenvalue (or property (-R)) and strong anti-reciprocal eigenvalue property (or property (-SR)) are discussed. [ABSTRACT FROM AUTHOR]

Emotion is one of the most important higher cognitive functions of the human brain and plays an important role in transaction processing and decisions. In traditional emotion recognition studies, the frequency band features in EEG signals have been shown to have a high correlation with emotion production. However, traditional emotion recognition methods cannot satisfactorily solve the problem of individual differences in subjects and data heterogeneity in EEG, and subject-independent emotion recognition based on EEG signals has attracted extensive attention from researchers. In this paper, we propose a subject-independent emotion recognition model based on adaptive extraction of layer structure based on frequency bands (BFE-Net), which is adaptive in extracting EEG map features through the multi-graphic layer construction module to obtain a frequency band-based multi-graphic layer emotion representation. To evaluate the performance of the model in subject-independent emotion recognition studies, extensive experiments are conducted on two public datasets including SEED and SEED-IV. The experimental results show that in most experimental settings, our model has a more advanced performance than the existing studies of the same type. In addition, the visualization of brain connectivity patterns reveals that some of the findings are consistent with previous neuroscientific validations, further validating the model in subject-independent emotion recognition studies. [ABSTRACT FROM AUTHOR]

For a set of graphs F , a graph is said to be F -free if it does not contain any graph in F as a subgraph. Let Ex s p (n , F) denote the graphs with the maximum spectral radius among all F -free graphs of order n. A linear forest is a graph whose connected components are paths. Denote by L s the family of all linear forests with s edges. In this paper the graphs in Ex s p (n , { K k + 1 , L s }) will be completely characterized when n is appropriately large. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (A) is the maximum absolute value of the eigenvalues of a matrix A. In this paper, we establish some relationship between the spectral radius of a symmetric matrix and its principal submatrices, i.e., if A is partitioned as a 2 × 2 block matrix A = ( 0 A 12 A 21 A 22 ) , then ρ (A) 2 ≤ ρ 2 2 + θ ⁎ , where θ ⁎ is the largest real root of the equation μ 2 = (x − ν) 2 (ρ 2 2 + x) and ρ 2 = ρ (A 22) , μ = ρ (A 12 A 22 A 21) , ν = ρ (A 12 A 21). Furthermore, the results are used to obtain several upper bounds of the spectral radius of graphs, which strengthen or improve some known results. [ABSTRACT FROM AUTHOR]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

In this article, we discuss the spectral properties of the general extended adjacency matrix for chain graphs. In particular, we discuss the eigenvalues of the general extended adjacency matrix of the chain graphs and obtain its general extended adjacency inertia. We obtain bounds for the largest and the smallest general extended adjacency eigenvalues and characterize the extremal graphs. We also obtain a lower bound for the spread of the general extended adjacency matrix. We characterize chain graphs with all the general extended adjacency eigenvalues being simple and chain graphs that are non-singular under the general extended adjacency matrix. Further, we determine the explicit formula for the determinant and the trace of the square of the general extended adjacency matrix of chain graphs. Finally, we discuss the energy of the general extended adjacency matrix and obtain some bounds for it. We characterize the extremal chain graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

Epilepsy is a chronic brain disease, and identifying seizures based on electroencephalogram (EEG) signals would be conducive to implement interventions to help patients reduce impairment and improve quality of life. In this paper, we propose a classification algorithm to apply dynamical graph neural network with attention mechanism to single channel EEG signals. Empirical mode decomposition (EMD) are adopted to construct graphs and the optimal adjacency matrix is obtained by model optimization. A multilayer dynamic graph neural network with attention mechanism is proposed to learn more discriminative graph features. The MLP-pooling structure is proposed to fuse graph features. We performed 12 classification tasks on the epileptic EEG database of the University of Bonn, and experimental results showed that using 25 runs of ten-fold cross-validation produced the best classification results with an average of 99.83 % accuracy, 99.91 % specificity, 99.78 % sensitivity, 99.87 % precision, and 99.47 % F 1 score for the 12 classification tasks. [ABSTRACT FROM AUTHOR]

Power forecast for each renewable power plant (RPP) in the renewable energy clusters is essential. Though existing graph neural networks (GNN)-based models achieve satisfactory prediction performance by capturing dependencies among distinct RPPs, the static graph structure employed in these models ignores crucial lead-lag correlations among RPPs, resulting from the time difference of the air flow at spatially dispersed RPPs. To address this problem, this paper proposes a novel dynamic graph structure using multiple temporal granularity groups (TGGs) to characterize the lead-lag correlations among RPPs. A granular-based GNN called GGNet is designed to generate an optimal adjacency matrix for the proposed graph structure. Specifically, a two-dimensional convolutional neural network (2D-CNN) is used to quantify the uncertain lead-lag correlations among RPPs; secondly, a gate mechanism is used to calculate a dynamic adjacency matrix; Finally, a graph attention network (GAT) is used to aggregate the information on RPPs based on the well-learned adjacency matrix. Case studies conducted using real-world datasets, with wind power plants and photovoltaic power plants, show our method outperforms state-of-the-art (SoTA) ones with better performance. Compared with the SoTA models, the RMSE N and MAE N of wind power plants for 1–4 h forecast steps decreased on average by 22.925% and 13.18%, respectively; the RMSE N and MAE N of photovoltaic power plants for 1–4 h forecast steps decreased on average by 48.95% and 18.75%, respectively. The results show that the proposed framework can generate improved performance with accuracy and robustness. • Dynamic graph structure can clarify lead-lag power correlation of renewable plants. • A novel model can quantity the lead-lag power correlation of renewable plants. • Memory cell can make the adjacency matrix among renewable plants learnable. • A graph attention network can improve power forecast accuracy of renewable plants. [ABSTRACT FROM AUTHOR]

Ergonomic risk assessment (ERA) is commonly used to identify and analyze postures that are detrimental to the health of workers in industrial workplaces, which is vital to prevent work-related musculoskeletal disorders (WMSDs). Among the automatic approaches, algorithms based on graph convolutional networks (GCNs) have shown promising results in ERA using skeleton sequence as input. However, previous GCN-based methods still have certain limitations. First, the separated modeling of spatial and temporal information and the manually pre-defined topology of graph may restrict the representation diversity of the networks. Additionally, RNN-based temporal modeling often incurs high computational costs and fails to capture long-range temporal dependencies, thereby reducing flexibility in describing long videos. To overcome these challenges, in this study, we propose an attention-based adaptive spatial–temporal graph convolutional network (AAST-GCN), aiming to achieve effective and efficient action representation for ERA in long video. First, we employ an alternate modeling strategy to effectively capture the spatial–temporal information, and propose an improved adaptive adjacency matrix scheme to learn various coordination and relations of body-joints, thus enhancing the flexibility to model diverse postures. Furthermore, we introduce an efficient multi-scale temporal convolutional network as a replacement for RNN-based algorithms, enabling the network to extract various granularities of temporal features. Moreover, to make the network focuses on more valuable information, we employ a spatial–temporal interaction attention (STIA) module. Finally, the aforementioned modules are aggregated within a multi-task learning framework, with the action segmentation serving as the auxiliary task to further improve the accuracy of ERA. We conducted the ergonomic risk assessment on the UW-IOM and TUM Kitchen datasets using our network. Extensive experiments conducted on the most popular datasets UW-IOM and TUM Kitchen demonstrated that our proposed AAST-GCN outperforms other GCN-based methods. Ablation studies and visualization also prove the effectiveness of the individual sub-modules. [ABSTRACT FROM AUTHOR]

A gain graph over a group G , also referred to as G -gain graph, is a graph where an element of a group G , called gain, is assigned to each oriented edge, in such a way that the inverse element is associated with the opposite orientation. Gain graphs can be regarded as a generalization of signed graphs, among others. In this work, we show a new switching method to construct cospectral gain graphs. Some previous methods known for graph cospectrality follow as a corollary of our results. [ABSTRACT FROM AUTHOR]

Accurate traffic flow forecasting is an important technical measure to alleviate traffic congestion. Since traffic flow has spatial and temporal characteristics, thus the adequate extraction of its spatio-temporal features is an important prerequisite to promote the forecast accuracy of the model. However, a majority of existing traffic flow prediction models cannot sufficiently consider the neighborhood spatio-temporal relationship for the real road network in the modeling process, which makes it difficult to improve the model prediction accuracy. For this reason, this paper takes improved feature enhancement graph convolution (FEGC), gated recurrent unit (GRU), and improved lightweight particle swarm optimization (ILPSO) algorithm as components, respectively, to construct a combinatorial traffic flow prediction model FEGC-GRU-ILPSO (FGI), aiming to achieve accurate forecast for regional traffic flow through fully learning spatio-temporal correlation characteristics. Firstly, considering that most traffic flow modeling methods are ineffective in characterizing the hidden association information within nodes, we propose the method of constructing the virtual space adjacency matrix based on the improved gray relational analysis (IGRA) algorithm, which achieves the effective characterization of road network neighborhood relationship by fusing it with the original adjacency matrix. Then, based on the idea of matrix decomposition, the weight adjacency matrix is further introduced to realize the dynamic capture of time-varying correlation of node graph structure in realistic road networks. Secondly, to address the performance degradation problem caused by feature assimilation in multi-layer graph convolution, an improved feature enhancement graph convolution component is proposed to alleviate the multi-layer graph convolution over-smoothing by enhancing salient features. Finally, considering the convex optimization problem caused by the way the hyperparameters of the model are determined through subjective experience, we propose the ILPSO algorithm to improve the overall prediction performance in an adaptive optimizing method. In this paper, real-world data acquired by the Caltrans Performance Measurement System (PeMS) is used as the object of study. The experimental results demonstrate that the FGI model has better prediction performance than the current mainstream baseline models. • An adaptive weighted adjacency matrix is proposed to learn road network features. • A feature enhancement graph convolution is proposed to reinforce important features. • An improved particle swarm algorithm is proposed to optimize the model parameters. • The feature capture process of feature enhancement graph convolution is visualized. • The proposed model has superior prediction accuracy than the baseline models. [ABSTRACT FROM AUTHOR]

We consider linear ternary codes generated by A + β I , where A is the adjacency matrix of a strongly regular signed graph, I is the identity matrix and β ∈ F 3. Our results include theoretical examinations on dimension and distance, and the interplay between the codes. We also compute many structural parameters of codes for some infinite families of strongly regular signed graphs and establish more than 60 particular codes of comparatively small dimension. It occurs that some known linear ternary codes are covered by this approach. [ABSTRACT FROM AUTHOR]