Showing 1–50 of 81 results for author: Young, J

The Language of Weather: Social Media Reactions to Weather Accounting for Climatic and Linguistic Baselines

Authors: James C. Young, Rudy Arthur, Hywel T. P. Williams

Abstract: This study explores how different weather conditions influence public sentiment on social media, focusing on Twitter data from the UK. By considering climate and linguistic baselines, we improve the accuracy of weather-related sentiment analysis. Our findings show that emotional responses to weather are complex, influenced by combinations of weather variables and regional language differences. The… ▽ More This study explores how different weather conditions influence public sentiment on social media, focusing on Twitter data from the UK. By considering climate and linguistic baselines, we improve the accuracy of weather-related sentiment analysis. Our findings show that emotional responses to weather are complex, influenced by combinations of weather variables and regional language differences. The results highlight the importance of context-sensitive methods for better understanding public mood in response to weather, which can enhance impact-based forecasting and risk communication in the context of climate change. △ Less

Submitted 10 July, 2024; originally announced July 2024.

Comments: 12 pages, 5 figures

On the maximal L1 influence of real-valued boolean functions

Authors: Andrew J. Young, Henry D. Pfister

Abstract: We show that any sequence of well-behaved (e.g. bounded and non-constant) real-valued functions of $n$ boolean variables $\{f_n\}$ admits a sequence of coordinates whose $L^1$ influence under the $p$-biased distribution, for any $p\in(0,1)$, is $Ω(\text{var}(f_n) \frac{\ln n}{n})$. We show that any sequence of well-behaved (e.g. bounded and non-constant) real-valued functions of $n$ boolean variables $\{f_n\}$ admits a sequence of coordinates whose $L^1$ influence under the $p$-biased distribution, for any $p\in(0,1)$, is $Ω(\text{var}(f_n) \frac{\ln n}{n})$. △ Less

Submitted 15 June, 2024; originally announced June 2024.

Symmetry-driven embedding of networks in hyperbolic space

Authors: Simon Lizotte, Jean-Gabriel Young, Antoine Allard

Abstract: Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic… ▽ More Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model. We show that combining random walk and random cluster transformations significantly improves mixing compared to the commonly used and state-of-the-art dynamic Hamiltonian Monte Carlo algorithm. Using this algorithm, we also provide evidence that the posterior distribution cannot be approximated by a multivariate normal distribution, thereby justifying the use of MCMC to quantify the uncertainty of the inferred parameters. △ Less

Submitted 15 June, 2024; originally announced June 2024.

The Role of AI in Peer Support for Young People: A Study of Preferences for Human- and AI-Generated Responses

Authors: Jordyn Young, Laala M Jawara, Diep N Nguyen, Brian Daly, Jina Huh-Yoo, Afsaneh Razi

Abstract: Generative Artificial Intelligence (AI) is integrated into everyday technology, including news, education, and social media. AI has further pervaded private conversations as conversational partners, auto-completion, and response suggestions. As social media becomes young people's main method of peer support exchange, we need to understand when and how AI can facilitate and assist in such exchanges… ▽ More Generative Artificial Intelligence (AI) is integrated into everyday technology, including news, education, and social media. AI has further pervaded private conversations as conversational partners, auto-completion, and response suggestions. As social media becomes young people's main method of peer support exchange, we need to understand when and how AI can facilitate and assist in such exchanges in a beneficial, safe, and socially appropriate way. We asked 622 young people to complete an online survey and evaluate blinded human- and AI-generated responses to help-seeking messages. We found that participants preferred the AI-generated response to situations about relationships, self-expression, and physical health. However, when addressing a sensitive topic, like suicidal thoughts, young people preferred the human response. We also discuss the role of training in online peer support exchange and its implications for supporting young people's well-being. Disclaimer: This paper includes sensitive topics, including suicide ideation. Reader discretion is advised. △ Less

Submitted 4 May, 2024; originally announced May 2024.

Journal ref: Proceedings of the CHI Conference on Human Factors in Computing Systems 2024

Complex contagions can outperform simple contagions for network reconstruction with dense networks or saturated dynamics

Authors: Nicholas W. Landry, William Thompson, Laurent Hébert-Dufresne, Jean-Gabriel Young

Abstract: Network scientists often use complex dynamic processes to describe network contagions, but tools for fitting contagion models typically assume simple dynamics. Here, we address this gap by developing a nonparametric method to reconstruct a network and dynamics from a series of node states, using a model that breaks the dichotomy between simple pairwise and complex neighborhood-based contagions. We… ▽ More Network scientists often use complex dynamic processes to describe network contagions, but tools for fitting contagion models typically assume simple dynamics. Here, we address this gap by developing a nonparametric method to reconstruct a network and dynamics from a series of node states, using a model that breaks the dichotomy between simple pairwise and complex neighborhood-based contagions. We then show that a network is more easily reconstructed when observed through the lens of complex contagions if it is dense or the dynamic saturates, and that simple contagions are better otherwise. △ Less

Submitted 30 April, 2024; originally announced May 2024.

Comments: 8 pages, 5 figures

Qwerty: A Basis-Oriented Quantum Programming Language

Authors: Austin J. Adams, Sharjeel Khan, Jeffrey S. Young, Thomas M. Conte

Abstract: Quantum computers have evolved from the theoretical realm into a race to large-scale implementations. This is due to the promise of revolutionary speedups, where achieving such speedup requires designing an algorithm that harnesses the structure of a problem using quantum mechanics. Yet many quantum programming languages today require programmers to reason at a low level of quantum gate circuitry.… ▽ More Quantum computers have evolved from the theoretical realm into a race to large-scale implementations. This is due to the promise of revolutionary speedups, where achieving such speedup requires designing an algorithm that harnesses the structure of a problem using quantum mechanics. Yet many quantum programming languages today require programmers to reason at a low level of quantum gate circuitry. This presents a significant barrier to entry for programmers who have not yet built up an intuition about quantum gate semantics, and it can prove to be tedious even for those who have. In this paper, we present Qwerty, a new quantum programming language that allows programmers to manipulate qubits more expressively than gates, relegating the tedious task of gate selection to the compiler. Due to its novel basis type and easy interoperability with Python, Qwerty is a powerful framework for high-level quantum-classical computation. △ Less

Submitted 18 April, 2024; originally announced April 2024.

Comments: 30 pages, 27 figures

HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network

Authors: Tatyana Benko, Martin Buck, Ilya Amburg, Stephen J. Young, Sinan G. Aksoy

Abstract: In data science, hypergraphs are natural models for data exhibiting multi-way relations, whereas graphs only capture pairwise. Nonetheless, many proposed hypergraph neural networks effectively reduce hypergraphs to undirected graphs via symmetrized matrix representations, potentially losing important information. We propose an alternative approach to hypergraph neural networks in which the hypergr… ▽ More In data science, hypergraphs are natural models for data exhibiting multi-way relations, whereas graphs only capture pairwise. Nonetheless, many proposed hypergraph neural networks effectively reduce hypergraphs to undirected graphs via symmetrized matrix representations, potentially losing important information. We propose an alternative approach to hypergraph neural networks in which the hypergraph is represented as a non-reversible Markov chain. We use this Markov chain to construct a complex Hermitian Laplacian matrix - the magnetic Laplacian - which serves as the input to our proposed hypergraph neural network. We study HyperMagNet for the task of node classification, and demonstrate its effectiveness over graph-reduction based hypergraph neural networks. △ Less

Submitted 14 February, 2024; originally announced February 2024.

Comments: 9 pages, 1 figure

CERM: Context-aware Literature-based Discovery via Sentiment Analysis

Authors: Julio Christian Young, Uchenna Akujuobi

Abstract: Driven by the abundance of biomedical publications, we introduce a sentiment analysis task to understand food-health relationship. Prior attempts to incorporate health into recipe recommendation and analysis systems have primarily focused on ingredient nutritional components or utilized basic computational models trained on curated labeled data. Enhanced models that capture the inherent relationsh… ▽ More Driven by the abundance of biomedical publications, we introduce a sentiment analysis task to understand food-health relationship. Prior attempts to incorporate health into recipe recommendation and analysis systems have primarily focused on ingredient nutritional components or utilized basic computational models trained on curated labeled data. Enhanced models that capture the inherent relationship between food ingredients and biomedical concepts can be more beneficial for food-related research, given the wealth of information in biomedical texts. Considering the costly data labeling process, these models should effectively utilize both labeled and unlabeled data. This paper introduces Entity Relationship Sentiment Analysis (ERSA), a new task that captures the sentiment of a text based on an entity pair. ERSA extends the widely studied Aspect Based Sentiment Analysis (ABSA) task. Specifically, our study concentrates on the ERSA task applied to biomedical texts, focusing on (entity-entity) pairs of biomedical and food concepts. ERSA poses a significant challenge compared to traditional sentiment analysis tasks, as sentence sentiment may not align with entity relationship sentiment. Additionally, we propose CERM, a semi-supervised architecture that combines different word embeddings to enhance the encoding of the ERSA task. Experimental results showcase the model's efficiency across diverse learning scenarios. △ Less

Submitted 27 January, 2024; originally announced February 2024.

Evaluation of General Large Language Models in Contextually Assessing Semantic Concepts Extracted from Adult Critical Care Electronic Health Record Notes

Authors: Darren Liu, Cheng Ding, Delgersuren Bold, Monique Bouvier, Jiaying Lu, Benjamin Shickel, Craig S. Jabaley, Wenhui Zhang, Soojin Park, Michael J. Young, Mark S. Wainwright, Gilles Clermont, Parisa Rashidi, Eric S. Rosenthal, Laurie Dimisko, Ran Xiao, Joo Heung Yoon, Carl Yang, Xiao Hu

Abstract: The field of healthcare has increasingly turned its focus towards Large Language Models (LLMs) due to their remarkable performance. However, their performance in actual clinical applications has been underexplored. Traditional evaluations based on question-answering tasks don't fully capture the nuanced contexts. This gap highlights the need for more in-depth and practical assessments of LLMs in r… ▽ More The field of healthcare has increasingly turned its focus towards Large Language Models (LLMs) due to their remarkable performance. However, their performance in actual clinical applications has been underexplored. Traditional evaluations based on question-answering tasks don't fully capture the nuanced contexts. This gap highlights the need for more in-depth and practical assessments of LLMs in real-world healthcare settings. Objective: We sought to evaluate the performance of LLMs in the complex clinical context of adult critical care medicine using systematic and comprehensible analytic methods, including clinician annotation and adjudication. Methods: We investigated the performance of three general LLMs in understanding and processing real-world clinical notes. Concepts from 150 clinical notes were identified by MetaMap and then labeled by 9 clinicians. Each LLM's proficiency was evaluated by identifying the temporality and negation of these concepts using different prompts for an in-depth analysis. Results: GPT-4 showed overall superior performance compared to other LLMs. In contrast, both GPT-3.5 and text-davinci-003 exhibit enhanced performance when the appropriate prompting strategies are employed. The GPT family models have demonstrated considerable efficiency, evidenced by their cost-effectiveness and time-saving capabilities. Conclusion: A comprehensive qualitative performance evaluation framework for LLMs is developed and operationalized. This framework goes beyond singular performance aspects. With expert annotations, this methodology not only validates LLMs' capabilities in processing complex medical data but also establishes a benchmark for future LLM evaluations across specialized domains. △ Less

Submitted 24 January, 2024; originally announced January 2024.

Hypergraph Topological Features for Autoencoder-Based Intrusion Detection for Cybersecurity Data

Authors: Bill Kay, Sinan G. Aksoy, Molly Baird, Daniel M. Best, Helen Jenne, Cliff Joslyn, Christopher Potvin, Gregory Henselman-Petrusek, Garret Seppala, Stephen J. Young, Emilie Purvine

Abstract: In this position paper, we argue that when hypergraphs are used to capture multi-way local relations of data, their resulting topological features describe global behaviour. Consequently, these features capture complex correlations that can then serve as high fidelity inputs to autoencoder-driven anomaly detection pipelines. We propose two such potential pipelines for cybersecurity data, one that… ▽ More In this position paper, we argue that when hypergraphs are used to capture multi-way local relations of data, their resulting topological features describe global behaviour. Consequently, these features capture complex correlations that can then serve as high fidelity inputs to autoencoder-driven anomaly detection pipelines. We propose two such potential pipelines for cybersecurity data, one that uses an autoencoder directly to determine network intrusions, and one that de-noises input data for a persistent homology system, PHANTOM. We provide heuristic justification for the use of the methods described therein for an intrusion detection pipeline for cyber data. We conclude by showing a small example over synthetic cyber attack data. △ Less

Submitted 9 November, 2023; originally announced December 2023.

MSC Class: 55N31

Stepping out of Flatland: Discovering Behavior Patterns as Topological Structures in Cyber Hypergraphs

Authors: Helen Jenne, Sinan G. Aksoy, Daniel Best, Alyson Bittner, Gregory Henselman-Petrusek, Cliff Joslyn, Bill Kay, Audun Myers, Garret Seppala, Jackson Warley, Stephen J. Young, Emilie Purvine

Abstract: Data breaches and ransomware attacks occur so often that they have become part of our daily news cycle. This is due to a myriad of factors, including the increasing number of internet-of-things devices, shift to remote work during the pandemic, and advancement in adversarial techniques, which all contribute to the increase in both the complexity of data captured and the challenge of protecting our… ▽ More Data breaches and ransomware attacks occur so often that they have become part of our daily news cycle. This is due to a myriad of factors, including the increasing number of internet-of-things devices, shift to remote work during the pandemic, and advancement in adversarial techniques, which all contribute to the increase in both the complexity of data captured and the challenge of protecting our networks. At the same time, cyber research has made strides, leveraging advances in machine learning and natural language processing to focus on identifying sophisticated attacks that are known to evade conventional measures. While successful, the shortcomings of these methods, particularly the lack of interpretability, are inherent and difficult to overcome. Consequently, there is an ever-increasing need to develop new tools for analyzing cyber data to enable more effective attack detection. In this paper, we present a novel framework based in the theory of hypergraphs and topology to understand data from cyber networks through topological signatures, which are both flexible and can be traced back to the log data. While our approach's mathematical grounding requires some technical development, this pays off in interpretability, which we will demonstrate with concrete examples in a large-scale cyber network dataset. These examples are an introduction to the broader possibilities that lie ahead; our goal is to demonstrate the value of applying methods from the burgeoning fields of hypernetwork science and applied topology to understand relationships among behaviors in cyber data. △ Less

Submitted 7 November, 2023; originally announced November 2023.

Comments: 18 pages, 11 figures. This paper is written for a general audience

MSC Class: 55N31

Fast Parallel Tensor Times Same Vector for Hypergraphs

Authors: Shruti Shivakumar, Ilya Amburg, Sinan G. Aksoy, Jiajia Li, Stephen J. Young, Srinivas Aluru

Abstract: Hypergraphs are a popular paradigm to represent complex real-world networks exhibiting multi-way relationships of varying sizes. Mining centrality in hypergraphs via symmetric adjacency tensors has only recently become computationally feasible for large and complex datasets. To enable scalable computation of these and related hypergraph analytics, here we focus on the Sparse Symmetric Tensor Times… ▽ More Hypergraphs are a popular paradigm to represent complex real-world networks exhibiting multi-way relationships of varying sizes. Mining centrality in hypergraphs via symmetric adjacency tensors has only recently become computationally feasible for large and complex datasets. To enable scalable computation of these and related hypergraph analytics, here we focus on the Sparse Symmetric Tensor Times Same Vector (S$^3$TTVc) operation. We introduce the Compound Compressed Sparse Symmetric (CCSS) format, an extension of the compact CSS format for hypergraphs of varying hyperedge sizes and present a shared-memory parallel algorithm to compute S$^3$TTVc. We experimentally show S$^3$TTVc computation using the CCSS format achieves better performance than the naive baseline, and is subsequently more performant for hypergraph $H$-eigenvector centrality. △ Less

Submitted 14 November, 2023; originally announced November 2023.

Malicious Cyber Activity Detection Using Zigzag Persistence

Authors: Audun Myers, Alyson Bittner, Sinan Aksoy, Daniel M. Best, Gregory Henselman-Petrusek, Helen Jenne, Cliff Joslyn, Bill Kay, Garret Seppala, Stephen J. Young, Emilie Purvine

Abstract: In this study we synthesize zigzag persistence from topological data analysis with autoencoder-based approaches to detect malicious cyber activity and derive analytic insights. Cybersecurity aims to safeguard computers, networks, and servers from various forms of malicious attacks, including network damage, data theft, and activity monitoring. Here we focus on the detection of malicious activity u… ▽ More In this study we synthesize zigzag persistence from topological data analysis with autoencoder-based approaches to detect malicious cyber activity and derive analytic insights. Cybersecurity aims to safeguard computers, networks, and servers from various forms of malicious attacks, including network damage, data theft, and activity monitoring. Here we focus on the detection of malicious activity using log data. To do this we consider the dynamics of the data by exploring the changing topology of a hypergraph representation gaining insights into the underlying activity. Hypergraphs provide a natural representation of cyber log data by capturing complex interactions between processes. To study the changing topology we use zigzag persistence which captures how topological features persist at multiple dimensions over time. We observe that the resulting barcodes represent malicious activity differently than benign activity. To automate this detection we implement an autoencoder trained on a vectorization of the resulting zigzag persistence barcodes. Our experimental results demonstrate the effectiveness of the autoencoder in detecting malicious activity in comparison to standard summary statistics. Overall, this study highlights the potential of zigzag persistence and its combination with temporal hypergraphs for analyzing cybersecurity log data and detecting malicious behavior. △ Less

Submitted 14 September, 2023; originally announced September 2023.

Phase-Specific Augmented Reality Guidance for Microscopic Cataract Surgery Using Long-Short Spatiotemporal Aggregation Transformer

Authors: Puxun Tu, Hongfei Ye, Haochen Shi, Jeff Young, Meng Xie, Peiquan Zhao, Ce Zheng, Xiaoyi Jiang, Xiaojun Chen

Abstract: Phacoemulsification cataract surgery (PCS) is a routine procedure conducted using a surgical microscope, heavily reliant on the skill of the ophthalmologist. While existing PCS guidance systems extract valuable information from surgical microscopic videos to enhance intraoperative proficiency, they suffer from non-phasespecific guidance, leading to redundant visual information. In this study, our… ▽ More Phacoemulsification cataract surgery (PCS) is a routine procedure conducted using a surgical microscope, heavily reliant on the skill of the ophthalmologist. While existing PCS guidance systems extract valuable information from surgical microscopic videos to enhance intraoperative proficiency, they suffer from non-phasespecific guidance, leading to redundant visual information. In this study, our major contribution is the development of a novel phase-specific augmented reality (AR) guidance system, which offers tailored AR information corresponding to the recognized surgical phase. Leveraging the inherent quasi-standardized nature of PCS procedures, we propose a two-stage surgical microscopic video recognition network. In the first stage, we implement a multi-task learning structure to segment the surgical limbus region and extract limbus region-focused spatial feature for each frame. In the second stage, we propose the long-short spatiotemporal aggregation transformer (LS-SAT) network to model local fine-grained and global temporal relationships, and combine the extracted spatial features to recognize the current surgical phase. Additionally, we collaborate closely with ophthalmologists to design AR visual cues by utilizing techniques such as limbus ellipse fitting and regional restricted normal cross-correlation rotation computation. We evaluated the network on publicly available and in-house datasets, with comparison results demonstrating its superior performance compared to related works. Ablation results further validated the effectiveness of the limbus region-focused spatial feature extractor and the combination of temporal features. Furthermore, the developed system was evaluated in a clinical setup, with results indicating remarkable accuracy and real-time performance. underscoring its potential for clinical applications. △ Less

Submitted 31 October, 2023; v1 submitted 10 September, 2023; originally announced September 2023.

Confidence-Building Measures for Artificial Intelligence: Workshop Proceedings

Authors: Sarah Shoker, Andrew Reddie, Sarah Barrington, Ruby Booth, Miles Brundage, Husanjot Chahal, Michael Depp, Bill Drexel, Ritwik Gupta, Marina Favaro, Jake Hecla, Alan Hickey, Margarita Konaev, Kirthi Kumar, Nathan Lambert, Andrew Lohn, Cullen O'Keefe, Nazneen Rajani, Michael Sellitto, Robert Trager, Leah Walker, Alexa Wehsener, Jessica Young

Abstract: Foundation models could eventually introduce several pathways for undermining state security: accidents, inadvertent escalation, unintentional conflict, the proliferation of weapons, and the interference with human diplomacy are just a few on a long list. The Confidence-Building Measures for Artificial Intelligence workshop hosted by the Geopolitics Team at OpenAI and the Berkeley Risk and Securit… ▽ More Foundation models could eventually introduce several pathways for undermining state security: accidents, inadvertent escalation, unintentional conflict, the proliferation of weapons, and the interference with human diplomacy are just a few on a long list. The Confidence-Building Measures for Artificial Intelligence workshop hosted by the Geopolitics Team at OpenAI and the Berkeley Risk and Security Lab at the University of California brought together a multistakeholder group to think through the tools and strategies to mitigate the potential risks introduced by foundation models to international security. Originating in the Cold War, confidence-building measures (CBMs) are actions that reduce hostility, prevent conflict escalation, and improve trust between parties. The flexibility of CBMs make them a key instrument for navigating the rapid changes in the foundation model landscape. Participants identified the following CBMs that directly apply to foundation models and which are further explained in this conference proceedings: 1. crisis hotlines 2. incident sharing 3. model, transparency, and system cards 4. content provenance and watermarks 5. collaborative red teaming and table-top exercises and 6. dataset and evaluation sharing. Because most foundation model developers are non-government entities, many CBMs will need to involve a wider stakeholder community. These measures can be implemented either by AI labs or by relevant government actors. △ Less

Submitted 3 August, 2023; v1 submitted 1 August, 2023; originally announced August 2023.

Reinforcement Learning for Photonic Component Design

Authors: Donald Witt, Jeff Young, Lukas Chrostowski

Abstract: We present a new fab-in-the-loop reinforcement learning algorithm for the design of nano-photonic components that accounts for the imperfections present in nanofabrication processes. As a demonstration of the potential of this technique, we apply it to the design of photonic crystal grating couplers fabricated on an air clad 220 nm silicon on insulator single etch platform. This fab-in-the-loop al… ▽ More We present a new fab-in-the-loop reinforcement learning algorithm for the design of nano-photonic components that accounts for the imperfections present in nanofabrication processes. As a demonstration of the potential of this technique, we apply it to the design of photonic crystal grating couplers fabricated on an air clad 220 nm silicon on insulator single etch platform. This fab-in-the-loop algorithm improves the insertion loss from 8.8 to 3.24 dB. The widest bandwidth designs produced using our fab-in-the-loop algorithm can cover a 150 nm bandwidth with less than 10.2 dB of loss at their lowest point. △ Less

Submitted 8 January, 2024; v1 submitted 14 July, 2023; originally announced July 2023.

Comments: Published version: 9 pages, 12 figures

Journal ref: APL Photonics 8, 106101 (2023)

CIDER: Context sensitive sentiment analysis for short-form text

Authors: James C. Young, Rudy Arthur, Hywel T. P. Williams

Abstract: Researchers commonly perform sentiment analysis on large collections of short texts like tweets, Reddit posts or newspaper headlines that are all focused on a specific topic, theme or event. Usually, general-purpose sentiment analysis methods are used. These perform well on average but miss the variation in meaning that happens across different contexts, for example, the word "active" has a very d… ▽ More Researchers commonly perform sentiment analysis on large collections of short texts like tweets, Reddit posts or newspaper headlines that are all focused on a specific topic, theme or event. Usually, general-purpose sentiment analysis methods are used. These perform well on average but miss the variation in meaning that happens across different contexts, for example, the word "active" has a very different intention and valence in the phrase "active lifestyle" versus "active volcano". This work presents a new approach, CIDER (Context Informed Dictionary and sEmantic Reasoner), which performs context-sensitive linguistic analysis, where the valence of sentiment-laden terms is inferred from the whole corpus before being used to score the individual texts. In this paper, we detail the CIDER algorithm and demonstrate that it outperforms state-of-the-art generalist unsupervised sentiment analysis techniques on a large collection of tweets about the weather. CIDER is also applicable to alternative (non-sentiment) linguistic scales. A case study on gender in the UK is presented, with the identification of highly gendered and sentiment-laden days. We have made our implementation of CIDER available as a Python package: https://pypi.org/project/ciderpolarity/. △ Less

Submitted 10 July, 2024; v1 submitted 15 July, 2023; originally announced July 2023.

Comments: 20 pages, 6 figures, 3 tables

Scalable tensor methods for nonuniform hypergraphs

Authors: Sinan G. Aksoy, Ilya Amburg, Stephen J. Young

Abstract: While multilinear algebra appears natural for studying the multiway interactions modeled by hypergraphs, tensor methods for general hypergraphs have been stymied by theoretical and practical barriers. A recently proposed adjacency tensor is applicable to nonuniform hypergraphs, but is prohibitively costly to form and analyze in practice. We develop tensor times same vector (TTSV) algorithms for th… ▽ More While multilinear algebra appears natural for studying the multiway interactions modeled by hypergraphs, tensor methods for general hypergraphs have been stymied by theoretical and practical barriers. A recently proposed adjacency tensor is applicable to nonuniform hypergraphs, but is prohibitively costly to form and analyze in practice. We develop tensor times same vector (TTSV) algorithms for this tensor which improve complexity from $O(n^r)$ to a low-degree polynomial in $r$, where $n$ is the number of vertices and $r$ is the maximum hyperedge size. Our algorithms are implicit, avoiding formation of the order $r$ adjacency tensor. We demonstrate the flexibility and utility of our approach in practice by developing tensor-based hypergraph centrality and clustering algorithms. We also show these tensor measures offer complementary information to analogous graph-reduction approaches on data, and are also able to detect higher-order structure that many existing matrix-based approaches provably cannot. △ Less

Submitted 3 April, 2024; v1 submitted 30 June, 2023; originally announced June 2023.

MSC Class: 05C65; 15A69; 05C50; 05C85

Seven open problems in applied combinatorics

Authors: Sinan G. Aksoy, Ryan Bennink, Yuzhou Chen, José Frías, Yulia R. Gel, Bill Kay, Uwe Naumann, Carlos Ortiz Marrero, Anthony V. Petyuk, Sandip Roy, Ignacio Segovia-Dominguez, Nate Veldt, Stephen J. Young

Abstract: We present and discuss seven different open problems in applied combinatorics. The application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems. We present and discuss seven different open problems in applied combinatorics. The application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems. △ Less

Submitted 20 March, 2023; originally announced March 2023.

Comments: 43 pages, 5 figures

MSC Class: 05C90; 65Y04; 65D25; 05C65; 81P68; 62R40; 55N31; 65F10

SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation

Authors: Yuxiang Peng, Jacob Young, Pengyu Liu, Xiaodi Wu

Abstract: Quantum Hamiltonian simulation, which simulates the evolution of quantum systems and probes quantum phenomena, is one of the most promising applications of quantum computing. Recent experimental results suggest that Hamiltonian-oriented analog quantum simulation would be advantageous over circuit-oriented digital quantum simulation in the Noisy Intermediate-Scale Quantum (NISQ) machine era. Howeve… ▽ More Quantum Hamiltonian simulation, which simulates the evolution of quantum systems and probes quantum phenomena, is one of the most promising applications of quantum computing. Recent experimental results suggest that Hamiltonian-oriented analog quantum simulation would be advantageous over circuit-oriented digital quantum simulation in the Noisy Intermediate-Scale Quantum (NISQ) machine era. However, programming analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software. In this paper, we design and implement SimuQ, the first framework for quantum Hamiltonian simulation that supports Hamiltonian programming and pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users specify the target quantum system with Hamiltonian Modeling Language, and the Hamiltonian-level programmability of analog quantum simulators is specified through a new abstraction called the abstract analog instruction set (AAIS) and programmed in AAIS Specification Language by hardware providers. Through a solver-based compilation, SimuQ generates executable pulse schedules for real devices to simulate the evolution of desired quantum systems, which is demonstrated on superconducting (IBM), neutral-atom (QuEra), and trapped-ion (IonQ) quantum devices. Moreover, we demonstrate the advantages of exposing the Hamiltonian-level programmability of devices with native operations or interaction-based gates and establish a small benchmark of quantum simulation to evaluate SimuQ's compiler with the above analog quantum simulators. △ Less

Submitted 18 November, 2023; v1 submitted 5 March, 2023; originally announced March 2023.

Comments: 34 pages, 15 figures, 3 tables. Appears in POPL 2024. The code is available at https://github.com/PicksPeng/SimuQ. A website is available at https://pickspeng.github.io/SimuQ/

Enabling Multi-threading in Heterogeneous Quantum-Classical Programming Models

Authors: Akihiro Hayashi, Austin Adams, Jeffrey Young, Alexander McCaskey, Eugene Dumitrescu, Vivek Sarkar, Thomas M. Conte

Abstract: In this paper, we address some of the key limitations to realizing a generic heterogeneous parallel programming model for quantum-classical heterogeneous platforms. We discuss our experience in enabling user-level multi-threading in QCOR as well as challenges that need to be addressed for programming future quantum-classical systems. Specifically, we discuss our design and implementation of introd… ▽ More In this paper, we address some of the key limitations to realizing a generic heterogeneous parallel programming model for quantum-classical heterogeneous platforms. We discuss our experience in enabling user-level multi-threading in QCOR as well as challenges that need to be addressed for programming future quantum-classical systems. Specifically, we discuss our design and implementation of introducing C++-based parallel constructs to enable 1) parallel execution of a quantum kernel with std::thread and 2) asynchronous execution with std::async. To do so, we provide a detailed overview of the current implementation of the QCOR programming model and runtime, and discuss how we add 1) thread-safety to some of its user-facing API routines, and 2) increase parallelism in QCOR by removing data races that inhibit multi-threading so as to better utilize available computing resources. We also present preliminary performance results with the Quantum++ back end on a single-node Ryzen9 3900X machine that has 12 physical cores (24 hardware threads) with 128GB of RAM. The results show that running two Bell kernels with 12 threads per kernel in parallel outperforms running the kernels one after the other each with 24 threads (1.63x improvement). In addition, we observe the same trend when running two Shor's algorthm kernels in parallel (1.22x faster than executing the kernels one after the other). Furthermore, the parallel version is better in terms of strong scalability. We believe that our design, implementation, and results will open up an opportunity not only for 1) enabling quicker prototyping of parallel/asynchrony-aware quantum-classical algorithms on quantum circuit simulators in the short-term, but also for 2) realizing a generic heterogeneous parallel programming model for quantum-classical heterogeneous platforms in the long-term. △ Less

Submitted 15 March, 2023; v1 submitted 27 January, 2023; originally announced January 2023.

Exact and rapid linear clustering of networks with dynamic programming

Authors: Alice Patania, Antoine Allard, Jean-Gabriel Young

Abstract: We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns prov… ▽ More We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, for example prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions to this problem. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks and show that it outperforms existing heuristics by a significant margin, with a similar execution time. △ Less

Submitted 8 December, 2023; v1 submitted 24 January, 2023; originally announced January 2023.

Comments: 14 pages, 8 figures

Compressing network populations with modal networks reveals structural diversity

Authors: Alec Kirkley, Alexis Rojas, Martin Rosvall, Jean-Gabriel Young

Abstract: Analyzing relational data consisting of multiple samples or layers involves critical challenges: How many networks are required to capture the variety of structures in the data? And what are the structures of these representative networks? We describe efficient nonparametric methods derived from the minimum description length principle to construct the network representations automatically. The me… ▽ More Analyzing relational data consisting of multiple samples or layers involves critical challenges: How many networks are required to capture the variety of structures in the data? And what are the structures of these representative networks? We describe efficient nonparametric methods derived from the minimum description length principle to construct the network representations automatically. The methods input a population of networks or a multilayer network measured on a fixed set of nodes and output a small set of representative networks together with an assignment of each network sample or layer to one of the representative networks. We identify the representative networks and assign network samples to them with an efficient Monte Carlo scheme that minimizes our description length objective. For temporally ordered networks, we use a polynomial time dynamic programming approach that restricts the clusters of network layers to be temporally contiguous. These methods recover planted heterogeneity in synthetic network populations and identify essential structural heterogeneities in global trade and fossil record networks. Our methods are principled, scalable, parameter-free, and accommodate a wide range of data, providing a unified lens for exploratory analyses and preprocessing large sets of network samples. △ Less

Submitted 23 June, 2023; v1 submitted 28 September, 2022; originally announced September 2022.

Journal ref: Communications Physics 6, 148 (2023)

Application Experiences on a GPU-Accelerated Arm-based HPC Testbed

Authors: Wael Elwasif, William Godoy, Nick Hagerty, J. Austin Harris, Oscar Hernandez, Balint Joo, Paul Kent, Damien Lebrun-Grandie, Elijah Maccarthy, Veronica G. Melesse Vergara, Bronson Messer, Ross Miller, Sarp Opal, Sergei Bastrakov, Michael Bussmann, Alexander Debus, Klaus Steinger, Jan Stephan, Rene Widera, Spencer H. Bryngelson, Henry Le Berre, Anand Radhakrishnan, Jefferey Young, Sunita Chandrasekaran, Florina Ciorba , et al. (6 additional authors not shown)

Abstract: This paper assesses and reports the experience of ten teams working to port,validate, and benchmark several High Performance Computing applications on a novel GPU-accelerated Arm testbed system. The testbed consists of eight NVIDIA Arm HPC Developer Kit systems built by GIGABYTE, each one equipped with a server-class Arm CPU from Ampere Computing and A100 data center GPU from NVIDIA Corp. The syst… ▽ More This paper assesses and reports the experience of ten teams working to port,validate, and benchmark several High Performance Computing applications on a novel GPU-accelerated Arm testbed system. The testbed consists of eight NVIDIA Arm HPC Developer Kit systems built by GIGABYTE, each one equipped with a server-class Arm CPU from Ampere Computing and A100 data center GPU from NVIDIA Corp. The systems are connected together using Infiniband high-bandwidth low-latency interconnect. The selected applications and mini-apps are written using several programming languages and use multiple accelerator-based programming models for GPUs such as CUDA, OpenACC, and OpenMP offloading. Working on application porting requires a robust and easy-to-access programming environment, including a variety of compilers and optimized scientific libraries. The goal of this work is to evaluate platform readiness and assess the effort required from developers to deploy well-established scientific workloads on current and future generation Arm-based GPU-accelerated HPC systems. The reported case studies demonstrate that the current level of maturity and diversity of software and tools is already adequate for large-scale production deployments. △ Less

Submitted 19 December, 2022; v1 submitted 20 September, 2022; originally announced September 2022.

Hypergraph reconstruction from noisy pairwise observations

Authors: Simon Lizotte, Jean-Gabriel Young, Antoine Allard

Abstract: The network reconstruction task aims to estimate a complex system's structure from various data sources such as time series, snapshots, or interaction counts. Recent work has examined this problem in networks whose relationships involve precisely two entities-the pairwise case. Here we investigate the general problem of reconstructing a network in which higher-order interactions are also present.… ▽ More The network reconstruction task aims to estimate a complex system's structure from various data sources such as time series, snapshots, or interaction counts. Recent work has examined this problem in networks whose relationships involve precisely two entities-the pairwise case. Here we investigate the general problem of reconstructing a network in which higher-order interactions are also present. We study a minimal example of this problem, focusing on the case of hypergraphs with interactions between pairs and triplets of vertices, measured imperfectly and indirectly. We derive a Metropolis-Hastings-within-Gibbs algorithm for this model and use the algorithms to highlight the unique challenges that come with estimating higher-order models. We show that this approach tends to reconstruct empirical and synthetic networks more accurately than an equivalent graph model without higher-order interactions. △ Less

Submitted 12 August, 2022; originally announced August 2022.

Journal ref: Sci. Rep. 13, 21364 (2023)

Literature Review: Graph Kernels in Chemoinformatics

Authors: James Young

Abstract: The purpose of this review is to introduce the reader to graph kernels and the corresponding literature, with an emphasis on those with direct application to chemoinformatics. Graph kernels are functions that allow for the inference of properties of molecules and compounds, which can help with tasks such as finding suitable compounds in drug design. The use of kernel methods is but one particular… ▽ More The purpose of this review is to introduce the reader to graph kernels and the corresponding literature, with an emphasis on those with direct application to chemoinformatics. Graph kernels are functions that allow for the inference of properties of molecules and compounds, which can help with tasks such as finding suitable compounds in drug design. The use of kernel methods is but one particular way two quantify similarity between graphs. We restrict our discussion to this one method, although popular alternatives have emerged in recent years, most notably graph neural networks. △ Less

Submitted 26 August, 2022; v1 submitted 9 August, 2022; originally announced August 2022.

Dateformer: Time-modeling Transformer for Longer-term Series Forecasting

Authors: Julong Young, Junhui Chen, Feihu Huang, Jian Peng

Abstract: Transformers have demonstrated impressive strength in long-term series forecasting. Existing prediction research mostly focused on mapping past short sub-series (lookback window) to future series (forecast window). The longer training dataset time series will be discarded, once training is completed. Models can merely rely on lookback window information for inference, which impedes models from a… ▽ More Transformers have demonstrated impressive strength in long-term series forecasting. Existing prediction research mostly focused on mapping past short sub-series (lookback window) to future series (forecast window). The longer training dataset time series will be discarded, once training is completed. Models can merely rely on lookback window information for inference, which impedes models from analyzing time series from a global perspective. And these windows used by Transformers are quite narrow because they must model each time-step therein. Under this point-wise processing style, broadening windows will rapidly exhaust their model capacity. This, for fine-grained time series, leads to a bottleneck in information input and prediction output, which is mortal to long-term series forecasting. To overcome the barrier, we propose a brand-new methodology to utilize Transformer for time series forecasting. Specifically, we split time series into patches by day and reform point-wise to patch-wise processing, which considerably enhances the information input and output of Transformers. To further help models leverage the whole training set's global information during inference, we distill the information, store it in time representations, and replace series with time representations as the main modeling entities. Our designed time-modeling Transformer -- Dateformer yields state-of-the-art accuracy on 7 real-world datasets with a 33.6\% relative improvement and extends the maximum forecast range to half-year. △ Less

Submitted 21 February, 2023; v1 submitted 12 July, 2022; originally announced July 2022.

CuPBoP: CUDA for Parallelized and Broad-range Processors

Authors: Ruobing Han, Jun Chen, Bhanu Garg, Jeffrey Young, Jaewoong Sim, Hyesoon Kim

Abstract: CUDA is one of the most popular choices for GPU programming, but it can only be executed on NVIDIA GPUs. Executing CUDA on non-NVIDIA devices not only benefits the hardware community, but also allows data-parallel computation in heterogeneous systems. To make CUDA programs portable, some researchers have proposed using source-to-source translators to translate CUDA to portable programming language… ▽ More CUDA is one of the most popular choices for GPU programming, but it can only be executed on NVIDIA GPUs. Executing CUDA on non-NVIDIA devices not only benefits the hardware community, but also allows data-parallel computation in heterogeneous systems. To make CUDA programs portable, some researchers have proposed using source-to-source translators to translate CUDA to portable programming languages that can be executed on non-NVIDIA devices. However, most CUDA translators require additional manual modifications on the translated code, which imposes a heavy workload on developers. In this paper, CuPBoP is proposed to execute CUDA on non-NVIDIA devices without relying on any portable programming languages. Compared with existing work that executes CUDA on non-NVIDIA devices, CuPBoP does not require manual modification of the CUDA source code, but it still achieves the highest coverage (69.6%), much higher than existing frameworks (56.6%) on the Rodinia benchmark. In particular, for CPU backends, CuPBoP supports several ISAs (e.g., X86, RISC-V, AArch64) and has close or even higher performance compared with other projects. We also compare and analyze the performance among CuPBoP, manually optimized OpenMP/MPI programs, and CUDA programs on the latest Ampere architecture GPU, and show future directions for supporting CUDA programs on non-NVIDIA devices with high performance △ Less

Submitted 15 June, 2022; originally announced June 2022.

UniMorph 4.0: Universal Morphology

Authors: Khuyagbaatar Batsuren, Omer Goldman, Salam Khalifa, Nizar Habash, Witold Kieraś, Gábor Bella, Brian Leonard, Garrett Nicolai, Kyle Gorman, Yustinus Ghanggo Ate, Maria Ryskina, Sabrina J. Mielke, Elena Budianskaya, Charbel El-Khaissi, Tiago Pimentel, Michael Gasser, William Lane, Mohit Raj, Matt Coler, Jaime Rafael Montoya Samame, Delio Siticonatzi Camaiteri, Benoît Sagot, Esaú Zumaeta Rojas, Didier López Francis, Arturo Oncevay , et al. (71 additional authors not shown)

Abstract: The Universal Morphology (UniMorph) project is a collaborative effort providing broad-coverage instantiated normalized morphological inflection tables for hundreds of diverse world languages. The project comprises two major thrusts: a language-independent feature schema for rich morphological annotation and a type-level resource of annotated data in diverse languages realizing that schema. This pa… ▽ More The Universal Morphology (UniMorph) project is a collaborative effort providing broad-coverage instantiated normalized morphological inflection tables for hundreds of diverse world languages. The project comprises two major thrusts: a language-independent feature schema for rich morphological annotation and a type-level resource of annotated data in diverse languages realizing that schema. This paper presents the expansions and improvements made on several fronts over the last couple of years (since McCarthy et al. (2020)). Collaborative efforts by numerous linguists have added 67 new languages, including 30 endangered languages. We have implemented several improvements to the extraction pipeline to tackle some issues, e.g. missing gender and macron information. We have also amended the schema to use a hierarchical structure that is needed for morphological phenomena like multiple-argument agreement and case stacking, while adding some missing morphological features to make the schema more inclusive. In light of the last UniMorph release, we also augmented the database with morpheme segmentation for 16 languages. Lastly, this new release makes a push towards inclusion of derivational morphology in UniMorph by enriching the data and annotation schema with instances representing derivational processes from MorphyNet. △ Less

Submitted 19 June, 2022; v1 submitted 7 May, 2022; originally announced May 2022.

Comments: LREC 2022; The first two authors made equal contributions

Network Onion Divergence: Network representation and comparison using nested configuration models with fixed connectivity, correlation and centrality patterns

Authors: Laurent Hébert-Dufresne, Jean-Gabriel Young, Alexander Daniels, Antoine Allard

Abstract: Random networks, constrained to reproduce specific features of networks, are often used to represent and analyze network data as well as their mathematical descriptions. Chief among them, the configuration model constrains random networks by their degree distribution and is foundational to many areas of network science. However, these representations are often selected based on intuition or mathem… ▽ More Random networks, constrained to reproduce specific features of networks, are often used to represent and analyze network data as well as their mathematical descriptions. Chief among them, the configuration model constrains random networks by their degree distribution and is foundational to many areas of network science. However, these representations are often selected based on intuition or mathematical and computational simplicity rather than on statistical evidence. To evaluate the quality of a network representation we need to consider both the amount of information required by a random network model as well as the probability of recovering the original data when using the model as a generative process. To this end, we calculate the approximate size of network ensembles generated by the popular configuration model and its generalizations that include degree-correlations and centrality layers based on the onion decomposition. We then apply minimum description length as a model selection criterion and also introduce the Network Onion Divergence: model selection and network comparison over a nested family of configuration models with differing level of structural details. Using over 100 empirical sets of network data, we find that a simple Layered Configuration Model offers the most compact representation of the majority of real networks. We hope that our results will continue to motivate the development of intricate random network models that help capture network structure beyond the simple degree distribution. △ Less

Submitted 18 April, 2022; originally announced April 2022.

Comments: Comments welcomed at laurent.hebert-dufresne@uvm.edu

"Smarter" NICs for faster molecular dynamics: a case study

Authors: Sara Karamati, Clayton Hughes, K. Scott Hemmert, Ryan E. Grant, W. Whit Schonbein, Scott Levy, Thomas M. Conte, Jeffrey Young, Richard W. Vuduc

Abstract: This work evaluates the benefits of using a "smart" network interface card (SmartNIC) as a compute accelerator for the example of the MiniMD molecular dynamics proxy application. The accelerator is NVIDIA's BlueField-2 card, which includes an 8-core Arm processor along with a small amount of DRAM and storage. We test the networking and data movement performance of these cards compared to a standar… ▽ More This work evaluates the benefits of using a "smart" network interface card (SmartNIC) as a compute accelerator for the example of the MiniMD molecular dynamics proxy application. The accelerator is NVIDIA's BlueField-2 card, which includes an 8-core Arm processor along with a small amount of DRAM and storage. We test the networking and data movement performance of these cards compared to a standard Intel server host using microbenchmarks and MiniMD. In MiniMD, we identify two distinct classes of computation, namely core computation and maintenance computation, which are executed in sequence. We restructure the algorithm and code to weaken this dependence and increase task parallelism, thereby making it possible to increase utilization of the BlueField-2 concurrently with the host. We evaluate our implementation on a cluster consisting of 16 dual-socket Intel Broadwell host nodes with one BlueField-2 per host-node. Our results show that while the overall compute performance of BlueField-2 is limited, using them with a modified MiniMD algorithm allows for up to 20% speedup over the host CPU baseline with no loss in simulation accuracy. △ Less

Submitted 12 April, 2022; originally announced April 2022.

The OCEAN mailing list data set: Network analysis spanning mailing lists and code repositories

Authors: Melanie Warrick, Samuel F. Rosenblatt, Jean-Gabriel Young, Amanda Casari, Laurent Hébert-Dufresne, James Bagrow

Abstract: Communication surrounding the development of an open source project largely occurs outside the software repository itself. Historically, large communities often used a collection of mailing lists to discuss the different aspects of their projects. Multimodal tool use, with software development and communication happening on different channels, complicates the study of open source projects as a soc… ▽ More Communication surrounding the development of an open source project largely occurs outside the software repository itself. Historically, large communities often used a collection of mailing lists to discuss the different aspects of their projects. Multimodal tool use, with software development and communication happening on different channels, complicates the study of open source projects as a sociotechnical system. Here, we combine and standardize mailing lists of the Python community, resulting in 954,287 messages from 1995 to the present. We share all scraping and cleaning code to facilitate reproduction of this work, as well as smaller datasets for the Golang (122,721 messages), Angular (20,041 messages) and Node.js (12,514 messages) communities. To showcase the usefulness of these data, we focus on the CPython repository and merge the technical layer (which GitHub account works on what file and with whom) with the social layer (messages from unique email addresses) by identifying 33% of GitHub contributors in the mailing list data. We then explore correlations between the valence of social messaging and the structure of the collaboration network. We discuss how these data provide a laboratory to test theories from standard organizational science in large open source projects. △ Less

Submitted 1 April, 2022; originally announced April 2022.

Comments: Accepted for the 19th International Conference on Mining Software Repositories (MSR '22), May 23--24, 2022, Pittsburgh, PA, USA

Cutting Through the Noise to Infer Autonomous System Topology

Authors: Kirtus G. Leyba, Joshua J. Daymude, Jean-Gabriel Young, M. E. J. Newman, Jennifer Rexford, Stephanie Forrest

Abstract: The Border Gateway Protocol (BGP) is a distributed protocol that manages interdomain routing without requiring a centralized record of which autonomous systems (ASes) connect to which others. Many methods have been devised to infer the AS topology from publicly available BGP data, but none provide a general way to handle the fact that the data are notoriously incomplete and subject to error. This… ▽ More The Border Gateway Protocol (BGP) is a distributed protocol that manages interdomain routing without requiring a centralized record of which autonomous systems (ASes) connect to which others. Many methods have been devised to infer the AS topology from publicly available BGP data, but none provide a general way to handle the fact that the data are notoriously incomplete and subject to error. This paper describes a method for reliably inferring AS-level connectivity in the presence of measurement error using Bayesian statistical inference acting on BGP routing tables from multiple vantage points. We employ a novel approach for counting AS adjacency observations in the AS-PATH attribute data from public route collectors, along with a Bayesian algorithm to generate a statistical estimate of the AS-level network. Our approach also gives us a way to evaluate the accuracy of existing reconstruction methods and to identify advantageous locations for new route collectors or vantage points. △ Less

Submitted 18 January, 2022; originally announced January 2022.

Comments: 10 pages, 8 figures, 1 table. To appear at IEEE INFOCOM 2022. © IEEE 2022

Journal ref: Proceedings of the IEEE Conference on Computer Communications (INFOCOM 2022), pp. 1609-1618

Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data

Authors: Caterina De Bacco, Martina Contisciani, Jonathan Cardoso-Silva, Hadiseh Safdari, Diego Baptista, Gabriela L. Borges, Tracy Sweet, Jean-Gabriel Young, Jeremy Koster, Cody T. Ross, Richard McElreath, Daniel Redhead, Eleanor A. Power

Abstract: Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that inc… ▽ More Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that incorporates ties reported by multiple individuals to estimate the unobserved network structure. In addition to estimating a parameter for each reporter that is related to their tendency of over- or under-reporting relationships, the model explicitly incorporates a term for ``mutuality,'' the tendency to report ties in both directions involving the same alter. Our model's algorithmic implementation is based on variational inference, which makes it efficient and scalable to large systems. We apply our model to data from 75 Indian villages collected with a name-generator design, and a Nicaraguan community collected with a roster-based design. We observe strong evidence of ``mutuality'' in both datasets, and find that this value varies by relationship type. Consequently, our model estimates networks with reciprocity values that are substantially different than those resulting from standard deterministic aggregation approaches, demonstrating the need to consider such issues when gathering, constructing, and analysing survey-based network data. △ Less

Submitted 12 December, 2022; v1 submitted 21 December, 2021; originally announced December 2021.

Challenges Porting a C++ Template-Metaprogramming Abstraction Layer to Directive-based Offloading

Authors: Jeffrey Kelling, Sergei Bastrakov, Alexander Debus, Thomas Kluge, Matt Leinhauser, Richard Pausch, Klaus Steiniger, Jan Stephan, René Widera, Jeff Young, Michael Bussmann, Sunita Chandrasekaran, Guido Juckeland

Abstract: HPC systems employ a growing variety of compute accelerators with different architectures and from different vendors. Large scientific applications are required to run efficiently across these systems but need to retain a single code-base in order to not stifle development. Directive-based offloading programming models set out to provide the required portability, but, to existing codes, they thems… ▽ More HPC systems employ a growing variety of compute accelerators with different architectures and from different vendors. Large scientific applications are required to run efficiently across these systems but need to retain a single code-base in order to not stifle development. Directive-based offloading programming models set out to provide the required portability, but, to existing codes, they themselves represent yet another API to port to. Here, we present our approach of porting the GPU-accelerated particle-in-cell code PIConGPU to OpenACC and OpenMP target by adding two new backends to its existing C++-template metaprogramming-based offloading abstraction layer alpaka and avoiding other modifications to the application code. We introduce our approach in the face of conflicts between requirements and available features in the standards as well as practical hurdles posed by immature compiler support. △ Less

Submitted 24 January, 2022; v1 submitted 16 October, 2021; originally announced October 2021.

Comments: 20 pages, 1 figure, 3 tables, WACCPD@SC21

ACM Class: D.1.3; D.2.1; D.3.3

Key Considerations for the Responsible Development and Fielding of Artificial Intelligence

Authors: Eric Horvitz, Jessica Young, Rama G. Elluru, Chuck Howell

Abstract: We review key considerations, practices, and areas for future work aimed at the responsible development and fielding of AI technologies. We describe critical challenges and make recommendations on topics that should be given priority consideration, practices that should be implemented, and policies that should be defined or updated to reflect developments with capabilities and uses of AI technolog… ▽ More We review key considerations, practices, and areas for future work aimed at the responsible development and fielding of AI technologies. We describe critical challenges and make recommendations on topics that should be given priority consideration, practices that should be implemented, and policies that should be defined or updated to reflect developments with capabilities and uses of AI technologies. The Key Considerations were developed with a lens for adoption by U.S. government departments and agencies critical to national security. However, they are relevant more generally for the design, construction, and use of AI systems. △ Less

Submitted 19 August, 2021; originally announced August 2021.

Comments: Report of the National Security Commission on AI (NSCAI), 44 pages

ACM Class: I.2.0

Clustering of heterogeneous populations of networks

Authors: Jean-Gabriel Young, Alec Kirkley, M. E. J. Newman

Abstract: Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we desc… ▽ More Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we describe a Bayesian analysis framework for such data that allows for the fact that network measurements may be reflective of multiple possible structures. We define a finite mixture model of the measurement process and derive a fast Gibbs sampling procedure that samples exactly from the full posterior distribution of model parameters. The end result is a clustering of the measured networks into groups with similar structure. We demonstrate the method on both real and synthetic network populations. △ Less

Submitted 23 January, 2022; v1 submitted 15 July, 2021; originally announced July 2021.

Comments: 12 pages, 3 figures

Journal ref: Phys. Rev. E 105, 014312 (2022)

The RSNA-ASNR-MICCAI BraTS 2021 Benchmark on Brain Tumor Segmentation and Radiogenomic Classification

Authors: Ujjwal Baid, Satyam Ghodasara, Suyash Mohan, Michel Bilello, Evan Calabrese, Errol Colak, Keyvan Farahani, Jayashree Kalpathy-Cramer, Felipe C. Kitamura, Sarthak Pati, Luciano M. Prevedello, Jeffrey D. Rudie, Chiharu Sako, Russell T. Shinohara, Timothy Bergquist, Rong Chai, James Eddy, Julia Elliott, Walter Reade, Thomas Schaffter, Thomas Yu, Jiaxin Zheng, Ahmed W. Moawad, Luiz Otavio Coelho, Olivia McDonnell , et al. (78 additional authors not shown)

Abstract: The BraTS 2021 challenge celebrates its 10th anniversary and is jointly organized by the Radiological Society of North America (RSNA), the American Society of Neuroradiology (ASNR), and the Medical Image Computing and Computer Assisted Interventions (MICCAI) society. Since its inception, BraTS has been focusing on being a common benchmarking venue for brain glioma segmentation algorithms, with wel… ▽ More The BraTS 2021 challenge celebrates its 10th anniversary and is jointly organized by the Radiological Society of North America (RSNA), the American Society of Neuroradiology (ASNR), and the Medical Image Computing and Computer Assisted Interventions (MICCAI) society. Since its inception, BraTS has been focusing on being a common benchmarking venue for brain glioma segmentation algorithms, with well-curated multi-institutional multi-parametric magnetic resonance imaging (mpMRI) data. Gliomas are the most common primary malignancies of the central nervous system, with varying degrees of aggressiveness and prognosis. The RSNA-ASNR-MICCAI BraTS 2021 challenge targets the evaluation of computational algorithms assessing the same tumor compartmentalization, as well as the underlying tumor's molecular characterization, in pre-operative baseline mpMRI data from 2,040 patients. Specifically, the two tasks that BraTS 2021 focuses on are: a) the segmentation of the histologically distinct brain tumor sub-regions, and b) the classification of the tumor's O[6]-methylguanine-DNA methyltransferase (MGMT) promoter methylation status. The performance evaluation of all participating algorithms in BraTS 2021 will be conducted through the Sage Bionetworks Synapse platform (Task 1) and Kaggle (Task 2), concluding in distributing to the top ranked participants monetary awards of $60,000 collectively. △ Less

Submitted 12 September, 2021; v1 submitted 5 July, 2021; originally announced July 2021.

Comments: 19 pages, 2 figures, 1 table

Which contributions count? Analysis of attribution in open source

Authors: Jean-Gabriel Young, Amanda Casari, Katie McLaughlin, Milo Z. Trujillo, Laurent Hébert-Dufresne, James P. Bagrow

Abstract: Open source software projects usually acknowledge contributions with text files, websites, and other idiosyncratic methods. These data sources are hard to mine, which is why contributorship is most frequently measured through changes to repositories, such as commits, pushes, or patches. Recently, some open source projects have taken to recording contributor actions with standardized systems; this… ▽ More Open source software projects usually acknowledge contributions with text files, websites, and other idiosyncratic methods. These data sources are hard to mine, which is why contributorship is most frequently measured through changes to repositories, such as commits, pushes, or patches. Recently, some open source projects have taken to recording contributor actions with standardized systems; this opens up a unique opportunity to understand how community-generated notions of contributorship map onto codebases as the measure of contribution. Here, we characterize contributor acknowledgment models in open source by analyzing thousands of projects that use a model called All Contributors to acknowledge diverse contributions like outreach, finance, infrastructure, and community management. We analyze the life cycle of projects through this model's lens and contrast its representation of contributorship with the picture given by other methods of acknowledgment, including GitHub's top committers indicator and contributions derived from actions taken on the platform. We find that community-generated systems of contribution acknowledgment make work like idea generation or bug finding more visible, which generates a more extensive picture of collaboration. Further, we find that models requiring explicit attribution lead to more clearly defined boundaries around what is and what is not a contribution. △ Less

Submitted 19 March, 2021; originally announced March 2021.

Comments: Extended version of a paper accepted at MSR 2021

Journal ref: 2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR), pp. 242-253 (2021)

Online Model Swapping in Architectural Simulation

Authors: Patrick Lavin, Jeffrey Young, Rich Vuduc, Jonathan Beard

Abstract: As systems and applications grow more complex, detailed simulation takes an ever increasing amount of time. The prospect of increased simulation time resulting in slower design iteration forces architects to use simpler models, such as spreadsheets, when they want to iterate quickly on a design. However, the task of migrating from a simple simulation to one with more detail often requires multiple… ▽ More As systems and applications grow more complex, detailed simulation takes an ever increasing amount of time. The prospect of increased simulation time resulting in slower design iteration forces architects to use simpler models, such as spreadsheets, when they want to iterate quickly on a design. However, the task of migrating from a simple simulation to one with more detail often requires multiple executions to find where simple models could be effective, which could be more expensive than running the detailed model in the first place. Also, architects must often rely on intuition to choose these simpler models, further complicating the problem. In this work, we present a method of bridging the gap between simple and detailed simulation by monitoring simulation behavior online and automatically swapping out detailed models with simpler statistical approximations. We demonstrate the potential of our methodology by implementing it in the open-source simulator SVE-Cachesim to swap out the level one data cache (L1D) within a memory hierarchy. This proof of concept demonstrates that our technique can handle a non-trivial use-case in not just approximation of local time-invariant statistics, but also those that vary with time (e.g., the L1D is a form of a time-series function), and downstream side-effects (e.g., the L1D filters accesses for the level two cache). Our simulation swaps out the built-in cache model with only an 8% error in the simulated cycle count while using the approximated cache models for over 90% of the simulation, and our simpler models require two to eight times less computation per "execution" of the model △ Less

Submitted 2 December, 2020; originally announced December 2020.

Ensembling geophysical models with Bayesian Neural Networks

Authors: Ushnish Sengupta, Matt Amos, J. Scott Hosking, Carl Edward Rasmussen, Matthew Juniper, Paul J. Young

Abstract: Ensembles of geophysical models improve projection accuracy and express uncertainties. We develop a novel data-driven ensembling strategy for combining geophysical models using Bayesian Neural Networks, which infers spatiotemporally varying model weights and bias while accounting for heteroscedastic uncertainties in the observations. This produces more accurate and uncertainty-aware projections wi… ▽ More Ensembles of geophysical models improve projection accuracy and express uncertainties. We develop a novel data-driven ensembling strategy for combining geophysical models using Bayesian Neural Networks, which infers spatiotemporally varying model weights and bias while accounting for heteroscedastic uncertainties in the observations. This produces more accurate and uncertainty-aware projections without sacrificing interpretability. Applied to the prediction of total column ozone from an ensemble of 15 chemistry-climate models, we find that the Bayesian neural network ensemble (BayNNE) outperforms existing ensembling methods, achieving a 49.4% reduction in RMSE for temporal extrapolation, and a 67.4% reduction in RMSE for polar data voids, compared to a weighted mean. Uncertainty is also well-characterized, with 90.6% of the data points in our extrapolation validation dataset lying within 2 standard deviations and 98.5% within 3 standard deviations. △ Less

Submitted 7 October, 2020; originally announced October 2020.

Journal ref: Advances in Neural Information Processing Systems (NeurIPS) 2020

Signing Information in the Quantum Era

Authors: K. Longmate, E. M. Ball, E. Dable-Heath, R. J. Young

Abstract: Signatures are primarily used as a mark of authenticity, to demonstrate that the sender of a message is who they claim to be. In the current digital age, signatures underpin trust in the vast majority of information that we exchange, particularly on public networks such as the internet. However, schemes for signing digital information which are based on assumptions of computational complexity are… ▽ More Signatures are primarily used as a mark of authenticity, to demonstrate that the sender of a message is who they claim to be. In the current digital age, signatures underpin trust in the vast majority of information that we exchange, particularly on public networks such as the internet. However, schemes for signing digital information which are based on assumptions of computational complexity are facing challenges from advances in mathematics, the capability of computers, and the advent of the quantum era. Here we present a review of digital signature schemes, looking at their origins and where they are under threat. Next, we introduce post-quantum digital schemes, which are being developed with the specific intent of mitigating against threats from quantum algorithms whilst still relying on digital processes and infrastructure. Finally, we review schemes for signing information carried on quantum channels, which promise provable security metrics. Signatures were invented as a practical means of authenticating communications and it is important that the practicality of novel signature schemes is considered carefully, which is kept as a common theme of interest throughout this review. △ Less

Submitted 25 September, 2020; originally announced September 2020.

Impact and dynamics of hate and counter speech online

Authors: Joshua Garland, Keyan Ghazi-Zahedi, Jean-Gabriel Young, Laurent Hébert-Dufresne, Mirta Galesic

Abstract: Citizen-generated counter speech is a promising way to fight hate speech and promote peaceful, non-polarized discourse. However, there is a lack of large-scale longitudinal studies of its effectiveness for reducing hate speech. To this end, we perform an exploratory analysis of the effectiveness of counter speech using several different macro- and micro-level measures to analyze 180,000 political… ▽ More Citizen-generated counter speech is a promising way to fight hate speech and promote peaceful, non-polarized discourse. However, there is a lack of large-scale longitudinal studies of its effectiveness for reducing hate speech. To this end, we perform an exploratory analysis of the effectiveness of counter speech using several different macro- and micro-level measures to analyze 180,000 political conversations that took place on German Twitter over four years. We report on the dynamic interactions of hate and counter speech over time and provide insights into whether, as in `classic' bullying situations, organized efforts are more effective than independent individuals in steering online discourse. Taken together, our results build a multifaceted picture of the dynamics of hate and counter speech online. While we make no causal claims due to the complexity of discourse dynamics, our findings suggest that organized hate speech is associated with changes in public discourse and that counter speech -- especially when organized -- may help curb hateful rhetoric in online discourse. △ Less

Submitted 5 September, 2021; v1 submitted 15 September, 2020; originally announced September 2020.

Hypergraph reconstruction from network data

Authors: Jean-Gabriel Young, Giovanni Petri, Tiago P. Peixoto

Abstract: Networks can describe the structure of a wide variety of complex systems by specifying which pairs of entities in the system are connected. While such pairwise representations are flexible, they are not necessarily appropriate when the fundamental interactions involve more than two entities at the same time. Pairwise representations nonetheless remain ubiquitous, because higher-order interactions… ▽ More Networks can describe the structure of a wide variety of complex systems by specifying which pairs of entities in the system are connected. While such pairwise representations are flexible, they are not necessarily appropriate when the fundamental interactions involve more than two entities at the same time. Pairwise representations nonetheless remain ubiquitous, because higher-order interactions are often not recorded explicitly in network data. Here, we introduce a Bayesian approach to reconstruct latent higher-order interactions from ordinary pairwise network data. Our method is based on the principle of parsimony and only includes higher-order structures when there is sufficient statistical evidence for them. We demonstrate its applicability to a wide range of datasets, both synthetic and empirical. △ Less

Submitted 13 January, 2022; v1 submitted 11 August, 2020; originally announced August 2020.

Comments: 13 pages, 7 figures. Code is available at https://graph-tool.skewed.de/

Journal ref: Communication Physics 4, 135 (2021)

Directional Laplacian Centrality for Cyber Situational Awareness

Authors: Sinan G. Aksoy, Emilie Purvine, Stephen J. Young

Abstract: Cyber operations is drowning in diverse, high-volume, multi-source data. In order to get a full picture of current operations and identify malicious events and actors analysts must see through data generated by a mix of human activity and benign automated processes. Although many monitoring and alert systems exist, they typically use signature-based detection methods. We introduce a general method… ▽ More Cyber operations is drowning in diverse, high-volume, multi-source data. In order to get a full picture of current operations and identify malicious events and actors analysts must see through data generated by a mix of human activity and benign automated processes. Although many monitoring and alert systems exist, they typically use signature-based detection methods. We introduce a general method rooted in spectral graph theory to discover patterns and anomalies without a priori knowledge of signatures. We derive and propose a new graph-theoretic centrality measure based on the derivative of the graph Laplacian matrix in the direction of a vertex. To build intuition about our measure we show how it identifies the most central vertices in standard network data sets and compare to other graph centrality measures. Finally, we focus our attention on studying its effectiveness in identifying important IP addresses in network flow data. Using both real and synthetic network flow data, we conduct several experiments to test our measure's sensitivity to two types of injected attack profiles, and show that vertices participating in injected attack profiles exhibit noticeable changes in our centrality measures, even when the injected anomalies are relatively small, and in the presence of simulated network dynamics. △ Less

Submitted 23 March, 2021; v1 submitted 10 August, 2020; originally announced August 2020.

Comments: 25 pages, 15 figures

Bayesian inference of network structure from unreliable data

Authors: Jean-Gabriel Young, George T. Cantwell, M. E. J. Newman

Abstract: Most empirical studies of complex networks do not return direct, error-free measurements of network structure. Instead, they typically rely on indirect measurements that are often error-prone and unreliable. A fundamental problem in empirical network science is how to make the best possible estimates of network structure given such unreliable data. In this paper we describe a fully Bayesian method… ▽ More Most empirical studies of complex networks do not return direct, error-free measurements of network structure. Instead, they typically rely on indirect measurements that are often error-prone and unreliable. A fundamental problem in empirical network science is how to make the best possible estimates of network structure given such unreliable data. In this paper we describe a fully Bayesian method for reconstructing networks from observational data in any format, even when the data contain substantial measurement error and when the nature and magnitude of that error is unknown. The method is introduced through pedagogical case studies using real-world example networks, and specifically tailored to allow straightforward, computationally efficient implementation with a minimum of technical input. Computer code implementing the method is publicly available. △ Less

Submitted 9 March, 2021; v1 submitted 7 August, 2020; originally announced August 2020.

Comments: 16 pages, 7 figures

Journal ref: J. Complex Netw. 8, cnaa046 (2021)

How are your robot friends doing? A design exploration of graphical techniques supporting awareness of robot team members in teleoperation

Authors: Stela H. Seo, James E. Young, Pourang Irani

Abstract: While teleoperated robots continue to proliferate in domains including search and rescue, field exploration, or the military, human error remains a primary cause for accidents or mistakes. One challenge is that teleoperating a remote robot is cognitively taxing as the operator needs to understand the robot's state and monitor all its sensor data. In a multi-robot team, an operator needs to additio… ▽ More While teleoperated robots continue to proliferate in domains including search and rescue, field exploration, or the military, human error remains a primary cause for accidents or mistakes. One challenge is that teleoperating a remote robot is cognitively taxing as the operator needs to understand the robot's state and monitor all its sensor data. In a multi-robot team, an operator needs to additionally monitor other robots' progress, states, notifications, errors, and so on to maintain team cohesion. One strategy for supporting the operator to comprehend this information is to improve teleoperation interface designs to carefully present data. We present a set of prototypes that simplify complex team robot states and actions, with an aim to help the operator to understand information from the robots easily and quickly. We conduct a series of pilot studies to explore a range of design parameters used in our prototypes (text, icon, facial expression, use of color, animation, and number of team robots), and develop a set of guidelines for graphically representing team robot states in the remote team teleoperation. △ Less

Submitted 8 June, 2020; originally announced June 2020.

Comments: submitted to International Journal of Social Robotics https://www.springer.com/journal/12369/

Countering hate on social media: Large scale classification of hate and counter speech

Authors: Joshua Garland, Keyan Ghazi-Zahedi, Jean-Gabriel Young, Laurent Hébert-Dufresne, Mirta Galesic

Abstract: Hateful rhetoric is plaguing online discourse, fostering extreme societal movements and possibly giving rise to real-world violence. A potential solution to this growing global problem is citizen-generated counter speech where citizens actively engage in hate-filled conversations to attempt to restore civil non-polarized discourse. However, its actual effectiveness in curbing the spread of hatred… ▽ More Hateful rhetoric is plaguing online discourse, fostering extreme societal movements and possibly giving rise to real-world violence. A potential solution to this growing global problem is citizen-generated counter speech where citizens actively engage in hate-filled conversations to attempt to restore civil non-polarized discourse. However, its actual effectiveness in curbing the spread of hatred is unknown and hard to quantify. One major obstacle to researching this question is a lack of large labeled data sets for training automated classifiers to identify counter speech. Here we made use of a unique situation in Germany where self-labeling groups engaged in organized online hate and counter speech. We used an ensemble learning algorithm which pairs a variety of paragraph embeddings with regularized logistic regression functions to classify both hate and counter speech in a corpus of millions of relevant tweets from these two groups. Our pipeline achieved macro F1 scores on out of sample balanced test sets ranging from 0.76 to 0.97---accuracy in line and even exceeding the state of the art. On thousands of tweets, we used crowdsourcing to verify that the judgments made by the classifier are in close alignment with human judgment. We then used the classifier to discover hate and counter speech in more than 135,000 fully-resolved Twitter conversations occurring from 2013 to 2018 and study their frequency and interaction. Altogether, our results highlight the potential of automated methods to evaluate the impact of coordinated counter speech in stabilizing conversations on social media. △ Less

Submitted 5 June, 2020; v1 submitted 2 June, 2020; originally announced June 2020.

Networks beyond pairwise interactions: structure and dynamics

Authors: Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, Giovanni Petri

Abstract: The complexity of many biological, social and technological systems stems from the richness of the interactions among their units. Over the past decades, a great variety of complex systems has been successfully described as networks whose interacting pairs of nodes are connected by links. Yet, in face-to-face human communication, chemical reactions and ecological systems, interactions can occur in… ▽ More The complexity of many biological, social and technological systems stems from the richness of the interactions among their units. Over the past decades, a great variety of complex systems has been successfully described as networks whose interacting pairs of nodes are connected by links. Yet, in face-to-face human communication, chemical reactions and ecological systems, interactions can occur in groups of three or more nodes and cannot be simply described just in terms of simple dyads. Until recently, little attention has been devoted to the higher-order architecture of real complex systems. However, a mounting body of evidence is showing that taking the higher-order structure of these systems into account can greatly enhance our modeling capacities and help us to understand and predict their emerging dynamical behaviors. Here, we present a complete overview of the emerging field of networks beyond pairwise interactions. We first discuss the methods to represent higher-order interactions and give a unified presentation of the different frameworks used to describe higher-order systems, highlighting the links between the existing concepts and representations. We review the measures designed to characterize the structure of these systems and the models proposed in the literature to generate synthetic structures, such as random and growing simplicial complexes, bipartite graphs and hypergraphs. We introduce and discuss the rapidly growing research on higher-order dynamical systems and on dynamical topology. We focus on novel emergent phenomena characterizing landmark dynamical processes, such as diffusion, spreading, synchronization and games, when extended beyond pairwise interactions. We elucidate the relations between higher-order topology and dynamical properties, and conclude with a summary of empirical applications, providing an outlook on current modeling and conceptual frontiers. △ Less

Submitted 2 June, 2020; originally announced June 2020.

Comments: Accepted for publication in Physics Reports. 109 pages, 47 figures

Journal ref: Physics Reports 874, 1 (2020)

A Clarified Typology of Core-Periphery Structure in Networks

Authors: Ryan J. Gallagher, Jean-Gabriel Young, Brooke Foucault Welles

Abstract: Core-periphery structure, the arrangement of a network into a dense core and sparse periphery, is a versatile descriptor of various social, biological, and technological networks. In practice, different core-periphery algorithms are often applied interchangeably, despite the fact that they can yield inconsistent descriptions of core-periphery structure. For example, two of the most widely used alg… ▽ More Core-periphery structure, the arrangement of a network into a dense core and sparse periphery, is a versatile descriptor of various social, biological, and technological networks. In practice, different core-periphery algorithms are often applied interchangeably, despite the fact that they can yield inconsistent descriptions of core-periphery structure. For example, two of the most widely used algorithms, the k-cores decomposition and the classic two-block model of Borgatti and Everett, extract fundamentally different structures: the latter partitions a network into a binary hub-and-spoke layout, while the former divides it into a layered hierarchy. We introduce a core-periphery typology to clarify these differences, along with Bayesian stochastic block modeling techniques to classify networks in accordance with this typology. Empirically, we find a rich diversity of core-periphery structure among networks. Through a detailed case study, we demonstrate the importance of acknowledging this diversity and situating networks within the core-periphery typology when conducting domain-specific analyses. △ Less

Submitted 21 May, 2020; v1 submitted 20 May, 2020; originally announced May 2020.

Comments: 21 pages, 6 figures, 1 table, updated abstract

Journal ref: Science Advances, 7:EABC9800, 2021