A comprehensive study of multiplicative attribute graph model

Graphs are powerful tools to describe social, technological and biological networks, with nodes representing agents (people, websites, gene, etc.) and edges (or links) representing relations (or interactions) between agents. Examples of real-world networks include social networks, the World Wide Web, collaboration networks, protein networks, etc. Researchers often model these networks as random graphs. In this dissertation, we study a recently introduced social network model, named the Multiplicative Attribute Graph model (MAG), which takes into account the randomness of nodal attributes in the process of link formation (i.e., the probability of a link existing between two nodes depends on their attributes). Kim and Lesckovec, who defined the model, have claimed that this model exhibit some of the properties a real world social network is expected to have. Focusing on a homogeneous version of this model, we investigate the existence of zero-one laws for graph properties, e.g., the absence of isolated nodes, graph connectivity and the emergence of triangles. We obtain conditions on the parameters of the model, so that these properties occur with high or vanishingly probability as the number of nodes becomes unboundedly large. In that regime, we also investigate the property of triadic closure and the nodal degree distribution.

Xylem plugging and postharvest longevity of cut Acacia holosericea

An inherently short vase life is a problematic characteristic of cut flowers and foliage for otherwise attractive native Australian Acacia spp. Reasons underlying the poor postharvest water uptake of cut acacia stems have been elusive. A. holosericea was used to investigate possible bacteria-induced and wound-induced xylem occlusion. The effects of bacterial-and wound-induced xylem blockage on water uptake were investigated by light and scanning and transmission electron microscopy. Observations were made on cut stems that stood into either deionised water (DIW; control) or 0.5 mM Cu2+ solution and on stems pulsed with 2.2 mM Cu2+ solution and then stood into DIW. The stem-end region of cut A. holosericea that stood into DIW or Cu2+ solution became covered with bacterial growth after 3 days. Regardless of the bacterial biofilm, the Cu2+ treated stems had improved water relations and vase life. Therefore, the biofilm had little or no effect on cut A. holosericea longevity. Further observations revealed presence of a vessel-occluding substance (gel) originating from axial parenchyma cells in direct physical contact with xylem vessels. The gel exuded into vessel lumens through pit membranes, evidently as a wound-response. Xylem occlusion by gels in A. holosericea may be especially problematic due to an abundance of secretory contact cells relative to xylem elements. Nonetheless, active wound response processes may be the key determinant of short postharvest longevity for this and possibly other cut Acacia spp. Cu2+ treatments, however, disrupted the secretory function of axial parenchyma cells thereby preventing vessel occlusion by the gels.

Spectral graph theory with applications to quantum adiabatic optimization

In this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.

Graph analysis of verbal fluency test discriminate between patients with Alzheimer’s disease, Mild Cognitive Impairment and normal elderly controls

Verbal fluency is the ability to produce a satisfying sequence of spoken words during a given time interval. The core of verbal fluency lies in the capacity to manage the executive aspects of language. The standard scores of the semantic verbal fluency test are broadly used in the neuropsychological assessment of the elderly, and different analytical methods are likely to extract even more information from the data generated in this test. Graph theory, a mathematical approach to analyze relations between items, represents a promising tool to understand a variety of neuropsychological states. This study reports a graph analysis of data generated by the semantic verbal fluency test by cognitively healthy elderly (NC), patients with Mild Cognitive Impairment – subtypes amnestic(aMCI) and amnestic multiple domain (a+mdMCI) - and patients with Alzheimer’s disease (AD). Sequences of words were represented as a speech graph in which every word corresponded to a node and temporal links between words were represented by directed edges. To characterize the structure of the data we calculated 13 speech graph attributes (SGAs). The individuals were compared when divided in three (NC – MCI – AD) and four (NC – aMCI – a+mdMCI – AD) groups. When the three groups were compared, significant differences were found in the standard measure of correct words produced, and three SGA: diameter, average shortest path, and network density. SGA sorted the elderly groups with good specificity and sensitivity. When the four groups were compared, the groups differed significantly in network density, except between the two MCI subtypes and NC and aMCI. The diameter of the network and the average shortest path were significantly different between the NC and AD, and between aMCI and AD. SGA sorted the elderly in their groups with good specificity and sensitivity, performing better than the standard score of the task. These findings provide support for a new methodological frame to assess the strength of semantic memory through the verbal fluency task, with potential to amplify the predictive power of this test. Graph analysis is likely to become clinically relevant in neurology and psychiatry, and may be particularly useful for the differential diagnosis of the elderly.

Nano-silver treatments reduced bacterial colonization and biofilm formation at the stem-ends of cut gladiolus ‘Eerde’ spikes

Postharvest treatments with nano-silver (NS) alleviate bacteria-related stem blockage of some cut flowers to extend their longevity. Gladiolus (Gladiolus hybridus) is a commercially important cut flower species. For the first time, the effects of NS pulses on cut gladiolus ‘Eerde’ spikes were investigated towards reducing bacterial colonization of and biofilm formation on their stems. As compared with a deionized water (DIW) control, pulse treatments with NS at 10, 25 and 50 mg L−1 for 24 h significantly (P ≤ 0.05) prolonged the vase life of cut gladiolus spikes moved into vases containing DIW. The NS treatments enhanced floret ‘opening rate’ and ‘daily ornamental value’. Although there were no significant differences among NS treatments, a 25 mg L−1 NS pulse treatment tended to give the longest vase life and the best ‘display quality’. All NS pulse treatments significantly improved water uptake by and reduced water loss from flowering spikes, thereby delaying the loss of water balance and maintaining relative fresh weight. Fifty (50) mg L−1 NS pulse-treated cut gladiolus spikes tended to exhibit the most water uptake and highest water balance over the vase period. However, there was no significant difference between 25 and 50 mg L−1 NS pulse treatments. Observations of stem-end bacterial proliferation during the vase period on cut gladiolus spikes either with or without NS pulse treatments were performed by confocal laser scanning microscopy (CLSM) and scanning electron microscopy (SEM). As compared to the control treatment, they revealed that the 25 mg L−1 NS pulse treatment effectively inhibited bacterial colonization and biofilm formation on the stem-end cut surface and in the xylem vessels, respectively. In vitro culture of the bacterial microflora and analysis of biofilm architecture using CLSM revealed that NS treatment restricted bacterial biofilm formation. After static culture for 24 h at 35 °C with 25 mg L−1 NS in the medium, no biofilm form or structure was evident. Rather, only limited bacterial cell number and scanty extracellular polysaccharide (EPS) material were observed. In contrast, mature bacterial biofilm architecture comprised of abundant bacteria interwoven with EPS formed in the absence of NS.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

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.

Postharvest quality changes in fresh-cut watercress stored under conventional and inert gas-enriched modified atmosphere packaging

The effect of modified atmosphere packaging (MAP) on the postharvest quality of fresh-cut watercress (Nasturtium officinale R. Br.) stored at 4 ºC for 7 d was studied. A portion of watercress was immediately analyzed (non-stored control) and the remaining fresh material was stored packaged under atmospheres enriched with N2, Ar, air, or vacuum. The analyzed parameters included colour, total soluble solids, pH, macronutrients, the individual profiles of sugars, organic acids, tocopherols and fatty acids, and total phenolics and flavonoids. Furthermore, four in vitro assays were performed to evaluate the antioxidant activity. After assessing the effect on individual quality parameters, it was possible to conclude that air was the less efficient atmosphere in preserving quality attributes of the non-stored control samples during cold storage. In turn, Ar-enriched MAP was the most suitable choice to preserve the overall postharvest quality. The present study also highlighted the nutritional and antioxidant properties of watercress, as well as the interest of its inclusion in human diets.

Suitability of gamma irradiation for preserving fresh-cut watercress quality during cold storage

The suitability of gamma irradiation (1, 2 and 5kGy) for preserving quality parameters of fresh-cut watercress (Nasturtium officinale R. Br.) during storage at 4±1°C for 7d was investigated. The storage time decreased the protein content and the main carbohydrates, and increased the levels of malic and fumaric acids, sucrose and mono- and polyunsaturated fatty acids (MUFA and PUFA). The different irradiation doses did not caused any significant colour change. In general, the 2kGy dose favoured PUFA and was the most suitable to preserve the overall postharvest quality of fresh-cut watercress during cold storage. In turn, the 5kGy dose better preserved the antioxidant activity and total flavonoids and favoured MUFA, tocopherols and total phenolics, thus originating a final product with enhanced functional properties. Therefore, the suitability of gamma irradiation for preserving fresh-cut watercress quality during cold storage was demonstrated.

Appraisal of open software for finite element simulation of 2D metal sheet laser cut.

FEA simulation of thermal metal cutting is central to interactive design and manufacturing. It is therefore relevant to assess the applicability of FEA open software to simulate 2D heat transfer in metal sheet laser cuts. Application of open source code (e.g. FreeFem++, FEniCS, MOOSE) makes possible additional scenarios (e.g. parallel, CUDA, etc.), with lower costs. However, a precise assessment is required on the scenarios in which open software can be a sound alternative to a commercial one. This article contributes in this regard, by presenting a comparison of the aforementioned freeware FEM software for the simulation of heat transfer in thin (i.e. 2D) sheets, subject to a gliding laser point source. We use the commercial ABAQUS software as the reference to compare such open software. A convective linear thin sheet heat transfer model, with and without material removal is used. This article does not intend a full design of computer experiments. Our partial assessment shows that the thin sheet approximation turns to be adequate in terms of the relative error for linear alumina sheets. Under mesh resolutions better than 10e−5 m , the open and reference software temperature differ in at most 1 % of the temperature prediction. Ongoing work includes adaptive re-meshing, nonlinearities, sheet stress analysis and Mach (also called ‘relativistic’) effects.

Graph-based structural analysis of planar mechanisms.

Kinematic structure of planar mechanisms addresses the study of attributes determined exclusively by the joining pattern among the links forming a mechanism. The system group classification is central to the kinematic structure and consists of determining a sequence of kinematically and statically independent-simple chains which represent a modular basis for the kinematics and force analysis of the mechanism. This article presents a novel graph-based algorithm for structural analysis of planar mechanisms with closed-loop kinematic structure which determines a sequence of modules (Assur groups) representing the topology of the mechanism. The computational complexity analysis and proof of correctness of the implemented algorithm are provided. A case study is presented to illustrate the results of the devised method.

A Hardware Task-Graph Scheduler for Reconfigurable Multi-tasking Systems

Reconfigurable hardware can be used to build a multitasking system where tasks are assigned to HW resources at run-time according to the requirements of the running applications. These tasks are frequently represented as direct acyclic graphs and their execution is typically controlled by an embedded processor that schedules the graph execution. In order to improve the efficiency of the system, the scheduler can apply prefetch and reuse techniques that can greatly reduce the reconfiguration latencies. For an embedded processor all these computations represent a heavy computational load that can significantly reduce the system performance. To overcome this problem we have implemented a HW scheduler using reconfigurable resources. In addition we have implemented both prefetch and replacement techniques that obtain as good results as previous complex SW approaches, while demanding just a few clock cycles to carry out the computations. We consider that the HW cost of the system (in our experiments 3% of a Virtex-II PRO xc2vp30 FPGA) is affordable taking into account the great efficiency of the techniques applied to hide the reconfiguration latency and the negligible run-time penalty introduced by the scheduler computations.

A Task-Graph Execution Manager for Reconfigurable Multi-tasking Systems

Reconfigurable hardware can be used to build multi tasking systems that dynamically adapt themselves to the requirements of the running applications. This is especially useful in embedded systems, since the available resources are very limited and the reconfigurable hardware can be reused for different applications. In these systems computations are frequently represented as task graphs that are executed taking into account their internal dependencies and the task schedule. The management of the task graph execution is critical for the system performance. In this regard, we have developed two dif erent versions, a software module and a hardware architecture, of a generic task-graph execution manager for reconfigurable multi-tasking systems. The second version reduces the run-time management overheads by almost two orders of magnitude. Hence it is especially suitable for systems with exigent timing constraints. Both versions include specific support to optimize the reconfiguration process.

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.