October 2012 - Math - moomers.org

paper: "Friendship networks and social status" (Brian Ball, M. E. J. Newman)
by Eric Purdy 17 Jan '13

17 Jan '13

First, some general advice about reading technical papers! Read the introduction, then the discussion/conclusion, then the experimental results, and THEN the technical details (in this case, the section entitled "Inference of rank from network structure"). This is out of order, obviously, but it's a good triage strategy: you read things in increasing level of difficulty, so that you always know whether you care enough to read the next, more difficult part. It's also good because you have more context to interpret the difficult parts if you've read all the easier parts of the paper. I've put a list of wikipedia articles at the bottom of this email, under the heading "Study Guide". They are a hopefully comprehensible explanation of the math needed to understand the most technical parts of the paper. But, if you don't feel like wading through the most technical parts, you don't have to read the study guide articles in order to participate in the discussion. (Also, I'm omitting some background for technical parts that I don't know much about, like ANOVA and statistical tests of model fit. If someone feels like adding anything to the study guide, go for it.) == Paper == PDF link: http://arxiv.org/pdf/1205.6822v1.pdf Arxiv page: http://arxiv.org/abs/1205.6822 == Abstract == In empirical studies of friendship networks participants are typically asked, in interviews or questionnaires, to identify some or all of their close friends, resulting in a directed network in which friendships can, and often do, run in only one direction between a pair of individuals. Here we analyze a large collection of such networks representing friendships among students at US high and junior-high schools and show that the pattern of unreciprocated friendships is far from random. In every network, without exception, we find that there exists a ranking of participants, from low to high, such that almost all unreciprocated friendships consist of a lower-ranked individual claiming friendship with a higher-ranked one. We present a maximum-likelihood method for deducing such rankings from observed network data and conjecture that the rankings produced reflect a measure of social status. We note in particular that reciprocated and unreciprocated friendships obey different statistics, suggesting different formation processes, and that rankings are correlated with other characteristics of the participants that are traditionally associated with status, such as age and overall popularity as measured by total number of friends. == Code == Mike Bishop has some C++ code that (I think?) the authors of the paper are releasing publicly. Mike, can you send that out? It would probably be a good base to start from if we want to run simulations. == Study guide == These are just to be helpful, don't feel like you have to read any of them to participate. And feel free to suggest additions, or say that one of these articles wasn't very helpful. Adjacency matrix: (http://en.wikipedia.org/wiki/Adjacency_matrix) This is useful because it gives you a dictionary between graph theory and linear algebra. It only comes up a little bit, but it's often used without any explanation. Elementary Bayesian stuff: (http://en.wikipedia.org/wiki/Bayesian_statistics) This is a very high-level article that gives links to more in-depth articles. Less elementary Bayesian stuff: (http://en.wikipedia.org/wiki/Bayesian_inference) This is the main piece of background for the technical section of this paper. If you really want to know this stuff, Bishop's "Pattern Recognition and Machine Learning" is the best textbook I know, although it's not accessible without a lot of mathematical background or a lot of free time. Bayesian games: (http://en.wikipedia.org/wiki/Bayesian_game) I've never seen this before, but it seems like the appropriate math to use when thinking about social science stuff with Bayesian methods. EM: (http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm) The workhorse of mathematically rigorous Bayesian statistics. It's a flaky piece of shit, but it's pretty much all we have. MCMC: (http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo) The workhorse of mathematically rigorous frequentist statistics. Gibbs sampling: (http://en.wikipedia.org/wiki/Gibbs_sampling) This is the most mature mathematics that specifies how emergent properties emerge from local interactions. It was first created to model thermodynamics, which is basically all about emergent properties of molecule interactions, like temperature, pressure, etc. Ising model: (http://en.wikipedia.org/wiki/Ising_model) This is the most straightforward example of a Gibbs distribution, it's what you should think about when you try to understand them. On Wed, Oct 3, 2012 at 10:37 AM, Eric Purdy <epurdy(a)uchicago.edu> wrote: > I am starting a new listhost, math(a)moomers.org. I am hoping that it > will function much like readings, but that we can have long and > intricate technical discussions without annoying anyone. > > Some proposed ground rules: > > - There are no stupid questions, and we're interested in everyone's > opinion. In particular, you are encouraged to subscribe to > math(a)moomers.org even if you do not have much mathematical training. > If you're interested in watching math being done, that's all that > matters. > > - There will be no status games, and no arguments from authority. > Nobody should sign up to math(a)moomers.org because they want to impress > anyone, and nobody can cite their professional status or mathematical > training to make someone else shut up. > > - If any publishable research is done on math(a)moomers.org, we will > decide by consensus whose names should be on any papers that result. > > The first proposed paper to read is "Friendship networks and social > status", by Ball and Newman. It is available online at > http://arxiv.org/abs/1205.6822 . I am interested in it because it > gives a nice model of social stratification as an emergent property of > social networks. I think it would be cool to try to extend it, and I > think it should be possible to give a scientific account of the > phenomenon of discursive privilege. > > Here is the abstract: > > In empirical studies of friendship networks participants are typically > asked, in interviews or questionnaires, to identify some or all of > their close friends, resulting in a directed network in which > friendships can, and often do, run in only one direction between a > pair of individuals. Here we analyze a large collection of such > networks representing friendships among students at US high and > junior-high schools and show that the pattern of unreciprocated > friendships is far from random. In every network, without exception, > we find that there exists a ranking of participants, from low to high, > such that almost all unreciprocated friendships consist of a > lower-ranked individual claiming friendship with a higher-ranked one. > We present a maximum-likelihood method for deducing such rankings from > observed network data and conjecture that the rankings produced > reflect a measure of social status. We note in particular that > reciprocated and unreciprocated friendships obey different statistics, > suggesting different formation processes, and that rankings are > correlated with other characteristics of the participants that are > traditionally associated with status, such as age and overall > popularity as measured by total number of friends. > > -- > -Eric -- -Eric

4 30

antfarm: A toolkit for social scientists based on Latour's Actor Network Theory
by Eric Purdy 27 Oct '12

27 Oct '12

Here are some ideas for a new sort of game theory based on Item Response Theory (http://en.wikipedia.org/wiki/Item_response_theory). I would like to implement them in a python library. Is anybody on this list interested in being part of that? I will probably just post it on github. * Mathematical Idea We imagine that we have actors playing a simple game. The game has only one turn, and each player has a list of possible moves, and they randomly choose to either play or not play each move that they are allowed to play. The choices are independent. We assume that every possible move is played by every player with probability P(move M | player A) = sigmoid( a_1 * g_1 + a_2 * g_2 + ... + a_k * g_k) where the a_i are the private and public variables of the actor A, and the g_i are functions of M specified by the rules of the game. This is actually very, very clever! We are using the mathematical trick (duality) used in the definition of a Nash equilibrium, but we are thinking of it in a Bayesian framework, rather than in a linear programming optimization framework. Fixed points of the computational process described below should correspond to social equilibria of a more general class of games than is treated by current game theory. * Model Components and Class Hierarchy - Actor - plans: a distribution over strategies - private: some set of parameters - public: some set of parameters - Strategy: distribution over roles - Role: distribution over moves - Game: model of actors and networks - moves: generator of all possible moves - rules: functions that specify how each move interacts with the private and public parameters of the players involved (if we assume perfect information, then the private parameters can be thought of as all other actors' collective model of the actor in question - player model: IRT-style model of how players choose a move - Move: atomic interactions in the game - Network: an instance of a played game - players: actors - turns: each is a list of moves and potential moves (the potential moves correspond to unobserved data) - IRT Model * Simulation and training We assume that we can only observe part of the network and part of the actor structure. That is, we assume that we can observe some moves, but not all, and that we can observe some actor variables, but not all. We alternate between sleep, waking, and training. We start with an initialization phase. For each move or non-move in the training network, we randomly decide whether or not to "hide" it from the algorithm with a certain probability. This lets us get an independent check of the model, since we can evaluate it by its ability to correctly guess the hidden data. (We will call the hidden data "holdout data".) During sleep, we reinfer the variables of each actor based on the moves played and not played during the previous cycle. This is just IRT/logistic regression on the variables a_i, given the observed moves. During waking, we try to reconstruct the network from scratch by sampling from the strategies of the actors. We assume that all moves are played simultaneously, and that the probability of each move being played is independent of all other moves. This is just sampling from the distribution P(M|A). During training, we update the rules and models of the game to reinforce good move guesses (places where the waking cycle agreed with the training data) and to eliminate bad move guesses (places where the waking cycle disagreed with the training data). This is just IRT/ logistic regression on the variables g_i. Use this to update score on held-out data. -- -Eric

2 3

John Nash's files
by Eric Purdy 17 Oct '12

17 Oct '12

Available here: http://web.math.princeton.edu/jfnj/ I haven't had a chance to look at them beyond a cursory browsing of a few directories, but they seem to talk about cooperative game theory and such, which seems like it should be of interest. (Also, there are a whole bunch of pictures and mp3s, it's kind of a fascinating look into his mind.) -- -Eric

1 0

popularity of programming languages
by Michael Bishop 04 Oct '12

04 Oct '12

You've probably seen things like this before, but you'll still probably find it interesting. http://www.drewconway.com/zia/?p=2892

1 0