Abstract
Many graph products have been applied to generate complex networks with striking properties observed in real-world systems. In this paper, we propose a simple generative model for simplicial ...networks by iteratively using edge corona product. We present a comprehensive analysis of the structural properties of the network model, including degree distribution, diameter, clustering coefficient, as well as distribution of clique sizes, obtaining explicit expressions for these relevant quantities, which agree with the behaviors found in diverse real networks. Moreover, we obtain exact expressions for all the eigenvalues and their associated multiplicities of the normalized Laplacian matrix, based on which we derive explicit formulas for mixing time, mean hitting time and the number of spanning trees. Thus, as previous models generated by other graph products, our model is also an exactly solvable one, whose structural properties can be analytically treated. More interestingly, the expressions for the spectra of our model are also exactly determined, which is sharp contrast to previous models whose spectra can only be given recursively at most. This advantage makes our model a good test bed and an ideal substrate network for studying dynamical processes, especially those closely related to the spectra of normalized Laplacian matrix, in order to uncover the influences of simplicial structure on these processes.
To some extent, graph evolutionary mechanisms can be explained by its spectra. Here, we are interested in two graph operations, namely, motif (subgraph) doubling and attachment that are biologically ...relevant. We investigate how these two processes affect the spectrum of the normalized graph Laplacian. A high (algebraic) multiplicity of the eigenvalues 1,1±0.5,1±0.5 and others have been observed in the spectrum of many real networks. We attempt to explain the production of distinct eigenvalues by motif doubling and attachment. Results on the eigenvalue 1 are discussed separately.
The eigenvalues of the graphs D(4,q) Moorhouse, G. Eric; Sun, Shuying; Williford, Jason
Journal of combinatorial theory. Series B,
July 2017, 2017-07-00, Letnik:
125
Journal Article
Recenzirano
Odprti dostop
The graphs D(k,q) have connected components CD(k,q) giving the best known bounds on extremal problems with forbidden even cycles, and are denser than the well-known graphs of Lubotzky, Phillips, ...Sarnak 14 and Margulis 15,16. Despite this, little is known about the spectrum and expansion properties of these graphs. In this paper we find the spectrum for k=4, the smallest open case. For each prime power q, the graph D(4,q) is q-regular graph on 2q4 vertices, all of whose eigenvalues other than ±q are bounded in absolute value by 2q. Accordingly, these graphs are good expanders, in fact very close to Ramanujan.
Motivated by recent extensive studies on Wenger graphs, we introduce a new infinite class of bipartite graphs of a similar type, called linearized Wenger graphs. The spectrum, diameter and girth of ...these linearized Wenger graphs are determined.
On energy of line graphs Das, Kinkar Ch; Mojallal, Seyed Ahmad; Gutman, Ivan
Linear algebra and its applications,
06/2016, Letnik:
499
Journal Article
Recenzirano
Odprti dostop
The energy E(G) of a simple graph G is the sum of absolute values of the eigenvalues of its adjacency matrix. The line graph of G is denoted by LG. We obtain a relation between E(LG) and E(G), and ...establish bounds on E(LG). Moreover, we present results pertaining to equienergetic and hyperenergetic graphs.
We investigate when a complete graph Kn with some edges deleted is determined by its adjacency spectrum. It is shown to be the case if the deleted edges form a matching, a complete graph Km provided ...m≤n−2, or a complete bipartite graph. If the edges of a path are deleted we prove that the graph is determined by its generalized spectrum (that is, the spectrum together with the spectrum of the complement). When at most five edges are deleted from Kn, there is just one pair of nonisomorphic cospectral graphs. We construct nonisomorphic cospectral graphs (with cospectral complements) for all n if six or more edges are deleted from Kn, provided that n is big enough.
Counting short cycles in bipartite graphs is a fundamental problem of interest in the analysis and design of low-density parity-check codes. The vast majority of research in this area is focused on ...algorithmic techniques. Most recently, Blake and Lin proposed a computational technique to count the number of cycles of length <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} </tex-math></inline-formula> in a bi-regular bipartite graph, where <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} </tex-math></inline-formula> is the girth of the graph. The information required for the computation is the node degree and the multiplicity of the nodes on both sides of the partition, as well as the eigenvalues of the adjacency matrix of the graph (graph spectrum). In this paper, the result of Blake and Lin is extended to compute the number of cycles of length <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} + \textbf {2}, \ldots, \textbf {2}\boldsymbol {g}-\textbf {2} </tex-math></inline-formula>, for bi-regular bipartite graphs, as well as the number of 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} \geq \textbf {4} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} \geq \textbf {6} </tex-math></inline-formula>, respectively.
•A novel multivariate hub identification method to jointly find a set of critical connector hub nodes in the network.•An extension of population-wise hub identification was also proposed to identify ...a set of common hubs from a group of networks across different populations or longitudinal time points.•Experiments based on both structural and functional data demonstrated the population-wise hub identification has a more power on distinguishing network alterations related to disorders such as Alzheimer's disease and obsessive-compulsive disorder.
Recent developments in neuroimaging allow us to investigate the structural and functional connectivity between brain regions in vivo. Mounting evidence suggests that hub nodes play a central role in brain communication and neural integration. Such high centrality, however, makes hub nodes particularly susceptible to pathological network alterations and the identification of hub nodes from brain networks has attracted much attention in neuroimaging. Current popular hub identification methods often work in a univariate manner, i.e., selecting the hub nodes one after another based on either heuristic of the connectivity profile at each node or predefined settings of network modules. Since the topological information of the entire network (such as network modules) is not fully utilized, current methods have limited power to identify hubs that link multiple modules (connector hubs) and are biased toward identifying hubs having many connections within the same module (provincial hubs). To address this challenge, we propose a novel multivariate hub identification method. Our method identifies connector hubs as those that partition the network into disconnected components when they are removed from the network. Furthermore, we extend our hub identification method to find the population-based hub nodes from a group of network data. We have compared our hub identification method with existing methods on both simulated and human brain network data. Our proposed method achieves more accurate and replicable discovery of hub nodes and exhibits enhanced statistical power in identifying network alterations related to neurological disorders such as Alzheimer's disease and obsessive-compulsive disorder.
Display omitted
PDF
