M.Sc. (Mathematics) / In Chapter 1, we consider the relevant theory pertaining to graphs and digraphs that will be used in the study of flows in networks. Warshall’s algorithm for reachability is also considered since it will allow us to ascertain whether some paths exist in some instance. In Chapter 2, we explore flows and cuts in networks. We define the basic concepts of source, sink, intermediate vertices, capacity, costs and lower-bounds. Feasible flows are defined, as well as the value of a flow. Cuts in capacitated networks are explored and further theory relating the value of a flow and cuts is given. We considered the problem of determining a maximal flow. In particular, we consider augmentations of the flow—this allows us to give a characterization of a maximal flow. The important Max-flow Min-cut theorem is also considered. After having explored the relevant theory, we move on to methods of finding a maximal flow for a given s-t network that has a capacity on each of its arcs. Firstly, we consider zero-one and unit-capacity networks since these play a role in the applications of maximal flows in Chapter 4. We, then, compile the relevant theory and algorithms in order to implement two augmenting path finding algorithms.

The aim of this thesis was to create a resilient network, capable of handling link failures without affecting the data flow. This was done by using graph theory and three mathematical models. A generic system was created, on which the models were applied on. The mathematical models were path diversity, edge protection and path restoration. These models were tested to evaluate if they could create a robust system. The models were also compared with each other to obtain the best performing one. It was concluded that it was possible to construct a resilient network using these types of mathematical modelling. It was also concluded that the models provided different results in terms of cost and robustness. The report ends with suggestions on future work of how studies can be conducted to create realistic systems.

Magister Scientiae - MSc / This thesis is a study on the confluence of algebraic structures and graph theory. Its aim is to consider groupoids from factorisations of complete graphs. We are especially interested in the cases where the factors are isomorphic. We analyse the loops obtained from homogeneous factorisations and ask if homogeneity is reflected in the kind of loops that are obtained. In particular, we are interested to see if we obtain either groups or quasi-associative Cayley sets from these loops. November 2008. / South Africa

Background: Deficits in the processing of emotional stimuli have long been associated with major depressive disorder (MDD). These emotional biases are believed central to the symptomatology of MDD, with evidence growing that such biases can also be seen during remission. Although such changes are typical of psychiatric morbidity evidence is growing for the impact of ageing on emotional processing as well. Evidence shows that relative to younger adults, older adults demonstrate biases that favour positive information over negative. There is therefore overlap between MDD and normal ageing that has yet to be explored in the literature. Because positive biases are implicated in successful ageing it is important to consider the impact of previous MDD as individuals age. It is this question that is explored in this thesis. Study 1: A behavioural neuropsychological investigation was undertaken comparing older and younger adults with and without a history of MDD on a battery of affective cognitive tasks. Results suggested that the difference between the older adults with and without a history of MDD lay in their ability to disengage from negative information. Study 2: An fMRI investigation was undertaken in a subset of the study 1 sample using neuroimaging paradigms assessing memory encoding and attention for emotional stimuli. Broadly results suggested no influence of previous MDD on the processing of emotional information in the studied domains, with evidence seen in both tasks for the neural basis of the positivity effect of ageing. Study 3: A resting-state fMRI investigation of brain connectivity was undertaken to assess the influence of previous MDD and normal ageing on the communication structure of the brain. Results were largely suggestive of the influence of normal healthy ageing, with limited evidence of the influence of previous MDD or its interaction with ageing. Conclusions: Results were mixed across the investigations. Generally speaking the initial behavioural study was best powered to investigation the questions of interest, suggesting the potential for differential affective processing strategies in later life dependent on previous MDD. The subsequent imaging studies were perhaps less well placed to draw conclusions given limitations in terms of the domains investigated and the sample size. Evidence for the postulate that previous MDD impacts the development of the positivity effect has therefore been demonstrated, but for now remains limited to the behavioural domain.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Pietro Poggi-Corradini / Caterina M. Scoglio / The modulus of a family of walks quantifies the richness of the family by favoring having many short walks over a few longer ones. In this dissertation, we investigate various families of walks to study new measures for quantifying network properties using modulus. The proposed new measures are compared to other known quantities. Our proposed method is based on walks on a network, and therefore will work in great generality. For instance, the networks we consider can be directed, multi-edged, weighted, and even contain disconnected parts. We study the popular centrality measure known in some circles as information centrality, also known as effective conductance centrality. After reinterpreting this measure in terms of modulus of families of walks, we introduce a modification called shell modulus centrality, that relies on the egocentric structure of the graph. Ego networks are networks formed around egos with a specific order of neighborhoods. We then propose efficient analytical and approximate methods for computing these measures on both directed and undirected networks. Finally, we describe a simple method inspired by shell modulus centrality, called general degree, which improves simple degree centrality and could prove to be a useful tool for practitioners in the applied sciences. General degree is useful for detecting the best set of nodes for immunization. We also study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks. Computing loop modulus benefits from efficient algorithms for finding shortest loops, thus we propose a deterministic combinatorial algorithm that finds a shortest cycle in graphs. The proposed algorithm reduces the worst case time complexity of the existing combinatorial algorithms while visiting at most the cycle basis. For most empirical networks with sublinear average degree our algorithm is subcubic.

A novel framework based on cluster co-occurrence and graph theory for structure discovery is applied to audio to find new types of audio objects which enable the compression of an input signal. These new objects differ from those found in current object coding schemes as their shape is not restricted by any a priori psychoacoustic knowledge. The framework is novel from an application perspective, as it marks the first time that graph theory is applied to audio, and with regards to theoretical developments, as it involves new extensions to the areas of unsupervised learning algorithms and frequent subgraph mining methods. Tests are performed using a corpus of audio files spanning a wide range of sounds. Results show that the framework discovers new types of audio objects which yield average respective overall and relative compression gains of 15.90% and 23.53% while maintaining a very good average audio quality with imperceptible changes.

Ph.D. / In this thesis, the ranks of many types of regular and strongly regular graphs are determined. Also determined are ranks of regular graphs under unary operations: the line graph, the complement, the subdivision graph, the connected cycle, the complete subdivision graph, and the total graph. The binary operations considered are the Cartesian product and the complete product. The ranks of the Cartesian product of regular graphs have been investigated previously in [BBD1]; here, we summarise and extend those results to include more regular graphs. We also examine a special nonregular graph, the path. Ranks of paths and products of graphs involving paths are presented as well

Characteristically, propagation of news on the Internet is a rather complex scenario. Its comprehensive understanding requires a consideration of diverse facets such as audience, problem domain, channel and type of news being propagated. My dissertation focuses on the understanding of propagation of a specific type of news- news articles, on a particular subset of the Internet, the social media. While a number of studies have looked into the phenomenon of propagation in social media, fewer of these have examined the propagation of content, specifically news articles, published by news provider websites. My dissertation presents a set of network theory based methodologies to extract and analyze various implicit propagation networks formed as a result of news article sharing on Twitter. These methodologies cover aspects related to users' article sharing behavior, influence of the news provider's social media accounts, role of followers and similarities between propagation networks of news providers. Furthermore, it also includes useful inferences derived about the news article propagation phenomenon by using a population sized data sampled from Twitter over a nine-month period. It expands on the inferences from my published works and the challenges identified in the area of news article consumption and distribution on the Internet. My dissertation intends to provide important guidelines for researchers and organizations studying social media related phenomena to derive insights about customer behavior. From the perspective of online news consumption and distribution, my study has important implications for the audience's preference of news content delivery. It also facilitates news providers to gauge their performance on social media and for news editors to help develop editorial policies tailored for an online consumer base. Finally, my dissertation presents an extensive set of network based models and methodologies that can enrich the applied network science discipline.

In this dissertation we study the Hamiltonicity and the uniform-Hamiltonicity of subset graphs, subspace graphs, and their associated bipartite graphs. In 1995 paper "The Subset-Subspace Analogy," Kung states the subspace version of a conjecture. The study of this problem led to a more general class of graphs. Inspired by Clark and Ismail's work in the 1996 paper "Binomial and Q-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and their Q-Analogues," we defined subset graphs, subspace graphs, and their associated bipartite graphs. The main emphasis of this dissertation is to describe those graphs and study their Hamiltonicity. The results on subset graphs are presented in Chapter 3, on subset bipartite graphs in Chapter 4, and on subspace graphs and subspace bipartite graphs in Chapter 5. We conclude the dissertation by suggesting some generalizations of our results concerning the panciclicity of the graphs.

Orientador: Célia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T04:52:30Z (GMT). No. of bitstreams: 1 Vilas-Boas_AloisiodeMenezes_M.pdf: 3075345 bytes, checksum: 59f85d259c9a55bce9d3409c06dd71fa (MD5) Previous issue date: 2015 / Resumo: Seja G um grafo simples. Uma coloração de arestas semiforte de G é uma coloração de arestas de G onde para cada par de vértices adjacentes u,v de G, o conjunto das cores atribuídas às arestas de u é diferente do conjunto das cores atribuídas às arestas de v. O índice cromático semiforte de G, denotado por chi'a(G), é o menor número de cores necessário para construir uma coloração de arestas semiforte para G. Esta coloração foi proposta por Zhang et al. em 2002. Nesse mesmo artigo, os autores conjecturaram que todo grafo simples conexo G, G diferente de C_5, com pelo menos três vértices possui chi'a(G) menor ou igual a Delta(G)+2. Esta conjectura conhecida como conjectura da coloração de arestas semiforte está aberta para grafos arbitrários, mas é válida para algumas classes de grafos. Nesta dissertação, apresentamos alguns resultados sobre a coloração de arestas semiforte. Em seguida, focamos em grafos split. Provamos a conjectura da coloração de arestas semiforte para algumas famílias destes grafos, dentre elas, os split-completos e os split-indiferença. Além disso, determinamos o índice cromático semiforte dos grafos split-indiferença com vértice universal. Para grafos split-indiferença sem vértice universal, exibimos condições para que seu índice cromático semiforte seja igual a Delta(G)+1 e conjecturamos chi'a(G) = Delta(G)+2 caso contrário / Abstract: Let G be a simple graph. An adjacent strong edge-coloring of G is an edge-coloring of G such that for each pair of adjacent vertices u,v of G, the set of colors assigned to the edges incident with u differs from the set of colors assigned to the edges incident with v. The adjacent strong chromatic index, denoted chi'a(G), of G is the minimum number of colors required to produce an adjacent strong edge-coloring for G. This coloring was proposed by Z. Zhang et al. In the same article, the authors conjectured that every simple connected graph G with at least three vertices and G not equal to C_5 (a 5-cycle) has chi'a(G) less or equal then Delta(G)+2. This conjecture is open for arbitrary graphs, but it holds for some classes of graphs. In this dissertation, we present some results on adjacent strong edge-coloring. Then, we focus on split graphs. We prove the conjecture for some families of split graphs including split-complete graphs and split-indifference graphs. Moreover, we determine a necessary condition for split-complete graphs G to have chi'a(G) = Delta(G)+1 and we determine the adjacent strong chromatic index for split-indifference graphs with a universal vertex. For a split-indifference graph G without universal vertices, we give conditions for its adjacent strong chromatic index to be Delta(G)+1 and we conjecture that chi'a(G) = Delta(G)+2, otherwise / Mestrado / Ciência da Computação / Mestre em Ciência da Computação