-
Spectral gap in random bipartite biregular graphs and applications
Authors:
Gerandy Brito,
Ioana Dumitriu,
Kameron Decker Harris
Abstract:
We prove an analogue of Alon's spectral gap conjecture for random bipartite, biregular graphs. We use the Ihara-Bass formula to connect the non-backtracking spectrum to that of the adjacency matrix, employing the moment method to show there exists a spectral gap for the non-backtracking matrix. A byproduct of our main theorem is that random rectangular zero-one matrices with fixed row and column s…
▽ More
We prove an analogue of Alon's spectral gap conjecture for random bipartite, biregular graphs. We use the Ihara-Bass formula to connect the non-backtracking spectrum to that of the adjacency matrix, employing the moment method to show there exists a spectral gap for the non-backtracking matrix. A byproduct of our main theorem is that random rectangular zero-one matrices with fixed row and column sums are full-rank with high probability. Finally, we illustrate applications to community detection, coding theory, and deterministic matrix completion.
△ Less
Submitted 2 June, 2021; v1 submitted 20 April, 2018;
originally announced April 2018.
-
High resolution neural connectivity from incomplete tracing data using nonnegative spline regression
Authors:
Kameron Decker Harris,
Stefan Mihalas,
Eric Shea-Brown
Abstract:
Whole-brain neural connectivity data are now available from viral tracing experiments, which reveal the connections between a source injection site and elsewhere in the brain. These hold the promise of revealing spatial patterns of connectivity throughout the mammalian brain. To achieve this goal, we seek to fit a weighted, nonnegative adjacency matrix among 100 $μ$m brain "voxels" using viral tra…
▽ More
Whole-brain neural connectivity data are now available from viral tracing experiments, which reveal the connections between a source injection site and elsewhere in the brain. These hold the promise of revealing spatial patterns of connectivity throughout the mammalian brain. To achieve this goal, we seek to fit a weighted, nonnegative adjacency matrix among 100 $μ$m brain "voxels" using viral tracer data. Despite a multi-year experimental effort, injections provide incomplete coverage, and the number of voxels in our data is orders of magnitude larger than the number of injections, making the problem severely underdetermined. Furthermore, projection data are missing within the injection site because local connections there are not separable from the injection signal.
We use a novel machine-learning algorithm to meet these challenges and develop a spatially explicit, voxel-scale connectivity map of the mouse visual system. Our method combines three features: a matrix completion loss for missing data, a smoothing spline penalty to regularize the problem, and (optionally) a low rank factorization. We demonstrate the consistency of our estimator using synthetic data and then apply it to newly available Allen Mouse Brain Connectivity Atlas data for the visual system. Our algorithm is significantly more predictive than current state of the art approaches which assume regions to be homogeneous. We demonstrate the efficacy of a low rank version on visual cortex data and discuss the possibility of extending this to a whole-brain connectivity matrix at the voxel scale.
△ Less
Submitted 26 October, 2016; v1 submitted 24 May, 2016;
originally announced May 2016.
-
Reply to Garcia et al.: Common mistakes in measuring frequency dependent word characteristics
Authors:
P. S. Dodds,
E. M. Clark,
S. Desu,
M. R. Frank,
A. J. Reagan,
J. R. Williams,
L. Mitchell,
K. D. Harris,
I. M. Kloumann,
J. P. Bagrow,
K. Megerdoomian,
M. T. McMahon,
B. F. Tivnan,
C. M. Danforth
Abstract:
We demonstrate that the concerns expressed by Garcia et al. are misplaced, due to (1) a misreading of our findings in [1]; (2) a widespread failure to examine and present words in support of asserted summary quantities based on word usage frequencies; and (3) a range of misconceptions about word usage frequency, word rank, and expert-constructed word lists. In particular, we show that the English…
▽ More
We demonstrate that the concerns expressed by Garcia et al. are misplaced, due to (1) a misreading of our findings in [1]; (2) a widespread failure to examine and present words in support of asserted summary quantities based on word usage frequencies; and (3) a range of misconceptions about word usage frequency, word rank, and expert-constructed word lists. In particular, we show that the English component of our study compares well statistically with two related surveys, that no survey design influence is apparent, and that estimates of measurement error do not explain the positivity biases reported in our work and that of others. We further demonstrate that for the frequency dependence of positivity---of which we explored the nuances in great detail in [1]---Garcia et al. did not perform a reanalysis of our data---they instead carried out an analysis of a different, statistically improper data set and introduced a nonlinearity before performing linear regression.
△ Less
Submitted 28 May, 2015; v1 submitted 25 May, 2015;
originally announced May 2015.
-
Human language reveals a universal positivity bias
Authors:
Peter Sheridan Dodds,
Eric M. Clark,
Suma Desu,
Morgan R. Frank,
Andrew J. Reagan,
Jake Ryland Williams,
Lewis Mitchell,
Kameron Decker Harris,
Isabel M. Kloumann,
James P. Bagrow,
Karine Megerdoomian,
Matthew T. McMahon,
Brian F. Tivnan,
Christopher M. Danforth
Abstract:
Using human evaluation of 100,000 words spread across 24 corpora in 10 languages diverse in origin and culture, we present evidence of a deep imprint of human sociality in language, observing that (1) the words of natural human language possess a universal positivity bias; (2) the estimated emotional content of words is consistent between languages under translation; and (3) this positivity bias i…
▽ More
Using human evaluation of 100,000 words spread across 24 corpora in 10 languages diverse in origin and culture, we present evidence of a deep imprint of human sociality in language, observing that (1) the words of natural human language possess a universal positivity bias; (2) the estimated emotional content of words is consistent between languages under translation; and (3) this positivity bias is strongly independent of frequency of word usage. Alongside these general regularities, we describe inter-language variations in the emotional spectrum of languages which allow us to rank corpora. We also show how our word evaluations can be used to construct physical-like instruments for both real-time and offline measurement of the emotional content of large-scale texts.
△ Less
Submitted 15 June, 2014;
originally announced June 2014.
-
Dynamical influence processes on networks: General theory and applications to social contagion
Authors:
Kameron Decker Harris,
Christopher M. Danforth,
Peter Sheridan Dodds
Abstract:
We study binary state dynamics on a network where each node acts in response to the average state of its neighborhood. Allowing varying amounts of stochasticity in both the network and node responses, we find different outcomes in random and deterministic versions of the model. In the limit of a large, dense network, however, we show that these dynamics coincide. We construct a general mean field…
▽ More
We study binary state dynamics on a network where each node acts in response to the average state of its neighborhood. Allowing varying amounts of stochasticity in both the network and node responses, we find different outcomes in random and deterministic versions of the model. In the limit of a large, dense network, however, we show that these dynamics coincide. We construct a general mean field theory for random networks and show this predicts that the dynamics on the network are a smoothed version of the average response function dynamics. Thus, the behavior of the system can range from steady state to chaotic depending on the response functions, network connectivity, and update synchronicity. As a specific example, we model the competing tendencies of imitation and non-conformity by incorporating an off-threshold into standard threshold models of social contagion. In this way we attempt to capture important aspects of fashions and societal trends. We compare our theory to extensive simulations of this "limited imitation contagion" model on Poisson random graphs, finding agreement between the mean-field theory and stochastic simulations.
△ Less
Submitted 7 July, 2014; v1 submitted 6 March, 2013;
originally announced March 2013.
-
The Geography of Happiness: Connecting Twitter sentiment and expression, demographics, and objective characteristics of place
Authors:
Lewis Mitchell,
Kameron Decker Harris,
Morgan R. Frank,
Peter Sheridan Dodds,
Christopher M. Danforth
Abstract:
We conduct a detailed investigation of correlations between real-time expressions of individuals made across the United States and a wide range of emotional, geographic, demographic, and health characteristics. We do so by combining (1) a massive, geo-tagged data set comprising over 80 million words generated over the course of several recent years on the social network service Twitter and (2) ann…
▽ More
We conduct a detailed investigation of correlations between real-time expressions of individuals made across the United States and a wide range of emotional, geographic, demographic, and health characteristics. We do so by combining (1) a massive, geo-tagged data set comprising over 80 million words generated over the course of several recent years on the social network service Twitter and (2) annually-surveyed characteristics of all 50 states and close to 400 urban populations. Among many results, we generate taxonomies of states and cities based on their similarities in word use; estimate the happiness levels of states and cities; correlate highly-resolved demographic characteristics with happiness levels; and connect word choice and message length with urban characteristics such as education levels and obesity rates. Our results show how social media may potentially be used to estimate real-time levels and changes in population-level measures such as obesity rates.
△ Less
Submitted 18 May, 2013; v1 submitted 13 February, 2013;
originally announced February 2013.
-
On-off Threshold Models of Social Contagion
Authors:
Kameron Decker Harris
Abstract:
We study binary state contagion dynamics on a social network where nodes act in response to the average state of their neighborhood. We model the competing tendencies of imitation and non-conformity by incorporating an off-threshold into standard threshold models of behavior. In this way, we attempt to capture important aspects of fashions and general societal trends. Allowing varying amounts of s…
▽ More
We study binary state contagion dynamics on a social network where nodes act in response to the average state of their neighborhood. We model the competing tendencies of imitation and non-conformity by incorporating an off-threshold into standard threshold models of behavior. In this way, we attempt to capture important aspects of fashions and general societal trends. Allowing varying amounts of stochasticity in both the network and node responses, we find different outcomes in the random and deterministic versions of the model. In the limit of a large, dense network, however, we show that these dynamics coincide. The dynamical behavior of the system ranges from steady state to chaotic depending on network connectivity and update synchronicity. We construct a mean field theory for general random networks. In the undirected case, the mean field theory predicts that the dynamics on the network are a smoothed version of the average node response dynamics. We compare our theory to extensive simulations on Poisson random graphs with node responses that average to the chaotic tent map.
△ Less
Submitted 10 September, 2012;
originally announced September 2012.
-
Limited Imitation Contagion on Random Networks: Chaos, Universality, and Unpredictability
Authors:
Peter Sheridan Dodds,
Kameron Decker Harris,
Christopher M. Danforth
Abstract:
We study a family of binary state, socially-inspired contagion models which incorporate imitation limited by an aversion to complete conformity. We uncover rich behavior in our models whether operating with either probabilistic or deterministic individual response functions on both dynamic and fixed random networks. In particular, we find significant variation in the limiting behavior of a populat…
▽ More
We study a family of binary state, socially-inspired contagion models which incorporate imitation limited by an aversion to complete conformity. We uncover rich behavior in our models whether operating with either probabilistic or deterministic individual response functions on both dynamic and fixed random networks. In particular, we find significant variation in the limiting behavior of a population's infected fraction, ranging from steady-state to chaotic. We show that period doubling arises as we increase the average node degree, and that the universality class of this well known route to chaos depends on the interaction structure of random networks rather than the microscopic behavior of individual nodes. We find that increasing the fixedness of the system tends to stabilize the infected fraction, yet disjoint, multiple equilibria are possible depending solely on the choice of the initially infected node.
△ Less
Submitted 7 March, 2013; v1 submitted 1 August, 2012;
originally announced August 2012.
-
Twitter reciprocal reply networks exhibit assortativity with respect to happiness
Authors:
Catherine A. Bliss,
Isabel M. Kloumann,
Kameron Decker Harris,
Christopher M. Danforth,
Peter Sheridan Dodds
Abstract:
The advent of social media has provided an extraordinary, if imperfect, 'big data' window into the form and evolution of social networks. Based on nearly 40 million message pairs posted to Twitter between September 2008 and February 2009, we construct and examine the revealed social network structure and dynamics over the time scales of days, weeks, and months. At the level of user behavior, we em…
▽ More
The advent of social media has provided an extraordinary, if imperfect, 'big data' window into the form and evolution of social networks. Based on nearly 40 million message pairs posted to Twitter between September 2008 and February 2009, we construct and examine the revealed social network structure and dynamics over the time scales of days, weeks, and months. At the level of user behavior, we employ our recently developed hedonometric analysis methods to investigate patterns of sentiment expression. We find users' average happiness scores to be positively and significantly correlated with those of users one, two, and three links away. We strengthen our analysis by proposing and using a null model to test the effect of network topology on the assortativity of happiness. We also find evidence that more well connected users write happier status updates, with a transition occurring around Dunbar's number. More generally, our work provides evidence of a social sub-network structure within Twitter and raises several methodological points of interest with regard to social network reconstructions.
△ Less
Submitted 11 May, 2012; v1 submitted 5 December, 2011;
originally announced December 2011.
-
Predicting flow reversals in chaotic natural convection using data assimilation
Authors:
Kameron Decker Harris,
El Hassan Ridouane,
Darren L. Hitt,
Christopher M. Danforth
Abstract:
A simplified model of natural convection, similar to the Lorenz (1963) system, is compared to computational fluid dynamics simulations in order to test data assimilation methods and better understand the dynamics of convection. The thermosyphon is represented by a long time flow simulation, which serves as a reference "truth". Forecasts are then made using the Lorenz-like model and synchronized to…
▽ More
A simplified model of natural convection, similar to the Lorenz (1963) system, is compared to computational fluid dynamics simulations in order to test data assimilation methods and better understand the dynamics of convection. The thermosyphon is represented by a long time flow simulation, which serves as a reference "truth". Forecasts are then made using the Lorenz-like model and synchronized to noisy and limited observations of the truth using data assimilation. The resulting analysis is observed to infer dynamics absent from the model when using short assimilation windows.
Furthermore, chaotic flow reversal occurrence and residency times in each rotational state are forecast using analysis data. Flow reversals have been successfully forecast in the related Lorenz system, as part of a perfect model experiment, but never in the presence of significant model error or unobserved variables. Finally, we provide new details concerning the fluid dynamical processes present in the thermosyphon during these flow reversals.
△ Less
Submitted 20 April, 2012; v1 submitted 29 August, 2011;
originally announced August 2011.
-
Direct, physically motivated derivation of triggering probabilities for spreading processes on generalized random networks
Authors:
Kameron Decker Harris,
Joshua L. Payne,
Peter Sheridan Dodds
Abstract:
We derive a general expression for the probability of global spreading starting from a single infected seed for contagion processes acting on generalized, correlated random networks. We employ a simple probabilistic argument that encodes the spreading mechanism in an intuitive, physical fashion. We use our approach to directly and systematically obtain triggering probabilities for contagion proces…
▽ More
We derive a general expression for the probability of global spreading starting from a single infected seed for contagion processes acting on generalized, correlated random networks. We employ a simple probabilistic argument that encodes the spreading mechanism in an intuitive, physical fashion. We use our approach to directly and systematically obtain triggering probabilities for contagion processes acting on a collection of random network families including bipartite random networks. We find the contagion condition, the location of the phase transition into an endemic state, from an expansion about the disease-free state.
△ Less
Submitted 30 June, 2015; v1 submitted 26 August, 2011;
originally announced August 2011.
-
Positivity of the English language
Authors:
Isabel M. Kloumann,
Christopher M. Danforth,
Kameron Decker Harris,
Catherine A. Bliss,
Peter Sheridan Dodds
Abstract:
Over the last million years, human language has emerged and evolved as a fundamental instrument of social communication and semiotic representation. People use language in part to convey emotional information, leading to the central and contingent questions: (1) What is the emotional spectrum of natural language? and (2) Are natural languages neutrally, positively, or negatively biased? Here, we r…
▽ More
Over the last million years, human language has emerged and evolved as a fundamental instrument of social communication and semiotic representation. People use language in part to convey emotional information, leading to the central and contingent questions: (1) What is the emotional spectrum of natural language? and (2) Are natural languages neutrally, positively, or negatively biased? Here, we report that the human-perceived positivity of over 10,000 of the most frequently used English words exhibits a clear positive bias. More deeply, we characterize and quantify distributions of word positivity for four large and distinct corpora, demonstrating that their form is broadly invariant with respect to frequency of word use.
△ Less
Submitted 12 January, 2012; v1 submitted 25 August, 2011;
originally announced August 2011.
-
Empirical correction of a toy climate model
Authors:
Nicholas A. Allgaier,
Kameron D. Harris,
Christopher M. Danforth
Abstract:
Improving the accuracy of forecast models for physical systems such as the atmosphere is a crucial ongoing effort. Errors in state estimation for these often highly nonlinear systems has been the primary focus of recent research, but as that error has been successfully diminished, the role of model error in forecast uncertainty has duly increased. The present study is an investigation of a particu…
▽ More
Improving the accuracy of forecast models for physical systems such as the atmosphere is a crucial ongoing effort. Errors in state estimation for these often highly nonlinear systems has been the primary focus of recent research, but as that error has been successfully diminished, the role of model error in forecast uncertainty has duly increased. The present study is an investigation of a particular empirical correction procedure that is of special interest because it considers the model a "black box", and therefore can be applied widely with little modification. The procedure involves the comparison of short model forecasts with a reference "truth" system during a training period in order to calculate systematic (1) state-independent model bias and (2) state-dependent error patterns. An estimate of the likelihood of the latter error component is computed from the current state at every timestep of model integration. The effectiveness of this technique is explored in two experiments: (1) a perfect model scenario, in which models have the same structure and dynamics as the true system, differing only in parameter values; and (2) a more realistic scenario, in which models are structurally different (in dynamics, dimension, and parameterization) from the target system. In each case, the results suggest that the correction procedure is more effective for reducing error and prolonging forecast usefulness than parameter tuning. However, the cost of this increase in average forecast accuracy is the creation of substantial qualitative differences between the dynamics of the corrected model and the true system. A method to mitigate the structural damage caused by empirical correction and further increase forecast accuracy is presented.
△ Less
Submitted 13 July, 2011;
originally announced July 2011.
-
Exact solutions for social and biological contagion models on mixed directed and undirected, degree-correlated random networks
Authors:
Joshua L. Payne,
Kameron Decker Harris,
Peter Sheridan Dodds
Abstract:
We derive analytic expressions for the possibility, probability, and expected size of global spreading events starting from a single infected seed for a broad collection of contagion processes acting on random networks with both directed and undirected edges and arbitrary degree-degree correlations. Our work extends previous theoretical developments for the undirected case, and we provide numerica…
▽ More
We derive analytic expressions for the possibility, probability, and expected size of global spreading events starting from a single infected seed for a broad collection of contagion processes acting on random networks with both directed and undirected edges and arbitrary degree-degree correlations. Our work extends previous theoretical developments for the undirected case, and we provide numerical support for our findings by investigating an example class of networks for which we are able to obtain closed-form expressions.
△ Less
Submitted 14 June, 2011; v1 submitted 28 February, 2011;
originally announced March 2011.
-
Direct, physically-motivated derivation of the contagion condition for spreading processes on generalized random networks
Authors:
Peter Sheridan Dodds,
Kameron Decker Harris,
Joshua L. Payne
Abstract:
For a broad range single-seed contagion processes acting on generalized random networks, we derive a unifying analytic expression for the possibility of global spreading events in a straightforward, physically intuitive fashion. Our reasoning lays bare a direct mechanical understanding of an archetypal spreading phenomena that is not evident in circuitous extant mathematical approaches.
For a broad range single-seed contagion processes acting on generalized random networks, we derive a unifying analytic expression for the possibility of global spreading events in a straightforward, physically intuitive fashion. Our reasoning lays bare a direct mechanical understanding of an archetypal spreading phenomena that is not evident in circuitous extant mathematical approaches.
△ Less
Submitted 16 May, 2011; v1 submitted 28 January, 2011;
originally announced January 2011.
-
Temporal patterns of happiness and information in a global social network: Hedonometrics and Twitter
Authors:
Peter Sheridan Dodds,
Kameron Decker Harris,
Isabel M. Kloumann,
Catherine A. Bliss,
Christopher M. Danforth
Abstract:
Individual happiness is a fundamental societal metric. Normally measured through self-report, happiness has often been indirectly characterized and overshadowed by more readily quantifiable economic indicators such as gross domestic product. Here, we examine expressions made on the online, global microblog and social networking service Twitter, uncovering and explaining temporal variations in happ…
▽ More
Individual happiness is a fundamental societal metric. Normally measured through self-report, happiness has often been indirectly characterized and overshadowed by more readily quantifiable economic indicators such as gross domestic product. Here, we examine expressions made on the online, global microblog and social networking service Twitter, uncovering and explaining temporal variations in happiness and information levels over timescales ranging from hours to years. Our data set comprises over 46 billion words contained in nearly 4.6 billion expressions posted over a 33 month span by over 63 million unique users. In measuring happiness, we use a real-time, remote-sensing, non-invasive, text-based approach---a kind of hedonometer. In building our metric, made available with this paper, we conducted a survey to obtain happiness evaluations of over 10,000 individual words, representing a tenfold size improvement over similar existing word sets. Rather than being ad hoc, our word list is chosen solely by frequency of usage and we show how a highly robust metric can be constructed and defended.
△ Less
Submitted 8 December, 2011; v1 submitted 26 January, 2011;
originally announced January 2011.
