# Tagged Questions

For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

532 views

137 views

### What do the eigenvalues/vectors of a metric describe?

Given a finite metric space $(X = \{ x_i \}_{i=1}^n,d)$, one can form the matrix $A$ of pairwise distances $a_{ij} = d(x_i, x_j)$. What does the eigenspectrum of this matrix say about the metric $d$? ...
74 views

207 views

141 views

I'm trying to do some clustering on a graph, which is represented by an adjacency matrix $B = A^2$, where $A$ is symmetric. I tried several methods like taking the eigenvectors of the Laplacian $L = ... 0answers 71 views ### Spectral gaps of common graphs I'm looking for the spectral gap of common graphs (alternatively, the mixing time of a (lazy) random walk on these graphs). Asymptotic values are fine. Assume that every node has a sufficient number ... 0answers 44 views ### About the topology of a$d$-regular tree What is the proof that the infinite$d$-regular tree is an universal covering space for any$d$-regular graph? Is it true that the infinite$d$-regular tree is a Ramanujan graph? (any easy way to see ... 0answers 38 views ### Spectral radius of a time-varying matrix with strictly positive increment Consider a time varying non-negative matrix$A(t)$and its spectral radius$\rho(A(t))$where$t$denotes the time. If$A(t)$changes over time with each time a random element in$A(t)$is being ... 0answers 44 views ### Fast Cholesky Factrorization for Tree Laplacians Suppose$T_1$and$T_2$represent two Laplacian matrices of two spanning trees of$n$vertices. Since the Cholesky factorization needs$O(n)$time for each$T_i\ (i=1,2)$due to the tree structure, ... 0answers 162 views ### a closed formula to enumerate the self avoiding walks of a graph Let$G$be a directed graph with$N$nodes and weighted adjacency matrix$W $defined by$$W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & \... 0answers 132 views ### interpretation of generalized eigenvalue/vectors in spectral graph theory Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation$Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ... 0answers 66 views ### How can I prove that a particular family of graphs is integral? I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs$G_{n,k}$and define them ... 0answers 60 views ### Possible Eigenvalues of Graph How would one prove (or disprove) that there is no such graph$G$with$\lambda$as an eigenvalue? I tried setting up a system of equations to see if it's possible for$-\frac{1}{2}$to be an ... 0answers 100 views ### when does a graph with normalized laplacian have a uniform degree distribution? Consider the graph$G(A)$with A as its adjacency matrix. Let$L$be its Laplacian and$L_{sym} = D^{\frac{1}{2}}LD^{\frac{1}{2}}$be the normalized Laplacian. Now let$A(L_{sym}) = I - L_{sym}$... 0answers 416 views ### Bounds on the maximum eigenvalue of the adjacency matrix of a graph. I managed to proof the following result for the maximum eigenvalue:$ d_{avg}\leq \lambda_{max} \leq \Delta(G) $where$d_{avg}$is the average degree of the graph while$\Delta(G)$is the maximum ... 0answers 53 views ### Properties of a generalized graph I'll start with formulating my problem and then ask my question: To generalize a graph$Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning$V$are subsets of$Va$... 0answers 796 views ### Is there any relation between the principal eigenvalue of sub matrix and the original matrix? I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select$n$rows and$n$columns from the ... 0answers 18 views ### How to prove the following statement for a simple graph to be bipartite? Let$G$be a simple graph on finite number of vertices and$A$be its adjacency matrix. Suppose, if$\lambda$is an eigenvalue of$A$with multiplicity$k$, then$-\lambda$is also an eigenvalue of$A$... 0answers 23 views ### How to prove the determinant of resistance matrix$R$? Let$G$be a connected graph with$n$vertices,$R$be the resistance matrix of$G$,$\tau$be the$n\times 1$vector with components$\tau_1,\tau_2,...\tau_n$,and$\tau_i=2-\sum_{j\thicksim i} r(i,j)$... 0answers 22 views ### Recommended overlapping community detection algorithms? Looking for overlapping community detection algorithm with following properties: undirected unweighted graph potentially overlapping communities good scalability to 1M nodes good intuitive results ... 0answers 40 views ### Merging two nodes in a directed graph with transitions Let's say I have$M=\begin{bmatrix}1&2&1\\ 4&2&0 \\ 1& 1& 1\end{bmatrix}$, a$3\times3$matrix which is the transition matrix or adjacency matrix of a$3$-node graph. I would ... 0answers 46 views ### Matrix -tree theorem-How to understand the theorem I am having trouble understanding Kirchhoff's Theorem. The statement I want to prove is that if$\lambda_1,\lambda_2,...,\lambda _{n-1}$are non-zero eigen values of$L(G)$then Number of ... 0answers 54 views ### On the eigenvalues of bipartite graph? Definition Let$G=U\cup V$is bipartite graph, where$U$and$V$are disjoint sets of size$p$and$q$, respectively. The complete bipartite graph denoted by$K_{p,q}$is bipartite graph where every ... 0answers 25 views ### The Laplacian spectra of random graph$G(n,m)$and$G(n,m+k)$I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define$\sigma_i=\frac{\lambda_i}{\lambda_2}$, where$0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$is the ... 0answers 34 views ### Spectral radius of perturbed bipartite graphs I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually I'm not exactly looking into bipartite but the ... 0answers 51 views ### Semigroup of matrices and expander Cayley graphs I am interested in proving or disproving that certain Cayley graphs are expander. Let$S$be the multiplicative semigroup of matrices generated by$A = \left( \begin{array}{cc} a & b \\ 0 & ...
A graph $G(V, E)$ is given. For a random pair of nodes $e_1, e_2 \in V$, what is the chance/probability of having a path of size less than $k$ (a fixed number) between $e_1$ and $e_2$ (let's assume ...