Ranked search on data graphs

Graph-structured databases are widely prevalent, and the problem of effective search and retrieval from such graphs has been receiving much attention recently. For example, the Web can be naturally viewed as a graph. Likewise, a relational database can be viewed as a graph where tuples are modeled as vertices connected via foreign-key relationships. Keyword search querying has emerged as one of the most effective paradigms for information discovery, especially over HTML documents in the World Wide Web. One of the key advantages of keyword search querying is its simplicity—users do not have to learn a complex query language, and can issue queries without any prior knowledge about the structure of the underlying data. The purpose of this dissertation was to develop techniques for user-friendly, high quality and efficient searching of graph structured databases. Several ranked search methods on data graphs have been studied in the recent years. Given a top-k keyword search query on a graph and some ranking criteria, a keyword proximity search finds the top-k answers where each answer is a substructure of the graph containing all query keywords, which illustrates the relationship between the keyword present in the graph. We applied keyword proximity search on the web and the page graph of web documents to find top-k answers that satisfy user’s information need and increase user satisfaction. Another effective ranking mechanism applied on data graphs is the authority flow based ranking mechanism. Given a top- k keyword search query on a graph, an authority-flow based search finds the top-k answers where each answer is a node in the graph ranked according to its relevance and importance to the query. We developed techniques that improved the authority flow based search on data graphs by creating a framework to explain and reformulate them taking in to consideration user preferences and feedback. We also applied the proposed graph search techniques for Information Discovery over biological databases. Our algorithms were experimentally evaluated for performance and quality. The quality of our method was compared to current approaches by using user surveys.

Effect of water on olivine single crystals plasticity, deformed under high pressure and high temperature

The Earth's upper mantle, mainly composed of olivine, is seismically anisotropic. Seismic anisotropy attenuation has been observed at 220km depth. Karato et al. (1992) attributed this attenuation to a transition between two deformation mechanisms, from dislocation creep above 220km to diffusion creep below 220km, induced by a change in water content. Couvy (2005) and Mainprice et al. (2005) predicted a change in Lattice Preferred Orientation induced by pressure, which comes from a change of slip system, from [100] slip to [001] slip, and is responsible for the seismic anisotropy attenuation. Raterron et al. (2007) ran single crystal deformation experiments under anhydrous conditions and observed that the slip system transition occurs around 8GPa, which corresponds to a depth of 260Km. Experiments were done to quantify the effects of water on olivine single crystals deformed using D-DIA press and synchrotron beam. Deformations were carried out in uniaxial compression along [110]c, [011]c, and [101]c, crystallographic directions, at pressure ranging from 4 to 8GPa and temperature between 1373 and 1473K. Talc sleeves about the annulus of the single crystals were used as source of water in the assembly. Stress and specimen strain rates were calculated by in-situ X-ray diffraction and time resolved imaging, respectively. By direct comparison of single crystals strain rates, we observed that [110]c deforms faster than [011]c below 5GPa. However above 6GPa [011]c deforms faster than [110]c. This revealed that [100](010) is the dominant slip system below 5GPa, and above 6GPa [001](010) becomes dominant. According to our results, the slip system transition, which is induced by pressure, occurs at 6GPa. Water influences the pressure where the switch over occurs, by lowering the transition pressure. The pressure effect on the slip systems activity has been quantified and the hydrolytic weakening has also been estimated for both orientations. Data also shows that temperature affects the slip system activity. The regional variation of the depth for the seismic anisotropy attenuation, which would depend on local hydroxyl content and temperature variations and explains the seismic anisotropy attenuation occurring at about 220Km depth in the mantle, where the pressure is about 6GPa. Deformation of MgO single crystal oriented [100], [110] and [111] were also performed. The results predict a change in the slip system activity at 23GPa, again induced by pressure. This explains the seismic anisotropy observed in the lower mantle.

Diversity in a honey bee pathogen: first report of a third master variant of the Deformed Wing Virus quasispecies

Treatment of emerging RNA viruses is hampered by the high mutation and replication rates that enable these viruses to operate as a quasispecies. Declining honey bee populations have been attributed to the ectoparasitic mite Varroa destructor and its affiliation with Deformed Wing Virus (DWV). In the current study we use next-generation sequencing to investigate the DWV quasispecies in an apiary known to suffer from overwintering colony losses. We show that the DWV species complex is made up of three master variants. Our results indicate that a new DWV Type C variant is distinct from the previously described types A and B, but together they form a distinct clade compared with other members of the Iflaviridae. The molecular clock estimation predicts that Type C diverged from the other variants ~319 years ago. The discovery of a new master variant of DWV has important implications for the positive identification of the true pathogen within global honey bee populations.

Diversity in a honey bee pathogen: first report of a third master variant of the Deformed Wing Virus quasispecies

Treatment of emerging RNA viruses is hampered by the high mutation and replication rates that enable these viruses to operate as a quasispecies. Declining honey bee populations have been attributed to the ectoparasitic mite Varroa destructor and its affiliation with Deformed Wing Virus (DWV). In the current study we use next-generation sequencing to investigate the DWV quasispecies in an apiary known to suffer from overwintering colony losses. We show that the DWV species complex is made up of three master variants. Our results indicate that a new DWV Type C variant is distinct from the previously described types A and B, but together they form a distinct clade compared with other members of the Iflaviridae. The molecular clock estimation predicts that Type C diverged from the other variants ~319 years ago. The discovery of a new master variant of DWV has important implications for the positive identification of the true pathogen within global honey bee populations.

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

An investigation of Hebbian phase sequences as assembly graphs

Hebb proposed that synapses between neurons that fire synchronously are strengthened, forming cell assemblies and phase sequences. The former, on a shorter scale, are ensembles of synchronized cells that function transiently as a closed processing system; the latter, on a larger scale, correspond to the sequential activation of cell assemblies able to represent percepts and behaviors. Nowadays, the recording of large neuronal populations allows for the detection of multiple cell assemblies. Within Hebb's theory, the next logical step is the analysis of phase sequences. Here we detected phase sequences as consecutive assembly activation patterns, and then analyzed their graph attributes in relation to behavior. We investigated action potentials recorded from the adult rat hippocampus and neocortex before, during and after novel object exploration (experimental periods). Within assembly graphs, each assembly corresponded to a node, and each edge corresponded to the temporal sequence of consecutive node activations. The sum of all assembly activations was proportional to firing rates, but the activity of individual assemblies was not. Assembly repertoire was stable across experimental periods, suggesting that novel experience does not create new assemblies in the adult rat. Assembly graph attributes, on the other hand, varied significantly across behavioral states and experimental periods, and were separable enough to correctly classify experimental periods (Naïve Bayes classifier; maximum AUROCs ranging from 0.55 to 0.99) and behavioral states (waking, slow wave sleep, and rapid eye movement sleep; maximum AUROCs ranging from 0.64 to 0.98). Our findings agree with Hebb's view that assemblies correspond to primitive building blocks of representation, nearly unchanged in the adult, while phase sequences are labile across behavioral states and change after novel experience. The results are compatible with a role for phase sequences in behavior and cognition.

Flexible modeling and estimation for high-dimensional graphs

Thesis (Ph.D.)--University of Washington, 2016-08

Microstructure characterization of 316L deformed at high strain rates using EBSD

Specimens from split Hopkinson pressure bar experiments, at strain rates between ~ 1000–9000 s− 1 at room temperature and 500 °C, have been studied using electron backscatter diffraction. No significant differences in the microstructures were observed at different strain rates, but were observed for different strains and temperatures. Size distribution for subgrains with boundary misorientations > 2° can be described as a bimodal lognormal area distribution. The distributions were found to change due to deformation. Part of the distribution describing the large subgrains decreased while the distribution for the small subgrains increased. This is in accordance with deformation being heterogeneous and successively spreading into the undeformed part of individual grains. The variation of the average size for the small subgrain distribution varies with strain but not with strain rate in the tested interval. The mean free distance for dislocation slip, interpreted here as the average size of the distribution of small subgrains, displays a variation with plastic strain which is in accordance with the different stages in the stress-strain curves. The rate of deformation hardening in the linear hardening range is accurately calculated using the variation of the small subgrain size with strain.

Unlinked Embedded Graphs

This paper is a self-contained development of an invariant of graphs embedded in three-dimensional Euclidean space using the Jones polynomial and skein theory. Some examples of the invariant are computed. An unlinked embedded graph is one that contains only trivial knots or links. Examples show that the invariant is sufficiently powerful to distinguish some different unlinked embeddings of the same graph.

Real-time analytics on large dynamic graphs

In today's fast-paced and interconnected digital world, the data generated by an increasing number of applications is being modeled as dynamic graphs. The graph structure encodes relationships among data items, while the structural changes to the graphs as well as the continuous stream of information produced by the entities in these graphs make them dynamic in nature. Examples include social networks where users post status updates, images, videos, etc.; phone call networks where nodes may send text messages or place phone calls; road traffic networks where the traffic behavior of the road segments changes constantly, and so on. There is a tremendous value in storing, managing, and analyzing such dynamic graphs and deriving meaningful insights in real-time. However, a majority of the work in graph analytics assumes a static setting, and there is a lack of systematic study of the various dynamic scenarios, the complexity they impose on the analysis tasks, and the challenges in building efficient systems that can support such tasks at a large scale. In this dissertation, I design a unified streaming graph data management framework, and develop prototype systems to support increasingly complex tasks on dynamic graphs. In the first part, I focus on the management and querying of distributed graph data. I develop a hybrid replication policy that monitors the read-write frequencies of the nodes to decide dynamically what data to replicate, and whether to do eager or lazy replication in order to minimize network communication and support low-latency querying. In the second part, I study parallel execution of continuous neighborhood-driven aggregates, where each node aggregates the information generated in its neighborhoods. I build my system around the notion of an aggregation overlay graph, a pre-compiled data structure that enables sharing of partial aggregates across different queries, and also allows partial pre-computation of the aggregates to minimize the query latencies and increase throughput. Finally, I extend the framework to support continuous detection and analysis of activity-based subgraphs, where subgraphs could be specified using both graph structure as well as activity conditions on the nodes. The query specification tasks in my system are expressed using a set of active structural primitives, which allows the query evaluator to use a set of novel optimization techniques, thereby achieving high throughput. Overall, in this dissertation, I define and investigate a set of novel tasks on dynamic graphs, design scalable optimization techniques, build prototype systems, and show the effectiveness of the proposed techniques through extensive evaluation using large-scale real and synthetic datasets.

Expedition in Data and Harmonic Analysis on Graphs

The graph Laplacian operator is widely studied in spectral graph theory largely due to its importance in modern data analysis. Recently, the Fourier transform and other time-frequency operators have been defined on graphs using Laplacian eigenvalues and eigenvectors. We extend these results and prove that the translation operator to the i’th node is invertible if and only if all eigenvectors are nonzero on the i’th node. Because of this dependency on the support of eigenvectors we study the characteristic set of Laplacian eigenvectors. We prove that the Fiedler vector of a planar graph cannot vanish on large neighborhoods and then explicitly construct a family of non-planar graphs that do exhibit this property. We then prove original results in modern analysis on graphs. We extend results on spectral graph wavelets to create vertex-dyanamic spectral graph wavelets whose support depends on both scale and translation parameters. We prove that Spielman’s Twice-Ramanujan graph sparsifying algorithm cannot outperform his conjectured optimal sparsification constant. Finally, we present numerical results on graph conditioning, in which edges of a graph are rescaled to best approximate the complete graph and reduce average commute time.

An investigation of Hebbian phase sequences as assembly graphs

Hebb proposed that synapses between neurons that fire synchronously are strengthened, forming cell assemblies and phase sequences. The former, on a shorter scale, are ensembles of synchronized cells that function transiently as a closed processing system; the latter, on a larger scale, correspond to the sequential activation of cell assemblies able to represent percepts and behaviors. Nowadays, the recording of large neuronal populations allows for the detection of multiple cell assemblies. Within Hebb's theory, the next logical step is the analysis of phase sequences. Here we detected phase sequences as consecutive assembly activation patterns, and then analyzed their graph attributes in relation to behavior. We investigated action potentials recorded from the adult rat hippocampus and neocortex before, during and after novel object exploration (experimental periods). Within assembly graphs, each assembly corresponded to a node, and each edge corresponded to the temporal sequence of consecutive node activations. The sum of all assembly activations was proportional to firing rates, but the activity of individual assemblies was not. Assembly repertoire was stable across experimental periods, suggesting that novel experience does not create new assemblies in the adult rat. Assembly graph attributes, on the other hand, varied significantly across behavioral states and experimental periods, and were separable enough to correctly classify experimental periods (Naïve Bayes classifier; maximum AUROCs ranging from 0.55 to 0.99) and behavioral states (waking, slow wave sleep, and rapid eye movement sleep; maximum AUROCs ranging from 0.64 to 0.98). Our findings agree with Hebb's view that assemblies correspond to primitive building blocks of representation, nearly unchanged in the adult, while phase sequences are labile across behavioral states and change after novel experience. The results are compatible with a role for phase sequences in behavior and cognition.

Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

Consider two graphs G and H. Let H^k[G] be the lexicographic product of H^k and G, where H^k is the lexicographic product of the graph H by itself k times. In this paper, we determine the spectrum of H^k[G]H and H^k when G and H are regular and the Laplacian spectrum of H^k[G] and H^k for G and H arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10^100 ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.

Extremal graphs for the sum of the two largest signless Laplacian eigenvalues

Let G be a simple graph on n vertices and e(G) edges. Consider the signless Laplacian, Q(G) = D + A, where A is the adjacency matrix and D is the diagonal matrix of the vertices degree of G. Let q1(G) and q2(G) be the first and the second largest eigenvalues of Q(G), respectively, and denote by S+ n the star graph with an additional edge. It is proved that inequality q1(G)+q2(G) e(G)+3 is tighter for the graph S+ n among all firefly graphs and also tighter to S+ n than to the graphs Kk _ Kn−k recently presented by Ashraf, Omidi and Tayfeh-Rezaie. Also, it is conjectured that S+ n minimizes f(G) = e(G) − q1(G) − q2(G) among all graphs G on n vertices.

Bethe graphs attached to the vertices of a connected graph: a spectral approach

A weighted Bethe graph $B$ is obtained from a weighted generalized Bethe tree by identifying each set of children with the vertices of a graph belonging to a family $F$ of graphs. The operation of identifying the root vertex of each of $r$ weighted Bethe graphs to the vertices of a connected graph $\mathcal{R}$ of order $r$ is introduced as the $\mathcal{R}$-concatenation of a family of $r$ weighted Bethe graphs. It is shown that the Laplacian eigenvalues (when $F$ has arbitrary graphs) as well as the signless Laplacian and adjacency eigenvalues (when the graphs in $F$ are all regular) of the $\mathcal{R}$-concatenation of a family of weighted Bethe graphs can be computed (in a unified way) using the stable and low computational cost methods available for the determination of the eigenvalues of symmetric tridiagonal matrices. Unlike the previous results already obtained on this topic, the more general context of families of distinct weighted Bethe graphs is herein considered.