Search

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [ABSTRACT FROM AUTHOR]

Different from other computer vision tasks, action recognition needs to process larger-scale video data. How to extract and analyze the effective parts from a huge amount of video information is the main difficulty of action recognition technology. In recent years, due to the outstanding performance of Graph Convolutional Networks (GCN) in many fields, a new solution to the action recognition algorithm has emerged. However, in current GCN models, the constant physical adjacency matrix makes it difficult to mine synergistic relationships between key points that are not directly connected in physical space. Additionally, a simple time connection of skeleton data from different frames makes each frame in the video contribute equally to the recognition results, which increases the difficulty of distinguishing action stages. In this paper, the information extraction ability of the model has been optimized in the space domain and time domain, respectively. In the space domain, an Adjacency Matrix Generation (AMG) module, which can pre-analyze node sets and generate an adaptive adjacency matrix, has been proposed. The adaptive adjacency matrix can help the graph convolution model to extract the synergistic information between the key points that are crucial for recognition. In the time domain, the Time Domain Attention (TDA) mechanism has been designed to calculate the time-domain weight vector through double pooling channels and complete the weights of key point sequences. Furthermore, performance of the improved TDA-AMG-GCN modules has been verified on the NTU-RGB+D dataset. Its detection accuracy at the CS and CV divisions reached 84.5% and 89.8%, respectively, with an average level higher than other commonly used detection methods at present. [ABSTRACT FROM AUTHOR]

Graph convolutional networks (GCNs), which extend convolutional neural networks (CNNs) to non-Euclidean structures, have been utilized to promote skeleton-based human action recognition research and have made substantial progress in doing so. However, there are still some challenges in the construction of recognition models based on GCNs. In this paper, we propose an enhanced adjacency matrix-based graph convolutional network with a combinatorial attention mechanism (CA-EAMGCN) for skeleton-based action recognition. Firstly, an enhanced adjacency matrix is constructed to expand the model's perceptive field of global node features. Secondly, a feature selection fusion module (FSFM) is designed to provide an optimal fusion ratio for multiple input features of the model. Finally, a combinatorial attention mechanism is devised. Specifically, our spatial-temporal (ST) attention module and limb attention module (LAM) are integrated into a multi-input branch and a mainstream network of the proposed model, respectively. Extensive experiments on three large-scale datasets, namely the NTU RGB+D 60, NTU RGB+D 120 and UAV-Human datasets, show that the proposed model takes into account both requirements of light weight and recognition accuracy. This demonstrates the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Modeling complex spatial and temporal dependencies in multivariate time series data is crucial for traffic forecasting. Graph convolutional networks have proved to be effective in predicting multivariate time series. Although a predefined graph structure can help the model converge to good results quickly, it also limits the further improvement of the model due to its stationary state. In addition, current methods may not converge on some datasets due to the graph structure of these datasets being difficult to learn. Motivated by this, we propose a novel model named Dynamic Correlation Graph Convolutional Network (DCGCN) in this paper. The model can construct adjacency matrices from input data using a correlation coefficient; thus, dynamic correlation graph convolution is used for capturing spatial dependencies. Meanwhile, gated temporal convolution is used for modeling temporal dependencies. Finally, we performed extensive experiments to evaluate the performance of our proposed method against ten existing well-recognized baseline methods using two original and four public datasets. [ABSTRACT FROM AUTHOR]

Accurate forecasting of taxi demand has facilitated the rational allocation of urban public transport resources, reduced congestion in urban transport networks, and shortened passenger waiting time. However, virtual station discovery and modelling of the demand when forecasting through graph convolutional neural networks remains challenging. In this study, the virtual station discovery problem was addressed by using a two-stage clustering approach, which considers the geographical and load characteristics of taxi demand. Furthermore, a fusion model combining non-negative matrix decomposition and a graph convolutional neural network was proposed in order to extract the features of the nodes for dimension reduction and adaptive adjacency matrix computation. By the construction of a local processing structure, further extraction of the local characteristics of the demand was achieved. The experimental results show that the method in this study outperforms state-of-the-art methods in terms of the root mean square error and average absolute value error. Therefore, the model proposed in this study is able to achieve accurate forecasting of taxi demand. [ABSTRACT FROM AUTHOR]

Exploring a general and effective method of isomorphism identification is an arduous task. For this aim, some new concepts such as binary link path and link-assortment adjacency matrix are introduced in this paper. On this basis, a new method is proposed to improve the operability of isomorphism identification and relieve the computational pressure. By generating new elements from structural features and connection relations among links or vertices in the graph, it transforms traditional high-ranking adjacency matrix into new low-ranking adjacency matrix. Some typical graphs including kinematic chains, topological graphs, and planetary gear trains are used to verify the effectiveness of the proposed method. As shown by a comparison with results in the cited references, the proposed method is available in isomorphism identification. [ABSTRACT FROM AUTHOR]

The research on node importance identification for temporal networks has attracted much attention. In this work, combined with the multi-layer coupled network analysis method, an optimized supra-adjacency matrix (OSAM) modeling method was proposed. In the process of constructing an optimized super adjacency matrix, the intra-layer relationship matrixes were improved by introducing the edge weight. The inter-layer relationship matrixes were formed by improved similarly and the inter-layer relationship is directional by using the characteristics of directed graphs. The model established by the OSAM method accurately expresses the structure of the temporal network and considers the influence of intra- and inter-layer relationships on the importance of nodes. In addition, an index was calculated by the average of the sum of the eigenvector centrality indices for a node in each layer and the node importance sorted list was obtained from this index to express the global importance of nodes in temporal networks. The experimental results on three real temporal network datasets Enron, Emaildept3, and Workspace showed that compared with the SAM and the SSAM methods, the OSAM method has a faster message propagation rate and larger message coverage and better SIR and NDCG@10 indicators. [ABSTRACT FROM AUTHOR]

The extended adjacency matrix Ae (G) of a graph G is determined by graph degrees. Some inequalities are found for the extended adjacency matrix including its vertices, its edges and its degrees in this paper. Also, some bounds are established for this matrix involving its energy and its laplacian energy. [ABSTRACT FROM AUTHOR]

Fast and accurate ellipse detection is critical in certain computer vision tasks. In this paper, we propose an arc adjacency matrix-based ellipse detection (AAMED) method to fulfill this requirement. At first, after segmenting the edges into elliptic arcs, the digraph-based arc adjacency matrix (AAM) is constructed to describe their triple sequential adjacency states. Curvature and region constraints are employed to make the AAM sparse. Secondly, through bidirectionally searching the AAM, we can get all arc combinations which are probably true ellipse candidates. The cumulative-factor (CF) based cumulative matrices (CM) are worked out simultaneously. CF is irrelative to the image context and can be pre-calculated. CM is related to the arcs or arc combinations and can be calculated by the addition or subtraction of CF. Then the ellipses are efficiently fitted from these candidates through twice eigendecomposition of CM using Jacobi method. Finally, a comprehensive validation score is proposed to eliminate false ellipses effectively. The score is mainly influenced by the constraints about adaptive shape, tangent similarity, distribution compensation. Experiments show that our method outperforms the 12 state-of-the-art methods on 9 datasets as a whole, with reference to recall, precision, F-measure, and time-consumption. [ABSTRACT FROM AUTHOR]

Accurate and real-time traffic forecasting is of great significance for urban traffic planning, traffic control, and traffic management. However, the time-varying dynamic spatial relations and the complicated spatial–temporal dependencies are still open problems to be considered in traffic forecasting. To address these issues, we propose a graph convolutional recurrent network for traffic forecasting with a dynamic adjacency matrix within an encoder–decoder framework, named DAGCRN. The DAGCRN consists of a spatial relation extraction module (SREM), an adjacency matrix update module (AMUM), a dynamic graph convolutional recurrent module (DGCRM), and a global temporal attention module (GTAM). Specifically, SREM and AMUM are proposed to capture nodes' mutual relations at each time step and to model the evolution of the dynamic adjacency matrix, respectively. DGCRM captures the spatial–temporal dependencies of traffic data based on dynamic graph convolution and gated recurrent unit. GTAM is designed to extract the long-range temporal dependencies between future time steps and historical time steps. Extensive experiments on two real-world traffic speed datasets demonstrate that the proposed DAGCRN outperforms a number of representative baselines consistently. [ABSTRACT FROM AUTHOR]

Abstract In this paper we introduce a new graph matrix, named the anti-adjacency matrix or eccentricity matrix, which is constructed from the distance matrix of a graph by keeping for each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping for each row and each column only the distances equal to 1. We show that the eccentricity matrix of trees is irreducible, and we investigate the relations between the eigenvalues of the adjacency and eccentricity matrices. Finally, we give some applications of this new matrix in terms of molecular descriptors, and we conclude by proposing some further research problems. [ABSTRACT FROM AUTHOR]

In a deregulated electric power system, it is important to distribute transmission losses between market participants fairly. This paper presents an effective method for active loss allocation by tracing power flow. In this method, after obtaining the alternating current (AC) load flow results of the system, it is first converted to a system in which the power flow is constant along each branch. A new matrix (i.e., power adjacency matrix) is then constructed for the system. The matrix is decoupled, and matrix operations are carried out using the submatrices to derive three other matrices. The contributions of the generators and loads of the main system to active losses of its branches and the shares of the generators in active power consumption of the loads are specified using these matrices. The proposed method is implemented on a four-bus system and several standard test systems. The results show that the method can be applied to any transmission system, and the loss allocation results are preferable to that of previous methods. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V(G) = {v1,v2,..., vn}. Let A(G) be the adjacency matrix of a graph G. The rows of A(G) corresponding to a vertex v of G, denoted by s(v) is the string. The Hamming index of a graph G is the sum of the Hamming distances between all pairs of vertices of G. In this paper we obtain Hamming index generated by adjacency matrix of some thorn graphs. [ABSTRACT FROM AUTHOR]

A mixed graph is a graph with edges and arcs, which can be considered as a hybrid of an undirected graph and a directed graph. In this paper we define the mixed adjacency matrix and the mixed energy of a mixed graph. The mixed adjacency matrix generalizes both the adjacency matrix of an undirected graph and the skew-adjacency matrix of a digraph. Then we compute the characteristic polynomial of the mixed adjacency matrix of a mixed graph and deduce some basic results from it. Furthermore, we give bounds to the mixed energy of a general mixed graph, and we compute the mixed energy of some special mixed graphs. At the end of the paper, we introduce mixed unitary Cayley graphs and compute their spectra. [ABSTRACT FROM AUTHOR]

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]

This article provides a new approach to searching solutions of water transport optimization problems. It brings a new tool of the graph theory which is the Weighted Adjacency Matrix. This Weighted Adjacency Matrix is suitable for searching for the Minimum Spanning Tree (MST) of the graph. It describes the Weighted Adjacency Matrix as a new element, and shows how it could be used in cases where weighted edges of the graph are given. This creates a new procedure of searching the MST of the graph and completes previously known algorithms of searching for the MST. In the field of ship transportation it could be succesfully used for solutions of optimizing transportation routes where lowest transport costs are needed. Proposed Weighted Adjacency Matrix could be used in similar issues in the field of graph theory, where graphs with weighted edges are given. The procedure is shown in the given example. The paper discusses the application of such route optimization technique forthe maritime sector. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]

Abstract: A threshold graph on n vertices is coded by a binary string of length . We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases. [Copyright &y& Elsevier]

Let Gσ be an oriented graph with underlying simple graph G. The skew-adjacency matrix of Gσ is the {0, 1,-1}-matrix S = S(Gσ) = [sij ], such that sij = 1 if (vi, vj) is an arc in Gσ, sij = -1 if (vj, vi) is an arc in Gσ and sij = 0, otherwise. In this paper, all connected oriented graphs with three distinct skew-eigenvalues 0 and ±2i are characterized. [ABSTRACT FROM AUTHOR]

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G , a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F , of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F , we take algebraic route. More formally, given a fixed positive integer r , we define F r as the family of graphs where for each G ∈ F r , the rank of the adjacency matrix of G is at most r . Using the family F r we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r - Rank Vertex Deletion , r - Rank Edge Deletion and r - Rank Editing . These problems generalize the classical Vertex Cover problem and a variant of the d - Cluster Editing problem. We first show that all the three problems are NP-Complete . Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2 O ( k log ⁡ r ) n O ( 1 ) for r - Rank Vertex Deletion , and an algorithm for r - Rank Edge Deletion and r - Rank Editing running in time 2 O ( f ( r ) k log ⁡ k ) n O ( 1 ) . We complement our FPT result by designing polynomial kernels for these problems. [ABSTRACT FROM AUTHOR]

A Hamiltonian cycle in a graph is a cycle that visits each node/vertex exactly once. A graph containing a Hamiltonian cycle is called a Hamiltonian graph. There have been several researches to find the number of Hamiltonian cycles of a Hamilton graph. As the number of vertices and edges grow, it becomes very difficult to keep track of all the different ways through which the vertices are connected. Hence, analysis of large graphs can be efficiently done with the assistance of a computer system that interprets graphs as matrices. And, of course, a good and well written algorithm will expedite the analysis even faster. The most convenient way to quickly test whether there is an edge between two vertices is to represent graphs using adjacent matrices. In this paper, a new algorithm is proposed to find fuzzy Hamiltonian cycle using adjacency matrix and the degree of the vertices of a fuzzy graph. A fuzzy graph structure is also modeled to illustrate the proposed algorithms with the selected air network of Indigo airlines. [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]

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]

In this paper, we present an innovative transmit power control scheme, based on optimization theory, for wireless sensor networks (WSNs) which use carrier sense multiple access (CSMA) with collision avoidance (CA) as medium access control (MAC) protocol. In particular, we focus on schemes where several remote nodes send data directly to a common access point (AP). Under the assumption of finite overall network transmit power and low traffic load, we derive the optimal transmit power allocation strategy that minimizes the packet error rate (PER) at the AP. This approach is based on modeling the CSMA/CA MAC protocol through a finite state machine and takes into account the network adjacency matrix, depending on the transmit power distribution and determining the network connectivity. It will be then shown that the transmit power allocation problem reduces to a convex constrained minimization problem. Our results show that, under the assumption of low traffic load, the power allocation strategy, which guarantees minimal delay, requires the maximization of network connectivity, which can be equivalently interpreted as the maximization of the number of non-zero entries of the adjacency matrix. The obtained theoretical results are confirmed by simulations for unslotted Zigbee WSNs. [ABSTRACT FROM AUTHOR]

Abstract: Let be an unweighted rooted tree of k levels such that in each level the vertices have equal degree. Let d k−j+1 denotes the degree of the vertices in the level j. We find the eigenvalues of the adjacency matrix and of the Laplacian matrix of . They are the eigenvalues of principal submatrices of two nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for both matrices are , and , while the diagonal entries are zeros, in the case of the adjacency matrix, and d j , 1⩽ j ⩽k, in the case of the Laplacian matrix. Moreover, we give some results concerning to the multiplicity of the above mentioned eigenvalues. [Copyright &y& Elsevier]

Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]

Abstract: Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices. [Copyright &y& Elsevier]

This paper investigates on the relation between the principal eigenvector of the adjacency matrix and the degree vector of a graph. Specifically the analysis deals with the derivation of an upper bound, which only depends on the elements of the matrix, for the difference between the prin- cipal eigenvector and the degree vector. The results hold true for a general irreducible, nonnegative, symmetric matrix. [ABSTRACT FROM AUTHOR]

In the heart, electrical stimulation of cardiac myocytes increases the open probability of sarcolemmal voltage-sensitive Ca2+ channels and flux of Ca2+ into the cells. This increases Ca2+ binding to ligand-gated channels known as ryanodine receptors (RyR2). Their openings cause cell-wide release of Ca2+, which in turn causes muscle contraction and the generation of the mechanical force required to pump blood. In resting myocytes, RyR2s can also open spontaneously giving rise to spatially-confined Ca2+ release events known as “sparks.” RyR2s are organized in a lattice to form clusters in the junctional sarcoplasmic reticulum membrane. Our recent work has shown that the spatial arrangement of RyR2s within clusters strongly influences the frequency of Ca2+ sparks. We showed that the probability of a Ca2+ spark occurring when a single RyR2 in the cluster opens spontaneously can be predicted from the precise spatial arrangements of the RyR2s. Thus, “function” follows from “structure.” This probability is related to the maximum eigenvalue (λ1) of the adjacency matrix of the RyR2 cluster lattice. In this work, we develop a theoretical framework for understanding this relationship. We present a stochastic contact network model of the Ca2+ spark initiation process. We show that λ1 determines a stability threshold for the formation of Ca2+ sparks in terms of the RyR2 gating transition rates. We recapitulate these results by applying the model to realistic RyR2 cluster structures informed by super-resolution stimulated emission depletion (STED) microscopy. Eigendecomposition of the linearized mean-field contact network model reveals functional subdomains within RyR2 clusters with distinct sensitivities to Ca2+. This work provides novel perspectives on the cardiac Ca2+ release process and a general method for inferring the functional properties of transmembrane receptor clusters from their structure. [ABSTRACT FROM AUTHOR]

Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t , the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 . [ABSTRACT FROM AUTHOR]

Abstract: Let G =(V, E) be a simple graph and {λ 1(G),…, λ n (G)} be its adjacency spectrum. It is easy to see that if an edge is added between two isolated vertices, then one zero eigenvalue increases by 1, and another zero eigenvalue decreases by 1. Let G + be a connected graph obtained from G by adding an edge e ∉ E(G). In this paper, it will be proved that the spectrum of G + is different from that of G only in two places with one eigenvalue increases by m and another eigenvalue decreases by m, where m >0 is a rational number, if and only if G is an empty graph with order 2. It will also be proved that one cannot construct a new adjacency integral connected graph with order n ⩾3 from a known one by adding an edge. [Copyright &y& Elsevier]

Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]

Recently there is huge interest in graph theory and intensive study on computing integer powers of matrices. In this paper, we consider one type of directed graph. Then we obtain a general form of the adjacency matrices of the graph. By using the well-known property which states the (i, j) entry of Am (A is adjacency matrix) is equal to the number of walks of length m from vertex i to vertex j, we show that elements of mth positive integer power of the adjacency matrix correspond to well-known Jacobsthal numbers. As a consequence, we give a Cassini-like formula for Jacobsthal numbers. We also give a matrix whose permanents are Jacobsthal numbers. [ABSTRACT FROM AUTHOR]

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. [ABSTRACT FROM AUTHOR]

Given that fingerprint localization methods can be effectively modeled as supervised learning problems, machine learning has been employed for indoor localization tasks based on fingerprint methods. However, it is often challenging for popular machine learning models to effectively capture the unstructured data features inherent in fingerprint data that are generated in diverse propagation environments. In this paper, we propose an indoor localization algorithm based on a high-order graph neural network (HoGNNLoc) to enhance the accuracy of indoor localization and improve localization stability in dynamic environments. The algorithm first designs an adjacency matrix based on the spatial relative locations of access points (APs) to obtain a graph structure; on this basis, a high-order graph neural network is constructed to extract and aggregate the features; finally, the designed fully connected network is used to achieve the regression prediction of the location of the target to be located. The experimental results on our self-built dataset show that the proposed algorithm achieves localization accuracy within 1.29 m at 80% of the cumulative distribution function (CDF) points. The improvements are 59.2%, 51.3%, 36.1%, and 22.7% compared to the K-nearest neighbors (KNN), deep neural network (DNN), simple graph convolutional network (SGC), and graph attention network (GAT). Moreover, even with a 30% reduction in fingerprint data, the proposed algorithm exhibits stable localization performance. On a public dataset, our proposed localization algorithm can also show better performance. [ABSTRACT FROM AUTHOR]

The maximum eigenvalue of the adjacency matrix (AM) has been supposed to contain rich information about the corresponding network. An experimental study focused on revealing the meaning and application of the maximum eigenvalue is missing. To this end, AM was constructed using mutual information (MI) to determine the functional connectivity with electroencephalogram (EEG) data recorded with a mental fatigue model, and then was converted into both binary and weighted brain functional network (BFN) and corresponding random networks (RNs). Both maximum eigenvalue and corresponding network characters in BFNs and RNs were considered to explore the changes during the formation of mental fatigue. The results indicated that large maximum eigenvalue means more edges in the corresponding network, along with a high degree and a short characteristic path length both in weighted and binary BFNs. Interestingly, the maximum eigenvalue of AM was always a little larger than that of the corresponding random matrix (RM), and had an obvious linearity with the sum of the AM elements, indicating that the maximum eigenvalue can be able to distinguish the network structures which have the same mean degree. What is more, the maximum eigenvalue, which increased with the deepening of mental fatigue, can become a good indicator for mental fatigue estimation. [ABSTRACT FROM AUTHOR]

Abstract: We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as , where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D. [Copyright &y& Elsevier]

Detecting communities in real world networks is an important problem for data analysis in science and engineering. By clustering nodes intelligently, a recursive algorithm is designed to detect community. Since the relabeling of nodes does not alter the topology of the network, the problem of community detection corresponds to the finding of a good labeling of nodes so that the adjacency matrix form blocks. By putting a fictitious interaction between nodes, the relabeling problem becomes one of energy minimization, where the total energy of the network is defined by putting interaction between the labels of nodes so that clustering nodes that are in the same community will decrease the total energy. A greedy method is used for the computation of minimum energy. The method shows efficient detection of community in artificial as well as real world network. The result is illustrated in a tree showing hierarchical structure of communities on the basis of sub-matrix density. Applications of the method to weighted and directed networks are discussed. [ABSTRACT FROM AUTHOR]

Abstract: We define cut-and-paste, a construction which, given a quadriculated disk obtains a disjoint union of quadriculated disks of smaller total area. We provide two examples of the use of this procedure as a recursive step. Tilings of a disk receive a parity: we construct a perfect or near-perfect matching of tilings of opposite parities. Let be the black-to-white adjacency matrix: we factor , where and are lower and upper triangular matrices, is obtained from a larger identity matrix by removing rows and columns and all entries of , and are equal to , or . [Copyright &y& Elsevier]

Abstract: Oscillations are a common type of plant-wide disturbances whose effects propagate to many units and thus may impact overall process performance. It is important to detect and diagnose such oscillations early in order to rectify the situation. Many frequency domain tools such as the power spectrum and spectrum envelope methods are capable of detecting the oscillation frequency. However, few methods are available for locating the root cause which is the main objective of oscillation diagnosis. This paper proposes a new method to diagnose the root cause of plant-wide oscillations using the adjacency matrix. A novel feature of the new method is that it utilizes the information in the process flowsheet. The method is not data-based and it can be carried out without using any data. However, this method complements the data based methods very well and it is best used in combination with other data-based methods to provide powerful diagnosis of plant-wide oscillations. This paper is the subject of a newly proposed complete procedure for detection and diagnosis of plant-wide oscillation. Two industrial case studies are also presented to demonstrate the applicability of the proposed procedure. [Copyright &y& Elsevier]

Let J(λ;n1,…,nk) be the set of matrices A such that λ is an eigenvalue of A and n1⩽⋯⩽nk are the sizes of the Jordan blocks associated with λ. For a given index v of A, denote by A−v the principal submatrix of co-order one obtained from A by deleting the vth row and column. In the present paper, all possible changes of the part of the Jordan form corresponding to λ under the transition from A to A−v are determined for matrices A∈J(λ;n1,…,nk) such that for the eigenvalue λ of both A and A⊤, there exists a Jordan chain of the largest length nk whose eigenvector has nonzero vth entry. In particular, it is shown that for almost every matrix A∈J(λ;n1,…,nk), n1,…,nk−1 are the sizes of Jordan blocks for λ considered as an eigenvalue of A−v. Moreover, it is also proved that if A is the adjacency matrix of a vertex-transitive digraph and k⩾2, then the change n1,…,nk→n1,…,nk−2,2nk−1−1 holds for the eigenvalue λ under the transition from A to A−v. In the case of k=1, λ is a simple eigenvalue of A and does not belong to the spectrum of A−v. [Copyright &y& Elsevier]

For a simple finite graph G, the generalized adjacency matrix is defined as A α (G) = α D (G) + (1 − α) A (G) , α ∈ [ 0 , 1 ] , where A (G) and D (G) are respectively the adjacency matrix and diagonal matrix of the vertex degrees. The A α -spread of a graph G is defined as the difference between the largest eigenvalue and the smallest eigenvalue of the A α (G) . In this paper, we answer the question posed in (Lin, Z.; Miao, L.; Guo, S. Bounds on the A α -spread of a graph. Electron. J. Linear Algebra2020, 36, 214–227). Furthermore, we show that the path graph, P n , has the smallest S (A α) among all trees of order n. We establish a relationship between S (A α) and S (A). We obtain several bounds for S (A α) . [ABSTRACT FROM AUTHOR]

Background: Post-translational modification (PTM) is a biological process that is associated with the modification of proteome, which results in the alteration of normal cell biology and pathogenesis. There have been numerous PTM reports in recent years, out of which, lysine phosphoglycerylation has emerged as one of the recent developments. The traditional methods of identifying phosphoglycerylated residues, which are experimental procedures such as mass spectrometry, have shown to be time-consuming and cost-inefficient, despite the abundance of proteins being sequenced in this post-genomic era. Due to these drawbacks, computational techniques are being sought to establish an effective identification system of phosphoglycerylated lysine residues. The development of a predictor for phosphoglycerylation prediction is not a first, but it is necessary as the latest predictor falls short in adequately detecting phosphoglycerylated and non-phosphoglycerylated lysine residues. Results: In this work, we introduce a new predictor named RAM-PGK, which uses sequence-based information relating to amino acid residues to predict phosphoglycerylated and non-phosphoglycerylated sites. A benchmark dataset was employed for this purpose, which contained experimentally identified phosphoglycerylated and non-phosphoglycerylated lysine residues. From the dataset, we extracted the residue adjacency matrix pertaining to each lysine residue in the protein sequences and converted them into feature vectors, which is used to build the phosphoglycerylation predictor. Conclusion: RAM-PGK, which is based on sequential features and support vector machine classifiers, has shown a noteworthy improvement in terms of performance in comparison to some of the recent prediction methods. The performance metrics of the RAM-PGK predictor are: 0.5741 sensitivity, 0.6436 specificity, 0.0531 precision, 0.6414 accuracy, and 0.0824 Mathews correlation coefficient. [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]

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]

Pose estimation in crowded scenes is key to understanding human behavior in real-life applications. Most existing CNN-based pose estimation methods often depend on the appearance of visible parts as cues to localize human joints. However, occlusion is typical in crowded scenes, and invisible body parts have no valid features for joint localization. Introducing prior information about the human pose structure to infer the locations of occluded parts is a natural solution to this problem. In this paper, we argue that learning structural information based on human joints alone is not enough to address human body variations and could be prone to overfitting. From a perspective on the human pose as a dual representation of joints and limbs, we propose a pose refinement network, coined as dual graph network (DGN), to jointly learn its structural information of body joints and limbs by incorporating the cooperative constraints between two branches. Specifically, our DGN has two coupled graph convolutional network (GCN) branches to model the structure information of joints and limbs. Each stage in the branch is composed of a feature aggregator and a GCN module for inter-branch information fusion and intra-branch context extraction, respectively. In addition, to enhance the modeling capacity of GCN, we design an adaptive GCN layer (AGL) embedded in the GCN module to handle each pose instance based on its graph structure. We also propose a heatmap-guided sampling to leverage the features of the body parts to provide rich visual features for the inference of occluded parts. We perform extensive experiments on five challenging datasets to demonstrate the effectiveness of our DGN on pose estimation. Our DGN obtains significant performance improvement from 67.9 to 72.4 mAP in the CrowdPose dataset with the same CNN-based pose estimator and training strategy as the OPEC-Net. It shows that, compared to the OPEC-Net only considering joints, our DGN has a clear advantage due to the joint consideration of both joints and limbs. Meanwhile, our DGN is also helpful for pose estimation in general datasets (i.e., COCO and Pose track) with less occlusion and mutual interference, demonstrating the generalization power of DGN on refining human poses. [ABSTRACT FROM AUTHOR]

Under elimination of two arcs, spectrum of digraph having ring structure and two Hamiltonian cycles is shown real, if and only if the number of vertices is even and “interval between arcs,” eliminated from the same cycle, is maximal. Possibility to apply the obtained results to evaluate failure-resistance of networks with ring topology is considered. [ABSTRACT FROM AUTHOR]

Biclustering algorithm is an effective tool for processing gene expression datasets. There are two kinds of data matrices, binary data and non-binary data, which are processed by biclustering method. A binary matrix is usually converted from pre-processed gene expression data, which can effectively reduce the interference from noise and abnormal data, and is then processed using a biclustering algorithm. However, biclustering algorithms of dealing with binary data have a poor balance between running time and performance. In this paper, we propose a new biclustering algorithm called the Adjacency Difference Matrix Binary Biclustering algorithm (AMBB) for dealing with binary data to address the drawback. The AMBB algorithm constructs the adjacency matrix based on the adjacency difference values, and the submatrix obtained by continuously updating the adjacency difference matrix is called a bicluster. The adjacency matrix allows for clustering of gene that undergo similar reactions under different conditions into clusters, which is important for subsequent genes analysis. Meanwhile, experiments on synthetic and real datasets visually demonstrate that the AMBB algorithm has high practicability. [ABSTRACT FROM AUTHOR]

Let A(G) be the adjacency matrix of a graph G. Let s(vi) denote the row entries of A(G) corresponding to the vertex vi of G. The Hamming distance between the strings s(ui) and s(vi) is the number of positions in which their elements differ. The sum of Hamming distance between all the pairs of vertices is the Hamming index of a graph. In this paper, we study the Hamming distance between the strings generated by the adjacency matrix of various products of complete bipartite and complete graph. We also compute the Hamming index generated by the adjacency matrix of these graph products. [ABSTRACT FROM AUTHOR]

Electroencephalography (EEG) is recorded by electrodes from different areas of the brain and is commonly used to measure neuronal activity. EEG-based methods have been widely used for emotion recognition recently. However, most current methods for EEG-based emotion recognition do not fully exploit the relationship of EEG channels, which affects the precision of emotion recognition. To address the issue, in this paper, we propose a novel method for EEG-based emotion recognition called CR-GCN: Channel-Relationships-based Graph Convolutional Network. Specifically, topological structure of EEG channels is distance-based and tends to capture local relationships, and brain functional connectivity tends to capture global relationships among EEG channels. Therefore, in this paper, we construct EEG channel relationships using an adjacency matrix in graph convolutional network where the adjacency matrix captures both local and global relationships among different EEG channels. Extensive experiments demonstrate that CR-GCN method significantly outperforms the state-of-the-art methods. In subject-dependent experiments, the average classification accuracies of 94.69% and 93.95% are achieved for valence and arousal. In subject-independent experiments, the average classification accuracies of 94.78% and 93.46% are obtained for valence and arousal. [ABSTRACT FROM AUTHOR]