Matching Items (15)

134602-Thumbnail Image.png

Virtual Reality Visualization of Constructive Solid Geometry Utilizing an HTC Vive

Description

This project created a tool for visualizing constructive solid geometry (CSG) using an HTC Vive virtual reality
headset. This tool provides functionality for surface triangulation
of a variety of three-dimensional

This project created a tool for visualizing constructive solid geometry (CSG) using an HTC Vive virtual reality
headset. This tool provides functionality for surface triangulation
of a variety of three-dimensional primitive solids. Then with those
solids it can perform the core CSG operations—intersection,
union and complement—to create more complex objects. This
tool also parses in Silo data files to allow the visualization
of scientific models like the Annular Core Research Reactor.
This project is useful for both education and visualization. This
project will be used by scientists to visualize and understand
their simulation results, and used as a museum exhibit to engage
the next generation of scientists in computer modeling.

Contributors

Agent

Created

Date Created
  • 2017-05

137483-Thumbnail Image.png

It Takes Five: Basketball Teams Using Network Metrics

Description

Analytic research on basketball games is growing quickly, specifically in the National Basketball Association. This paper explored the development of this analytic research and discovered that there has been a

Analytic research on basketball games is growing quickly, specifically in the National Basketball Association. This paper explored the development of this analytic research and discovered that there has been a focus on individual player metrics and a dearth of quantitative team characterizations and evaluations. Consequently, this paper continued the exploratory research of Fewell and Armbruster's "Basketball teams as strategic networks" (2012), which modeled basketball teams as networks and used metrics to characterize team strategy in the NBA's 2010 playoffs. Individual players and outcomes were nodes and passes and actions were the links. This paper used data that was recorded from playoff games of the two 2012 NBA finalists: the Miami Heat and the Oklahoma City Thunder. The same metrics that Fewell and Armbruster used were explained, then calculated using this data. The offensive networks of these two teams during the playoffs were analyzed and interpreted by using other data and qualitative characterization of the teams' strategies; the paper found that the calculated metrics largely matched with our qualitative characterizations of the teams. The validity of the metrics in this paper and Fewell and Armbruster's paper was then discussed, and modeling basketball teams as multiple-order Markov chains rather than as networks was explored.

Contributors

Agent

Created

Date Created
  • 2013-05

136340-Thumbnail Image.png

An exploration of proofs of the Szemerédi regularity lemma

Description

This paper focuses on the Szemerédi regularity lemma, a result in the field of extremal graph theory. The lemma says that every graph can be partitioned into bounded equal parts

This paper focuses on the Szemerédi regularity lemma, a result in the field of extremal graph theory. The lemma says that every graph can be partitioned into bounded equal parts such that most edges of the graph span these partitions, and these edges are distributed in a fairly uniform way. Definitions and notation will be established, leading to explorations of three proofs of the regularity lemma. These are a version of the original proof, a Pythagoras proof utilizing elemental geometry, and a proof utilizing concepts of spectral graph theory. This paper is intended to supplement the proofs with background information about the concepts utilized. Furthermore, it is the hope that this paper will serve as another resource for students and others to begin study of the regularity lemma.

Contributors

Created

Date Created
  • 2015-05

132775-Thumbnail Image.png

Skipping Turns on the Ordering Game

Description

In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum

In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum number of neighbors that any vertex has before it in the ordering. Alice's goal in the ordering game is to minimize the score, while Bob's goal is to maximize it. The game coloring number is the least score that Alice can always guarantee in the ordering game, no matter how Bob plays. This paper examines what happens to the game coloring number if Alice or Bob skip turns on the ordering game. Preliminary definitions and examples are provided to give context to the ordering game. These include a polynomial time algorithm to compute the coloring number, a non-competitive version of the game coloring number. The notion of the preordered game is introduced as the primary tool of the paper, along with its naturally defined preordered game coloring number. To emphasize the complex relationship between the coloring number and the preordered game coloring number, a non-polynomial time strategy is given to Alice and Bob that yields the preordered game coloring number on any graph. Additionally, the preordered game coloring number is shown to be monotonic, one of the most useful properties for turn-skipping. Techniques developed throughout the paper are then used to determine that Alice cannot reduce the score and Bob cannot improve the score by skipping any number of their respective turns. This paper can hopefully be used as a stepping stone towards bounding the score on graphs when vertices are removed, as well as in deciphering further properties of the asymmetric marking game.

Contributors

Created

Date Created
  • 2019-05

157657-Thumbnail Image.png

Computational interdisciplinarity: a study in the history of science

Description

This dissertation focuses on creating a pluralistic approach to understanding and measuring interdisciplinarity at various scales to further the study of the evolution of knowledge and innovation. Interdisciplinarity is

This dissertation focuses on creating a pluralistic approach to understanding and measuring interdisciplinarity at various scales to further the study of the evolution of knowledge and innovation. Interdisciplinarity is considered an important research component and is closely linked to higher rates of innovation. If the goal is to create more innovative research, we must understand how interdisciplinarity operates.

I begin by examining interdisciplinarity with a small scope, the research university. This study uses metadata to create co-authorship networks and examine how a change in university policies to increase interdisciplinarity can be successful. The New American University Initiative (NAUI) at Arizona State University (ASU) set forth the goal of making ASU a world hub for interdisciplinary research. This kind of interdisciplinarity is produced from a deliberate, engineered, reorganization of the individuals within the university and the knowledge they contain. By using a set of social network analysis measurements, I created an algorithm to measure the changes to the co-authorship networks that resulted from increased university support for interdisciplinary research.

The second case study increases the scope of interdisciplinarity from individual universities to a single scientific discourse, the Anthropocene. The idea of the Anthropocene began as an idea about the need for a new geological epoch and underwent unsupervised interdisciplinary expansion due to climate change integrating itself into the core of the discourse. In contrast to the NAUI which was specifically engineered to increase interdisciplinarity, the I use keyword co-occurrence networks to measure how the Anthropocene discourse increases its interdisciplinarity through unsupervised expansion after climate change becomes a core keyword within the network and behaves as an anchor point for new disciplines to connect and join the discourse.

The scope of interdisciplinarity increases again with the final case study about the field of evolutionary medicine. Evolutionary medicine is a case of engineered interdisciplinary integration between evolutionary biology and medicine. The primary goal of evolutionary medicine is to better understand "why we get sick" through the lens of evolutionary biology. This makes it an excellent candidate to understand large-scale interdisciplinarity. I show through multiple type of networks and metadata analyses that evolutionary medicine successfully integrates the concepts of evolutionary biology into medicine.

By increasing our knowledge of interdisciplinarity at various scales and how it behaves in different initial conditions, we are better able to understand the elusive nature of innovation. Interdisciplinary can mean different things depending on how its defined. I show that a pluralistic approach to defining and measuring interdisciplinarity is not only appropriate but necessary if our goal is to increase interdisciplinarity, the frequency of innovations, and our understanding of the evolution of knowledge.

Contributors

Agent

Created

Date Created
  • 2019

158314-Thumbnail Image.png

Estimating Low Generalized Coloring Numbers of Planar Graphs

Description

The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of

The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.

It is well known that the coloring number is an upper bound for the

chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is

a generalization of the coloring number, and it was first introduced

by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$

is the minimum integer $k$ such that for some linear ordering $L$

of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller

vertices $u$ (with respect to $L$) with a path of length at most

$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.

The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$

is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$

if and only if the distance between $x$ and $y$ in $G$ is $3$.

This dissertation improves the best known upper bound of the

chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$

of planar graphs $G$, which is $105$, to $95$. It also improves

the best known lower bound, which is $7$, to $9$.

A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number.

Contributors

Agent

Created

Date Created
  • 2020

160061-Thumbnail Image.png

On the existence of loose cycle tilings and rainbow cycles

Description

Extremal graph theory results often provide minimum degree

conditions which guarantee a copy of one graph exists within

another. A perfect $F$-tiling of a graph $G$ is a collection

$\mathcal{F}$ of subgraphs of

Extremal graph theory results often provide minimum degree

conditions which guarantee a copy of one graph exists within

another. A perfect $F$-tiling of a graph $G$ is a collection

$\mathcal{F}$ of subgraphs of $G$ such that every element of

$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$

is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote

the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph

obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$

on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is

uniquely assigned to $e$. This dissertation proves for even

$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$

on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree

$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +

1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect

$C^{3}_{t}$-tiling. The result is tight, generalizing previous

results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,

let the minimum color degree $\delta^c(G)$ be the minimum number of

distinctly colored edges incident to a vertex. Call $G$ rainbow if

every edge has a unique color. For $\ell \geq 5$, this dissertation

proves that any sufficiently large edge colored graph $G$ on $n$

vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow

cycle on $\ell$ vertices. The result is tight for odd $\ell$ and

extends previous results for $\ell = 3$. In addition, for even

$\ell \geq 4$, this dissertation proves that any sufficiently large

edge colored graph $G$ on $n$ vertices with

$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where

$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$

vertices. The result is tight when $6 \nmid \ell$. As a related

result, this dissertation proves for all $\ell \geq 4$, that any

sufficiently large oriented graph $D$ on $n$ vertices with

$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on

$\ell$ vertices. This partially generalizes a result by Kelly,

K\uhn" and Osthus that uses minimum semidegree rather than minimum

out degree."

Contributors

Agent

Created

Date Created
  • 2019

155077-Thumbnail Image.png

TiCTak: target-specific centrality manipulation on large networks

Description

Measuring node centrality is a critical common denominator behind many important graph mining tasks. While the existing literature offers a wealth of different node centrality measures, it remains a daunting

Measuring node centrality is a critical common denominator behind many important graph mining tasks. While the existing literature offers a wealth of different node centrality measures, it remains a daunting task on how to intervene the node centrality in a desired way. In this thesis, we study the problem of minimizing the centrality of one or more target nodes by edge operation. The heart of the proposed method is an accurate and efficient algorithm to estimate the impact of edge deletion on the spectrum of the underlying network, based on the observation that the edge deletion is essentially a local, sparse perturbation to the original network. Extensive experiments are conducted on a diverse set of real networks to demonstrate the effectiveness, efficiency and scalability of our approach. In particular, it is average of 260.95%, in terms of minimizing eigen-centrality, better than the standard matrix-perturbation based algorithm, with lower time complexity.

Contributors

Agent

Created

Date Created
  • 2016

151429-Thumbnail Image.png

On-line coloring of partial orders, circular arc graphs, and trees

Description

A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and

A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.

Contributors

Agent

Created

Date Created
  • 2012

157470-Thumbnail Image.png

Applying a Novel Integrated Persistent Feature to Understand Topographical Network Connectivity in Older Adults with Autism Spectrum Disorder

Description

Autism spectrum disorder (ASD) is a developmental neuropsychiatric condition with early childhood onset, thus most research has focused on characterizing brain function in young individuals. Little is understood about brain

Autism spectrum disorder (ASD) is a developmental neuropsychiatric condition with early childhood onset, thus most research has focused on characterizing brain function in young individuals. Little is understood about brain function differences in middle age and older adults with ASD, despite evidence of persistent and worsening cognitive symptoms. Functional Magnetic Resonance Imaging (MRI) in younger persons with ASD demonstrate that large-scale brain networks containing the prefrontal cortex are affected. A novel, threshold-selection-free graph theory metric is proposed as a more robust and sensitive method for tracking brain aging in ASD and is compared against five well-accepted graph theoretical analysis methods in older men with ASD and matched neurotypical (NT) participants. Participants were 27 men with ASD (52 +/- 8.4 years) and 21 NT men (49.7 +/- 6.5 years). Resting-state functional MRI (rs-fMRI) scans were collected for six minutes (repetition time=3s) with eyes closed. Data was preprocessed in SPM12, and Data Processing Assistant for Resting-State fMRI (DPARSF) was used to extract 116 regions-of-interest defined by the automated anatomical labeling (AAL) atlas. AAL regions were separated into six large-scale brain networks. This proposed metric is the slope of a monotonically decreasing convergence function (Integrated Persistent Feature, IPF; Slope of the IPF, SIP). Results were analyzed in SPSS using ANCOVA, with IQ as a covariate. A reduced SIP was in older men with ASD, compared to NT men, in the Default Mode Network [F(1,47)=6.48; p=0.02; 2=0.13] and Executive Network [F(1,47)=4.40; p=0.04; 2=0.09], a trend in the Fronto-Parietal Network [F(1,47)=3.36; p=0.07; 2=0.07]. There were no differences in the non-prefrontal networks (Sensory motor network, auditory network, and medial visual network). The only other graph theory metric to reach significance was network diameter in the Default Mode Network [F(1,47)=4.31; p=0.04; 2=0.09]; however, the effect size for the SIP was stronger. Modularity, Betti number, characteristic path length, and eigenvalue centrality were all non-significant. These results provide empirical evidence of decreased functional network integration in pre-frontal networks of older adults with ASD and propose a useful biomarker for tracking prognosis of aging adults with ASD to enable more informed treatment, support, and care methods for this growing population.

Contributors

Agent

Created

Date Created
  • 2019