Digital Commons Network^™

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Properties Of (Claw, 4k₁, Bridge)-Free Graphs, Taite Lagrange

Theses and Dissertations (Comprehensive)

Given a set H of graphs, a graph G is H-free if it does not contain any graph in H as an induced subgraph. The complexity of the colouring problem is known when H is a set of graphs on four vertices, with three exceptions. One of those exceptions is the case of {claw, 4K₁}-free graphs, for which our classes of {claw, 4K₁, bridge}-free and {claw, 4K₁, bridge,C₄-twin}-free graphs are subclasses.

The original goal of this work was to prove that {claw, 4K₁, …

Efficient And Scalable Triangle Centrality Algorithms In The Arkouda Framework, Joseph Thomas Patchett

Theses

Graph data structures provide a unique challenge for both analysis and algorithm development. These data structures are irregular in that memory accesses are not known a priori and accesses to these structures tend to lack locality.

Despite these challenges, graph data structures are a natural way to represent relationships between entities and to exhibit unique features about these relationships. The network created from these relationships can create unique local structures that can describe the behavior between members of these structures. Graphs can be analyzed in a number of different ways including at a high level in community detection and at …

Presto : Fast And Effective Group Closeness Maximization, Baibhav L. Rajbhandari

Legacy Theses & Dissertations (2009 - 2024)

Given a graph and an integer k, the goal of group closeness maximization is to find, among all possible sets of k vertices (called seed sets), a set that has the highest group closeness centrality. Existing techniques for this NP-hard problem strive to quickly find a seed set with a high, but not necessarily the highest centrality.

Optimization Opportunities In Human In The Loop Computational Paradigm, Dong Wei

Dissertations

An emerging trend is to leverage human capabilities in the computational loop at different capacities, ranging from tapping knowledge from a richly heterogeneous pool of knowledge resident in the general population to soliciting expert opinions. These practices are, in general, termed human-in-the-loop (HITL) computations.

A HITL process requires holistic treatment and optimization from multiple standpoints considering all stakeholders: a. applications, b. platforms, c. humans. In application-centric optimization, the factors of interest usually are latency (how long it takes for a set of tasks to finish), cost (the monetary or computational expenses incurred in the process), and quality of the completed …

Local-Global Results On Discrete Structures, Alexander Lewis Stevens

Electronic Theses and Dissertations

Local-global arguments, or those which glean global insights from local information, are central ideas in many areas of mathematics and computer science. For instance, in computer science a greedy algorithm makes locally optimal choices that are guaranteed to be consistent with a globally optimal solution. On the mathematical end, global information on Riemannian manifolds is often implied by (local) curvature lower bounds. Discrete notions of graph curvature have recently emerged, allowing ideas pioneered in Riemannian geometry to be extended to the discrete setting. Bakry- Émery curvature has been one such successful notion of curvature. In this thesis we use combinatorial …

Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer

Theses and Dissertations--Computer Science

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …

Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao

Dissertations and Theses

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.

In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …

Dijkstra’S Pathfinder, Taylor F. Malamut

Honors Theses

Dijkstra’s algorithm has been widely studied and applied since it was first published in 1959. This research shows that Dijkstra’s algorithm can be used to find the shortest path between two stations on the Washington D.C. Metro. After exploring different types of research and applying Dijkstra’s algorithm, it was found that the algorithm will always yield the shortest path, even if visually a shorter path was initially expected.

Evaluation Of Algorithms For Randomizing Key Item Locations In Game Worlds, Caleb Johnson

LSU Master's Theses

In the past few years, game randomizers have become increasingly popular. In general, a game randomizer takes some aspect of a game that is usually static and shuffles it somehow. In particular, in this paper we will discuss the type of randomizer that shuffles the locations of items in a game where certain key items are needed to traverse the game world and access some of these locations. Examples of these types of games include series such as The Legend of Zelda and Metroid.

In order to accomplish this shuffling in such a way that the player is able to …

Functional Object-Oriented Network: A Knowledge Representation For Service Robotics, David Andrés Paulius Ramos

USF Tampa Graduate Theses and Dissertations

In this dissertation, we discuss our work behind the development of the functional object-oriented network (abbreviated as FOON), a graphical knowledge representation for robotic manipulation and understanding of its own actions and (potentially) the intentions of humans in the household. Based on the theory of affordance, this representation captures manipulations and their effects on actions through the coupling of object and motion nodes as fundamental learning units known as functional units. The activities currently represented in FOON are cooking related, but this representation can be extended to other activities that involve manipulation of objects which result in observable changes of …

Courcelle's Theorem: Overview And Applications, Samuel Frederic Barr

Honors Papers

Courcelle's Theorem states that any graph property expressible in monadic second order logic can be decidedin O(f(k)n) for graphs of treewidth k. This paper gives a broad overview of how this theorem is proved and outlines tools available to help express graph properties in monadic second order logic.

Simulating Epidemics And Interventions On High Resolution Social Networks, Christopher E. Siu

Master's Theses

Mathematical models of disease spreading are a key factor of ensuring that we are prepared to deal with the next epidemic. They allow us to predict how an infection will spread throughout a population, thereby allowing us to make intelligent choices when attempting to contain the disease. Whether due to a lack of empirical data, a lack of computational power, a lack of biological understanding, or some combination thereof, traditional models must make sweeping assumptions about the behavior of a population during an epidemic.

In this thesis, we implement granular epidemic simulations using a rich social network constructed from real-world …

Stock Market Prediction Using Ensemble Of Graph Theory, Machine Learning And Deep Learning Models, Pratik Patil

Master's Projects

Efficient Market Hypothesis (EMH) is the cornerstone of the modern financial theory and it states that it is impossible to predict the price of any stock using any trend, fundamental or technical analysis. Stock trading is one of the most important activities in the world of finance. Stock price prediction has been an age-old problem and many researchers from academia and business have tried to solve it using many techniques ranging from basic statistics to machine learning using relevant information such as news sentiment and historical prices. Even though some studies claim to get prediction accuracy higher than a random …

Separability And Vertex Ordering Of Graphs, Elizabeth Gorbonos

Theses and Dissertations (Comprehensive)

Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph …

Optimization Methods For Learning Graph-Structured Sparse Models, Baojian Zhou

Legacy Theses & Dissertations (2009 - 2024)

Learning graph-structured sparse models has recently received significant attention thanks to their broad applicability to many important real-world problems. However, such models, of more effective and stronger interpretability compared with their counterparts, are difficult to learn due to optimization challenges. This thesis presents optimization algorithms for learning graph-structured sparse models under three different problem settings. Firstly, under the batch learning setting, we develop methods that can be applied to different objective functions that enjoy linear convergence guarantees up to constant errors. They can effectively optimize the statistical score functions in the task of subgraph detection; Secondly, under stochastic learning setting, …

Kings In The Direct Product Of Digraphs, Morgan Norge

Theses and Dissertations

A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.

Analysis Of Bulk Power System Resilience Using Vulnerability Graph, Md Ariful Haque

Computational Modeling & Simulation Engineering Theses & Dissertations

Critical infrastructure such as a Bulk Power System (BPS) should have some quantifiable measure of resiliency and definite rule-sets to achieve a certain resilience value. Industrial Control System (ICS) and Supervisory Control and Data Acquisition (SCADA) networks are integral parts of BPS. BPS or ICS are themselves not vulnerable because of their proprietary technology, but when the control network and the corporate network need to have communications for performance measurements and reporting, the ICS or BPS become vulnerable to cyber-attacks. Thus, a systematic way of quantifying resiliency and identifying crucial nodes in the network is critical for addressing the cyber …

An Efficient System For Subgraph Discovery, Aparna Joshi

Legacy Theses & Dissertations (2009 - 2024)

Subgraph discovery in a single data graph---finding subsets of vertices and edges satisfying a user-specified criteria---is an essential and general graph analytics operation with a wide spectrum of applications. Depending on the criteria, subgraphs of interest may correspond to cliques of friends in social networks, interconnected entities in RDF data, or frequent patterns in protein interaction networks to name a few. Existing systems usually examine a large number of subgraphs while employing many computers and often produce an enormous result set of subgraphs. How can we enable fast discovery of only the most relevant subgraphs while minimizing the computational requirements?

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 …

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 …

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 …

Automated Conjecturing Approach For Benzenoids, David Muncy

Theses and Dissertations

Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our …

Situational Assessment Using Graph Comparison, Pavan Kumar Pallapunidi

UNLV Theses, Dissertations, Professional Papers, and Capstones

In strategic operations, the assessment of any given situation is very important and may trigger the development of a mission plan. The mission plan consists of various actions that should be executed in order to successfully mitigate the situation. For a new mission plan to be designed or implemented, the effect of the previous mission plan should be accessed. These mission plans use various sensors to collect the data which can be very large and aggregate them to obtain detailed information of the situation. In order to implement an effective mission plan the current situation has to be assessed effectively. …

The Apprentices' Tower Of Hanoi, Cory Bh Ball

Electronic Theses and Dissertations

The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.

Positive Influence Dominating Set Generation Via A New Greedy Algorithm, Matthew Rink

Computer Science Honors Papers

Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than either existing algorithm, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.

Towards An Integrated Model Of The Mental Lexicon, Natawut Monaikul

All Student Theses

Several models have been proposed attempting to describe the mental lexicon-the abstract organization of words in the human mind. Numerous studies have shown that by representing the mental lexicon as a network, where nodes represent words and edges connect similar words using a metric based on some word feature, a small-world structure is formed. This property, pervasive in many real-world networks, implies processing efficiency and resiliency to node deletion within the system, explaining the need for such a robust network as the mental lexicon. However, each model considered a single word feature at a time, such as semantic or phonological …

Social Fingerprinting: Identifying Users Of Social Networks By Their Data Footprint, Denise Koessler Gosnell

Doctoral Dissertations

This research defines, models, and quantifies a new metric for social networks: the social fingerprint. Just as one's fingers leave behind a unique trace in a print, this dissertation introduces and demonstrates that the manner in which people interact with other accounts on social networks creates a unique data trail. Accurate identification of a user's social fingerprint can address the growing demand for improved techniques in unique user account analysis, computational forensics and social network analysis.

In this dissertation, we theorize, construct and test novel software and methodologies which quantify features of social network data. All approaches and methodologies are …

A Framework For Web Object Self-Preservation, Charles L. Cartledge

Computer Science Theses & Dissertations

We propose and develop a framework based on emergent behavior principles for the long-term preservation of digital data using the web infrastructure. We present the development of the framework called unsupervised small-world (USW) which is at the nexus of emergent behavior, graph theory, and digital preservation. The USW algorithm creates graph based structures on the Web used for preservation of web objects (WOs). Emergent behavior activities, based on Craig Reynolds’ “boids” concept, are used to preserve WOs without the need for a central archiving authority. Graph theory is extended by developing an algorithm that incrementally creates small-world graphs. Graph theory …

Construction Algorithms For Expander Graphs, Vlad S. Burca

Senior Theses and Projects

Graphs are mathematical objects that are comprised of nodes and edges that connect them. In computer science they are used to model concepts that exhibit network behaviors, such as social networks, communication paths or computer networks. In practice, it is desired that these graphs retain two main properties: sparseness and high connectivity. This is equivalent to having relatively short distances between two nodes but with an overall small number of edges. These graphs are called expander graphs and the main motivation behind studying them is the efficient network structure that they can produce due to their properties. We are specifically …