ASU Scholarship Showcase

Locating sources of diffusion and spreading from minimum data is a significant problem in network science with great applied values to the society. However, a general theoretical framework dealing with optimal source localization is lacking. Combining the controllability theory for complex networks and compressive sensing, we develop a framework with high efficiency and robustness for optimal source localization in arbitrary weighted networks with arbitrary distribution of sources. We offer a minimum output analysis to quantify the source locatability through a minimal number of messenger nodes that produce sufficient measurement for fully locating the sources. When the minimum messenger nodes are discerned, the problem of optimal source localization becomes one of sparse signal reconstruction, which can be solved using compressive sensing. Application of our framework to model and empirical networks demonstrates that sources in homogeneous and denser networks are more readily to be located. A surprising finding is that, for a connected undirected network with random link weights and weak noise, a single messenger node is sufficient for locating any number of sources. The framework deepens our understanding of the network source localization problem and offers efficient tools with broad applications.

Insects communicate with pheromones using sensitive antennal sensilla. Although trace amounts of pheromones can be detected by many insects, context-dependent increased costs of high sensitivity might lead to plasticity in sensillum responsiveness. We have functionally characterized basiconic sensilla of the ant Harpegnathos saltator for responses to general odors in comparison to cuticular hydrocarbons which can act as fertility signals emitted by the principal reproductive(s) of a colony to inhibit reproduction by worker colony members. When released from inhibition workers may become reproductive gamergates. We observed plasticity in olfactory sensitivity after transition to reproductive status with significant reductions in electrophysiological responses to several long-chained cuticular hydrocarbons. Although gamergates lived on average five times longer than non-reproductive workers, the shift to reproductive status rather than age differences matched the pattern of changes in olfactory sensitivity. Decreasing sensillum responsiveness to cuticular hydrocarbons could potentially reduce mutually inhibitory or self-inhibitory effects on gamergate reproduction.

Eusocial insects use cuticular hydrocarbons as components of pheromones that mediate social behaviours, such as caste and nestmate recognition, and regulation of reproduction. In ants such as Harpegnathos saltator, the queen produces a pheromone which suppresses the development of workers’ ovaries and if she is removed, workers can transition to a reproductive state known as gamergate. Here we functionally characterize a subfamily of odorant receptors (Ors) with a nine-exon gene structure that have undergone a massive expansion in ants and other eusocial insects. We deorphanize 22 representative members and find they can detect cuticular hydrocarbons from different ant castes, with one (HsOr263) that responds strongly to gamergate extract and a candidate queen pheromone component. After systematic testing with a diverse panel of hydrocarbons, we find that most Harpegnathos saltator Ors are narrowly tuned, suggesting that several receptors must contribute to detection and discrimination of different cuticular hydrocarbons important in mediating eusocial behaviour.

Ants are a highly successful family of insects that thrive in a variety of habitats across the world. Perhaps their best-known features are complex social organization and strict division of labor, separating reproduction from the day-to-day maintenance and care of the colony, as well as strict discrimination against foreign individuals. Since these social characteristics in ants are thought to be mediated by semiochemicals, a thorough analysis of these signals, and the receptors that detect them, is critical in revealing mechanisms that lead to stereotypic behaviors. To address these questions, we have defined and characterized the major chemoreceptor families in a pair of behaviorally and evolutionarily distinct ant species, Camponotus floridanus and Harpegnathos saltator. Through comprehensive re-annotation, we show that these ant species harbor some of the largest yet known repertoires of odorant receptors (Ors) among insects, as well as a more modest number of gustatory receptors (Grs) and variant ionotropic glutamate receptors (Irs).

Our phylogenetic analyses further demonstrate remarkably rapid gains and losses of ant Ors, while Grs and Irs have also experienced birth-and-death evolution to different degrees. In addition, comparisons of antennal transcriptomes between sexes identify many chemoreceptors that are differentially expressed between males and females and between species. We have also revealed an agonist for a worker-enriched OR from C. floridanus, representing the first case of a heterologously characterized ant tuning Or. Collectively, our analysis reveals a large number of ant chemoreceptors exhibiting patterns of differential expression and evolution consistent with sex/species-specific functions. These differentially expressed genes are likely associated with sex-based differences, as well as the radically different social lifestyles observed between C. floridanus and H. saltator, and thus are targets for further functional characterization. Our findings represent an important advance toward understanding the molecular basis of social interactions and the differential chemical ecologies among ant species.

Evolutionary games model a common type of interactions in a variety of complex, networked, natural systems and social systems. Given such a system, uncovering the interacting structure of the underlying network is key to understanding its collective dynamics. Based on compressive sensing, we develop an efficient approach to reconstructing complex networks under game-based interactions from small amounts of data. The method is validated by using a variety of model networks and by conducting an actual experiment to reconstruct a social network. While most existing methods in this area assume oscillator networks that generate continuous-time data, our work successfully demonstrates that the extremely challenging problem of reverse engineering of complex networks can also be addressed even when the underlying dynamical processes are governed by realistic, evolutionary-game type of interactions in discrete time.

There is a need for indicators of transportation-land use system quality that are understandable to a wide range of stakeholders, and which can provide immediate feedback on the quality of interactively designed scenarios. Location-based accessibility indicators are promising candidates, but indicator values can vary strongly depending on time of day and transfer wait times. Capturing this variation increases complexity, slowing down calculations. We present new methods for rapid yet rigorous computation of accessibility metrics, allowing immediate feedback during early-stage transit planning, while being rigorous enough for final analyses. Our approach is statistical, characterizing the uncertainty and variability in accessibility metrics due to differences in departure time and headway-based scenario specification. The analysis is carried out on a detailed multi-modal network model including both public transportation and streets. Land use data are represented at high resolution. These methods have been implemented as open-source software running on commodity cloud infrastructure. Networks are constructed from standard open data sources, and scenarios are built in a map-based web interface. We conclude with a case study, describing how these methods were applied in a long-term transportation planning process for metropolitan Amsterdam.

Accessibility is increasingly used as a metric when evaluating changes to public transport systems. Transit travel times contain variation depending on when one departs relative to when a transit vehicle arrives, and how well transfers are coordinated given a particular timetable. In addition, there is necessarily uncertainty in the value of the accessibility metric during sketch planning processes, due to scenarios which are underspecified because detailed schedule information is not yet available. This article presents a method to extend the concept of "reliable" accessibility to transit to address the first issue, and create confidence intervals and hypothesis tests to address the second.

Controlling complex networks has become a forefront research area in network science and engineering. Recent efforts have led to theoretical frameworks of controllability to fully control a network through steering a minimum set of driver nodes. However, in realistic situations not every node is accessible or can be externally driven, raising the fundamental issue of control efficacy: if driving signals are applied to an arbitrary subset of nodes, how many other nodes can be controlled? We develop a framework to determine the control efficacy for undirected networks of arbitrary topology. Mathematically, based on non-singular transformation, we prove a theorem to determine rigorously the control efficacy of the network and to identify the nodes that can be controlled for any given driver nodes. Physically, we develop the picture of diffusion that views the control process as a signal diffused from input signals to the set of controllable nodes. The combination of mathematical theory and physical reasoning allows us not only to determine the control efficacy for model complex networks and a large number of empirical networks, but also to uncover phenomena in network control, e.g., hub nodes in general possess lower control centrality than an average node in undirected networks.

Epigenetic inheritance plays an important role in mediating alternative phenotype in highly social species. In order to gain a greater understanding of epigenetic effects in societies, we investigated DNA methylation in the termite Zootermopsis nevadensis. Termites are the most ancient social insects, and developmentally distinct from highly-studied, hymenopteran social insects. We used replicated bisulfite-sequencing to investigate patterns of DNA methylation in both sexes and among castes of Z. nevadensis. We discovered that Z. nevadensis displayed some of the highest levels of DNA methylation found in insects. We also found strong differences in methylation between castes. Methylated genes tended to be uniformly and highly expressed demonstrating the antiquity of associations between intragenic methylation and gene expression. Differentially methylated genes were more likely to be alternatively spliced than not differentially methylated genes, and possessed considerable enrichment for development-associated functions. We further observed strong overrepresentation of multiple transcription factor binding sites and miRNA profiles associated with differential methylation, providing new insights into the possible function of DNA methylation. Overall, our results show that DNA methylation is widespread and associated with caste differences in termites. More generally, this study provides insights into the function of DNA methylation and the success of insect societies.

A challenging problem in network science is to control complex networks. In existing frameworks of structural or exact controllability, the ability to steer a complex network toward any desired state is measured by the minimum number of required driver nodes. However, if we implement actual control by imposing input signals on the minimum set of driver nodes, an unexpected phenomenon arises: due to computational or experimental error there is a great probability that convergence to the final state cannot be achieved. In fact, the associated control cost can become unbearably large, effectively preventing actual control from being realized physically. The difficulty is particularly severe when the network is deemed controllable with a small number of drivers. Here we develop a physical controllability framework based on the probability of achieving actual control. Using a recently identified fundamental chain structure underlying the control energy, we offer strategies to turn physically uncontrollable networks into physically controllable ones by imposing slightly augmented set of input signals on properly chosen nodes. Our findings indicate that, although full control can be theoretically guaranteed by the prevailing structural controllability theory, it is necessary to balance the number of driver nodes and control cost to achieve physical control.