Catch up on stories from the past week (and beyond) at the Slashdot story archive

typodupeerror
DEAL: For \$25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×

## Using Graph Theory To Predict NCAA Tournament Outcomes91

New submitter SocratesJedi writes "Like many technically-minded people, I don't have a lot of time to keep up with sports. Nevertheless, trying to predict the outcome of the NCAA men's basketball tournament is a fun activity to share with friends, family and colleagues. This year, I abandoned my usual strategy of quasi-randomly choosing teams and instead modeled the win-loss history of all Division I teams as a weighted network. The network included information from 5242 games played during the 2011-2012 season. From this, teams came be ranked using tools from graph theory and those rankings can be used to predict tournament outcomes. Without any a priori information, this method accurately identified all the #1 seeds in the top 5 best teams. It also predicts that at least one underdog, Belmont (#14 seed), will reach the Elite Eight. Although the ultimate test will be how well it predicts tournament outcomes, initial benchmarks suggest 70-80% accuracy would not be unreasonable."
This discussion has been archived. No new comments can be posted.

## Using Graph Theory To Predict NCAA Tournament Outcomes

• #### past history (Score:5, Insightful)

on Tuesday March 13, 2012 @09:01AM (#39337577) Homepage

wouldn't running the algorithm against past years' records and testing against past tournament results be the best possible test to tune the algorithm?

• #### Re:past history (Score:5, Insightful)

on Tuesday March 13, 2012 @09:35AM (#39337955)
I worked in a research group in college that worked on exactly this problem - predicting NCAA tournaments with a graph-theoretic approach. That is exactly how you test the algorithm. And the cited estimate of 70-80% accuracy seems made up. People who research the field know that there is far less certainty than that. At something like 20% confidence, your prediction should be something like 20%-90%.

The problem stems from the fact that we traditionally predict a team will win if it is a stronger or better team, and we use our graph theory to produce relative team ratings. And if each game of the tournament were played over and over again with the winner of the majority going to the next round, then our methods would work even better. As it stands though, we are trying to predict a single sampling from a probability distribution - which will necessarily have error. Informally, the real tournament has upsets (when a weaker team beats a stronger one). Our algorithms can't predict these, the best they can do is gain a better understanding than humans as to which team is better.

Add to that the fact that the tournament is structured hierarchically - a mis-prediction in the first round prevents you from even attempting to predict later games (and by NCAA bracket scoring, that counts the same as mis-predicting those later games). So early upsets can potentially have large negative outcomes on brackets.
• #### Our algorithms can't predict these, (Score:2)

Yeah, like when someone intentionally throws a game. As long as people are gambling (somewhere) and money is to be made, there is an opportunity and incentive to cheat. Get your graph theory to account for that!

Or maybe regression analysis is better like Levitt used to find cheating with Sumo wrestling and US student test takers in his book Freakonomics. (Awesome book BTW) ;)

• #### Re: (Score:2)

Yeah, like when someone intentionally throws a game. As long as people are gambling (somewhere) and money is to be made, there is an opportunity and incentive to cheat.

and as long as the NCAA allows everyone *except* players to make any money directly from their game at all, there's loads of incentive for players to do so.

• #### Re: (Score:2)

And the cited estimate of 70-80% accuracy seems made up. People who research the field know that there is far less certainty than that. At something like 20% confidence, your prediction should be something like 20%-90%.

If a coin flip is 50% accurate, than an extra 20% accuracy will give you 70%.

• #### Re: (Score:2)

The problem stems from the fact that we traditionally predict a team will win if it is a stronger or better team, and we use our graph theory to produce relative team ratings. And if each game of the tournament were played over and over again with the winner of the majority going to the next round, then our methods would work even better. As it stands though, we are trying to predict a single sampling from a probability distribution - which will necessarily have error. Informally, the real tournament has upsets (when a weaker team beats a stronger one). Our algorithms can't predict these, the best they can do is gain a better understanding than humans as to which team is better.

It's not just the single game problem - and even if you set aside upsets, the "stronger" team doesn't always win because as the coaches have been saying for years, it's about matchups. Teams have strengths & weaknesses - style of play, offensive & defensive skill sets of individual players, etc. A team with a tremendous front court but weak ball handlers is more likely to lose to a inferior team that has a high pressure trapping defense whereas it might beat a stronger team that doesn't use the same

• #### Predicting the top is easy (Score:5, Insightful)

on Tuesday March 13, 2012 @09:01AM (#39337581)

Everyone knows who the big names are who are likely to make it to the final four. It's predicting how things will go at the middle and bottom, where teams are much more likely to be evenly matched, that's really hard.

• #### Re: (Score:3)

You mean like penciling in Butler for the championship two years in a row? Or the final four matchup of Butler vs VCU?

• #### 70-80%? (Score:2, Informative)

by Anonymous Coward

Okay, you can get 50% accuracy just by flipping a coin.
If you go with "the higher seed wins", you get to 85% or so. Color me unimpressed.

• #### Re: (Score:3)

Should be lower seed (I am the AC).

• #### Re:70-80%? (Score:5, Informative)

on Tuesday March 13, 2012 @09:20AM (#39337755) Journal

And my numbers are off. In 2011, 43 times out of 63, the lower seed won for about a 68% win rate.

• #### Re: (Score:2)

Going off of the 2011 tournament for any generalized method of picking games is a bad idea. It was a particularly chaotic tournament for a variety of reasons. Having a system that failed last year is potentially a good thing because last year didn't work like the majority of tournaments do.
• #### Re: (Score:1)

Pretty sure you had it right the first time. Higher seed = lower number of seed.
• #### Just take last years results (Score:2)

You can get very reasonable results by just taking last years results. This works for most sports.

• #### Re:Just take last years results (Score:5, Insightful)

on Tuesday March 13, 2012 @09:22AM (#39337777)

That may work for pro sports, but not for college sports. In fact, because teams usually lose their nucleus after winning it all (players declare for the draft), it is rare for a team to make it to the final game two or more years in a row.

• #### Re: (Score:1)

by Anonymous Coward

I believe the point was that he could take last years season and build his dataset around the regular season games, create a bracket, and then match his bracket against the winning results.

• #### Re: (Score:3)

I disagree - how good a team is can vary wildly year to year. Coaching changes, injuries, age, experience and so on can play huge roles in how a team performs especially on a collegiate level where there is so much growth between juniors and seniors in terms of development. This is less so in professional sports but still relavent.
• #### Re: (Score:3)

Yes but last year's tournament had 2 small schools, Butler and VCU, in the Final Four. While Butler made it to the championship 2 years in a row, they were a surprise both times. VCU has never made it that far in the tournament and there were some TV pundits that said they should not have been selected for the tournament at all when the bracket was announced. VCU got to the Final Four after the same pundits predicted they would lose in the next game for every single game.
• #### How is this news? (Score:2)

People have been doing this, either knowing or unknowingly, since the inception of sports gambling.
• #### Re: (Score:3)

It's not. This is just a puff piece trying to drive hits to their site by mentioning the NCAA tournament.

• #### As a sports fan (Score:4, Interesting)

<jayhawk88@gmail.com> on Tuesday March 13, 2012 @09:23AM (#39337791)

Some problems I see. Disclaimer: I know there's a margin of error here as the author said, and I know my observations will be based largely on anecdotal evidence, making it inferior. But if sports were so easy to predict there would be no sports gambling.

- That's probably too far for Belmont; a #14 has only ever gotten as far as the Sweet 16, twice (Cleveland State '86, Chattanooga '97). Lowest seed to make an Elite 8 is Missouri in 2002 as a #12 . Belmont is actually going to be one of the more popular upset picks, but they would have to upset two far superior teams twice in 3 days.

- It's a bit too "chalk". #1 seeds generally survive the first two games (undefeated against #16's, 55-14 v. #8's, 59-6 v. #9's), but the #2's have it worse (only four losses v. #15's, but 58-21 v. #7's and 29-21 v. #10's). I know two #12's, a #13 and a #14 doesn't seem like "chalk" but historically it's much more likely that we'll see more #5-7 or #10-11's. To have only one #2 not make the Elite 8 and all the #1's would be almost unheard of.

- A #12 always beats a #5, but three of them doing so in one year would seem unlikely, as they're only 39-89 overall.

- Some of the other first round matchups seem a bit improbably. It has every #6 and every #7 winning, for example.

• #### Re: (Score:3)

I didn't read the article (yet), but I put together a game result predictor a couple of years ago that I ran against the tournament field with about an 83% success rate for the whole tournament. It was in the 93% range for the first two rounds. My algorithm utilized season long team statistics to get a team's baseline and then incorporated strength of schedule and seeding components. Just like you mentioned about how far a team has historically progressed from a specific seed, I used historical analysis of

• #### Re: (Score:3)

It is not hard to create a model that works perfectly on observed data. But then you run into the problem of overfitting [wikipedia.org] and your model loses any general predictability it had. To counter overfitting you need to have separate datasets for training and testing otherwise the model will depend on random details in the data. The proof of the pudding is in the eating and if you're model is good enough, you should be able to make money on sports betting on it.
• #### Re: (Score:2)

if you're model is good enough, you should be able to make money on sports betting on it.

Not against people whose model is just as good, and not (over the long term) against any professional gambling enterprise (legal casino or bookie) set up to profit whether you win or lose. A professional gambling outfit either takes a cut that negates all statistical advantages of having a good predictive method or they set up the odds so that they'll make back what they lost to you last time when you lose to them next time. The only people who make money reliably in gambling are those who have found a suck

• #### Re: (Score:3)

If there is a core of deep, personal knowledge about early upsets in the NCAA BB Tourney, it would definitely be at Kansas University (KU). Oh; I meant University of Kansas: UK. No, wait... what?
• #### "Like many technically-minded people, I don't... (Score:1)

by Anonymous Coward

... have a lot of time to keep up with sports."

Yes, if you enjoy sports, you must not be technically-minded. Tis for the plebes...

But, I bet you have time for Skyrim!

• #### Re: (Score:3)

At least in Skyrim, you're an interactive participant. That, and Skyrim isn't just a polite way for people to act out their base tribalistic instincts.

• #### Re: (Score:1)

Skyrim isn't a polite way to act out my base tribalistic instincts? Am I offending people when I slaughter entire towns of virtual Argonian civilians?
• #### Morale of the story... (Score:2)

...you're rich! 70~80% accuracy beats the 70~80% of people who don't know/use/master the graph theory, thus you're gonna win 70~80% of online bets.
• #### Re: (Score:3)

Not quite. Picking winners =/= winning at gambling. Margin of victory, aka the spread, comes into play. That is a bit harder to account for in these types of situations involving so much human variable. Granted, being able to identify some potential upsets could allow someone to bet big on those and become potentially rich.
• #### Re: (Score:2)

And then he has to persuade someone to take the bet. You can sure that betting establishments will pay someone to work out the odds at least as well as he does. It's okay for informal betting among friends, but if you're trying to make money then fleecing your friends only works a few times before you run out of friends...
• #### Re: (Score:3)

Ah, you would think that the casino sports book odds were the most accurate availibe and only determined by scientific study of the sports.

BZZZT! Wrong. Casinos need to make a profit. So they determine the *initial* odds by studing the sport, but then change the odds in reaction to the bets that are placed. They try to have equal amounts on both sides of a bet. They pay less to the winners than they get from the losers.

What's the point of pointing that out? Well, you have some pro gamblers who actually do m

• #### Re: (Score:1)

lol trusting a casino. betting exchanges are the future
• #### The joys of single elimination (Score:3)

on Tuesday March 13, 2012 @09:28AM (#39337869)

March Madness is notoriously hard to predict, partly because of the number of teams involved and also because of the single elimination system that I love so much. Its prevalent in few sports and makes each game mean a lot more, also opening the door for cinderalla to take her 15 minutes of fame. 7-game playoff rounds like they have in Baseball and the NBA tend to nullify those outliers. I honestly think that's a big reason for the success of the NFL too - every game and every play means a hell of a lot more when the best possible record is 19-0.

• #### Doesn't matter if it works (Score:2, Insightful)

by Anonymous Coward

Can you write a windows installer for it and sell it to gamblers?

• #### Nerd (Score:2)

Like many technically-minded people, I don't have a lot of time to keep up with sports.

The word you're looking for is "Nerd". It's OK to say it, it's in the title-bar of Slashdot.

• #### Re: (Score:3)

You know, for stereotypical nerd behaviour like communicating to each other in incomprehensible jargon and obscure references that other people don't get, obsessive behaviour, dressing up in ridiculous costumes for gatherings, etc, I've come to realize that nothing beats a hard-core sports fan.

• #### I'll go with the squid (Score:2)

Just have to find one with 32 tentacles. Or a large appetite.
• #### Behind the Curve (Score:1)

You're some way behind the curve if you want to make money sports betting on this. There is an extreme non-stationarity problem with basketball teams which inevitably means methods using past statistics will never be that successful. I know of professional basketball modellers who pay an army of students and the like to watch college games while clicking on hand-held devices to record second-by-second data on passes, interceptions etc. This data is then fed into their models and provides a very accurate pic
• #### *YAWN* (Score:2)

Between 70 and 80%. That's a HUGE difference. That means that compared to the other computerized systems out there [thepredictiontracker.com] you're either totally awesome or really suck.

That's like saying, "I did a lap in a Formula 1 car, and I'm either 15 seconds ahead of last year's world champion, or I'm a minute behind the field."

You haven't done this before, have you?
• #### A plug for Nate Silver's FiveThirtyEight (Score:1)

His statistical reasoning is always well described, so that if you disagree with his results, at least you understand why you disagree. He's got "picks" [nytimes.com] and a description of the system [nytimes.com] used to generate them.

The original article is an interesting network analysis exercise, but it is really limited by its assumption of no a priori quality data. (Any time you beat Kentucky or North Carolina or other perennial powerhouses, that's almost always a quality win.) Sagarin and LRMC follow similar logic, but without a

• #### Not enough time? (Score:4, Insightful)

on Tuesday March 13, 2012 @10:36AM (#39338601)

You don't have time to follow sports, but you have time to model "information from 5242 games played during the 2011-2012 season".

You could be honest and just say you don't really care, but get involved in the playoffs because everyone else is talking about it.

I'm guessing your level 80 warlock probably doesn't 'have time' either. :)

• #### Re: (Score:1)

That's a dark elf mohawk! Pity the fool!
• #### Re: (Score:2)

You don't have time to follow sports, but you have time to model "information from 5242 games played during the 2011-2012 season".

How is that a contradictory statement? He's so busy doing data modeling stuff that he doesn't have time to watch sports.

When someone says they "don't have time" to do something, it's generally because they're very busy with....gasp....other things!

• #### My Best Luck (Score:2)

It seems in office pools I do the best by picking favorite team colors.

• #### Re: (Score:2)

I "won" an office pool once without even playing. I told the guy that I could win the whole thing, but, as I didn't want to take their money through gambling, I would just tell him my picks after it was closed.

The problem? He was giving points to each "winner" based on their number. If a #1 won, you got one point. If a #12 won, you got 12 points. I just picked 9-16 the whole tournament through. (He admitted that they all would have hated me had I played.) After the first round, with 4 upsets, there w

• #### The problem is (Score:2)

There's too much data and too many variables. Even just inputting all the known, public data might significantly improve the accuracy, but there's also lots of unknown private data that can influence games. Algorithms like this can't account for things like the coach's son getting killed in an automobile accident the night before a game, or the star center getting hit with a bad flu. And when you make it complex enough to take in all that data, it still has to get all that data somewhere, which means it has

• #### Yes, I see... (Score:2)

.

... modeled the win-loss history of all Division I teams as a weighted network. The network included information from 5242 games played during the 2011-2012 season. From this, teams came be ranked using tools from graph theory ...

... you obviously don't have enough time to keep up with sports.

#### Related LinksTop of the: day, week, month.

"The eleventh commandment was `Thou Shalt Compute' or `Thou Shalt Not Compute' -- I forget which." -- Epigrams in Programming, ACM SIGPLAN Sept. 1982

Working...