Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 19 of 19 for “"Spectral partitioning"”.
-
Spectral partitioning of graphs into compact, connected regions
Partitioning a graph into regions that are both compact and connected is an important problem with applications in many areas, for example, circuit design, social network analysis, and electoral redistricting. Our work builds on existing ideas of spectral bipartitioning and Markov chain Monte Carlo …
-
Graph analysis combining numerical, statistical, and streaming techniques
… understand dynamic behavior and graph structure. Spectral partitioning methods rely on eigenvectors for solving data analysis problems such as clustering. Eigenvectors of large sparse systems must be approximated with iterative methods. This dissertation analyzes how data analysis accuracy depends …
-
Dynamic Isoperimetry on Graphs and Weighted Riemannian manifolds
… of vertex permutations. We develop a dynamic spectral partitioning method via a new dynamic Laplacian matrix. We prove a dynamic Cheeger inequality for graphs, and demonstrate the effectiveness of this dynamic spectral partitioning method on both structured and unstructured graphs. We then …
-
Unmanned aerial vehicle path planning for traffic estimation and detection of non-recurrent congestion
… working in parallel, we investigate methods for partitioning a network such that each drone operates in a particular subnetwork. The partitioning objectives are to minimize inter-flow between partitions and to create balanced subnetworks. We implement a flow-weighted spectral partitioning …
-
Community Detection Detailed for Online Social Networks
… both the structures of the network and that of a spectral partitioning algorithm to return covers of a network.
-
Data parallel algebraic multigrid
… eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with …
-
Graph-Based Fracture Models for Rigid Body Explosions
… as graph and using one of the two proposed graph partitioning algorithms to divide the object into the desired number of pieces. By treating fracture as a pre-processing step, much less computation need be done during the simulation than models based on physics. <br /><br /> It is shown that the …
-
Learning on Inhomogeneous Hypergraphs
… incorporating EDVWs, based on which I propose spectral partitioning algorithms for co-clustering vertices and hyperedges. Second, I develop a framework for incorporating EDVWs into hypergraph cut problems via introducing a new class of hyperedge splitting functions which are both submodular and …
-
Next-Generation Earth Radiation Budget Instrument Concepts
… of the Earth's radiant energy budget in three spectral bands. A potential next-generation concept involves modification of the current CERES instrument to measure in a larger number of wavelength bands. This increased spectral partitioning would be achieved by the addition of filters and …
-
Algorithms for exploring structure in complex networks
… techniques such as local improvement methods and spectral partitioning, a number of specialised methods are studied. These include link centrality, similarity, communicability, optimisation, and the Louvain method. We then look at topics associated with near bipartivity in real world graphs. …
-
Ocean swell decay observed over relatively short distances with directional buoys
… general superior to three thousand kilometers. Spectral partitioning techniques are employed to isolate the swell components. Hence, the storm’s position is computed and also the storm features based on the characteristics of the vorticity field at 850 hPa level. The rate of energy variation is …
-
Reweighted Eigenvalues: A New Approach to Spectral Theory beyond Undirected Graphs
… concept called reweighted eigenvalues, to extend spectral graph theory beyond undirected graphs. Our main motivation is to derive Cheeger inequalities and spectral rounding algorithms for a general class of graph expansion problems, including vertex expansion and edge conductance in directed …
-
A Study of Load Imbalance for Parallel Reservoir Simulation with Multiple Partitioning Strategies
… from case to case. Load imbalance caused by mesh partitioning and message passing through connections between partitions are the main reasons that prevent successful parallel implementation. This thesis introduces several mesh partitioning methods that assign relatively similar loads to processes …
-
Critical Node Identifcation for accessing network vulnerability, a necessary consideration
… minimization problem is obtained through spectral partitioning considerations. This approach leads to a distributed solution which is computationally less expensive than other approaches that exist in the literature and is near optimal, in the sense that it is shown through simulations to …
-
On Graph Coloring, Max Cut, and Semidefinite Rank
… programming with Trevisan's algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral …
-
Resolving the Spectral and Directional Structure of Solar Radiation for the NASA Libera Mission: From TOA Retrieval to Terrestrial Ecosystem Impacts
… support of the NASA Libera mission by resolving spectral and directional structure from top-of-atmosphere radiance retrievals through surface radiative forcing to land-surface impacts. It addresses three coupled challenges: developing an operational method to partition broadband shortwave …
-
Graph Inference and Graph Matching
Graphs are widely used in many fields of research, ranging from natural sciences to computer and mathematical sciences. Graph inference is an area of intense research. In this dissertation, we propose several methodologies in graph inference. We focus on statistical inference using graph …
-
Rigid Partitioning Techniques for Efficiently Generating 3D Reconstructions from Images
… technique. To address this, we present a spectral technique for clustering the tightly coupled portions of a reconstruction into rigid groups. Reconstructions partitioned in this manner can closely mimic the poorly conditioned, low error modes, and therefore efficiently incorporate …