# Tag Info

20

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes. Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between ...

7

Yes, because the (i,j)th entry simply talks about whether or not there exists an edge from vertex i to vertex j, and represents existence by a 1 and non-existence by a 0. However, many graph representations store the edge weight instead of 1s in the matrix. This way, a single matrix can compactly represent both the edges and their weights.

6

You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M[j,i]$ instead of $M[i,j]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely ...

6

The sequence you (correctly) identified sums up to $\frac{n(n-1)}{2}=\theta(n^2)$, which gives the runtime you were looking for. I'm not sure what you are referring to by "leading constants". Do you mean you can ignore e.g. $1+2+3$ ? sure, but that will reduce $6$ from the complexity, which is clearly meaningless. On the other hand, you cannot ignore $f(n)$ ...

6

The second (in magnitude) eigenvalue controls the rate of convergence of the random walk on the graph. This is explained in many lecture notes, for example lecture notes of Luca Trevisan. Roughly speaking, the L2 distance to uniformity after $t$ steps can be bounded by $\lambda_2^t$. Another place where the second eigenvalue shows up is the planted clique ...

6

(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.) An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e.,...

5

I think for most things it's more productive to look at the Laplacian of the graph $G$, which is closely related to the adjacency matrix. Here you can use it to relate the second eigenvalue to a "local vs global" property of the graph. For simplicity, let's suppose that $G$ is $d$-regular. Then the normalized Laplacian of $G$ is $L= I - \frac1d A$, where $... 4 there are almost no other information regarding this algorithm online [...] I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm. I invite you to read my paper "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" appeared in the Proceedings of the 16th International ... 3 Your problem is answered in the Wikipedia article on vertex-disjoint cycle covers. According to the article, you can reduce this problem to that of finding whether a related graph contains a perfect matching. Details can be found in a paper of Tutte or in recitation notes of a course given by Avrim Blum. As a comment, in the graph-theoretic literature a ... 3 There are many methods for computing the eigenvalues of a matrix. If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests. Typically the power method takes$O(n)$time to find (an approximation to) the largest eigenvalue of a$n \times n$matrix, if the matrix is sparse (it has$O(1)$non-zero entries per ... 3 Consider a graph with$N$nodes and$E$edges. Ignoring low-order terms, a bit matrix for a graph uses$N^2$bits no matter how many edges there are. How many bits do you actually need, though? Assuming that edges are independent, the number of graphs with$N$nodes and$E$edges is${N^2 \choose E}$. The minimum number of bits required to store this ... 3 The paper "SimRank++: Query Rewriting through Link Analysis of the Click Graph" describes a weighted SimRank algorithm that is similar to my attempt. It uses this formula to update similarity scores:$s_{k+1}(a, b) = \text{evidence}(a, b) \cdot C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b) \cdot \text{spread}(i) \cdot \...

2

The most popular generative model for scale-free networks is the preferential attachment model of BarabÃ¡si and Albert. A graph is sampled using an iterative procedure. This is a different sampling procedure than you suggest, since the goal is not only to generate a certain degree sequence, but also to mimic other properties of real-life networks. If all you'...

2

This is done exactly by multiplying the matrix by itself 6 times, and then $A_6[i,j]$ will give you the number of paths. To get the intuition, figure out what a single matrix multiplication does to the adjacency matrix.

2

Does $\{b,c\}$ point to $b$ or $c$? Neither. The adjacency list representation of a graph, you are given, for each vertex $x$, a list of the vertices adjacent to $x$. Thus, the lists $\{b,c\}$, $\{a,c\}$, $\{a,b\}$, tell you that $a$ is adjacent to $b$ and $c$, $b$ is adjacent to $a$ and $c$ and $c$ $is$ adjacent to $a$ ...

2

Your graph is actually undirected. The notation is a list of edges in the graph. Since edges are undirected, each edge is a set of two vertices. Your lists contains three edges, since a triangle has three edges. It actually contains all possible edges involving the vertices $a,b,c$. A directed graph is one in which edges consist of two ordered vertices. The ...

2

What you need is to take advantage of disjoint set, a very efficient data structure. Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component. MakeSet of size $n$. Choose two random vertices that has not been connected by an edge. Union these two vertices. That means adding the edge between them. Use an implementation of ...

2

The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$ The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$

1

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like for c := 2 to -2 step -1 for x := 0 to 2 y := x-c if 0<=y<=2 print A[x,y]

1

If I understand you correctly, one solution to your problem would be to compute a spanning forest. A spanning forest of a graph is a smallest possible (in terms of number of edges) graph such that there's a path between two vertices in the forest if, and only if, there's a path between them in the original graph.

1

The main advantages of matrices are in solving linear equations. In fact judging whether there even exists solutions to a system of equations becomes very easy when you represent equations in form of matrices. Matrices form the core of Linear Algebra. Systems of linear equations pop up everywhere in the real world. Linear Algebra is integral to Machine ...

1

By definition you can check if a graph is a tree (regardless of its representation) with these facts: The graph does not have cycles. It only has a single connected component. The first condition can be checked with a simple DFS checking if there is a back edge. The connected components can be counted using either DFS or BFS. Regarding to an adjacency ...

1

Let $f$ be an isomorphism from graph $G$ to graph $G'$ which takes vertex $v_i$ to vertex $v_i'$. Let $A$ and $A'$ be the adjacency matrix of $G$ and $G'$, respectively. If the rows and columns of $A$ are in the order $v_1,\ldots,v_n$, and the rows and columns of $A'$ follow the same order $v_1', \ldots, v_n'$, then it can be seen that $A=A'$. If $f$ is ...

1

Note that for an undirected graph, the adjacency matrix is symmetric, i.e. A[i,j] == A[j,i]. From this, we can see that we can simply compute the new value of A[i,j] = A[j,i] depending if A[i,j] or A[j,i] is set. Assuming the graph is unweighted, we can do: for i from 0 to n-1 for j from 0 to i if A[i,j] == 1 OR A[j,i] == 1 A[i,j] = ...

1

I didn't realize what is your problem with Kruskal algorithm. To me, a usual Kruskal has time complexity $O(E \ log E)$ that $E$ is the number of edges in a graph, and I don't have any difficulty to ignore those edges which make a cycle. To answer you question, all adjacency lists, maintaining adjacent vertices, can be sorted in an ascending order. Then, ...

1

Your question is fairly unclear and it seems you lack basic understanding in the topic of scale-free networks. Congratulations! You now feel like almost every other PhD student ever. ;) From how I understand your question, you would like to have a probability distribution over graphs such that you obtain a scale-free graph with high probability from this ...

1

Yes there is an easy way to generate a random DAG. If a graph is a DAG it can be separated into levels or ranks. The idea is to rank the nodes and randomly generate edges from lower ranked nodes to higher ranked nodes. A little bit of Googling finds the exact same question asked on stackoverflow a few months ago (with sample code!). My only concern is that ...

Only top voted, non community-wiki answers of a minimum length are eligible