2012 Abstracts

Influence in Social Networks.

Benjamin Lundell, University of Washington

The behavior of members of a social network has been studied for many years. The traditional approach has been to look at the aggregate behavior of the network, and then average this aggregate over the network's users to determine a "representative member" of the network. In particular, this method assumes that each member acts independently of his or her peers and ignores the influence one member might have on another. In the last ten years, computer scientists and physicists have developed new approaches to studying this problem which are based on the assumption that a members' peers greatly influence his or her behavior. Thus, these models raise the question, "Who are the most influential members of a social network?" In this talk, I'll discuss some ideas on how to answer this question, and share some results of an ongoing project about political influence in the United States. This is joint work with Chris Aholt.

Towards generating random mammalian genomes.

Marni Mishna, Simon Fraser University

Genome arrangements, a major mechanism of evolution, shuffle genetic material along chromosomes. Thus, a now standard approach models groups of close genomes as signed permutations. The correct data structure to study permutations in this context is the common interval tree. In this talk we will describe the process of considering tree parameters to refine the class of common interval trees (hence permutations) to those that represent mammalian genomes well. These refinements are particularly amenable to Boltzmann random generation and analytic enumerative techniques. Work in collaboration with Mathilde Bouvel, Cedric Chauve, Rosemary McCloskey, Cyril Nicaud and Carine Pivoteau.

Formal Identification of DC Operating Points in Integrated Circuits and some Lessons in (Ir)Reproducible Research in Computational Math

Ian Mitchell, University of British Columbia

A DC operating point is an equilibrium toward which a circuit will be drawn for sufficiently nearby initial conditions when any inputs are held fixed.  DC operating points may or may not be desirable features in a circuit -- in an oscillator they represent lockup, but in a memory element they are the mechanism whereby discrete state is
stored.  Consequently, it is useful to identify a circuit's DC operating points.  Because the circuit is naturally drawn towards them, the most common technique to identifying such equilibria is through simulation; however, it is quite possible for the domain of attraction of an equilibrium to be small enough that simulation is unlikely to find it, yet large enough to cause occasional problems.

In joint work with Mohamed Zaki & Mark Greenstreet, we strung together a collection of public software from the formal verification and numerical analysis communities to rigourously identify and classify all potential DC operating points for surprisingly complex circuit models.  Unfortunately, the resulting workflow has proved fragile, and significant effort would be required for reproduction and/or extension.  In the second half of the talk I will discuss some tools and techniques that would have significantly improved the reproducibility of the results had they been adopted.

Venn diagrams and tatami tilings: vignettes from computational mathematics.

Frank Ruskey, University of Victoria

In this talk I will explain how computation has helped me and my students in resolving certain mathematical questions, via two specific recent examples. In the first example, we consider the problem of constructing a simple rotationally symmetric 11-Venn diagram. This problem was open for about 40 years and several incorrect solutions were proposed. Initially the problem seemed to be beyond the reach of exhaustive searches, but our recognition of a new type of "near-symmetry" in Venn diagrams suggested that searching in a certain reduced solution space might be fruitful --- which indeed it was. In the second example, we consider a tiling problem first investigated by Don Knuth. On the basis of his computations it seemed that the generating function for counting those tilings was I(z)*S(z) where I(z) was a mysterious irreducible polynomial and S(z) was a well structured and predictable. We have proved that S(z) is what it seemed to be, and revealed many interesting properties of the irreducible I(z), but its exact expression is still not known. [The students mentioned above are Khalegh Mamakani and Alejandro Erickson.]

Spectral Analysis and Dynamical Behavior of Complex Networks.

Ljiljana Trajkovic, Simon Fraser University

Discovering properties of the Internet topology is important for evaluating performance of various network protocols and applications. The discovery of power-laws and the application of spectral analysis to the Internet topology data indicate a complex behavior of the underlying network infrastructure that carries a variety of the Internet applications. In this talk, we present analysis of datasets collected from the Route Views and RIPE projects. The analysis of collected data shows certain historical trends in the development of the Internet topology. While values of various power-laws exponents have not substantially changed over the recent years, spectral analysis of matrices associated with Internet graphs reveals notable changes in the clustering of Autonomous Systems and their connectivity.