- Marvel
- In recent years there has been a growing public fascination with the complex "connectedness" of modern society. This connectedness is found in many incarnations: in the rapid growth of the Internet and the Web, in the ease with which global communication now takes place, and in the ability of news and information as well as epidemics and financial crises to spread around the world with surprising speed and intensity. These are phenomena that involve networks, incentives, and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which each of our decisions can have subtle consequences for the outcomes of everyone else. Networks, Crowds, and Markets combines different scientific perspectives in its approach to understanding networks and behavior. Drawing on ideas from economics, sociology, computing and information science, and applied mathematics, it describes the emerging field of study that is growing at the interface of all these areas, addressing fundamental questions about how the social, economic, and technological worlds are connected. The book is based on an inter-disciplinary course that we teach at Cornell. The book, like the course, is designed at the introductory undergraduate level with no formal prerequisites. To support deeper explorations, most of the chapters are supplemented with optional advanced sections.
- Three-Toed Sloth Slow Takes from the Canopy (My Very Own Internet Tradition) June 15, 2007 « Reformatting in Progress | Main | Books to Read While the Algae Grow in Your Fur, May 2007 » So You Think You Have a Power Law — Well Isn't That Special? Regular readers who care about such things — I think there are about three of you — will recall that I have long had a thing about just how unsound many of the claims for the presence of power law distributions in real data are, especially those made by theoretical physicists, who, with some honorable exceptions, learn nothing about data analysis. (I certainly didn't.) I have even whined about how I should really be working on a paper about how to do all this right, rather than merely snarking in a weblog. As evidence that the age of wonders is not passed — and, more relevantly, that I have productive collaborators — this paper is now loosed upon the world: Aaron Clauset, CRS and M. E. J. Newman, "Power-law distributions in empirical data", arxiv:0706.1062, with code available in Matlab and R; forthcoming (2009) in SIAM Review Abstract: Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out. The paper is deliberately aimed at physicists, so we assume some things that they know (like some of the mechanisms, e.g. critical fluctuations, which can lead to power laws), and devote extra detail to things they don't but which e.g. statisticians do know (such as how to find the cumulative distribution function of a standard Gaussian). In particular, we refrained from making a big deal about the need for an error-statistical approach to problems like this, but it definitely shaped our thinking. Aaron has already posted about the paper, but I'll do so myself anyway. Partly this is to help hammer the message home, and partly this is because I am a basically negative and critical man, and this sort of work gives me an excuse to vent my feelings of spite under the pretense of advancing truth (unlike Aaron and Mark, who are basically nice guys and constructive scholars). Here are the take-home points, none of which ought to be news, but which, taken together, would lead to a real change in the literature. (For example, half or more each issue of Physica A would disappear.) 1. Lots of distributions give you straight-ish lines on a log-log plot. True, a Gaussian or a Poisson won't, but lots of other things will. Don't even begin to talk to me about log-log plots which you claim are "piecewise linear". 2. Abusing linear regression makes the baby Gauss cry. Fitting a line to your log-log plot by least squares is a bad idea. It generally doesn't even give you a probability distribution, and even if your data do follow a power-law distribution, it gives you a bad estimate of the parameters. You cannot use the error estimates your regression software gives you, because those formulas incorporate assumptions which directly contradict the idea that you are seeing samples from a power law. And no, you cannot claim that because the line "explains" (really, describes) a lot of the variance that you must have a power law, because you can get a very high R^2 from other distributions (that test has no "power"). And this is without getting into the additional errors caused by trying to fit a line to binned histograms. It's true that fitting lines on log-log graphs is what Pareto did back in the day when he started this whole power-law business, but "the day" was the 1890s. There's a time and a place for being old school; this isn't it. 3. Use maximum likelihood to estimate the scaling exponent. It's fast! The formula is easy! Best of all, it works! The method of maximum likelihood was invented in 1922 [parts 1 and 2], by someone who studied statistical mechanics, no less. The maximum likelihood estimators for the discrete (Zipf/zeta) and continuous (Pareto) power laws were worked out in 1952 and 1957 (respectively). They converge on the correct value of the scaling exponent with probability 1, and they do so efficiently. You can even work out their sampling distribution (it's an inverse gamma) and so get exact confidence intervals. Use the MLEs! 4. Use goodness of fit to estimate where the scaling region begins. Few people pretend that the whole of their data-set follows a power law distribution; usually the claim is about the right or upper tail, the large values over some given threshold. This ought to raise the question of where the tail begins. Usually people find it by squinting at their log-log plot. Mark Handcock and James Jones, in one of the few worthwhile efforts here, suggested using Schwarz's information criterion. This isn't bad, but has trouble with with continuous data. Aaron devised an ingenious method which finds the empirically-best scaling region, by optimizing the Kolmogorov-Smirnov goodness-of-fit statistic; it performs slightly better than the information criterion. (Yes, one could imagine more elaborate semi-parametric approaches to this problem. Feel free to go ahead and implement them.) 5. Use a goodness-of-fit test to check goodness of fit. In particular, if you're looking at the goodness of fit of a distribution, use a statistic meant for distributions, not one for regression curves. This means forgetting about R^2, the fraction of variance accounted for by the curve, and using the Kolmogorov-Smirnov statistic, the maximum discrepancy between the empirical distribution and the theoretical one. If you've got the right theoretical distribution, KS statistic will converge to zero as you get more data (that's the Glivenko-Cantelli theorem). The one hitch in this case is that you can't use the usual tables/formulas for significance levels, because you're estimating the parameters of the power law from the data. (If you really want to see where the problem comes from, see Pollard, starting on p. 99.) This is why God, in Her wisdom and mercy, gave us the bootstrap. If the chance of getting data which fits the estimated distribution as badly as your data fits your power law is, oh, one in a thousand or less, you had better have some other, very compelling reason to think that you're looking at a power law. 6. Use Vuong's test to check alternatives, and be prepared for disappointment. Even if you've estimated the parameters of your parameters properly, and the fit is decent, you're not done yet. You also need to see whether other, non-power-law distributions could have produced the data. This is a model selection problem, with the complication that possibly neither the power law nor the alternative you're looking at is exactly right; in that case you'd at least like to know which one is closer to the truth. There is a brilliantly simple solution to this problem (at least for cases like this) which was first devised by Quang Vuong in a 1989 Econometrica paper: use the log-likelihood ratio, normalized by an estimate of the magnitude of the fluctuations in that ratio. Vuong showed that this test statistic asymptotically has a standard Gaussian distribution when the competing models are equally good; otherwise it will almost surely converge on picking out the better model. This is extremely clever and deserves to be much better known. And, unlike things like the fit to a log-log regression line, it actually has the power to discriminate among the alternatives. If you use sensible, heavy-tailed alternative distributions, like the log-normal or the Weibull (stretched exponential), you will find that it is often very, very hard to rule them out. In the two dozen data sets we looked at, all chosen because people had claimed they followed power laws, the log-normal's fit was almost always competitive with the power law, usually insignificantly better and sometimes substantially better. (To repeat a joke: Gauss is not mocked.) For about half the data sets, the fit is substantially improved by adding an exponential cut-off to the power law. (I'm too lazy to produce the necessary equations; read the paper.) This means that there is a characteristic scale after all, and that super-mega-enormous, as opposed to merely enormous, events are, indeed, exponentially rare. Strictly speaking, a cut-off power law should always fit the data better than a pure one (just let the cut-off scale go to infinity, if need be), so you need to be a little careful in seeing whether the improvement is real or just noise; but often it's real. 7. Ask yourself whether you really care. Maybe you don't. A lot of the time, we think, all that's genuine important is that the tail is heavy, and it doesn't really matter whether it decays linearly in the log of the variable (power law) or quadratically (log-normal) or something else. If that's all that matters, then you should really consider doing some kind of non-parametric density estimation (e.g. Markovitch and Krieger's [preprint]). Sometimes, though, you do care. Maybe you want to make a claim which depends heavily on just how common hugely large observations are. Or maybe you have a particular model in mind for the data-generating process, and that model predicts some particular distribution for the tail. Then knowing whether it really is a power law, or closer to a power law than (say) a stretched exponential, actually matters to you. In that case, you owe it to yourself to do the data analysis right. You also owe it to yourself to think carefully about whether there are other ways of checking your model. If the only testable prediction it makes is about the shape of the tail, it doesn't sound like a very good model, and it will be intrinsically hard to check it. Because this is, of course, what everyone ought to do with a computational paper, we've put our code online, so you can check our calculations, or use these methods on your own data, without having to implement them from scratch. I trust that I will no longer have to referee papers where people use GnuPlot to draw lines on log-log graphs, as though that meant something, and that in five to ten years even science journalists and editors of Wired will begin to get the message. Manual trackbacks: The Statistical Mechanic; Uncertain Principles; zs; LanguageLog; Science After Sunclipse; Philosophia Naturalis 11 (at Highly Allochthonous); Langreiter; blogs for industry ... blogs for the dead; Infectious Greed; No Free Lunch; Look Here First; TPMCafe; Science After Sunclipse; Cosmic Variance; Messy Matters Power Laws; Enigmas of Chance; Complexity Posted by crshalizi at June 15, 2007 13:00 | permanent link Three-Toed Sloth: Hosted, but not endorsed, by the Center for the Study of Complex Systems
- Brad Fitzpatrick recently wrote an elegant and important post about the Social Graph, a term used by Facebook to describe their social network. In his post, Fitzpatrick defines "social graph" as "the global mapping of everybody and how they're related". He went on to outline the problems with it, as well as a broad set of goals going forward. One problem is that currently you need to have different logins for different social networks. Another issue is portability and ownership of an individual's information, explicitly and implicitly revealed while using social networks. As was recently asserted in the Social...
- Think back to the last time you were in a crowded airport or bus terminal far from home. Did you consider that the person sitting next to you probably knew a friend of a friend of a friend of yours? In the 1960s, social psychologist Stanley Milgram’s “small world experiment” famously tested the idea that any two people in the world are separated by only a small number of intermediate connections, arguably the first experimental study to reveal the surprising structure of social networks. With the rise of modern computing, social networks are now being mapped in digital form, giving researchers the ability to study them on a much grander, even global, scale. Continuing this tradition of social network research, Facebook, in collaboration with researchers at the Università degli Studi di Milano, is today releasing two studies of the Facebook social graph. First, we measured how many friends people have, and found that this distribution differs significantly from previous studies of large-scale social networks. Second, we found that the degrees of separation between any two Facebook users is smaller than the commonly cited six degrees, and has been shrinking over the past three years as Facebook has grown. Finally, we observed that while the entire world is only a few degrees away, a user’s friends are most likely to be of a similar age and come from the same country. In our studies, performed earlier this year, we examined all 721 million active Facebook users (more than 10% of the global population), with 69 billion friendships among them. To date, these are the largest social network studies ever released.
- Gephi is an open-source software for visualizing and analyzing large networks graphs. Gephi uses a 3D render engine to display graphs in real-time and speed up the exploration. Use Gephi to explore, analyse, spatialise, filter, cluterize, manipulate and export all types of graphs.
- modularity
- QAP
- measures

*Journal of the American Society for Information Science and Technology**58 (7): 1019--1031*(*2007*)*Proceedings of the 2008 International Conference on Web Search and Data Mining,**page 107--116.**New York, NY, USA,**ACM,*(*2008*)*Proceedings of the International Conference on Database and Expert Systems Applications (DEXA),**volume 2453 of LNCS,**page 534-546.**Springer,*(*2002*)*Formal Concept Analysis,**volume 4933 of Lecture Notes in Computer Science,**Springer,**Berlin/Heidelberg,*(*2008*)*International Journal of Conceptual Structures and Smart Applications (IJCSSA)**1 (1): 73--89*(*2013*)*Proceedings of the LWA 2015 (KDML Special Track),*(*2015*)- (
*2016*) *Science Advances*(*May 2016*)*Science Advances*(*May 2016*)*Proceedings of the LWA 2015 (KDML Special Track),*(*2015*)*The International Review of Research in Open and Distributed Learning*(*2014*)*Physics Reports**519 (3): 97--125*(*2012*)*Proc. WWW2007 Workshop ``Tagging and Metadata for Social Information Organization'',**Banff,*(*May 8, 2007*)*Proceedings of the 3rd European Semantic Web Conference,**volume 4011 of LNCS,**page 514-529.**Budva, Montenegro,**Springer,*(*June 2006*)*Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,**page 407--416.**New York, NY, USA,**ACM,*(*2015*)*SIGKDD Explorations Newsletter**15 (2): 20--29*(*June 2014*)*Handbook of Graph Drawing and Visualization,**page 805--840.**CRC Press,*(*2014*)*HT '08: Proceedings of the Nineteenth ACM Conference on Hypertext and Hypermedia,**page 157--166.**New York, NY, USA,**ACM,*(*2008*)*The Semantic Web: Research and Applications,**volume 4011 of Lecture Notes in Computer Science,**page 514--529.**Berlin/Heidelberg,**Springer,*(*2006*)*10.1007/11762256_38.**Proceedings of the 3rd European Semantic Web Conference,**volume 4011 of LNCS,**page 514-529.**Budva, Montenegro,**Springer,*(*June 2006*)