Physical Sciences and Mathematics Commons^™

Color-Connected Graphs And Information-Transfer Paths, Stephen Devereaux

Dissertations

The Department of Homeland Security in the United States was created in 2003 in response to weaknesses discovered in the transfer of classied information after the September 11, 2001 terrorist attacks. While information related to national security needs to be protected, there must be procedures in place that permit access between appropriate parties. This two-fold issue can be addressed by assigning information-transfer paths between agencies which may have other agencies as intermediaries while requiring a large enough number of passwords and rewalls that is prohibitive to intruders, yet small enough to manage. Situations such as this can be represented by …

Linking Taxonomic Diversity And Trophic Function: A Graph-Based Theoretical Approach, Marcella M. Jurotich, Kaitlyn Dougherty, Barbara Hayford, Sally Clark

Transactions of the Nebraska Academy of Sciences and Affiliated Societies

The purpose of this study is to develop a novel, visual method in analyzing complex functional trait data in freshwater ecology. We focus on macroinvertebrates in stream ecosystems under a gradient of habitat degradation and employ a combination of taxonomic and functional trait diversity analyses. Then we use graph theory to link changes in functional trait diversity to taxonomic richness and habitat degradation. We test the hypotheses that: 1) taxonomic diversity and trophic functional trait diversity both decrease with increased habitat degradation; 2) loss of taxa leads to a decrease in trophic function as visualized using a bipartite graph; and …

Random Walks On Digraphs, J.J.P. Veerman

Mathematics and Statistics Faculty Publications and Presentations

Let V = {1, · · · n} be a vertex set and S a non-negative row-stochastic matrix (i.e. rows sum to 1). V and S define a digraph G = G(V, S) and a directed graph Laplacian L as follows. If (S)ij > 0 (in what follows we will leave out the parentheses) there is a directed edge j → i. Thus the ith row of S identifies the edges coming into vertex i and their weights. This set of vertices are collectively the neighbors of i, and is denoted by Ni . The diagonal elements Sii are chosen such …

Approximation Algorithms For Effective Team Formation, George Rabanca

Dissertations, Theses, and Capstone Projects

This dissertation investigates the problem of creating multiple disjoint teams of maximum efficacy from a fixed set of workers. We identify three parameters which directly correlate to the team effectiveness — team expertise, team cohesion and team size — and propose efficient algorithms for optimizing each in various settings. We show that under standard assumptions the problems we explore are not optimally solvable in polynomial time, and thus we focus on developing efficient algorithms with guaranteed worst case approximation bounds. First, we investigate maximizing team expertise in a setting where each worker has different expertise for each job and each …

Application Of Support Vector Machine Modeling And Graph Theory Metrics For Disease Classification, Jessica M. Rudd

Published and Grey Literature from PhD Candidates

Disease classification is a crucial element of biomedical research. Recent studies have demonstrated that machine learning techniques, such as Support Vector Machine (SVM) modeling, produce similar or improved predictive capabilities in comparison to the traditional method of Logistic Regression. In addition, it has been found that social network metrics can provide useful predictive information for disease modeling. In this study, we combine simulated social network metrics with SVM to predict diabetes in a sample of data from the Behavioral Risk Factor Surveillance System. In this dataset, Logistic Regression outperformed SVM with ROC index of 81.8 and 81.7 for models with …

Behavior Of Petrie Lines In Certain Edge-Transitive Graphs, Ruby A. Chick

Math Theses

We survey the construction and classification of one-, two- and infinitely-ended members of a class of highly symmetric, highly connected infinite graphs. In addition, we pose a conjecture concerning the relationship between the Petrie lines and ends of some infinitely-ended members of this class.

Merging Peg Solitaire In Graphs, John Engbers, Ryan Weber

Mathematics, Statistics and Computer Science Faculty Research and Publications

Peg solitaire has recently been generalized to graphs. Here, pegs start on all but one of the vertices in a graph. A move takes pegs on adjacent vertices x and y, with y also adjacent to a hole on vertex z, and jumps the peg on x over the peg ony to z, removing the peg on y. The goal of the game is to reduce the number of pegs to one.

We introduce the game merging peg solitaire on graphs, where a move takes pegs on vertices x and z (with a hole on y) and merges them to …

Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler

Honors College Theses

Many factors come into play when it comes to the transmission of infectious diseases. In disease control and prevention, it is inevitable to consider the general population and the relationships between individuals as a whole, which calls for advanced mathematical modeling approaches.

We will use the concept of network flow and the modified Ford-Fulkerson algorithm to demonstrate the transmission of infectious diseases over a given period of time. Through our model one can observe what possible measures should be taken or improved upon in the case of an epidemic. We identify key nodes and edges in the resulted network, which …

On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy

Electronic Theses and Dissertations

For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where every …

Quantifying The Structure Of Misfolded Proteins Using Graph Theory, Walter G. Witt

Electronic Theses and Dissertations

The structure of a protein molecule is highly correlated to its function. Some diseases such as cystic fibrosis are the result of a change in the structure of a protein so that this change interferes or inhibits its function. Often these changes in structure are caused by a misfolding of the protein molecule. To assist computational biologists, there is a database of proteins together with their misfolded versions, called decoys, that can be used to test the accuracy of protein structure prediction algorithms. In our work we use a nested graph model to quantify a selected set of proteins that …

Average Shortest Path Length In A Novel Small-World Network, Andrea J. Allen

Honors Papers

We study a novel model of random graph which exhibits the structural characteristics of the Watts- Strogatz small-world network. The small-world network is characterized by a high level of local clustering while also having a relatively small graph diameter. The same behavior that makes the Watts-Strogatz model behave like this also makes it difficult to analyze. Our model addresses this issue, closely mimicking the same structure experimentally while following a constructive process that makes it easier to analyze mathematically. We present a bound on the average shortest path length in our new model, which we approach by looking at the …

Tying The Knot: Applications Of Topology To Chemistry, Tarini S. Hardikar

Honors Theses

Chirality (or handedness) is the property that a structure is “different” from its mirror image. Topology can be used to provide a rigorous framework for the notion of chirality. This project examines various types of chirality and discusses tools to detect chirality in graphs and knots. Notable theorems that are discussed in this work include ones that identify chirality using properties of link polynomials (HOMFLY polynomials), rigid vertex graphs, and knot linking numbers. Various other issues of chirality are explored, and some specially unique structures are discussed. This paper is borne out of reading Dr. Erica Flapan’s book, When Topology …

Complex Valued Graphs For Soft Computing, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilanthenral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce in a systematic way the notion of complex valued graphs, strong complex valued graphs and complex neutrosophic valued graphs. Several interesting properties are defined, described and developed. Most of the conjectures which are open in case of usual graphs continue to be open problems in case of both complex valued graphs and strong complex valued graphs. We also give some applications of them in soft computing and social networks. At this juncture it is pertinent to keep on record that Dr. Tohru Nitta was the pioneer to use complex valued graphs …

Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri

Theses and Dissertations

miRNAs are non-coding RNAs of approx. 22 nucleotides in length that inhibit gene expression at the post-transcriptional level. By virtue of this gene regulation mechanism, miRNAs play a critical role in several biological processes and patho-physiological conditions, including cancers. miRNA behavior is a result of a multi-level complex interaction network involving miRNA-mRNA, TF-miRNA-gene, and miRNA-chemical interactions; hence the precise patterns through which a miRNA regulates a certain disease(s) are still elusive. Herein, I have developed an integrative genomics methods/pipeline to (i) build a miRNA regulomics and data analytics repository, (ii) create/model these interactions into networks and use optimization techniques, motif …