共查询到20条相似文献，搜索用时 0 毫秒
1.
We previously introduced the concept of “set‐complexity,” based on a context‐dependent measure of information, and used this concept to describe the complexity of gene interaction networks. In a previous paper of this series we analyzed the set‐complexity of binary graphs. Here, we extend this analysis to graphs with multicolored edges that more closely match biological structures like the gene interaction networks. All highly complex graphs by this measure exhibit a modular structure. A principal result of this work is that for the most complex graphs of a given size the number of edge colors is equal to the number of “modules” of the graph. Complete multipartite graphs (CMGs) are defined and analyzed. The relation between complexity and structure of these graphs is examined in detail. We establish that the mutual information between any two nodes in a CMG can be fully expressed in terms of entropy, and present an explicit expression for the set complexity of CMGs (Theorem 3). An algorithm for generating highly complex graphs from CMGs is described. We establish several theorems relating these concepts and connecting complex graphs with a variety of practical network properties. In exploring the relation between symmetry and complexity we use the idea of a similarity matrix and its spectrum for highly complex graphs. © 2012 Wiley Periodicals, Inc. Complexity, 2012 相似文献
2.
3.
We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph. 相似文献
4.
5.
6.
In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix. 相似文献
7.
This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous Erdös‐Rényi random graphs on n vertices, where edges form independently and possibly with different probabilities pij. Sparse random graphs whose expected degrees are fail to concentrate; the obstruction is caused by vertices with abnormally high and low degrees. We show that concentration can be restored if we regularize the degrees of such vertices, and one can do this in various ways. As an example, let us reweight or remove enough edges to make all degrees bounded above by O(d) where . Then we show that the resulting adjacency matrix concentrates with the optimal rate: . Similarly, if we make all degrees bounded below by d by adding weight d / n to all edges, then the resulting Laplacian concentrates with the optimal rate: . Our approach is based on Grothendieck‐Pietsch factorization, using which we construct a new decomposition of random graphs. We illustrate the concentration results with an application to the community detection problem in the analysis of networks. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 538–561, 2017 相似文献
8.
For a tree T with n vertices, we apply an algorithm due to Jacobs and Trevisan (2011) to study how the number of small Laplacian eigenvalues behaves when the tree is transformed by a transformation defined by Mohar (2007). This allows us to obtain a new bound for the number of eigenvalues that are smaller than 2. We also report our progress towards a conjecture on the number of eigenvalues that are smaller than the average degree. 相似文献
9.
Mirjana Lazić 《Czechoslovak Mathematical Journal》2006,56(4):1207-1213
In this paper we consider the energy of a simple graph with respect to its Laplacian eigenvalues, and prove some basic properties
of this energy. In particular, we find the minimal value of this energy in the class of all connected graphs on n vertices (n = 1, 2, ...). Besides, we consider the class of all connected graphs whose Laplacian energy is uniformly bounded by a constant
α ⩾ 4, and completely describe this class in the case α = 40. 相似文献
10.
Noga Alon 《Journal of Graph Theory》2013,72(1):1-6
A graph G is called spectrally d‐degenerate if the largest eigenvalue of each subgraph of it with maximum degree D is at most . We prove that for every constant M there is a graph with minimum degree M, which is spectrally 50‐degenerate. This settles a problem of Dvo?ák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367). 相似文献
11.
12.
Russell Merris 《Linear and Multilinear Algebra》1997,43(1):201-205
Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers. 相似文献
13.
Russell Merris 《Linear and Multilinear Algebra》2013,61(1-3):201-205
Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers. 相似文献
14.
15.
An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined. 相似文献
16.
We show that there is no (95, 40, 12, 20) strongly regular graph and, consequently, there is no (96, 45, 24, 18) strongly regular graph, no nontrivial regular two‐graph on 96 vertices, and no partial geometry pg(4, 9, 2). The main idea of the result is based on the star complement technique and requires a moderate amount of computation. 相似文献
17.
Hongying Lin 《Linear and Multilinear Algebra》2013,61(2):377-383
We determine all connected graphs with at most one signless Laplacian eigenvalue exceeding three. 相似文献
18.
Joseph Esfandiar Hannon Bozorgmehr 《Complexity》2011,16(6):17-31
All life depends on the biological information encoded in DNA with which to synthesize and regulate various peptide sequences required by an organism's cells. Hence, an evolutionary model accounting for the diversity of life needs to demonstrate how novel exonic regions that code for distinctly different functions can emerge. Natural selection tends to conserve the basic functionality, sequence, and size of genes and, although beneficial and adaptive changes are possible, these serve only to improve or adjust the existing type. However, gene duplication allows for a respite in selection and so can provide a molecular substrate for the development of biochemical innovation. Reference is made here to several well‐known examples of gene duplication, and the major means of resulting evolutionary divergence, to examine the plausibility of this assumption. The totality of the evidence reveals that, although duplication can and does facilitate important adaptations by tinkering with existing compounds, molecular evolution is nonetheless constrained in each and every case. Therefore, although the process of gene duplication and subsequent random mutation has certainly contributed to the size and diversity of the genome, it is alone insufficient in explaining the origination of the highly complex information pertinent to the essential functioning of living organisms. © 2011 Wiley Periodicals, Inc. Complexity, 2011 相似文献
19.
This article calls attention to flaws in the scientific enterprise, providing a case study of the lack of professionalism in published journal articles in a particular area of research, namely, network complexity. By offering details of a special case of poor scholarship, which is very likely indicative of a broader problem, the authors hope to stimulate editors and referees to greater vigilance, and to strengthen authors' resolve to take their professional responsibilities more seriously. © 2014 Wiley Periodicals, Inc. Complexity 21: 10–14, 2016 相似文献
20.
In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log5 n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003 相似文献