Approximate axial symmetries from continuous time quantum walks

The analysis of complex networks is usually based on key properties such as small-worldness and vertex degree distribution. The presence of symmetric motifs on the other hand has been related to redundancy and thus robustness of the networks. In this paper we propose a method for detecting approximate axial symmetries in networks. For each pair of nodes, we define a continuous-time quantum walk which is evolved through time. By measuring the probability that the quantum walker to visits each node of the network in this time frame, we are able to determine whether the two vertices are symmetrical with respect to any axis of the graph. Moreover, we show that we are able to successfully detect approximate axial symmetries too. We show the efficacy of our approach by analysing both synthetic and real-world data. © 2012 Springer-Verlag Berlin Heidelberg.

Marginal Densities of the Wishart Distribution

2010 Mathematics Subject Classification: 62H10.

On strongly regular graphs with m2 = qm3 and m3 = qm2

2010 Mathematics Subject Classification: 05C50.

Stable sets in one-seller assignment games

We consider von Neumann -- Morgenstern stable sets in assignment games with one seller and many buyers. We prove that a set of imputations is a stable set if and only if it is the graph of a certain type of continuous and monotone function. This characterization enables us to interpret the standards of behavior encompassed by the various stable sets as possible outcomes of well-known auction procedures when groups of buyers may form bidder rings. We also show that the union of all stable sets can be described as the union of convex polytopes all of whose vertices are marginal contribution payoff vectors. Consequently, each stable set is contained in the Weber set. The Shapley value, however, typically falls outside the union of all stable sets.

Distance-based accessibility indices

The paper attempts to develop a suitable accessibility index for networks where each link has a value such that a smaller number is preferred like distance, cost, or travel time. A measure called distance sum is characterized by three independent properties: anonymity, an appropriately chosen independence axiom, and dominance preservation, which requires that a node not far to any other is at least as accessible. We argue for the need of eliminating the independence property in certain applications. Therefore generalized distance sum, a family of accessibility indices, will be suggested. It is linear, considers the accessibility of vertices besides their distances and depends on a parameter in order to control its deviation from distance sum. Generalized distance sum is anonymous and satisfies dominance preservation if its parameter meets a sufficient condition. Two detailed examples demonstrate its ability to reflect the vulnerability of accessibility to link disruptions.

A tudásérték meghatározása minőségügyi szempontból, hálózatelemzési módszerekkel (The knowledge value in terms of quality with network analysis methods)

A minőségügy egyik kulcsfeladata, hogy azonosítsa az értékteremtés szempontjából kritikus tényezőket, meghatározza ezek értékét, valamint intézkedjen negatív hatásuk megelőzése és csökkentése érdekében. Az értékteremtés sok esetben folyamatokon keresztül történik, amelyek tevékenységekből, elvégzendő feladatokból állnak. Ezekhez megfelelő munkatársak kellenek, akiknek az egyik legfontosabb jellemzője az általuk birtokolt tudás. Mindezek alapján a feladat-tudás-erőforrás kapcsolatrendszer ismerete és kezelése minőségügyi feladat is. A komplex rendszerek elemzésével foglalkozó hálózatkutatás eszközt biztosíthat ehhez, ezért indokolt a minőségügyi területen történő alkalmazhatóságának vizsgálata. Az alkalmazási lehetőségek rendszerezése érdekében a szerzők kategorizálták a minőségügyi hálózatokat az élek (kapcsolatok) és a csúcsok (hálózati pontok) típusai alapján. Ezt követően definiálták a multimodális (több különböző csúcstípusból álló) tudáshálózatot, amely a feladatokból, az erőforrásokból, a tudáselemekből és a közöttük lévő kapcsolatokból épül fel. A hálózat segítségével kategóriákba sorolták a tudáselemeket, valamint a fokszámok alapján meghatározták értéküket. A multimodális hálózatból képzett tudáselem-hálózatban megadták az összefüggő csoportok jelentését, majd megfogalmaztak egy összefüggést a tudáselem-elvesztés kockázatának meghatározására. _______ The aims of quality management are to identify those factors that have significant influence on value production, qualify or quantify them, and make preventive and corrective actions in order to reduce their negative effects. The core elements of value production are processes and tasks, along with workforce having the necessary knowledge to work. For that reason the task-resource-knowledge structure is pertinent to quality management. Network science provides methods to analyze complex systems; therefore it seems reasonable to study the use of tools of network analysis in association with quality management issues. First of all the authors categorized quality networks according to the types of nodes (vertices) and links (edges or arcs). Focusing on knowledge management, they defined the multimodal knowledge network, consisting of tasks, resources, knowledge items and their interconnections. Based on their degree, network nodes can be categorized and their value can be quantified. Derived from the multimodal network knowledge-item network is to be created, where the meaning of cohesive subgroups is defined. Eventually they proposed a formula for determining the risk of knowledge loss.

3D TerraFly: Quality of service management for online interactive 3D geographic information system

3D geographic information system (GIS) is data and computation intensive in nature. Internet users are usually equipped with low-end personal computers and network connections of limited bandwidth. Data reduction and performance optimization techniques are of critical importance in quality of service (QoS) management for online 3D GIS. In this research, QoS management issues regarding distributed 3D GIS presentation were studied to develop 3D TerraFly, an interactive 3D GIS that supports high quality online terrain visualization and navigation. ^ To tackle the QoS management challenges, multi-resolution rendering model, adaptive level of detail (LOD) control and mesh simplification algorithms were proposed to effectively reduce the terrain model complexity. The rendering model is adaptively decomposed into sub-regions of up-to-three detail levels according to viewing distance and other dynamic quality measurements. The mesh simplification algorithm was designed as a hybrid algorithm that combines edge straightening and quad-tree compression to reduce the mesh complexity by removing geometrically redundant vertices. The main advantage of this mesh simplification algorithm is that grid mesh can be directly processed in parallel without triangulation overhead. Algorithms facilitating remote accessing and distributed processing of volumetric GIS data, such as data replication, directory service, request scheduling, predictive data retrieving and caching were also proposed. ^ A prototype of the proposed 3D TerraFly implemented in this research demonstrates the effectiveness of our proposed QoS management framework in handling interactive online 3D GIS. The system implementation details and future directions of this research are also addressed in this thesis. ^

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.

Notes on sufficient conditions for a graph to be Hamiltonian

The first part of this paper deals with an extension of Dirac's Theorem to directed graphs. It is related to a result often referred to as the Ghouila-Houri Theorem. Here we show that the requirement of being strongly connected in the hypothesis of the Ghouila-Houri Theorem is redundant. The Second part of the paper shows that a condition on the number of edges for a graph to be hamiltonian implies Ore's condition on the degrees of the vertices.

Magnetic ordering in Er₂Ti₂O₇ and elastic softening in Tb₂Ti₂O₇

Geometric frustration occurs in the rare earth pyrochlores due to magnetic rare earth ions occupying the vertices of the network of corner-sharing tetrahedra. In this research, we have two parts. In the first one we study the phase transition to the magnetically ordered state at low temperature in the pyrochlore Er₂Ti₂O₇. The molecular field method was used to solve this problem. In the second part, we analyse the crystal electric field Hamiltonian for the rare earth sites. The rather large degeneracy of the angular momentum J of the rare earth ion is lifted by the crystal electric field due to the neighboring ions in the crystal. By rewriting the Stevens operators in the crystal electric field Hamiltonian ᴴCEF in terms of charge quadruple operators, we can identify unstable order parameters in ᴴCEF . These may be related to lattice instabilities in Tb₂Ti₂O₇.

Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.

Irreducibility of Random Hilbert Schemes

We prove that a random Hilbert scheme that parametrizes the closed subschemes with a fixed Hilbert polynomial in some projective space is irreducible and nonsingular with probability greater than $0.5$. To consider the set of nonempty Hilbert schemes as a probability space, we transform this set into a disjoint union of infinite binary trees, reinterpreting Macaulay's classification of admissible Hilbert polynomials. Choosing discrete probability distributions with infinite support on the trees establishes our notion of random Hilbert schemes. To bound the probability that random Hilbert schemes are irreducible and nonsingular, we show that at least half of the vertices in the binary trees correspond to Hilbert schemes with unique Borel-fixed points.

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Partition alignment in three dimensional unstructured mesh multi-physics modelling

Unstructured mesh codes for modelling continuum physics phenomena have evolved to provide the facility to model complex interacting systems. Parallelisation of such codes using single Program Multi Data (SPMD) domain decomposition techniques implemented with message passing has been demonstrated to provide high parallel efficiency, scalability to large numbers of processors P and portability across a wide range of parallel platforms. High efficiency, especially for large P requires that load balance is achieved in each parallel loop. For a code in which loops span a variety of mesh entity types, for example, elements, faces and vertices, some compromise is required between load balance for each entity type and the quantity of inter-processor communication required to satisfy data dependence between processors.

Integrability for Relativistic Spin Networks

The evaluation of relativistic spin networks plays a fundamental role in the Barrett-Crane state sum model of Lorentzian quantum gravity in 4 dimensions. A relativistic spin network is a graph labelled by unitary irreducible representations of the Lorentz group appearing in the direct integral decomposition of the space of L^2 functions on three-dimensional hyperbolic space. To `evaluate' such a spin network we must do an integral; if this integral converges we say the spin network is `integrable'. Here we show that a large class of relativistic spin networks are integrable, including any whose underlying graph is the 4-simplex (the complete graph on 5 vertices). This proves a conjecture of Barrett and Crane, whose validity is required for the convergence of their state sum model.