VTechWorks staff will be away for the winter holidays starting Tuesday, December 24, 2024, through Wednesday, January 1, 2025, and will not be replying to requests during this time. Thank you for your patience, and happy holidays!

Browsing by Author "Kuhlman, Christopher James"

Now showing 1 - 6 of 6
  • Thumbnail Image
    An Algorithm for Influence Maximization and Target Set Selection for the Deterministic Linear Threshold Model
    Swaminathan, Anand (Virginia Tech, 2014-07-03)
    The problem of influence maximization has been studied extensively with applications that include viral marketing, recommendations, and feed ranking. The optimization problem, first formulated by Kempe, Kleinberg and Tardos, is known to be NP-hard. Thus, several heuristics have been proposed to solve this problem. This thesis studies the problem of influence maximization under the deterministic linear threshold model and presents a novel heuristic for finding influential nodes in a graph with the goal of maximizing contagion spread that emanates from these influential nodes. Inputs to our algorithm include edge weights and vertex thresholds. The threshold difference greedy algorithm presented in this thesis takes into account both the edge weights as well as vertex thresholds in computing influence of a node. The threshold difference greedy algorithm is evaluated on 14 real-world networks. Results demonstrate that the new algorithm performs consistently better than the seven other heuristics that we evaluated in terms of final spread size. The threshold difference greedy algorithm has tuneable parameters which can make the algorithm run faster. As a part of the approach, the algorithm also computes the infected nodes in the graph. This eliminates the need for running simulations to determine the spread size from the influential nodes. We also study the target set selection problem with our algorithm. In this problem, the final spread size is specified and a seed (or influential) set is computed that will generate the required spread size.
  • Thumbnail Image
    Contributions to Efficient Statistical Modeling of Complex Data with Temporal Structures
    Hu, Zhihao (Virginia Tech, 2022-03-03)
    This dissertation will focus on three research projects: Neighborhood vector auto regression in multivariate time series, uncertainty quantification for agent-based modeling networked anagrams, and a scalable algorithm for multi-class classification. The first project studies the modeling of multivariate time series, with the applications in the environmental sciences and other areas. In this work, a so-called neighborhood vector autoregression (NVAR) model is proposed to efficiently analyze large-dimensional multivariate time series. The time series are assumed to have underlying distances among them based on the inherent setting of the problem. When this distance matrix is available or can be obtained, the proposed NVAR method is demonstrated to provides a computationally efficient and theoretically sound estimation of model parameters. The performance of the proposed method is compared with other existing approaches in both simulation studies and a real application of stream nitrogen study. The second project focuses on the study of group anagram games. In a group anagram game, players are provided letters to form as many words as possible. In this work, the enhanced agent behavior models for networked group anagram games are built, exercised, and evaluated under an uncertainty quantification framework. Specifically, the game data for players is clustered based on their skill levels (forming words, requesting letters, and replying to requests), the multinomial logistic regressions for transition probabilities are performed, and the uncertainty is quantified within each cluster. The result of this process is a model where players are assigned different numbers of neighbors and different skill levels in the game. Simulations of ego agents with neighbors are conducted to demonstrate the efficacy of the proposed methods. The third project aims to develop efficient and scalable algorithms for multi-class classification, which achieve a balance between prediction accuracy and computing efficiency, especially in high dimensional settings. The traditional multinomial logistic regression becomes slow in high dimensional settings where the number of classes (M) and the number of features (p) is large. Our algorithms are computing efficiently and scalable to data with even higher dimensions. The simulation and case study results demonstrate that our algorithms have huge advantage over traditional multinomial logistic regressions, and maintains comparable prediction performance.
  • Thumbnail Image
    Generalizations of Threshold Graph Dynamical Systems
    Kuhlman, Christopher James (Virginia Tech, 2013-05-02)
    Dynamics of social processes in populations, such as the spread of emotions, influence, language, mass movements, and warfare (often referred to individually and collectively as contagions), are increasingly studied because of their social, political, and economic impacts. Discrete dynamical systems (discrete in time and discrete in agent states) are often used to quantify contagion propagation in populations that are cast as graphs, where vertices represent agents and edges represent agent interactions. We refer to such formulations as graph dynamical systems. For social applications, threshold models are used extensively for agent state transition rules (i.e., for vertex functions). In its simplest form, each agent can be in one of two states (state 0 (1) means that an agent does not (does) possess a contagion), and an agent contracts a contagion if at least a threshold number of its distance-1 neighbors already possess it. The transition to state 0 is not permitted. In this study, we extend threshold models in three ways. First, we allow transitions to states 0 and 1, and we study the long-term dynamics of these bithreshold systems, wherein there are two distinct thresholds for each vertex; one governing each of the transitions to states 0 and 1. Second, we extend the model from a binary vertex state set to an arbitrary number r of states, and allow transitions between every pair of states. Third, we analyze a recent hierarchical model from the literature where inputs to vertex functions take into account subgraphs induced on the distance-1 neighbors of a vertex. We state, prove, and analyze conditions characterizing long-term dynamics of all of these models.
  • Thumbnail Image
    On the Feasibility of MapReduce to Compute Phase Space Properties of Graphical Dynamical Systems: An Empirical Study
    Hamid, Tania (Virginia Tech, 2015-07-09)
    A graph dynamical system (GDS) is a theoretical construct that can be used to simulate and analyze the dynamics of a wide spectrum of real world processes which can be modeled as networked systems. One of our goals is to compute the phase space of a system, and for this, even 30-vertex graphs present a computational challenge. This is because the number of state transitions needed to compute the phase space is exponential in the number of graph vertices. These problems thus produce memory and execution speed challenges. To address this, we devise various MapReduce programming paradigms that can be used to characterize system state transitions, compute phase spaces, functional equivalence classes, dynamic equivalence classes and cycle equivalence classes of dynamical systems. We also evaluate these paradigms and analyze their suitability for modeling different GDSs.
  • Thumbnail Image
    Pipelines for Computational Social Science Experiments and Model Building
    Cedeno, Vanessa Ines (Virginia Tech, 2019-07-12)
    There has been significant growth in online social science experiments in order to understand behavior at-scale, with finer-grained data collection. Considerable work is required to perform data analytics for custom experiments. In this dissertation, we design and build composable and extensible automated software pipelines for evaluating social phenomena through iterative experiments and modeling. To reason about experiments and models, we design a formal data model. This combined approach of experiments and models has been done in some studies without automation, or purely conceptually. We are motivated by a particular social behavior, namely collective identity (CI). Group or CI is an individual's cognitive, moral, and emotional connection with a broader community, category, practice, or institution. Extensive experimental research shows that CI influences human decision-making. Because of this, there is interest in modeling situations that promote the creation of CI in order to learn more from the process and to predict human behavior in real life situations. One of our goals in this dissertation is to understand whether a cooperative anagram game can produce CI within a group. With all of the experimental work on anagram games, it is surprising that very little work has been done in modeling these games. Also, abduction is an inference approach that uses data and observations to identify plausibly (and preferably, best) explanations for phenomena. Abduction has broad application in robotics, genetics, automated systems, and image understanding, but have largely been devoid of human behavior. We use these pipelines to understand intra-group cooperation and its effect on fostering CI. We devise and execute an iterative abductive analysis process that is driven by the social sciences. In a group anagrams web-based networked game setting, we formalize an abductive loop, implement it computationally, and exercise it; we build and evaluate three agent-based models (ABMs) through a set of composable and extensible pipelines; we also analyze experimental data and develop mechanistic and data-driven models of human reasoning to predict detailed game player action. The agreement between model predictions and experimental data indicate that our models can explain behavior and provide novel experimental insights into CI.
  • Thumbnail Image
    Providing High Performance Computing based Models as a Service: Architecture and Services for Modeling Contagions on Large Networked Populations
    El Meligy Abdelhamid, Sherif Hanie (Virginia Tech, 2017-02-06)
    Network science emerged as an interdisciplinary field over the last 20 years, and played a central role to address fundamental problems in other fields, e.g., epidemiology, public health, and transportation, and is now part of most university curriculums. Network dynamics is a major area within network science where researchers study different forms of processes in networked populations, such as the spread of emotions, influence, opinions, flu, ebola, and mass movements. These processes often referred to individually and collectively as contagions. Contagions are increasingly studied because of their economic, social, and political impacts. Yet, resources for studying network dynamics are largely dispersed and stand-alone. Furthermore, many researchers interested in the study of networks are not computer scientists. As a result, they do not have easy access to computing and data resources. Even with the presence of software or tools, it is challenging to install, build, and maintain software. These challenges create a barrier for researchers and domain scientists. The goal of this work is the design and implementation of a research framework for modeling contagions on large networked populations. The framework consists of various systems and services that provide support for researchers and domain scientists at different stages of their research workflow.