We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence ...of good 2-lifts of every graph. We also establish the existence of infinite families of "irregular Ramanujan" graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all nontrivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$ for all c, d ≥ 3. Our proof exploits a new technique for controlling the eigenvalues of certain random matrices, which we call the "method of interlacing polynomials."
Spectral redemption in clustering sparse networks Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan ...
Proceedings of the National Academy of Sciences - PNAS,
12/2013, Letnik:
110, Številka:
52
Journal Article
Recenzirano
Odprti dostop
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases ...completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
In this paper, a multichannel EEG emotion recognition method based on a novel dynamical graph convolutional neural networks (DGCNN) is proposed. The basic idea of the proposed EEG emotion recognition ...method is to use a graph to model the multichannel EEG features and then perform EEG emotion classification based on this model. Different from the traditional graph convolutional neural networks (GCNN) methods, the proposed DGCNN method can dynamically learn the intrinsic relationship between different electroencephalogram (EEG) channels, represented by an adjacency matrix, via training a neural network so as to benefit for more discriminative EEG feature extraction. Then, the learned adjacency matrix is used to learn more discriminative features for improving the EEG emotion recognition. We conduct extensive experiments on the SJTU emotion EEG dataset (SEED) and DREAMER dataset. The experimental results demonstrate that the proposed method achieves better recognition performance than the state-of-the-art methods, in which the average recognition accuracy of 90.4 percent is achieved for subject dependent experiment while 79.95 percent for subject independent cross-validation one on the SEED database, and the average accuracies of 86.23, 84.54 and 85.02 percent are respectively obtained for valence, arousal and dominance classifications on the DREAMER database.
Many applications collect a large number of time series, for example, the financial data of companies quoted in a stock exchange, the health care data of all patients that visit the emergency room of ...a hospital, or the temperature sequences continuously measured by weather stations across the US. These data are often referred to as un structured. The first task in its analytics is to derive a low dimensional representation, a graph or discrete manifold, that describes well the interrelations among the time series and their intra relations across time. This paper presents a computationally tractable algorithm for estimating this graph that structures the data. The resulting graph is directed and weighted, possibly capturing causal relations, not just reciprocal correlations as in many existing approaches in the literature. A convergence analysis is carried out. The algorithm is demonstrated on random graph datasets and real network time series datasets, and its performance is compared to that of related methods. The adjacency matrices estimated with the new method are close to the true graph in the simulated data and consistent with prior physical knowledge in the real dataset tested.
Let
$ \mathbb {F} $
F
be a field and suppose
$ \mathbf {a} := (a_1, a_2, \dotsc ) $
a
:=
(
a
1
,
a
2
,
...
)
is a sequence of non-zero elements in
$ \mathbb {F} $
F
. For a tournament T on
$ n $
n
..., associate the
$ n \times n $
n
×
n
symmetric matrix
$ M_{T}(\mathbf {a}) $
M
T
(
a
)
(resp. skew-symmetric matrix
$ M_{T, \mathrm {skew}}(\mathbf {a}) $
M
T
,
skew
(
a
)
) with zero diagonal as follows: for i<j, if the edge ij is directed as
$ i \to j $
i
→
j
in T, then set
$ M_{T}(\mathbf {a}) = a_i $
M
T
(
a
)
=
a
i
(resp.
$ M_{T, \mathrm {skew}}(\mathbf {a}) = a_i $
M
T
,
skew
(
a
)
=
a
i
), else set
$ M_{T}(\mathbf {a}) = a_j $
M
T
(
a
)
=
a
j
(resp.
$ M_{T, \mathrm {skew}}(\mathbf {a}) = a_j $
M
T
,
skew
(
a
)
=
a
j
). Let
$ \mathcal {M}_{n}(\mathbf {a}) $
M
n
(
a
)
(resp.
$ \mathcal {M}_{n, \mathrm {skew}}(\mathbf {a}) $
M
n
,
skew
(
a
)
) be the family consisting of all the
$ n \times n $
n
×
n
symmetric matrices
$ M_{T}(\mathbf {a}) $
M
T
(
a
)
(resp. skew-symmetric matrices
$ M_{T, \mathrm {skew}}(\mathbf {a}) $
M
T
,
skew
(
a
)
) as T varies over all tournaments on
$ n $
n
. We show that any matrix in
$ \mathcal {M}_n(\mathbf {a}) $
M
n
(
a
)
or
$ \mathcal {M}_{n, \mathrm {skew}}(\mathbf {a}) $
M
n
,
skew
(
a
)
corresponding to a transitive tournament has a rank at least n−1, and this is best possible. This settles in a strong form a conjecture posed in Balachandran et al. An ensemble of high-rank matrices arising from tournaments; Linear Algebra Appl. 2023;658:310-318. As a corollary, any matrix in these families has rank at least
$ \lfloor \log _2(n) \rfloor $
⌊
log
2
(
n
)
⌋
.
There is a type of distance-regular graph, said to be
Q
-polynomial. In this paper, we investigate a generalized
Q
-polynomial property involving a graph that is not necessarily distance-regular. We ...give a detailed description of an example associated with the projective geometry
L
N
(
q
)
.
In an earlier work, the author together with Guo 7 introduced the Hermitian adjacency matrix of directed (and partially directed) graphs. However, it appears that a more natural Hermitian matrix ...exists, and it is the purpose of this note to bring this new Hermitian matrix to the attention of researchers in algebraic graph theory.
It is crucial to predict the wind speed for the utilization of renewable wind energy and the operation of transmission lines with increased capacity. The intermittency and stochastic fluctuations of ...wind speed pose a significant challenge for the high-quality wind speed prediction, and a novel wind speed interval prediction (WSIP) model is constructed in this study by employing the residual estimation (RE)-oriented dynamic spatio-temporal graph convolutional network (DSTGCN) approach. Firstly, a dynamic adjacency matrix is designed to obtain time-varying global spatial weight allocations among each wind speed node. Then, the spatio-temporal features are extracted by using gated recurrent units (GRUs) and GCNs to construct the wind speed graph networks. Moreover, the RE-oriented strategy incorporating the pinball loss is designed to provide a guidance the parameter training of the constructed model, thus eliminating the quantile crossings problem. As a result, the deterministic point prediction of the wind speed is expanded to the quantile-based probabilistic interval prediction. Finally, the experimental results are presented to demonstrate the validity and superiority of proposed scheme in both qualitative and quantitative performance.
•A dynamic adjacency matrix is used to assess the significance of spatial features.•The DSTGCN is proposed to boost the sensitivity of the model to critical features.•A residual estimation strategy is applied to eliminate the quantile crossings problem.•Conduct comprehensive comparisons with the-state-of-the-art methods.
Molecular network plays a critical role in determining dynamic elasticity of soft condensed polymers, e.g., their varied cross-linking densities and end-to-end distances with changed Young's moduli. ...Although it has been studied for decades, the coupling relationship between vertices and edges of molecular networks is not well understood, mainly because the degree of the crosslinking points and asymmetry molecular networks have not been considered in the previously models. In this study, a graph theory was employed to formulate an undirected graphical model and describe the coupling between vertices and edges in molecular networks, based on which the dynamic elasticity of polyelectrolyte hydrogel was modeled. From the Kirchhoff graph theory and bead-spring model, the coupling relationship between vertices and edges was obtained using end-to-end distance and viscosity parameters. Combining the Watts–Strogatz model and kinetic probability, the coupling between vertices and edges for the polyelectrolyte network was studied. Furthermore, an adjacency matrix with eigenvalue, number of vertices and mean degree was proposed to formulate constitutive relationships including dynamic elasticity and stress-strain, according to rubber elasticity theory and Mooney-Rivlin model, respectively. The linking between the vertices and edges determines the network structure and dynamic elasticity of the polyelectrolyte hydrogel. Based on the graph theory, the vertices and edges are encoded by adjacency matrix, which is proposed to describe the dynamic elasticity of symmetric and asymmetric network structures using the crosslinking density and end-to-end distance. Finally, effectiveness of the undirected graphical model was verified using both finite element analysis and experimental results of polyelectrolyte hydrogels reported in literature.
Constitutive stress-elongation ratio curves for the polyelectrolyte hydrogel, of which the graph network is determined by the mean degree of d = 2, d = 3, d = 4, d = 5, d = 6 and d = 7, at the same vertex number of N = 8 in molecular network. Display omitted
•An undirected graphical model and describe the coupling between vertices and edges in molecular networks.•Dynamic elasticity of polyelectrolyte hydrogel has been modeled using the adjacency matrix.•A constitutive relationship is developed to understand the molecular networks and their dynamic elasticities.
G
is a simple connected graph with adjacency matrix
A
(
G
) and degree diagonal matrix
D
(
G
). The signless Laplacian matrix of
G
is defined as
Q
(
G
) =
D
(
G
) +
A
(
G
). In 2017, Nikiforov 1 ...defined the matrix
A
α
(
G
) =
α D
(
G
) + (
1
−
α
)
A
(
G
) for
α
∈ 0,1. The
A
α
-spectral radius of
G
is the maximum eigenvalue of
A
α
(
G
). In 2019, Liu
et al.
2 defined the matrix
Θ
k
(
G
) as
Θ
k
(
G
) =
kD
(
G
) +
A
(
G
), for
k
∈ ℝ. In this paper, we present a new type of lower bound for the
A
α
-spectral radius of a graph after vertex deletion. Furthermore, we deduce some corollaries on
Θ
k
(
G
),
A
(
G
),
Q
(
G
) matrices.
PDF
