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 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.

Yesterday, I finished my semester project for my randomized algorithms course.  I started the project almost a month in advance since I knew there was going to be a significant amount of research and reading to do. The original plan was to create a mathematica module for processing Exponential Random Graph simulations.  The concept is this:

You have some observed social network, collected from data or in the field.  You want to know things about the relationships of people in the network, like, how likely are people to form connections randomly or do they form connections based on other sociological things. For example, if Alice is connected to both Bob and Eve, is there likely going to be a relationship between Bob and Eve? In other words, do they complete the triangle?  Standard random graph models can’t test for this but we can use exponential random graphs. The output of the algorithm is a set of values that indicate how strong various network structures are.

My presentation went alright. In the mathematical sciences (engineering, math, etc) proofs are the only method you can use to show something is true. In the applied sciences (communications, sociology, statistics) the only method you can use to prove something is statistical inference. So, explaining inference to engineers is difficult since they don’t encounter it (I think they should!). Explaining math to social scientists is challenging since they’re not familiar with proof techniques (what is the contrapositive again?)

I haven’t finished the paper yet (almost done) and I will post the results here shortly. In the mean time, I’ve compiled some of my thoughts about approaching this topic in the future. This is what I want to study (using computer science theory in other fields) so I am noting this for posterity.

• Use more visualizations to explain inference.  Mathematicians love proofs and it is ok to use math on your slides. However, when talking about statistical inference, you’re looking at how something observed fits something hypothesized.  The best way to do this, I suspect, is to plaster a N(0,1) curve on the slides and point to where things fit.
• For social networks stuff, use examples! I used a couple examples in my slides and people found it helpful and interesting.  There are so many great visualization tools for social networks, so I should use them more.
• Take a course on econometrics.  I’m doing this next year.  Econometrics is using statistical inference to reach economic conclusions. There has to be some good techniques they use.
• Write the slides AFTER you write the paper. In this case, I was so worried about the presentation, I did it before I wrote the paper and ended up rushing the paper.  Next time, I’ll flip it and spend time worrying more about visualizations and teaching people than plastering equations on slides.

Hello blog-world. I haven’t blogged in a while. I’ve been working on some pretty cool research, including a Mathematica implementation of the Metropolis Algorithm for social network (ERGM) analysis. I will add it to the site when I complete it.  You should be excited.  Anyway, for the sake of record-keeping, here are the courses I am looking forward to taking next term here at Northwestern.

• Applied Math 495 – Dynamical Processes on Networks – This is an applied math course, so I expect it to be pretty challenging. However, it is on my research specialty, social networks.  I’m taking this course with an undergrad friend of mine who really knows his stuff, so this should be a great course. It’s taught by Dirk Brockman, who has done some cool research.
• Economics 410-3 – This is the third series in the dreaded PhD level economics sequence. The theme for next quarter is game theory.  The theme this semester was general equilibrium theory. So, yeah. I’m happy to be moving on to game theory, something I’m more comfortable with.  The course is taught by Michael Whinston, the guy that co-wrote the infamous Mas-Collell (MWG) textbook.  I’m looking forward to this course but I’m also terrified.
• Computer Science 495 – Algorithmic Mechanism Design – One of my co-advisers, Jason Hartline is teaching this course. His research speciality is mechanism design and his last few papers have been focused around bayesian and prior-free settings. I expect this course to be rigorous mathematically but have lots of applied uses in research, especially since I started at NU wanting to do computational mechanism design work.
• I’m also auditing a course taught by Uri Wilinsky on NetLogo, a really cool agent-based modeling software that I used for a while when I was at Michigan. The course is a 300-level, so if the workload isn’t too bad, I may take it for credit. Otherwise, I will just audit it and work at getting better at the software which can be used in a lot of simulation settings, especially when plugged into Mathematica.

Anyway, my final project for the randomized algorithms course is due in a few weeks, so once I complete it, I will post the assignment and the mathematica plugin on my website. So far, it seems like it may be a helpful overview of the research into exponential random graph models (ERGM) for those interested in algorithms.

RandQSLet’s talk about algorithms! I’m taking a randomized algorithms course next semester and having never taken regular algorithms, I figured I should do some self-study first. So, basically I’m working my way through chapters 1-5 of the Randomized Algorithms textbook.  The book is actually pretty reasonable, even for someone who hasn’t taken algorithms before.  Ok, now let’s talk about something cool: RandQS.

RandQS is short for Randomized Quick-Sort. It’s an efficient algorithm used to sort lists of numbers.  This is important because, for computers, sorting isn’t necessarily an easy task. If you gave a computer a long list of numbers, it would have to compare every number versus every other number and do this recursively – i.e. look at all possible combinations. This is not very computationally easy!

So, we use randomized algorithms. RandQS works like this:

1. Pick a random number from our list.
2. Take all of the numbers bigger than our random number and make a list. Do the same with the numbers smaller. So you’ll have two new lists.
3. Go back to step 1 with our two new lists. Do this as many times as we need to.

Why is this important? First, this algorithm runs faster than its non-randomized deterministic cousin! Secondly, it’s really easy to implement. This is huge for people who have to design algorithms for sorting enormous quantities of data – like the people who build the sorting engine for MySQL, for example.

Since I am Mathematica geek, below is the relevant bit of Mathematica code, for those of you coming from Google looking for it. Note that this algorithm only works with unique sets but could probably be easily modified to work with sets that have duplicates. You can download the whole notebook file down at the bottom.

SetSize = 100;
S = RandomInteger[{0, 100}, SetSize]
RandQS[sss_] := Module[{sOne, sTwo, y}, (

    (* pick our random element  *)
    y = RandomChoice[sss];

    (* build set larger and set smaller by doing comparisons*)

    sOne = sTwo = List[];

    If[# < y, AppendTo[sOne, #]] & /@ sss;
    If[# > y, AppendTo[sTwo, #]] & /@ sss;

    If[Length[sOne] > 1, sOne = RandQS[sOne]];
    If[Length[sTwo] > 1, sTwo = RandQS[sTwo]];

    Return[Flatten[Join[sOne, {y}, sTwo]]];
    )];
RandQS[S]

Download RandQS.nb