Thesis (Ph. D.)--University of Louisville, 2009. / Department of Mathematics. Vita. "May 2009." Includes bibliographical references (leaves 67-69) and index.

Interpreting graphically displayed data is an important life skill. This thesis examines some of the problems that 14 and 15 year olds encounter when interpreting trends in cartesian graphs. A survey of errors made by 144 pupils is discussed, which shows that two of the most difficult aspects of graph work are interpreting changes in gradients, and inter-relating the graph with its context. A detailed analysis of individual pupils interpretations of changes in gradients shows that pupils conceptions of gradient can be classified according to whether they have an 'iconic' or an 'analytical' origin. iconic descriptions are concerned with the structure, shape or position of the curve, whereas analytical descriptions are concerned with more abstract notions, such as the angle or steepness of the curve, and rate of increase. The results indicate that the occurrence of different kinds of conceptions is influenced by both the form of the graph and its context. In another study, the pupils were given two structurally isomorphic graph interpretation tasks. The results of this investigation also show that the context of a graph in relation to its structural form, has a profound influence upon the way that pupils interpret it. Interpretations are described, in which the influence of metaphors, knowledge from everyday life experience and anthropomorphic reactions can be seen. Pictorial accounts show how conceptions from some of these sources are brought into the pupils interpretations.

Magister Scientiae - MSc / In the course of exploring various symmetries of vertex-transitive graphs, we introduce the concept of quasi-normal subgroups in groups. This is done since the symmetries of vertex-transitive graphs are intimately linked to those, fait accompli, of groups. With this, we ask if the concept of strongly simple groups has a place for consideration. / South Africa

M.Sc. / The aim of this thesis is to investigate the topic of edge-colourings of graphs in the context of hereditary graph properties. We particularly aim to investigate analogues of reducibility, unique factorization and some related concepts. Chapter 1 gives the basic definitions and terminology. A few useful general results are also stated. In Chapter 2 we define and investigate decomposability, the analogue of reducibility. Some general results are first proved, such as that the indecomposability of an additive induced-hereditary property in the lattice of such properties implies that it is indecomposable in a general sense. The decomposability of various specific properties is then investigated in the rest of the chapter. In Chapter 3 we investigate unique decomposability, the analogue of unique factorization. We give examples showing that not every additive hereditary property is uniquely decomposable, and we obtain some results on homomorphism properties which lead to the unique decomposability of Ok. We also consider some related questions, such as cancellation and preservation of strict inclusions. Chapter 4 deals with Ramsey properties. We obtain some general results and, using the so-called partite construction, we obtain a few restricted Ramsey-graph results. As a corollary, we obtain two more unique decomposability results. In Chapter 5 we obtain various bounds involving the property Vk of k-degeneracy. We also investigate the sharpness of these bounds and prove that Vk is indecomposable for every k. Chapter 6 deals with the connection between colourings of infinite graphs and properties of finite graphs. We obtain some extensions of the Compactness Principle and give an example showing that the Compactness Principle can be useful in studying finite graphs.

Ph.D. / Please refer to full text to view abstract

In this dissertation we consider the problem of mining cohesive (dense) subgraphs in probabilistic graphs, where each edge has a probability of existence. Mining probabilistic graphs has become the focus of interest in analyzing many real-world datasets, such as social, trust, communication, and biological networks due to the intrinsic uncertainty present in them. Studying cohesive subgraphs can reveal important information about connectivity, centrality, and robustness of the network, with applications in areas such as bioinformatics and social networks. In deterministic graphs, there exists various definitions of cohesive substructures, including cliques, quasi-cliques, k-cores and k-trusses. In this regard, k-core and k-truss decompositions are popular tools for finding cohesive subgraphs. In deterministic graphs, a k-core is the largest subgraph in which each vertex has at least k neighbors, and a k-truss is the largest subgraph whose edges are contained in at least k triangles (or k-2 triangles depending on the definition). The k-core and k-truss decomposition in deterministic graphs have been thoroughly studied in the literature. However, in the probabilistic context, the computation is challenging and state-of-art approaches are not scalable to large graphs. The main challenge is efficient computation of the tail probabilities of vertex degrees and triangle count of edges in probabilistic graphs. We employ a special version of central limit theorem (CLT) to obtain the tail probabilities efficiently. Based on our CLT approach we propose peeling algorithms for core and truss decomposition of a probabilistic graph that scales to very large graphs and offers significant improvement over state-of-the-art approaches. Moreover, we propose a second algorithm for probabilistic core decomposition that can handle graphs not fitting in memory by processing them sequentially one vertex at a time. In terms of truss decomposition, we design a second method which is based on progressive tightening of the estimate of the truss value of each edge based on h-index computation and novel use of dynamic programming. We provide extensive experimental results to show the efficiency of the proposed algorithms. Another contribution of this thesis is mining cohesive subgraphs using the recent notion of nucleus decomposition introduced by Sariyuce et al. Nucleus decomposition is based on higher order structures such as cliques nested in other cliques. Nucleus decomposition can reveal interesting subgraphs that can be missed by core and truss decompositions. In this dissertation, we present nucleus decomposition for probabilistic graphs. The major questions we address are: How to define meaningfully nucleus decomposition in probabilistic graphs? How hard is computing nucleus decomposition in probabilistic graphs? Can we devise efficient algorithms for exact or approximate nucleus decomposition in large graphs? We present three natural definitions of nucleus decomposition in probabilistic graphs: local, global, and weakly-global. We show that the local version is in PTIME, whereas global and weakly-global are #P-hard and NP-hard, respectively. We present an efficient and exact dynamic programming approach for the local case. Further, we present statistical approximations that can scale to bigger datasets without much loss of accuracy. For global and weakly-global decompositions we complement our intractability results by proposing efficient algorithms that give approximate solutions based on search space pruning and Monte-Carlo sampling. Extensive experiments show the scalability and efficiency of our algorithms. Compared to probabilistic core and truss decompositions, nucleus decomposition significantly outperforms in terms of density and clustering metrics. / Graduate

No description available.

No description available.

No description available.

No description available.