I just returned from Durham, North Carolina where I was at the Harambee 2010 Social Networks for Educators workshop.* I was there wearing two hats: 1) as someone who is qualified to talk about teaching a social networks course (using this text) and  2) as a teacher interested in using social networks to get high school students interested in social networks.** There were about 40 other academics there interested in using social networks in education, from all sorts of disciplines: computer science, communications, sociology, and education mostly.  The goal of the conference was to assist educators in 1) developing new courses using social networks, 2) finding ways to implement social networks into existing courses and 3) help students develop better critical thinking skills.

I came into the conference with the following thought: the teaching of social networks can be divided into a simplex like below, where a class is somewhere along the boundary.  This leads to classes which are a combination of sociology, mathematics and engineering.  The study of social networks is a discipline in itself and each field has its own approach.

In retrospect, I was thinking too narrowly.  Rather than being a discipline in itself, social networks are a great pedagogical tool to reach some other learning goal. For example, for students early in their CS education, social networks make a great introduction to algorithmic and game theoretic thinking. For sociology students, social networks are a great introduction into statistical analysis and complex systems.  Rather than teaching social networks as an end in itself, there are much broader goals that can be accomplished.  This is definitely a skill I can take into a K-12 classroom in the fall; I conjecture that high school students certainly know about social networks (i.e. Facebook) and are vaguely familiar with the concept of network.  This can be leveraged with good examples to help students develop critical thinking skills: many things can be modeled as networks: economies, ecologies, supply chains, etc.  Recognizing networks is a skill that every person in our modern society should have, they’re so pervasive.

A couple random highlights of the conference:

Ben Shneiderman’s inspirational talk about how the future of CS is modeling computational AND human behavior.  His NodeXL project is really impressive and would work great for an introductory networks class.

Jon Kleinberg‘s keynote talk at the end of the conference.  He concisely summarized what I was trying to say the day before, when I spoke about teaching a course using his book.  It was nice to hear another CS theorist talk at the conference, I felt a little lonely in CS theory-land at times.

That summarizes my Harambee adventure this year. Hopefully, next year, I’ll get invited back to talk about my experience using social networks to encourage high school students.

* – The conference was sponsored by the NSF CNS-0722288. Thanks NSF!

** – I am a NSF GK-12 Fellow, so I will be spending my fall in the classroom with a teacher! Thanks again NSF!

This summer, I am in a reading group working through the book Complex Adaptive Systems. I don’t have the book yet but a PDF of the first two chapters and I thought I would post my thoughts here before I go to the talk this afternoon.

I was originally a big fan of complex systems. I took a few courses at Michigan on complex systems and I’m very familiar with statistical techniques for running simulations.  I even have a sample NetLogo widget on my website somewhere of a theoretical model from my adviser.  Running simulations is kind of exciting and sexy – you usually see graphics of how agents in a system interact and plot out the results.  Then, using stats and inference you can make awesome claims about how the system works and try to infer how this relates to things in the real universe.  This is cool and fun and what made me interested in going into academia.

But then I started my PhD program in the theory department at Northwestern. In theory, we try to make much grander claims: we want to show that something is true or false in all cases or for wide ranges of classes, not just a specific instance.  For example, we want to show certain classes of algorithms can be computed in a certain amount of time. As long as we can show an algorithm is in that class of problems, then we instantly know something about it.  Theoretical findings are powerful but hard to reach, they require extensive mathematical proofs and a great deal of intellectual and logical rigor.

Simulation is useful when you’re using it to compare a theoretical finding against some form of empirical data.   In other words, you’re given some actual real world data points.  You can simulate the theoretical models and show that the data fits your theory.   Verifying theory is important however I contend it is not as powerful of a finding as the theoretical result itself.

Where do complex systems come into this? The authors of the aforementioned book argue that some systems are too complex: we can’t break them down into their components. Therefore, this implies that they argue that theoretical results cannot be found for these systems! Perhaps the systems are too complex; there are too many of what accountants call “intangibles”, things that have value but cannot be counted as assets.  I am not yet convinced of this line of argument; theoreticians should seek to develop mathematical models and tools precisely to model these cases, such that we can develop a better understanding of how our world is classified.

Over the past few weeks (and for the next two weeks) I’ve been captivated by the World Cup. As an American, this is stereotypically unusual; most Americans are pretty apathetic about the most popular sport on the planet.  I’ve even been watching games that don’t involve Team USA.

However, I know I’m not the only American excited about the game; I see the (mostly American) twitterati going wild over game results.  I read an article yesterday about how bars in the big American cities are packed at 9am for Team USA games. People in places like Washington DC, Chicago, New York, Los Angeles, Seattle are excited about the games.  So, I ask – who are these people packing bars at 9am to watch soccer? Do they have jobs? Here in academia, I can spend a few hours in morning in my office or at home with the game on ESPN3 on my computer.  What about everyone else?

I planned on typing up a long blog post about this; making a case for a soccer intelligentsia. I conjecture that the average US soccer fan is white, grew up in the suburbs, works in some creative form (academia, design, etc), drinks microbrews, lives in an urban area, and probably has a graduate degree.  This lead me to some googling and clearly I am the 1,329,401st person to think about this problem.  A better summary of my thoughts about this can be found in an already written article over at Slate.com

I was doing some work today, catching up on some reading about social choice functions.  Most of the literature was written by Kenneth Arrow, for which he won a Nobel Prize (among other work on general equilibrium).  On his wikipedia page, I stumbed up on this 2009 paper Some Developments in Economic Theory since 1940.

Anyone who has taken a PhD-level micro course should read this text. It provides a concise guide to the development of modern thinking about game theory, general equilibrium theory, and mathematical economics along with a pleasantly written autobiography of Dr. Arrow.  I recommend.

My big plans to write a proof of the day already tanked! On day #1. In my defense, I’ve been writing proofs all weekend and didn’t feel like writing another one for the blog. Primarily they have been proofs about linear algebra, algorithmic game theory, and microeconomics.  I think I have a good one on supermodularity coming later this afternoon. This is an econ concept that, for all I can tell, is not used outside of economics.

In other news, there is a really great post on the Lovasz Local Lemma over on Lance Fortnow’s blog.  I have to admit, I have had three different classes and own two books that talk about the local lemma. However, I still have no idea what it means. The blog post is a bit more insightful and I feel like I’m getting closer to full understanding; but still not there yet. The LLL is like this pinnacle of academic achievement for me. If I can understand the lemma, then there is nothing stopping me from conquering all of discrete mathematics.

In another epic fail moment, this blog has started getting hits for the search term “paul milgrom sucks”. For those who don’t know,  Paul Milgrom is a famous economist and researcher of auction theory. He’s one of the fathers of the modern day FCC spectrum auction and wrote much of the auction literature that exists. He was given an award here at Northwestern, which I blogged about at the time.  In a later blog post, I mentioned that “Windows Vista Sucks”. Google’s algorithm connected the terms and now I get hits for that search query.  So, I would like to clear the air here; I don’t think Paul Milgrom sucks, in fact, I own several of his books and think he is an excellent writer. His work on the FCC auctions is phenomenal (I think the companies he consults for probably agree) and he is a good speaker. In fact, I would argue that he is probably a good candidate for a Economics Nobel some day.

This is my very first proof of the day, so the proof is probably wrong (although, I hope not).

Source: Linear Algebra Done Right by Sheldon Axler – p.59 Question #9

Prerequisite: Some advanced linear algebra

Claim: Prove that if is a linear map from to such that , then is surjective.

Idea: In the problem, they give us a very specific null vector of T.  Since we know this, we can derive some information about . Then, we can construct a vector, put it through the function and show that it is surjective by construction by looking at the dimension of of the input and output.

Proof: We know that and that , and want to show that T is surjective.  By definition, for T to be surjective, its range must be equal to the codomain of the linear map. Therefore, if , then is surjective. To show this, let . Then, we know that .  Since and the dimension of the resulting mapping is 2, we have shown that and hence is surjective.

I’m going to try an experiment with this blog. In an effort to develop better proof writing skills, I am going to try to write a proof per day on here. Sometimes, it will be something assigned to me as homework and sometimes, it will be something random that I want to prove. Either way, at this moment, I feel like I am a horrible proof writer. Spending a dedicated amount of time each day (probably each weekday) will help be improve. I should disclose that sometimes my proofs will be really bad (or not even right), so caveat emptor.

At first, I considered starting a separate blog just for the proofs but then I realized that I’d have to reinstall all of my themes and modules that I already configured for this wordpress install. It took me long enough to get this one right that I don’t want to go through the process again. Maybe I’m lazy or maybe WordPress is not very scalable for this kind of thing.  So, I created a wordpress category “POTD” (Proof Of The Day).  I then went through and hacked all of my custom db calls to the wordpress library to separate posts with category=1 (uncategorized) versus category=92 (potd). Hopefully, it won’t be confusing for my readers.

You can view my first Proof of the Day!

One of my colleagues in my lab here sent me a link to this paper, by Sitaram Asur and Bernardo Huberman at HP – Predicting the Future with Social Media (PDF). I’m not sure if this was published in any conference proceeding or a journal. Either way, their findings are really cool.

They take data collected from the Twitter Search API and extract data about 24 big Hollywood films — i.e. how many times people talk about the movie, post a link to the film’s website, etc.  Then, they take this data and compare it to data from the Hollywood Exchange and the box office returns.  They show that Twitter chatter is a tremendously accurate predictor (R^2>.90) for the box office returns. Even better, they show that for the films they selected it is a better predictor than the Hollywood Exchange.  They expand on their findings by considering the “sentiment” of the tweets and show that this is also a significant indicator of week 2 movie success. The twitter chatter is a good analog to traditional word-of-mouth marketing.

This is the first quantitative finding that I’ve seen that shows a social network is a good indicator of some product’s success. There are lots of business books out there claiming that viral and social marketing is going to revolutionize the world.  The general interpretation seems to be: if we plaster our product all over social networks than this automatically equates to higher profit. The above findings show that this is generally not always the case; social networks are more of a conduit for traditional word-of-mouth advertising. Simply just plastering social networks with your promotional material does not appear to be a good predictor of your early performance.  Furthermore, if people think your product sucks, negative sentiment among the social network users does translate to poor performance later on.   So, I guess it still pays to make a good product, rather than unnecessarily spending money advertising your promotional material on social networks.

This evening, I had a chance to go do some work with the Meaningful Science Consortium.  The consortium is a group out of a few Chicago-based Universities that advocates teaching more science in inner-city Chicago schools.  My task this afternoon was to grade some of the student projects, which were assigned in advance.  For the chemistry project, they were tasked with inventing some kind of board game to help other students learn about the periodic table. For the physics project, they were to design a roller coaster and calculate the requisite numbers (i.e. velocity, kinetic energy, etc).  The project that I didn’t grade but was the most excited about with the 9th grade biology project.

Their project was to design a school building in Florida, with certain guidelines (had to be three buildings, you have a predesigned plot of land, etc).  Their primary constraint, was to not kill off a specific tortoise species that existed on this plot of land.  The tortoise existed in a complex food network.  The student’s goal was to place the buildings in such a way as to maintain the ecosystem while still constructing a functional campus.  They had to develop an objective along with more “constraints” and “considerations”.  Further, there were some additional tasks which are now escaping me.  Basically, they couldn’t just drain the swamp and build the school.

My immediate response: Awesome! This is a computer science / operations research problem!  Essentially, the students were tasked with writing a linear program; maximize some objective function with respect to (binding) constraints. Even more interestingly, their constraint involved a graph! With node dependencies!  This is the kind of program that researchers who work in algorithm design or optimization struggle with every day — how can we design better algorithms and solution concepts for these problems? Even better, this is an interesting and applied problem that includes finding ways to protect the environment with human considerations.   Academics sometimes forget the reason that they consider these problems in the first place; focusing on making “the numbers work” and forget about the interesting ways this research can improve the human condition.

I hope stuff like this inspires a new generation of students interesting in questions of optimization, algorithm design, and similar topics.  We need more people thinking about these kinds of problems and developing new approaches.

Over the spring break, I’ve really been enjoying watching many of the videos from the TED conference. It would be such an honor to be able to go to that conference some time. I guess I better start writing!

They haven’t posted two talks from this year that I’m looking forward to: Stephen Wolfram and Moot. Wolfram is a scientist, author, and software developer.  His talk will probably be interesting and I expect him to put in many plugs for Wolfram Alpha.  Moot, on the other hand, is a the kid that started 4chan (NSFW). I have no idea what the hell he is going to talk about. Caturday? Memes? I can’t wait until his talk gets posted.

Anyway, as a bit of a secular humanist, here is the video I’ve enjoyed the most from the 2010 talks: