Inlägg October 2009
2009-10-24 23:42
Solving the Good Will Hunting problem
I've seen the movie Good Will Hunting from 1997, starring Matt Damon in the role as a mathematical gifted janitor, twice. The first time I hadn’t taken a course in graph theory, the second time I had. Regarding the mathematical aspect of the movie, it makes all the difference. The second time I could actually understand the problem the professor posed when he threw down the gauntlet. In the movie the MIT professor stated a, supposedly, very tough problem that they had worked on intensely for almost two years before they were able to solve it. It reads:
"Draw all the homeomorphically irreducible trees having 10 vertices, such that no vertex has degree 2."
In plain words, connect ten dots together with lines such that all dots are connected to at least one other dot. Further, there must only be one path from any dot to any other dot, which means that circles are not allowed. Lastly, all dots must have 1, 3, or more lines connecting it to other dots, but not 2. Now draw all the different figures that satisfies the requirement.
That's what the gifted janitor did on the white board in the hallway.
Sounds simple? Well, it is – surprisingly simple actually.
In reality, the problem is no harder than any other high school problem. The real problem is quite different, namely that we accepted it was hard because Hollywood said so. A corollary to this claim could be to check the Internet and realize that many people already have solved the problem and some even before the movie. Another corollary could be to spend the next 10 minutes or so to solve it yourself, tell someone you know that has seen the movie, and then watch their reaction.
So, the only thing left now, is to challenge you to solve the problem and to present the solution.
This week I challenged Erik Forsberg, Avega Öresund’s .Net consultant. He solved the problem before he zipped his morning coffee a third time. Can you?
I've hidden the solution from plain view here.
Postad av Martin Kaarup
Kommentarer (1)
Kategorier:
Graph Theory
2009-10-16 09:14
My scale-free contacts
One drawback of returning from Avega’s 2009 conference in Karpathos, Greece, is having a head full of ideas and recharged batteries. It manifested itself a couple of days ago. Around bed time, I felt a sudden urge to map all my contacts, and their connections as well, on the professional network site LinkedIn. Supposedly, I should be able to see the scale-free invariance property of a social network.
That night I went to bed at around 4 a.m. and I was still miles from completing my data gathering. I didn’t finish the next night either – or the next. The fourth night it dawned on me. The very raison d’être for my investigation, the scale-free invariance, was the problem.
Since LinkedIn is a typical social network site, it follows the power law function which, simply put, states that the vast majority of people would have few contacts, but also that there exist a small handful of people that would have lots and lots of contacts.
And so, on the fifth evening, I haven’t finished gathering the data yet. I expect to be done in a week or so, and then I can finally begin automate a solution to connect the dots, so to speak. On the positive side, I have finished connecting my 1st degree contacts, and if they are ordered by number of connections, it’s possible to observe the scale-free invariance pattern – albeit with some minor variance, mainly because the sample set is small. It’s truly remarkable.
As can be seen, I’m missing a person; preferably, one with a really huge number of contacts. And more than 500 of those would be nice. This would fix the vertical asymptote that breaks off at around 325 instead of going straight up. I’m not worried though, because the nature of the power law itself also states that, in time, such a power law-conformant person will emerge.
The center of the universe is… me
In my small universe on LinkedIn, I’m the only one that knows everyone else. While some of my contacts know each other, along with some people outside my network, it’s not the case that everyone knows everyone else in my network, i.e. my network is not a complete graph.
In case you're wondering, I’m the dot labeled “29” that sits in the middle and connects the two big clusters of people to the left and to the right. I should mention, that the labels on the dots indicate the number of people that each person knows in total. Also, I have sized the dots relatively and accordingly.
There really isn’t much interesting to say about this small universe, except from the fact that if a person from the left side connects to a person from the right side, I will be rendered utterly worthless as a broker between small worlds .
As I mentioned earlier, I expect that in a few weeks time I have gathered, automated, and analyzed enough data from my contacts and their connections to write a follow-up. Then we can begin to talk about all kinds of interesting things, like for instance the best way to vaccinate an entire population against the hyped swine-flu, with the fewest possible vaccines.
References
- Albert-Laszlo Barabasi, Linked: How Everything Is Connected to Everything Else and What It Means, Plume, 2003
- Brian Uzzi & Shannon Dunlap, Managing Yourself: How to Build Your Network, Harvard Business Review, December 2005
- Kurt Mehlhorn & Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer-Verlag, 2008
- Malcolm Gladwell, The Tipping Point: How Little Things Can Make a Big Difference, Back Bay Books, 2002
- Rob Cross, Jeanne Liedtka & Leigh Weiss, A Practical Guide to Social Networks, Harvard Business Review, March 2005
Postad av Martin Kaarup
Kommentarer (3)
Kategorier:
Graph Theory
Scale-free Networks
Self-organization