Search

Let G be a tree on n vertices and let L = D − A denote the Laplacian matrix on G. The second-smallest eigenvalue λ 2 (G) > 0 , also known as the algebraic connectivity, as well as the associated eigenvector have been of substantial interest. We investigate the question of when the maxima and minima of an associated eigenvector are assumed at the endpoints of the longest path in G. Our results also apply to more general graphs that 'behave globally' like a tree but can exhibit more complicated local structure. The crucial new ingredient is a reproducing formula for eigenvectors of graphs. [ABSTRACT FROM AUTHOR]

For a weighted graph G , the rotation of an edge u v 1 from v 1 to a vertex v 2 is defined as follows: delete the edge u v 1 , set w (u v 2) as w (u v 1) + w (u v 2) if u v 2 is an edge of G ; otherwise, add a new edge u v 2 and set w (u v 2) = w (u v 1) , where w (u v 1) and w (u v 2) are the weights of the edges u v 1 and u v 2 , respectively. In this paper, effects on the algebraic connectivity of weighted graphs under edge rotations are studied. For a weighted graph, a sufficient condition for an edge rotation to reduce its algebraic connectivity and a necessary condition for an edge rotation to improve its algebraic connectivity are proposed based on Fiedler vectors of the graph. As applications, we show that, by using a series of edge rotations, a pair of pendent paths (a pendent tree) of a weighted graph can be transformed into one pendent path (pendent edges attached at a common vertex) of the graph with the algebraic connectivity decreasing (increasing) monotonically. These results extend previous findings of reducing the algebraic connectivity of unweighted graphs by using edge rotations. [ABSTRACT FROM AUTHOR]

We present a novel method for faster physics simulations of elastic solids. Our key idea is to reorder the unknown variables according to the Fiedler vector (i.e., the second-smallest eigenvector) of the combinatorial Laplacian. It is well known in the geometry processing community that the Fiedler vector brings together vertices that are geometrically nearby, causing fewer cache misses when computing differential operators. However, to the best of our knowledge, this idea has not been exploited to accelerate simulations of elastic solids which require an expensive linear (or non-linear) system solve at every time step. The cost of computing the Fiedler vector is negligible, thanks to an algebraic Multigrid-preconditioned Conjugate Gradients (AMGPCG) solver. We observe that our AMGPCG solver requires approximately 1 s for computing the Fiedler vector for a mesh with approximately 50K vertices or 100K tetrahedra. Our method provides a speed-up between 10 % – 30 % at every time step, which can lead to considerable savings, noting that even modest simulations of elastic solids require at least 240 time steps. Our method is easy to implement and can be used as a plugin for speeding up existing physics simulators for elastic solids, as we demonstrate through our experiments using the Vega library and the ADMM solver, which use different algorithms for elasticity. [ABSTRACT FROM AUTHOR]

The Fiedler vector is the eigenvector associated with the algebraic connectivity of the graph Laplacian. It is central to graph analysis as it provides substantial information to learn the latent structure of a graph. In real-world applications, however, the data may be subject to heavy-tailed noise and outliers which deteriorate the structure of the Fiedler vector estimate and lead to a breakdown of popular methods. Thus, we propose a Robust Regularized Locality Preserving Indexing (RRLPI) Fiedler vector estimation method that approximates the nonlinear manifold structure of the Laplace Beltrami operator while minimizing the impact of outliers. To achieve this aim, an analysis of the effects of two fundamental outlier types on the eigen-decomposition of block affinity matrices is conducted. Then, an error model is formulated based on which the RRLPI method is developed. It includes an unsupervised regularization parameter selection algorithm that leverages the geometric structure of the projection space. The performance is benchmarked against existing methods in terms of detection probability, partitioning quality, image segmentation capability, robustness and computation time using a large variety of synthetic and real data experiments.

A tree can be classified in two types, according to the existence or not of zero entries of its Fiedler vector. In this paper, the type of broom trees T n , k of order n for particular values of k is determined. [ABSTRACT FROM AUTHOR]

AbstractIn this article, we associate a Hermitian matrix to a multidigraph G. We call it the complex Laplacian matrix of G and denote it by [Formula: see text]. It is shown that the complex Laplacian matrix is a generalization of the Laplacian matrix of a graph. But, unlike the Laplacian matrix of a graph, the complex Laplacian matrix of a multidigraph may not always be singular. We obtain a necessary and sufficient condition for the complex Laplacian matrix of a multidigraph to be singular. For a multidigraph G, if [Formula: see text] is singular, we say G is [Formula: see text]-singular. We generalize some properties of the Fiedler vectors of undirected graphs to the eigenvectors corresponding to the second smallest eigenvalue of [Formula: see text]-singular multidigraphs.

An important challenge in the study of complex systems is to identify appropriate effective variables at different times. In this paper, we explain why structures that are persistent with respect to changes in length and time scales are proper effective variables, and illustrate how persistent structures can be identified from the spectra and Fiedler vector of the graph Laplacian at different stages of the topological data analysis (TDA) filtration process for twelve toy models. We then investigated four market crashes, three of which were related to the COVID-19 pandemic. In all four crashes, a persistent gap opens up in the Laplacian spectra when we go from a normal phase to a crash phase. In the crash phase, the persistent structure associated with the gap remains distinguishable up to a characteristic length scale ϵ * where the first non-zero Laplacian eigenvalue changes most rapidly. Before ϵ * , the distribution of components in the Fiedler vector is predominantly bi-modal, and this distribution becomes uni-modal after ϵ *. Our findings hint at the possibility of understanding market crashs in terms of both continuous and discontinuous changes. Beyond the graph Laplacian, we can also employ Hodge Laplacians of higher order for future research. [ABSTRACT FROM AUTHOR]

Ranking sports teams generally relies on supervised techniques, requiring either prior knowledge or arbitrary metrics. In this paper, we offer a purely unsupervised technique. We apply this to operational decision-making, specifically, the controversial European Super League for association football, demonstrating how this approach can select dominant teams to form the new league. We first use random forest regression to select important variables predicting goal difference, which we use to calculate the Euclidian distances between teams. Creating a Laplacian eigenmap, we bisect the Fiedler vector to identify the natural clusters in five major European football leagues. Our results show how an unsupervised approach could identify four clusters based on five basic performance metrics: shots, shots on target, shots conceded, possession, and pass success. The top two clusters identify teams that dominate their respective leagues and are the best candidates to create the most competitive elite super league. [ABSTRACT FROM AUTHOR]

Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al. under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

• A topological network connectivity design problem based on spectral analysis is given. • The problem is a convex program and the solution is global. • It can be converted into a semidefinite programming problem. • A new interpretation of the 2nd minimum eigenvalue as a connectivity measure is given. • A method for identifying critical links using the Fiedler vector is provided. How to improve network connectivity and which parts of the network are vulnerable are critical issues. We begin by defining an equal distribution problem, in which supplies are distributed equally to all nodes in the network. We then derive a topological network connectivity measure from the convergence speed, which is the second minimum eigenvalue of a Laplacian network matrix. Based on the equal distribution problem, we propose a method for identifying critical links for network connectivity using the derivative of the second minimum eigenvalue. Furthermore, we develop a network design problem that maximizes topological connectivity within a budget creating strengthening network links. The problem is convex programming, and the solution is global. Furthermore, it can be converted into an identical semidefinite programming problem, which requires less computational effort. Finally, we test the developed problems on road networks in the Japanese prefectures of Ishikawa and Toyama to determine their applicability and validity. [ABSTRACT FROM AUTHOR]

Accurate simultaneous semantic and instance segmentation of a plant 3D point cloud is critical for automatic plant phenotyping. Classically, each organ of the plant is detected based on the local geometry of the point cloud, but the consistency of the global structure of the plant is rarely assessed. We propose a two-level, graph-based approach for the automatic, fast and accurate segmentation of a plant into each of its organs with structural guarantees. We compute local geometric and spectral features on a neighbourhood graph of the points to distinguish between linear organs (main stem, branches, petioles) and two-dimensional ones (leaf blades) and even 3-dimensional ones (apices). Then a quotient graph connecting each detected macroscopic organ to its neighbors is used both to refine the labelling of the organs and to check the overall consistency of the segmentation. A refinement loop allows to correct segmentation defects. The method is assessed on both synthetic and real 3D point-cloud data sets of Chenopodium album (wild spinach) and Solanum lycopersicum (tomato plant). [ABSTRACT FROM AUTHOR]

Accurate simultaneous semantic and instance segmentation of a plant 3D point cloud is critical for automatic plant phenotyping. Classically, each organ of the plant is detected based on the local geometry of the point cloud, but the consistency of the global structure of the plant is rarely assessed. We propose a two-level, graph-based approach for the automatic, fast and accurate segmentation of a plant into each of its organs with structural guarantees. We compute local geometric and spectral features on a neighbourhood graph of the points to distinguish between linear organs (main stem, branches, petioles) and two-dimensional ones (leaf blades) and even 3-dimensional ones (apices). Then a quotient graph connecting each detected macroscopic organ to its neighbors is used both to refine the labelling of the organs and to check the overall consistency of the segmentation. A refinement loop allows to correct segmentation defects. The method is assessed on both synthetic and real 3D point-cloud data sets of Chenopodium album (wild spinach) and Solanum lycopersicum (tomato plant).

An important challenge in the study of complex systems is to identify appropriate effective variables at different times. In this paper, we explain why structures that are persistent with respect to changes in length and time scales are proper effective variables, and illustrate how persistent structures can be identified from the spectra and Fiedler vector of the graph Laplacian at different stages of the topological data analysis (TDA) filtration process for twelve toy models. We then investigated four market crashes, three of which were related to the COVID-19 pandemic. In all four crashes, a persistent gap opens up in the Laplacian spectra when we go from a normal phase to a crash phase. In the crash phase, the persistent structure associated with the gap remains distinguishable up to a characteristic length scale ϵ* where the first non-zero Laplacian eigenvalue changes most rapidly. Before ϵ*, the distribution of components in the Fiedler vector is predominantly bi-modal, and this distribution becomes uni-modal after ϵ*. Our findings hint at the possibility of understanding market crashs in terms of both continuous and discontinuous changes. Beyond the graph Laplacian, we can also employ Hodge Laplacians of higher order for future research.

The algebraic connectivity of a graph is the second smallest eigenvalue of its Laplacian matrix. An eigenvector affording the algebraic connectivity is called a Fiedler vector. The barbell graph B p , q ; l is the graph obtained by joining a vertex in a cycle C p (p ≠ 2) and a vertex in a cycle C q (q ≠ 2) by a path P l with p ≥ 3 or q ≥ 3 , and l ≥ 2 if p = 1 or q = 1. In this paper, we determine the graphs minimizing the algebraic connectivity among all barbell graphs and the graphs containing a barbell graph as a spanning subgraph of given order, respectively. Moreover, we investigate how the algebraic connectivity behaves under some graph perturbations, and compare the algebraic connectivities of barbell graphs, cycles, and θ -graphs. [ABSTRACT FROM AUTHOR]

To aid the implementation of athlete surveillance systems relative to logistical circumstances, easy-to-access information that summarises the extent to which methods of acquiring data are used in practice to monitor athletes is required. In this scoping review, Social Network Analysis and Mining (SNAM) techniques were used to summarise and identify the most prevalent combinations of methods used to monitor athletes in research studying team, individual, field- and court-based sports (357 articles; SPORTDiscus, MEDLINE, CINHAL, and WebOfScience; 2014-2018 inc.). The most prevalent combination in team and field-based sports were HR and/or sRPE (internal) and GPS, whereas in individual and court-based sports, internal methods (e.g., HR and sRPE) were most prevalent. In court-based sports, where external methods were occasionally collected in combination with internal methods of acquiring data, the use of accelerometers or inertial measuring units (ACC/IMU) were most prevalent. Whilst individual and court-based sports are less researched, this SNAM-based summary reveals that court-based sports may lead the way in using ACC/IMU to monitor athletes. Questionnaires and self-reported methods of acquiring data are common in all categories of sport. This scoping review provides coaches, sport-scientists and researchers with a data-driven visual resource to aid the selection of methods of acquiring data from athletes in all categories of sport relative to logistical circumstances. A guide on how to practically implement a surveillance system based on the visual summaries provided herein, is also presented. [ABSTRACT FROM AUTHOR]

In spectral bisection, a Fielder vector is used for partitioning a graph into two connected subgraphs according to its sign pattern. We investigate graphs having Fiedler vectors with unbalanced sign patterns such that a partition can result in two connected subgraphs that are distinctly different in size. We present a characterization of graphs having a Fiedler vector with exactly one negative component, and discuss some classes of such graphs. We also establish an analogous result for regular graphs with a Fiedler vector with exactly two negative components. In particular, we examine the circumstances under which any Fiedler vector has unbalanced sign pattern according to the number of vertices with minimum degree. [ABSTRACT FROM AUTHOR]

Ranking sports teams generally relies on supervised techniques, requiring either prior knowledge or arbitrary metrics. In this paper, we offer a purely unsupervised technique. We apply this to operational decision-making, specifically, the controversial European Super League for association football, demonstrating how this approach can select dominant teams to form the new league. We first use random forest regression to select important variables predicting goal difference, which we use to calculate the Euclidian distances between teams. Creating a Laplacian eigenmap, we bisect the Fiedler vector to identify the natural clusters in five major European football leagues. Our results show how an unsupervised approach could identify four clusters based on five basic performance metrics: shots, shots on target, shots conceded, possession, and pass success. The top two clusters identify teams that dominate their respective leagues and are the best candidates to create the most competitive elite super league.

In this paper, some subclasses of block graphs are considered in order to analyze Fiedler vector of its members. Twofamilies of block graphs with cliques of fixed size, the block-path and block-starlike graphs, are analyzed. Cases A and B of classification for both families were considered, as well as the behavior of the algebraic connectivity when some vertices and edges are added for particular cases of block-path graphs. [ABSTRACT FROM AUTHOR]

Algebraic connectivity, the second smallest eigenvalue of the graph Laplacian matrix, is a fundamental performance measure in various network systems, such as multi-agent networked systems. Here, we focus on how to add an edge to a network to increase network connectivity and robustness by maximizing the algebraic connectivity. Most efficient algorithms for maximizing algebraic connectivity need to calculate it directly, which results in high time complexity, especially for large networks. We present a heuristic algorithm, the minimum degree and maximum distance algorithm, based on the analysis of the Fiedler vector, which does not need to compute the algebraic connectivity. The proposed algorithm is tested in large random networks and networks of autonomous systems peering information. The results show that it is effective and can achieve shorter running times than other algorithms. Hence, it can be applied to very large networks, especially to large sparse networks.

Abstract We study the eigenvectors of Laplacian matrices of trees. The Laplacian matrix is reduced to a tridiagonal matrix using the Schur complement. This preserves the eigenvectors and allows us to provide formulas for the ratio of eigenvector entries. We also obtain bounds on the ratio of eigenvector entries along a path in terms of the eigenvalue and Perron values. The results are then applied to the Fiedler vector. Here we locate the extremal entries of the Fiedler vector and study classes of graphs such that the extremal entries can be found at the end points of the longest path. [ABSTRACT FROM AUTHOR]

This article describes the structure of the graph minimizing the algebraic connectivity among all connected graphs made with some given blocks with fixed number of pendant blocks, the blocks that have exactly one point of articulation. As an application, we conclude that over all graphs made with given blocks, the algebraic connectivity is minimum for a graph whose block structure is a path. [ABSTRACT FROM AUTHOR]

• If arcs are added to the followers, then the algebraic connectivity increases if and only if the sum of entries of the Fiedler vector, corresponding to all the tails, is smaller than that of the heads. • For the case when a fixed number of arcs with a common head are added, the smaller the sum of entries of the Fiedler vector is, corresponding to all the tails, the larger the algebraic connectivity will be. • Each entry of the Fiedler vector, corresponding to the informed agents, is greater than that of the other types of followers. • If the Laplacian matrix of a leader follower interaction topology can be divided into equal row sum blocks by layers, then the entries of the Fiedler vector in each layer are the same and the entries increase by layers. Thus the effects of adding arcs on algebraic connectivity can be determined by the layers of heads and tails of the arcs. For a first-order leader-follower multi-agent system (MAS) with a directed graph as its interaction topology, the consensus convergence rate is determined by the algebraic connectivity (the smallest real part of the nonzero eigenvalues of the Laplacian matrix). Adding arcs to the followers is an effective approach to improve the consensus convergence rate of a leader-follower MAS. In this paper, the effects of adding arcs to the followers on the algebraic connectivity are investigated, when the followers' interaction topology is a strongly connected directed graph. Our results include: (1) If arcs are added to the followers, then the algebraic connectivity increases if and only if the sum of entries of the Fiedler vector, corresponding to all the tails, is smaller than that of the heads; (2) For the case when a fixed number of arcs with a common head are added, the smaller the sum of entries of the Fiedler vector is, corresponding to all the tails, the larger the algebraic connectivity will be; (3) Each entry of the Fiedler vector, corresponding to the informed agents, is greater than that of the other types of followers; (4) If the Laplacian matrix of a leader-follower interaction topology can be divided into equal row sum blocks by layers, then the entries of the Fiedler vector in each layer are the same and the entries increase by layers. Thus the effects of adding arcs on algebraic connectivity can be determined by the layers of heads and tails of the arcs. Finally, the theoretical results are illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

We have recently shown that one can obtain the numbers and sizes of modules of a software system from the eigenvectors of its modularity matrix symmetrized and weighted by an affinity matrix. However such a weighting still demands a suitable definition of an affinity. This paper offers an alternative way to obtain the same results by means of the eigenvectors of a Laplacian matrix, directly obtained from the modularity matrix without the need of weighting. These two formalizations stand in a mutual isomorphism. We call it bipartite isomorphism since it is most straightforwardly shown by deriving the Laplacian from the modularity matrix and vice versa through the intermediate bipartite graph between two separate sets: the structors’ and the functionals’ sets. This isomorphism is also demonstrated through the equation defining the Laplacian in terms of the modularity matrix, or by the direct mapping of the respective matrices’ eigenvectors. Both matrices and the bipartite graph reflect one central idea: modules are connected components with high cohesion. The Laplacian matrix technique, of which the Fiedler vector is of central importance, is illustrated by case studies. An important claim of this paper is that, independently of the modularity matrix- and Laplacian matrix-specific properties, behind these two alternative matrices there is just one unified algebraic theory of software composition — the Linear Software Models — here concerning the application of the matrices’ eigenvectors to software modularity. [ABSTRACT FROM AUTHOR]

Based on recent advances in spectral hypergraph theory [L. Qi and Z. Luo, Tensor Anaysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017], we explore the Fiedler vector of an even-uniform hypergraph, which is the Z-eigenvector associated with the second smallest Z-eigenvalue of a normalized Laplacian tensor arising from the hypergraph. Then, we develop a novel tensor-based spectral method for partitioning vertices of the hypergraph. For this purpose, we extend the normalized Laplacian matrix of a simple graph to the normalized Laplacian tensor of an evenuniform hypergraph. The corresponding Fiedler vector is related to the Cheeger constant of the hypergraph. Then, we establish a feasible optimization algorithm to compute the Fiedler vector according to the normalized Laplacian tensor. The convergence of the proposed algorithm and the probability of obtaining the Fiedler vector of the hypergraph are analyzed theoretically. Finally, preliminary numerical experiments illustrate that the new app roach based on a hypergraph-based Fiedler vector is effective and promising for some combinatorial optimization problems arising from subspace partitioning and face clustering. [ABSTRACT FROM AUTHOR]

We show a spectral bisection algorithm which makes use of the second and third eigenvector of the Laplacian matrix. This algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. To this end, we investigate combinatorial properties of certain configurations of a graph partition. These properties, that we call organized partition s, are shown to be related to the minimality and maximality of a cut. We show that organized partitions are related to the third eigenvector of the Laplacian matrix and give bounds on the minimum cut in terms of organized partitions and eigenvalues. [ABSTRACT FROM AUTHOR]

In design and manufacturing, mesh segmentation is required for FACE construction in boundary representation (B-Rep), which in turn is central for feature-based design, machining, parametric CAD and reverse engineering, among others. Although mesh segmentation is dictated by geometry and topology, this article focuses on the topological aspect (graph spectrum), as we consider that this tool has not been fully exploited. We pre-process the mesh to obtain a edge-length homogeneous triangle set and its Graph Laplacian is calculated. We then produce a monotonically increasing permutation of the Fiedler vector (2nd eigenvector of Graph Laplacian) for encoding the connectivity among part feature sub-meshes. Within the mutated vector, discontinuities larger than a threshold (interactively set by a human) determine the partition of the original mesh. We present tests of our method on large complex meshes, which show results which mostly adjust to B-Rep FACE partition. The achieved segmentations properly locate most manufacturing features, although it requires human interaction to avoid over segmentation. Future work includes an iterative application of this algorithm to progressively sever features of the mesh left from previous sub-mesh removals. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Chongqing University of Posts & Telecommunications (Natural Science Edition) is the property of Chongqing University of Posts & Telecommunications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a robust tool for graph partitioning. Using a special class of graphs, we prove that the standard spectral graph bisection can produce bisections that are far from optimal. In particular, we show that the maximum error in the spectral approximation of the optimal bisection (partition sizes exactly equal) cut for such graphs is bounded below by a constant multiple of the order of the graph squared. [ABSTRACT FROM PUBLISHER]

The perturbed Laplacian matrix of a graph G is defined as DL = D− A, where D is any diagonal matrix and A is a weighted adjacency matrix of G. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use the notion of Perron component for the perturbed Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition. [ABSTRACT FROM AUTHOR]

We use a geometric technique based on embeddings of graphs to provide an explicit formula for the absolute algebraic connectivity and its eigenvectors of double brooms. Besides, we give a polynomial time combinatorial algorithm that computes the absolute algebraic connectivity of a given tree. [ABSTRACT FROM AUTHOR]

Music plays a prominent role in society and companies have even started studying its aspects for commercial purposes. It is only natural to ask what characteristics make certain songs appealing. While much research has been conducted on the mathematical principles of sound, there has been less focus on analyzing the structure of popular songs from a mathematical perspective. One mathematical tool that researchers have used to study musical structure is seriation, ordering. This paper applies several types of seriation algorithms to conduct a mathematical analysis of the structural qualities of several musical pieces. This paper focuses on 10 popular artists and their musical influences. The artists chosen for this research are linked because of the influences they cite, musical genre, and the popularity of their music. Results show that an artist's songs have a higher quantitatively measured connection with the artists they cite as influences rather than the artists who they never mention as musical influences. [ABSTRACT FROM AUTHOR]