You have a graph. It’s very dense. You have this elliptic operator...
May 22, 2018 8:50 AM Subscribe
Now-retired Baltimore Ravens guard and center John Urschel discusses his favorite mathematical theorem (one for the graph theory fans), among other things. This is generally what people do at My Favorite Theorem.
Well, 'similar game, different rules' is kinda math in a nut shell.
posted by kaibutsu at 9:38 AM on May 22, 2018 [2 favorites]
posted by kaibutsu at 9:38 AM on May 22, 2018 [2 favorites]
Huh, John Urschel quit the NFL over concerns about CTE and now is a PHD student in math at MIT.
posted by octothorpe at 9:48 AM on May 22, 2018 [7 favorites]
posted by octothorpe at 9:48 AM on May 22, 2018 [7 favorites]
he was a PhD student in math at MIT before quitting the NFL, and a couple of his papers give his institution as “Baltimore Ravens”.
posted by vogon_poet at 9:51 AM on May 22, 2018 [12 favorites]
posted by vogon_poet at 9:51 AM on May 22, 2018 [12 favorites]
There's a transcript! Amazing!
posted by tobascodagama at 9:52 AM on May 22, 2018 [1 favorite]
posted by tobascodagama at 9:52 AM on May 22, 2018 [1 favorite]
“It’s the spectral sparsifier of beers.” When I die and go to heaven, all beer commercials will sound like this.
posted by mondo dentro at 9:52 AM on May 22, 2018 [3 favorites]
posted by mondo dentro at 9:52 AM on May 22, 2018 [3 favorites]
I sure wish I could understand anything they're talking about.
posted by runcibleshaw at 10:13 AM on May 22, 2018 [2 favorites]
posted by runcibleshaw at 10:13 AM on May 22, 2018 [2 favorites]
Yeah, I hear you runcibleshaw. I feel like I'm a bit mathier than the average bear, but that whole explanation definitely started with an assumption of baseline knowledge that I did not have. Like, I understood the shape of the conversation, but that's about it.
posted by solotoro at 10:21 AM on May 22, 2018 [1 favorite]
posted by solotoro at 10:21 AM on May 22, 2018 [1 favorite]
At least it's a branch of math I know a little bit about (via CS school).
posted by atoxyl at 11:01 AM on May 22, 2018
posted by atoxyl at 11:01 AM on May 22, 2018
In case anyone wants it, I think this is (a version of) the Batson, Spielman, & Srinivasta paperat arXiv.
posted by mhum at 11:52 AM on May 22, 2018 [1 favorite]
posted by mhum at 11:52 AM on May 22, 2018 [1 favorite]
Ahhh I know Evelyn through some summer math programs and this is SO COOL! I had forgotten she did this podcast!
posted by augustimagination at 2:53 PM on May 22, 2018
posted by augustimagination at 2:53 PM on May 22, 2018
There are a few different formulations of the Laplacian but here's one that's reasonably easy to explain.
I've started a new social network called ContrariaNet. People can join and friend each other and all that. You get to see how many friends you have (that's called your "degree").
But the heart of ContrariaNet culture is that it is populated entirely by contrarians. Whenever you post anything, you become more convinced of it by an amount proportional to your degree. Obviously your pronouncements matter; you've got such a friend count! But your friends become slightly less convinced of any position you post about. After all, they're contrarians, too.
Let's put this into numbers. In particular, a big-ass matrix of numbers. Each person gets a row and a column. Every entry in the matrix represents a pair of people- the row-th person and the column-th person. Along the diagonal of the matrix (the cell in the 1st row and 1st column, the cell in the 2nd row and 2nd column... etc) each entry is a pairing of a person with themselves; put their degree there. When the row-th person of a cell is friends with the column-th person, put a -1 in that cell. Otherwise you don't know each other and the cell gets a zero.
This map of influence is ContrariaNet's Laplacian matrix.
This has some interesting dynamics. You post something inflammatory espousing position X; all of your friends post position Y pieces in response. But your friends' friends see all those Y pieces and post their own X responses and the whole network fairly vibrates with activity*.
After ContrariaNet gets really big and maybe leaks data to a secretive propaganda outfit in cahoots with a hostile foreign power everyone decides to eff that noise and go to a different social network, ButActuallist. ButActuallist has the same rules and everything as ContrariaNet, with just two differences:
1. In ContrariaNet, you could friend as many people as you wanted, but in ButActuallist, there's a strict limit on your friend count.
2. ButActuallist lets you assign a "weight" to each friendship that captures exactly how much you are put off by that friend's opinions, on a scale from 0 (who is this person again) to 1 (Cillizza).
Because everyone has far fewer friends than they used to, this migration from ContrariaNet to ButActuallist is called "sparsification".
The theorem they're talking about is that, bizarrely, given a big, dense graph like ContrariaNet, you can reproduce its Laplacian pretty closely when everyone moves over to ButActuallist, despite the austere friend limit. And that friend limit can result in a greatly reduced total number of friendships in the graph, but just having weights on what few friendships remain allows ButActuallist to have the same sort of connectivity characteristics and dynamics.
*When people use the word "spectral" in connection with graphs, you can imagine they're treating the graph like a medium along which stuff can propagate. An "eigenvector" of a graph is an allocation of stuff-amounts-per-node that, after you apply the rules of stuff-propagation that you've adopted, will result in proportionally-the-same stuff-amounts-per-node. Maybe the stuff-per-node will grow or shrink or flip negative but it will do so uniformly, by the same amount per node.
The talked-about theorem gives a method for sparsifying a graph (reducing the number of edges) that roughly preserves the eigenvectors of the Laplacian; that is, it roughly preserves which allocations of opinions to people are stable-ish in a social network of contrarians. It also says how the friend limit ties into exactly how accurately the Laplacian is preserved.
Finally, Urschel mentions that the method is cool and beautiful but not computationally useful. Here's why: when you have only a few people, there's not much difference between ContrariaNet and ButActuallist; the friend limit doesn't change much. The technique only gets useful when the networks get huge. But actually going through the work of finding the right weights for ButActuallist takes an amount of time proportional to the cube of the number of people. So if you're like Facebook and you have 3 billion-ish members, your computer has to do (3 billion)*(3 billion)*(3 billion) = 27 octillion steps to find the right weights. A bit much. While the network is nice and easy to work with after sparsification because it has dramatically fewer connections, the actual work of sparsification itself is prohibitively expensive.
posted by a snickering nuthatch at 9:49 PM on May 22, 2018 [11 favorites]
I've started a new social network called ContrariaNet. People can join and friend each other and all that. You get to see how many friends you have (that's called your "degree").
But the heart of ContrariaNet culture is that it is populated entirely by contrarians. Whenever you post anything, you become more convinced of it by an amount proportional to your degree. Obviously your pronouncements matter; you've got such a friend count! But your friends become slightly less convinced of any position you post about. After all, they're contrarians, too.
Let's put this into numbers. In particular, a big-ass matrix of numbers. Each person gets a row and a column. Every entry in the matrix represents a pair of people- the row-th person and the column-th person. Along the diagonal of the matrix (the cell in the 1st row and 1st column, the cell in the 2nd row and 2nd column... etc) each entry is a pairing of a person with themselves; put their degree there. When the row-th person of a cell is friends with the column-th person, put a -1 in that cell. Otherwise you don't know each other and the cell gets a zero.
This map of influence is ContrariaNet's Laplacian matrix.
This has some interesting dynamics. You post something inflammatory espousing position X; all of your friends post position Y pieces in response. But your friends' friends see all those Y pieces and post their own X responses and the whole network fairly vibrates with activity*.
After ContrariaNet gets really big and maybe leaks data to a secretive propaganda outfit in cahoots with a hostile foreign power everyone decides to eff that noise and go to a different social network, ButActuallist. ButActuallist has the same rules and everything as ContrariaNet, with just two differences:
1. In ContrariaNet, you could friend as many people as you wanted, but in ButActuallist, there's a strict limit on your friend count.
2. ButActuallist lets you assign a "weight" to each friendship that captures exactly how much you are put off by that friend's opinions, on a scale from 0 (who is this person again) to 1 (Cillizza).
Because everyone has far fewer friends than they used to, this migration from ContrariaNet to ButActuallist is called "sparsification".
The theorem they're talking about is that, bizarrely, given a big, dense graph like ContrariaNet, you can reproduce its Laplacian pretty closely when everyone moves over to ButActuallist, despite the austere friend limit. And that friend limit can result in a greatly reduced total number of friendships in the graph, but just having weights on what few friendships remain allows ButActuallist to have the same sort of connectivity characteristics and dynamics.
*When people use the word "spectral" in connection with graphs, you can imagine they're treating the graph like a medium along which stuff can propagate. An "eigenvector" of a graph is an allocation of stuff-amounts-per-node that, after you apply the rules of stuff-propagation that you've adopted, will result in proportionally-the-same stuff-amounts-per-node. Maybe the stuff-per-node will grow or shrink or flip negative but it will do so uniformly, by the same amount per node.
The talked-about theorem gives a method for sparsifying a graph (reducing the number of edges) that roughly preserves the eigenvectors of the Laplacian; that is, it roughly preserves which allocations of opinions to people are stable-ish in a social network of contrarians. It also says how the friend limit ties into exactly how accurately the Laplacian is preserved.
Finally, Urschel mentions that the method is cool and beautiful but not computationally useful. Here's why: when you have only a few people, there's not much difference between ContrariaNet and ButActuallist; the friend limit doesn't change much. The technique only gets useful when the networks get huge. But actually going through the work of finding the right weights for ButActuallist takes an amount of time proportional to the cube of the number of people. So if you're like Facebook and you have 3 billion-ish members, your computer has to do (3 billion)*(3 billion)*(3 billion) = 27 octillion steps to find the right weights. A bit much. While the network is nice and easy to work with after sparsification because it has dramatically fewer connections, the actual work of sparsification itself is prohibitively expensive.
posted by a snickering nuthatch at 9:49 PM on May 22, 2018 [11 favorites]
« Older Beyond Love | [+] - - - --->!!!<--- - - - [-] Newer »
This thread has been archived and is closed to new comments
posted by Glomar response at 9:36 AM on May 22, 2018