Search

Various important and useful quantities or measures that characterize the topological network structure are usually investigated for a network, then they are averaged over the samples. In this paper, we propose an explicit representation by the beforehand averaged adjacency matrix over samples of growing networks as a new general framework for investigating the characteristic quantities. It is applied to some network models, and shows a good approximation of degree distribution asymptotically. In particular, our approach will be applicable through the numerical calculations instead of intractable theoretical analysises, when the time-course of degree is a monotone increasing function like power-law or logarithm., Comment: 13 paghes, 7 figures

19 April 2022 A Correction to this paper has been published: https://doi.org/10.1007/s42979-022-01141-w [Abstract] Computing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper, we show that some well-known webgraph and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. We focus on the compressed representations of (a) Boldi and Vigna and (b) Hernández and Navarro, and show that the product computation can be conducted in time proportional to the compressed graph size. Our experimental results show speedups of at least 2 on graphs that were compressed at least 5 times with respect to the original. We thank Cecilia Hernández for providing us with her software extracting the bicliques, and a helpful description in how to run it. This research has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie [grant agreement No 690941], namely while the first author was visiting the University of Chile, and while the second author was affiliated with the University of Helsinki and visiting the University of A Coruña. The first author was funded by Fundação para a Ciência e a Tecnologia (FCT) [grant number UIDB/50021/2020 and PTDC/CCI-BIO/29676/2017]; the second author was funded by the Academy of Finland [Grant number 268324], Fondecyt [Grant number 1171058] and NSERC [Grant number RGPIN-07185-2020]; the third author was funded by JSPS KAKENHI [grant numbers JP21K17701 and JP21H05847]; the fourth author was funded by AEI and Ministerio de Ciencia e Innovación (PGE and FEDER) [grant number PID2019-105221RB-C41] and Xunta de Galicia (co-funded with FEDER) [Grant numbers ED431C 2021/53 and ED431G 2019/01]; and the fifth author was funded by ANID – Millennium Science Initiative Program – Code ICN17_002 Xunta de Galicia; ED431C 2021/53 Xunta de Galicia; ED431G 2019/01

In this paper, we found the Moore-Penrose generalized inverse of adjacency matrix of an undirected graph, explicitly. We proved that the matrix $R_\lambda= [r_{ij}]$ is nonsingular where $r_{ii}=\frac{1}{\lambda}+ \deg v_i$ and $r_{ij}=\mid N_G(V_i)\cap N_G(V_j)\mid$ for $i\neq j$, and we proved that $A^{\dagger}_G=[s_{ij}]_{1\leq i, j \leq n}$ where $\displaystyle{s_{ij}=s_{ji}=\lim_{\lambda \rightarrow +\infty} \langle R^{-1}_{\lambda}e_j, f_i \rangle }$. The proof of the main result was based on the Tikhonov regularization., Comment: 6, articles

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 .

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.

This article provides a new approach to searching solutions of the ship transport optimalization problems. It brings a new variant of one algorithm of searching for the Minimum Spanning Tree. The new element in the algorithm is that it uses the Weighted Adjacency Matrix. This Weighted Adjacency Matrix is suitable for searching for the Minimum Spanning Tree (MST) of the graph. It shows how it could be used in cases where weighted edges of the graph are given. This creates a new procedure of searching for the MST of the graph and completes previously known algorithms of searching for the MST. In the field of transportation it could be succesfully used for solutions of optimizing transportation routes where smallest costs are wanted. Proposed Weighted Adjacency Matrix could be used in similar issues in the field of the graph theory, where graphs with weighted edges are given. The procedure is shown on the attached example.

In graph theory, different types of matrices associated with graph, e.g. Adjacency matrix, Incidence matrix, Laplacian matrix etc. Among all adjacency matrix play an important role in graph theory. Many products of two graphs as well as its generalized form had been studied, e.g., cartesian product, 2−cartesian product, tensor product, 2−tensor product etc. In this paper, we discuss the adjacency matrix of two new product of graphs G H, where = ⊗2, ×2. Also, we obtain the spectrum of these products of graphs.

A graph is a set of vertices and edges where each edge connects two vertices in the graph. There are several ways to represent a graph, e.g., it can be represented as a matrix: its adjacency matrix, anti-adjacency matrix, Laplacian matrix, or distance matrix. Two matrices which will be explored in this paper are the adjacency matrix and distance matrix. The adjacency matrix represents the presence or absence of an edge connecting two vertices, while the distance matrix represents the shortest path between two vertices. A graph with diameter two is a graph such that the longest distance between any two vertices is equal to two. Examples of two-diameter graphs include bipartite graphs, wheel graphs, and fan graphs. The relation between the distance and adjacency matrices is already known. The purpose of this paper is to find the relation between the square of the distance matrix and the square of the adjacency matrix of a two diameter graph and to find the characteristic polynomial of the distance matrix of a complete bipartite graph Kn,n (which is a special type of two-diameter graph). We prove that where D2=4(J−I)A−+A2 where D is the distance matrix, J is the matrix all of whose entries are 1, I is the identity matrix, A is the adjacency matrix and Ā is the complement of A. Moreover, we also find that the characteristic polynomial of the distance matrix of a complete bipartite graph is P(λ)=(λ+2)2n−2(λ−(n−2))(λ−(3n−2)).

[Abstract] Computing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper we show that some well-known Web and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. In particular, we show that the format of Boldi and Vigna allows computing the product in time proportional to the compressed graph size. Our experimental results show speedups of at least 2 on graphs that were compressed at least 5 times with respect to the original. We show that other successful graph compression formats enjoy this property as well. Fundação para a Ciência e a Tecnologia (Portugal); UID/CEC/50021/2013 Academy of Finland; 268324 Fondo Nacional de Desarrollo Científico y Tecnológico (Chile); 1171058 Ministerio de Economía y Competitividad; TIN2016-77158-C4-3-R Xunta de Galicia; ED431C 2017/58 Xunta de Galicia; ED431G/01 Agencia Nacional de Investigación y Desarrollo (Chile); ICM/FIC RC130003

The article gives a thorough introduction to spectra of digraphs via its Hermitian adjacency matrix. This matrix is indexed by the vertices of the digraph, and the entry corresponding to an arc from x to y is equal to the complex unity i (and its symmetric entry is −i) if the reverse arc yx is not present. We also allow arcs in both directions and unoriented edges, in which case we use 1 as the entry. This allows to use the definition also for mixed graphs. This matrix has many nice properties; it has real eigenvalues and the interlacing theorem holds for a digraph and its induced subdigraphs. Besides covering the basic properties, we discuss many differences from the properties of eigenvalues of undirected graphs and develop basic theory. The main novel results include the following. Several surprising facts are discovered about the spectral radius; some consequences of the interlacing property are obtained; operations that preserve the spectrum are discussed—they give rise to a large number of cospectral digraphs; for every 0≤α≤3, all digraphs whose spectrum is contained in the interval (−α,α) are determined.

Cascading failure models for command and control networks (C2 networks) continue to be a challenging and important research area. Current solutions share a common limitation because the solutions focus only on the importance of each node in isolation using one index rather than considering the contribution degree of neighboring nodes, which makes the initial load definition inaccurate and affects the cascading invulnerability of the network. To address this limitation, a new cascading failure model for C2 networks is proposed. The new model CFMAdjM, which is based on an m-order adjacency matrix, proposes a method of initial load definition using the contribution degree of m-order neighboring nodes and defines the nonlinear load capacity model according to the nonlinear relationship between load and capacity. Finally, the influence of model parameters on the cascading failure of C2 networks is analyzed through simulation, and the results demonstrate that the new model effectively resists the cascading failure and enhances the survivability of the network by defining the initial load and adjusting the coefficient appropriately.

Graph theory was first introduced by Leonhard Euler in 1736 and still being one of the mathematic’s topics which is rapidly developing and can be used to simplify mathematic problems. There are many interesting topics in graph theory; one of them is graph labeling. There are many ways of labeling a graph, and one of them is graceful labeling. Let G(V, E is a graph. The injective mapping f: V → {0,1, …, |E|} is called graceful if the weights of edge w(uv) = |f(u) – f(v)| are all different for every edge uv. There is a famous conjecture in graceful labeling. It is said that all trees are graceful. To prove this conjecture, then we must show that every tree is graceful. There are many research papers dealing with the special cases of trees. Many classes of trees have been proven graceful, and one of them is supercaterpillar. Previous research had proved that supercaterpillars with certain conditions are also graceful. In this paper, we generalize the concept of supercaterpillar, and show that the subclass of supercaterpillar graphs that has not been discussed earlier is also graceful, using an adjacency matrix for the construction.

A complex unit gain graph is a simple graph in which each orientation of an edge is given a complex number with modulus 1 and its inverse is assigned to the opposite orientation of the edge. In this article, first we establish bounds for the eigenvalues of the complex unit gain graphs. Then we study some of the properties of the adjacency matrix of complex unit gain graph in connection with the characteristic and the permanental polynomials. Then we establish spectral properties of the adjacency matrices of complex unit gain graphs. In particular, using Perron-Frobenius theory, we establish a characterization for bipartite graphs in terms of the set of eigenvalues of gain graph and the set of eigenvalues of the underlying graph. Also, we derive an equivalent condition on the gain so that the eigenvalues of the gain graph and the eigenvalues of the underlying graph are the same., Comment: 14 pages, 2 figures

Todays, stability of human life is threatened by a set of parameters. So sustainable urban development theory is introduced after the stability theory to protect the urban environment. In recent years, sustainable urban development gains a lot of attraction by different sciences and totally becomes a final target for urban development planners and managers to use resources properly and to establish a balanced relationship among human, community, and nature. Proper distribution of services for decreasing spatial inequalities, promoting the quality of living environment, and approaching an urban stability requires an analytical understanding of the present situation. Understanding the present situation is the first step for making a decision and planning effectively. This paper evaluates effective parameters affecting proper arrangement of land-uses using a descriptive-analytical method, to develop a conceptual framework for understanding of the present situation of urban land-uses, based on the assessment of their compatibility. This study considers not only the local parameters, but also spatial parameters are included in this study. The results indicate that land-uses in the zone considered here are not distributed properly. Considering mentioned parameters and distributing service land-uses effectively cause the better use of these land-uses.

In this paper, we review recent developments in network analysis using the graphtheory, and introduce ongoing research area with relevant theoretical results. In spe-ci c, we introduce basic notations in graph, and conditional and marginal approach inconstructing the adjacency matrix. Also, we introduce the Marcenko-Pastur law, theTracy-Widom law, the white Wishart distribution, and the spiked distribution. Finally,we mention the relationship between degrees and eigenvalues for the detection of hubsin a network.Keywords: Adjacency matrix, conditional dependency, graph theory, marginal depen-dency, Tracy-Widom law. 1. Introduction Recently Big data is one of the most hot issues in many branches of science, and complexnetwork problem is the central issue in Big data. Lots of interest arose in complex networkssuch as the world-wide web, the internet, biological networks, social networks, and so on. Awonderful scienti c fact is that any complex network can be represented by a graph, and anygraph can be represented by an adjacency matrix. Further, degree matrix and/or Laplacianmatrix are derived by the adjacency matrix.Graph theory has been developed by mathematicians for a long time, and mathematiciansare interested in properties of eigenvalues of adjacency matrix, distribution of eigenvalues(Wigner, 1955; Marcenko and Pastur, 1967) and distribution of the largest eigenvalue (Tracyand Widom, 1996), lower and/or upper bound of eigenvalues, relationship between degreeand eigenvalues, and so on. There are numerous books on the graph theory, and one of therecent and best references is Mieghem (2010).On the other hand, statisticians paid attention to the graph theory quite recently, and theyare mainly interested in graphical models and estimation of adjacency matrix using availableobservations. Recently, statisticians are interested in the case where p(number of variables)is larger than n(sample size) because lots of recent networks such as biological networks and

Let G be a metacyclic 2-group and g amma(conj,G) is the conjugate graph of G . The vertices of gamma(conj,G) are non-central elements in which two vertices are adjacent if they are conjugate. The adjacency matrix of gamma(conj,G) is a matrix A=[a(i,j)] consisting 0' s and 1' s in which the entry a(i,j) is 1 if there is an edge between i th and j th vertices and 0 otherwise. In this paper, the adjacency matrix of a conjugate graph of metacyclic 2-groups is presented.

The paper reviews the applications of eigen value in different areas. One of the area is in the analysis of graphs coming from networks. The development of theory regarding the eigenvalues and its maximum eigenvalue of the adjacency matrix arising from a general graph is already well-established. Here we review some notions from different context, i.e. led by observation of some simple experiments regarding the relation between graph, cliques, and the eigen values of the adjacency matrix. We focus on regular graphs having one or more cliques in their graph structures. We do some numerical experiment on the computation of the eigen values of the adjacency matrix and show some patterns on the relation between the structure of the graph (e.g. the maximum cliques, chromatic number) and the eigen values of the adjacency matrix. By observing these patterns we find some conclusion, such as: i. the maximum clique of a complete graph is given by the largest eigen value plus one; ii. the maximum clique of a cycle g...

Node grouping is a common way of adding structure and information to networks that aids their interpretation. However, certain networks benefit from the grouping of links instead of nodes. Link communities, for example, are a form of link groups that describe high-quality overlapping node communities. There is a conceptual gap between node groups and link groups that poses an interesting visualization challenge. We introduce the Dual Adjacency Matrix to bridge this gap. This matrix combines node and link group techniques via a generalization that also enables it to be coordinated with a node-link-contour diagram. These methods have been implemented in a prototype that we evaluated with an information scientist and neuroscientist via interviews and prototype walk-throughs. We demonstrate this prototype with the analysis of a trade network and an fMRI correlation network.

Graph theory is an applied branch of the mathematics which deals the problems, with the help of graphs. There are many applications of graph theory to a wide variety of subjects which include Operations Research, Physics, Chemistry, Economics, Genetics, Sociology, Computer Science, Engineering, Mechanical Engineering and the other branches of science. A graph can be represented inside a computer by using the adjacency matrix. We define adjacency matrix and observed based on adjacency matrix. We prove theorem of adjacency matrix and give example. Also draw a graph of adjacency matrix. We derive algorithm to found new adjacency matrix after fusion and fusion for connectedness. Also use fusion algorithm to check the connectedness.

A threshold graph on n vertices is coded by a binary string of length n − 1 . 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.

This contribution gives an extensive study on spectra of mixed graphs via its Hermitian adjacency matrix of the second kind { ($N$-matrix for short)} introduced by Mohar \cite{0001}. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from $u$ to $v$ is equal to the sixth root of unity $\omega=\frac{1+{\bf i}\sqrt{3}}{2}$ (and its symmetric entry is $\bar{\omega}=\frac{1-{\bf i}\sqrt{3}}{2}$); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. The main results of this paper include the following: {equivalent} conditions for a mixed graph that shares the same spectrum of its $N$-matrix with its underlying graph are given. A sharp upper bound on the spectral radius is established and the corresponding extremal mixed graphs are identified. Operations which are called two-way and three-way switchings are discussed--they give rise to some cospectral mixed graphs. We extract all the mixed graphs whose rank of its $N$-matrix is $2$ (resp. 3). Furthermore, we show that {if $M_G$ is a connected mixed graph with rank $2,$ then $M_G$ is switching equivalent to each connected mixed graph to which it is cospectral}. However, this does not hold for some connected mixed graphs with rank $3$. We identify all mixed graphs whose eigenvalues of its $N$-matrix lie in the range $(-\alpha,\, \alpha)$ for $\alpha\in\left\{\sqrt{2},\,\sqrt{3},\,2\right\}$., Comment: 31pages,15figures

The boost of signal processing on graph has recently solicited research on the problem of identifying (learning) the graph underlying the observed signal values according to given criteria, such as graph smoothness or graph sparsity. This paper proposes a procedure for learning the adjacency matrix of a graph providing support to a set of irregularly sampled image values. Our approach to the graph adjacency matrix learning takes into account both the image luminance and the spatial samples' distances, and leads to a flexible and computationally light parametric procedure. We show that, under mild conditions, the proposed procedure identifies a near optimal graph for Markovian fields; specifically, the links identified by the learning procedure minimize the potential energy of the Markov random field for the signal samples under concern. We also show, by numerical simulations, that the learned adjacency matrix leads to a higly compact spectral wavelet graph transform of the so obtained signal on graph and favourably compares to state-of-the-art graph learning procedures, definetly matching the intrinsic signal structure.

Let $G$ be a finite tree. For any matching $M$ of $G$, let $U(M)$ be the set of vertices uncovered by $M$. Let $\mathcal{M}_G$ be a uniform random maximum size matching of $G$. In this paper, we analyze the structure of $U(\mathcal{M}_G)$. We first show that $U(\mathcal{M}_G)$ is a determinantal process. We also show that for most vertices of $G$, the process $U(\mathcal{M}_G)$ in a small neighborhood of that vertex can be well approximated based on a somewhat larger neighborhood of the same vertex. Then we show that the normalized Shannon entropy of $U(\mathcal{M}_G)$ can be also well approximated using the local structure of $G$. In other words, in the realm of trees, the normalized Shannon entropy of $U(\mathcal{M}_G)$ -- that is, the normalized logarithm of the number of maximum size matchings of $G$ -- is a Benjamini-Schramm continuous parameter. We show that $U(\mathcal{M}_G)$ is a determinantal process through establishing a new connection between $U(\mathcal{M}_G)$ and the adjacency matrix of $G$. This result sheds a new light on the well-known fact that on a tree, the number of vertices uncovered by a maximum size matching is equal to the nullity of the adjacency matrix. Some of the proofs are based on the well established method of introducing a new perturbative parameter, which we call temperature, and then define the positive temperature analogue of $\mathcal{M}_G$, the so called monomer-dimer model, and let the temperature go to zero.