normalized Laplacian matrix is defined as . The left or right normalized Laplacian matrix is not symmetric if the adjacency matrix is symmetric, except for the trivial case of all isolated vertices. For example, The example also demonstrates that if has no isolated vertices, then right stochastic and hence is the matrix of a random walk, so that the left normalized Laplacian has each row summing to zero. Thus we sometimes alternatively call the random-walk normalized Laplacian. In the less uncommonly used right normalized Laplacian each column sums to zero since is left stochastic. For a non-symmetric adjacency matrix of a directed graph, one also needs to choose indegree or outdegree for normalization: The left out-degree normalized Laplacian with row-sums all 0 relates to right stochastic , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic . Definitions for graphs with weighted edges Common in applications graphs with weighted edges are conveniently defined by their adjacency matrices where values of the entries are numeric and no longer limited to zeros and ones. In spectral clustering and graph-based signal processing, where graph vertices represent data points, the edge weights can be computed, e.g., as inversely proportional to the distances between pairs of data points, leading to all weights being non-negative with larger values informally corresponding to more similar pairs of data points. Using correlation and anti-correlation between the data points naturally leads to both positive and negative weights. Most definitions for simple graphs are trivially extended to the standard case of non-negative weights, while negative weights require more attention, especially in normalization. Laplacian matrix The Laplacian matrix is defined by where D is the degree matrix and A is the adjacency matrix of the graph. For directed graphs, either the indegree or outdegree might be used, depending on the application, as in the following example: Graph self-loops, manifesting themselves by non-zero entries on the main diagonal of the adjacency matrix, are allowed but do not affect the graph Laplacian values. Symmetric Laplacian via the incidence matrix For graphs with weighted edges one can define a weighted incidence matrix B and use it to construct the corresponding symmetric Laplacian as . An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using the incidence matrix as for regular graphs and introduce a matrix just holding the values of the weights. A spring system