Research

A social perspective on perceived distances reveals deep community structure
(with Kenneth Berenhaut and Ryan Melvin)

Community structure arising through relationships and interactions is essential to our understanding of the world around us. Leveraging social concepts of conflict and support, we introduce a method to transform input dissimilarity comparisons into output pairwise relationship strengths (or cohesion) and resulting weighted networks. The introduced perspective may be particularly valuable for data with varying local density, such as that arising from complex evolutionary processes.  Mathematical results together with applications in linguistics, genetics, and cultural psychology, as well as to benchmark data have been included. Together, these demonstrate how meaningful community structure can be identified without additional inputs (e.g., number of clusters or neighborhood size), optimization criteria, iterative procedures, nor distributional assumptions. Published in PNAS.

Link: A social perspective on perceived distances reveals deep community structure.

Characterizations and Enumerations of Patterns of Signed Shifts
(with Sergi Elizalde)

Signed shifts are generalizations of the shift map in which, interpreted as a map from the unit interval to itself sending x to the fractional part of Nx, some slopes are allowed to be negative. Permutations realized by the relative order of the elements in the orbits of these maps have been studied recently by Amigo, Archer and Elizalde. In this paper, we give a complete characterization of the permutations (also called patterns) realized by signed shifts. In the case of the negative shift, which is the signed shift having only negative slopes, we use the characterization to give an exact enumeration of these patterns. Finally, we improve the best-known bounds for the number of patterns realized by the tent map, and calculate the topological entropy of signed shifts using these combinatorial methods.

Link: Characterizations and Enumerations of Patterns of Signed Shifts.

Screen Shot 2017-11-22 at 5.44.05 PM

Random Walk Null Models for Time Series Data
(joint work with Daryl DeFord)

Permutation entropy has become a standard tool for time series analysis that exploits the temporal properties of these data sets. Many current applications use an approach based on Shannon entropy, which implicitly assumes an underlying uniform distribution of patterns. In this paper, we analyze random walk null models for time series and determine the corresponding permutation distributions. These new techniques allow us to explicitly describe the behavior of real-world data in terms of more complex generative processes. Additionally, building on recent results of Martinez, we define a validation measure that allows us to determine when a random walk is an appropriate model for a time series. We demonstrate the usefulness of our methods using empirical data drawn from a variety of fields.

Link: Random Walk Null Models for Time Series Data.

Patterns in Negative Shifts and Signed Shifts
(with Kassie Archer and Sergi Elizalde)

Given a function f from a linearly ordered set X to itself, we say that a permutation \pi is an allowed pattern of f if the relative order of the first n iterates of f beginning at some x \in X is given by \pi. We give a characterization of the allowed patterns of signed shifts in terms of monotone runs of a certain transformation of \pi, which completes and simplifies the original characterization given by Amigó. Signed shifts, which are generalizations of the shift map where some slopes are allowed to be negative, are particularly well-suited to a combinatorial analysis. In the special case where all the slopes are negative, we give an exact formula for the number of allowed patterns. Finally, we obtain a combinatorial derivation of the topological entropy of signed shifts.

 

Link: FPSAC Proceedings.

Screen Shot 2017-10-14 at 3.03.35 PM.png

Patterns of Negative Shifts and Beta-Shifts
(with Sergi Elizalde)

Given a \beta-shift is the transformation from the unit interval to itself that maps x to the fractional part of \beta x.  Permutations realized by the relative order of the elements in the orbits of these maps have been studied for positive integer values of \beta and for real values \beta > 1>. In both cases, a combinatorial description of the smallest positive value of \beta needed to realize a permutation is provided.  In this paper we extend these results to the case of the negative \beta, both in the integer and in the real case.  Negative \beta-shifts are related to digital expansions with negative real bases, studied by Ito and Sadahiro, and Liao and Steiner.

Link: Patterns of Negative Shifts and Beta-Shifts.