Theorem: There Exist Arbitrarily Long Songs of Complexity O(1)

As discussed in a paper by Donald Knuth, the proof is due to Casey and the Sunshine Band.

"A Simple Generative Model of Collective Online Behavior"

Last Monday, PNAS published, in their early edition (so there are no volume or page numbers yet), a new article by my collaborators and me about how to model complex systems in a way that incorporates data directly into a simple model. We also illustrate with this example a nice situation in which several different situations (in particular, different parameter values, where one gets different qualitative mechanisms in different regions of parameter space) give the same qualitative long-time behavior (and very similar quantitative long-time behavior) so that one needs to consider the temporal dynamics explicitly to distinguish between the mechanisms. There are many papers that seem to assume mechanisms based on statistical fitting of long-time (or even equilibrium) behavior, and that is very dangerous. Here are the details about the article.


Title: A Simple Generative Model of Collective Online Behavior

Authors: James P. Gleesona, Davide Cellai, Jukka-Pekka Onnela, Mason A. Porter, and Felix Reed-Tsochas

Abstract: Human activities increasingly take place in online environments, providing novel opportunities for relating individual behaviors to population-level outcomes. In this paper, we introduce a simple generative model for the collective behavior of millions of social networking site users who are deciding between different software applications. Our model incorporates two distinct mechanisms: one is associated with recent decisions of users, and the other reflects the cumulative popularity of each application. Importantly, although various combinations of the two mechanisms yield long-time behavior that is consistent with data, the only models that reproduce the observed temporal dynamics are those that strongly emphasize the recent popularity of applications over their cumulative popularity. This demonstrates--even when using purely observational data without experimental design--that temporal data-driven modeling can effectively distinguish between competing microscopic mechanisms, allowing us to uncover previously unidentified aspects of collective online behavior.

Significance Paragraph (which is now a part of PNAS papers): One of the most common strategies in studying complex systems is to investigate and interpret whether any "hidden order" is present by fitting observed statistical regularities via data analysis and then reproducing such regularities with long-time or equilibrium dynamics fromsome generative model. Unfortunately, many different models can possess indistinguishable long-time dynamics, so the above recipe is often insufficient to discern the relative quality of competing models. In this paper, we use the example of collective online behavior to illustrate that, by contrast, time-dependent modeling can be very effective at disentangling competing generative models of a complex system.


This paper has gotten a little bit of press coverage. You can find links to press coverage for this article (and other articles of mine) on the press part of my web page.

LinkedIn Fail

LinkedIn Fail: Today I got an e-mail notice suggesting that I should congratulate one of my connections on a professional milestone: "[first name] [last name] is celebrating 7 years at [Institution of Higher Learning]"

Dear LinkedIn: You do realize that that means that this person is still a graduate student at that place, right?

For what it's worth, I would laugh at this out of sheer perversity even if that anniversary were mine.

"Social Structure of Facebook Networks"

My "data dump" paper on Facebook networks is finally out in final form (including page numbers and all of the trimmings). Here is some information about it.

Title: Social Structure of Facebook Networks

Authors: Amanda L. Traud, Peter J. Mucha, and Mason A. Porter

Abstract: We study the social structure of Facebook ‘‘friendship’’ networks at one hundred American colleges and universities at a single point in time, and we examine the roles of user attributes – gender, class year, major, high school, and residence – at these institutions. We investigate the influence of common attributes at the dyad level in terms of assortativity coefficients and regression models. We then examine larger-scale groupings by detecting communities algorithmically and comparing them to network partitions based on user characteristics. We thereby examine the relative importance of different characteristics at different institutions, finding for example that common high school is more important to the social organization of large institutions and that the importance of common major varies significantly between institutions. Our calculations illustrate how microscopic and macroscopic perspectives give complementary insights on the social organization at universities and suggest future studies to investigate such phenomena further.

Comparing Community Structure to Characteristics in Online Collegiate Social Networks

My first paper on Facebook networks, which was originally submitted to SIAM Review in September 2008, has finally been published in final form in that journal. The project itself was first formulated in December 2004 (and January 2005) and the initial work started with Eric Kelsic's Caltech SURF project at the end of June 2005. So it's been a long road. The sequel to this paper is already on the arXiv, but in the meantime let's savor the publication of the present paper.

Title: Comparing Community Structure to Characteristics in Online Collegiate Social Networks

Authors: Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, Mason A. Porter

Abstract: We study the structure of social networks of students by examining the graphs of Facebook "friendships" at five U.S. universities at a single point in time. We investigate the community structure of each single-institution network and employ visual and quantitative tools, including standardized pair-counting methods, to measure the correlations between the network communities and a set of self-identified user characteristics (residence, class year, major, and high school). We review the basic properties and statistics of the employed pair-counting indices and recall, in simplified notation, a useful formula for the z-score of the Rand coefficient. Our study illustrates how to examine different instances of social networks constructed in similar environments, emphasizes the array of social forces that combine to form "communities," and leads to comparative observations about online social structures, which reflect offline social structures. We calculate the relative contributions of different characteristics to the community structure of individual universities and compare these relative contributions at different universities. For example, we examine the importance of common high school affiliation at large state universities and the varying degrees of influence that common major can have on the social structure at different universities. The heterogeneity of the communities that we observe indicates that university networks typically have multiple organizing factors rather than a single dominant one.


Update (9/16/11): This article turns out to be the cover story of that issue of SIAM Review. Sweet!

Update 2 (9/18/11): Here is a better picture of my cover article. Now I just need my physical copy to arrive so that I can show it to certain people who insist that I am a physicist rather than a mathematician. :)

AIP/APS Publication Social Network

The American Institute of Physics (AIP) has a new social networking service (called "uniPHY", which is a really stupid name) that includes some nice visualizations of one's collaboration network (and related objects) in AIP and American Physical Society journals. One can also do other social networking type stuff, but I was basically curious just about the visualizations and some simple statistics. (Granted, this ignores all of the publications I have in other venues, but I still wanted to check it out.)

Finding a Lost Camera using the Small World Phenomenon

I wasn't following this story about the Facebook-mediated search for somebody's lost camera, but this is really cool for those of us who study network science. It's the small-world effect at work, with Facebook lending a helping hand. In fact, it's an absolutely beautiful example of cascading dynamics on small-world networks, and it might even be worth a mention in a paper on which I'm currently working on cascading dynamics on such networks (where my Facebook data is one of the many data sets we're employing).

It's also quite a nice story, as it's excellent that somebody would start such an effort for a total stranger. I hope that I'm eventually that nice a person. I'm rather good (I think) about caring about friends, but I do much less well about caring about people more generally.

(Tip of the cap to Martin Gould.)

"Project 'Gaydar'": Oy Vey

You'll notice that I have quotes in part of the title for this blog entry, and that's because this study about using network information to infer unknown demographics has been given a rather unfortunate and irresponsible name.

The link I have provided is a Boston Globe article about some research coming (mostly) out of MIT about using Facebook data to infer demographic information that people have not openly acknowledged---in this case, sexual orientation. Now, of course it is true that such data can be used for that, and indeed many of the tools to do so come from network science. And it is essential for people to be far more aware than they seem to be that that is the case. Of course the media is going to butcher the actual research, so as a scientist it is crucial when talking them to make sure approximations are reasonable and---when it comes to sensitive studies like this one---non-damaging. ("First, do no harm.") I'll come back to some of this in a minute, but first I want to tell a story (and then beyond my research interests, it will really become clear why I am blogging about this incident).

I saw a link to this study this morning when I was going through the daily digest from SOCnet listserv. Among the included e-mails was one from sociologist Barry Wellman that included a link to this newspaper article and some of his commentary. More commentary from others came in subsequent e-mails. Obviously, I have a great deal of interest in this topic based on my research, and instead of saving the article for later (as I often might, but in this case I was especially interested in the article), I opened it up immediately. Scanning through the text, I noticed a very familiar name: Fuck! One of the students on this project is one of my former research students from Georgia Tech!. He worked with me on an abstract problem in dynamical systems---nothing to do with networks---but I am one of his educators, and my memories of him are of his being just a fundamentally nice kid (not a generic nice kid, but somehow nicer in some deeper sense). Also, educators have nightmares about seeing their students' names in situations like this. When he applies for jobs in a few years, people will google him, and this thing is what they're going to see, and he's probably going to have to explain himself.

For this kind of research, there are obviously very serious issues---especially when such personal information is involved---and any study of this nature necessarily has a lot of hurdles to pass to even be allowed to happen, and that includes ensuring that the data is anonymized. The article in the Boston Globe indicates one of the ethical hurdle but not one that would be sufficient. (Based on an e-mail exchange with my former student, there were several beyond this, though I can't say if they are sufficient.) Also, the "validation" that was mentioned in the article is just frightening. My former student assures me that there is more in there, but things are exacerbated by the fact that the paper is not available publicly in any form. It is currently under review and isn't even around as a preprint. So the experts reading the Boston Globe article can't even look it up to see what the researchers really did. Also, it seems like huge mistakes were made in the discussions with the media---I wonder if the people on the project actually used the term 'gaydar' in those discussions, and that is just stupid. How could one think that something like that wouldn't blow up in one's face? (And not that it's a particularly nice term in the first place.)

Anyway, conveying science to the media is a very difficult endeavor, but it needs to be done in way that doesn't result in articles like this. Obviously, the researchers didn't want this kind of article, and something like this could have been prevented---even with a sensitive subject (which is when you want to be especially careful). Work with your interviewers, prepare for your interviews by establishing both talking points and things not to say, try not to say asinine things, and insist very stubbornly to look at drafts of what might get published. Some of the science will necessarily get approximated; grin and bear it if the approximation is reasonable and kindly offer corrections if it isn't. And, especially, as it is with doctors: "First, do no harm."

If you want to see an excellent capsule of the scientist-journalist relationship, take a look at the short sequence of PHD Comics that starts with this one. "Robots", indeed.

Quote of the Day: Tweeting During Life's Rituals

Today's quote comes from this CNN article about using twitter during childbirth.

The quote comes from psychologist Renana Brooks: "That's like Twittering on your wedding night. You can blog about it afterward."

I don't think she intended her comment to be funny, but I find it highly amusing.

My Life According to Depeche Mode (I was tempted to choose "Modern English" in deference to a certain incident on KROQ)

I noticed an interest meme on Facebook today in a post by Vincent Kong, and I decided it would be an interesting exercise to try it out (and my food was actually still somewhat warm by the time I finished). I think a few of my answers are pretty clever, so I decided to include my post in this spot as well.

Instructions: Using only song names from ONE ARTIST, cleverly answer these questions. Pass it on to at least 15 people and include me. You can't use the band I used. Try not to repeat a song title. It's a lot harder than you think! Re-post as "my life according to (band name)".

MAP's additional note: I am spending way too much time trying to be clever with this. It helps that Depeche Mode (which is my favorite artist) has such a huge catalog. This would have been significantly harder had I picked Modern English or---dare I say it?---Baltimora.


Are you a male or female?
"Everything Counts"

Describe Yourself:
"I Want It All"

How do you feel?
"I Feel You" (Oh, _how_ do I feel... Sorry, I misunderstood the question.)

Describe where you currently live:
"Home"

If you could go anywhere, where would you go:
"Only When I Lose Myself"

Your favorite form of transportation:
"Walking In My Shoes"

Your best friend is:
"I Feel Loved" (I had to resist the urge to put "Master and Servant" here. DM can be so convenient for some things... And my answer refers to the friendship type of love, by the way, so nobody should get any ideas.)

What's the weather like:
"Precious" (I guess I'm writing this on the one day of the year it's that way here... Oh crap, I need to use this later. How about "Enjoy the Silence", which actually makes sense if you've seen the music video.)

Favorite time of day:
"Waiting for the Night"

If your life was a TV show, what would it be called:
"World in My Eyes"

What is life to you:
"Black Celebration" (Just kidding!)

Your fear:
"Death's Door"

What is the best advice you have to give:
"Get the Balance Right!"

Thought for the Day:
"Precious"

How I would like to die:
"Black Celebration" (Am I allowed to use the same answer twice? If not, then I'll be honest and select "But Not Tonight" and have that refer to now and forever more. Maybe I should become a lich?)

My soul's present condition:
"Dream On"

My motto:
"Policy of Truth"

De-Anonymizing Social Networks

Here is interesting but scary study on how to de-anonymize social network data. It's cool, powerful, and frightening.

Note additionally that there are multiple sides to the implications of such methods: Besides pure privacy issues, there are also the privacy issues that are conjoined with the increasing number of anonymized data sets that are being analyzed by scientists like me.

Social Networking Sites (and related phenomena) for protests and reactions to them

CNN.com has an interest article about the upcoming G-20 protest and the roll of technology like Facebook and Twitter for organizing both protesting and reactions to them.

Sacrificing Facebook "friends" for Whoppers

I am officially amused.

Here is an article about a new Burger King promo that allows one to get a free whopper if one removes 10 Facebook "friends". That's pretty funny. (Tip of the hat to Sham Kakade, a Scurve from one of my old D & D groups.) Best. Promo. Ever.

Spyspace

Here's the straight line (you provide the joke).

As reported in this article:

Later this month, intelligence community analysts will begin using A-Space, an online collaboration environment that officials hope will improve analysts’ abilities to share information, form communities and collaborate.... Like many social-networking sites, each analyst will create an online personal profile, and colleagues can see what others are working on and the A-Space workspaces that they are using.... A-Space analysts will have access to all information at the highest classification level that is accessible through the collaboration environment.

I would really love to apply community-detection techniques to that data set...

(Tip of the cap to Ben Williamson for pointing me to this article.)

Tales from the arXiv: Narcissistic Edition

My collaborators and I finally submitted our paper on Facebook networks last night. I normally post blog entries about my papers after the official journal version comes out, but this one was a royal pain in the ass ('particularly arduous' in more official language) to write, so I'm going to make an exception. Besides, this article is 38 journal-pages of sheer joy and community detection, so how can I not post about it now. (This is the longest article I've ever written, and it's longer than many doctoral theses. As I said, writing it was a pain in the ass, but I'm quite proud of the article and I hope it has a nice impact.)

First, here is the link to the arXiv posting.

Before I give the abstract, let me also shout out to my coauthors Mandi Traud (UNC student), Eric Kelsic (my 2005 Caltech SURF student, which is where this project all started), and Peter Mucha (UNC applied mathematician). Let me also give a shout out to Aaron Clauset and James Fowler, whose thorough commentary on an older version of the manuscript were inordinately valuable and way above and beyond the call of duty. (I can overstate my thanks for your help!) Without further ado...

Article title: Community Structure in Online Collegiate Social Networks

Article abstract: We apply the tools of network analysis to study the roles of university organizations and affiliations in structuring the social networks of students by examining the graphs of Facebook "friendships" at five American universities at a single point in time. In particular, we investigate each single-institution network's community structure, which we obtain by partitioning the graphs using an eigenvector method. We employ both graphical and quantitative tools, including pair-counting methods that we interpret through statistical analysis and permutation tests, to measure the correlations between the network communities and a set of self-identified user characteristics (residence, class year, major, and high school). We additionally investigate single-gender subsets of the university networks and also examine the impact of incomplete demographic information in the data. Our study across five universities allows one to make comparative observations about the online social lives at the different institutions, which can in turn be used to infer differences in offline lives. It also illustrates how to examine different instances of social networks constructed in similar environments, while emphasizing the array of social forces that combine to form simplified "communities" obtainable by the consideration of the friendship links. In an appendix, we review the basic properties and statistics of the employed pair-counting similarity coefficients and recall, in simplified notation, a useful analytical formula for the z-score of the Rand coefficient.