Social Media Research Blog

Attending KDD 2008, Las Vegas

I will be attending the KDD 2008 conference in Las Vegas this week where I will be presenting our paper titled "Detecting Communities Via Simultaneous Clustering of Graphs and Folksonomies" at the WebKDD 2008 workshop. Please let me know if you are at KDD and I would love to sync up with you!

I also plan to make a short detour to the Bay Area, CA (August 27-31st). We could try to organize a Social Media meetup at a coffee shop if there are enough folks interested in meeting up on August 28th or 29th? Really looking forward to this trip and catching up with my old friends (school, ex-colleagues, academic) as well as my "Linkedin/Facebook/Blog/Twitter/FriendFeed/..... friends":

Just for kicks, here is a funny video on this topic:

Only 10 Cherry Picked? Thats not Enough!

Sixapart re-launced Blogs.com as a blog directory... yawn! (Wow! A Yawn is really contagious... via techcrunch's coverage -- the Yawn cascade initiator).

Seriously.. Sixapart? I am sure you could do a lot better than having an expensive team of editors cherry pick their favorite blogs in a handful of categories. You guys have a ton of good, high quality blogs and the interesting thing is that you can use some of the tag information to cluster these blogs into the different communities they belong to. For example blogs that talk about business are likely to use tags like marketing, advertising, finance etc. Algorithmic approaches can be effectively used to mine blog graphs to find high quality feeds.

At eBiquity, we have looked at this problem from two different approaches:

• Using readership information from Bloglines, we can cluster the blogs based on how people subscribe and categorize their feeds. Although typepad probably does not have access to subscription information it has other sources (like what tags are used by the blogger, and the number of people visiting and commenting on the blogs) to come up with a much better directory. Something on the lines of "Feeds That Matter" (see site here, bit outdated though).
• More recently, I have looked at how we can combine the graph structure and folksonomy information to identify communities in social media. This was an Idea that I first shared on this blog and subsequently submitted a paper, which I would be presenting at this year's WebKDD workshop.

The point is, I beleive that the top 10 offered by sixapart and bloglines are not really that interesting anymore. In the era of hundreds of thousands of potentially good blog (of the millions that exist), we can rely on algorithmic approaches to find (more than just 10) high quality blogs. This is also related to the "Feed Distillation Task" that TREC ran for 2007. If you are interested in feed distillation... check out CMU's submission by Elsas et al. and the follow up papers by Jon at other venues.

Another challenge is being able to find not just popular blogs but also that cool blog that probably be down there somewhere in the long tail.

Structure of Information Pathways in Social Networks

One of the papers I am looking forward to at KDD 2008 is "The Structure of Information Pathways in a Social Communication Network"  by Kossinets, Kleinberg and Watts (PDF). This paper analyzes the communication graph of an email network. The authors present two important and novel concepts to social networks research: Temporal distance and Network backbone. They beautifully incorporate a rather Operating Systems textbook technique of vector clocks into the analysis of social networks. Following is an excerpt from the abstract:

....We formulate a temporal notion of “distance” in the underlying social network by measuring the minimum time required for information to spread from one node to another — a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges—a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

The authors use vector clocks to determine the nodes that are up-to date with respect to each other and describe a network backbone as

the subset of edges in the social network that are not bypassed by a faster alternate path.

Thus a network backbone is the set of edges that are critical in ensuring the flow of information within the network and thereby responsible for keeping the nodes 'in sync' with respect to each other. The idea of a backbone is not new and many real world networks like the internet are known to have some such equivalent. Traditionally, in social networks most of the attention so far has been on the "strength of weak links".  In this paper, the authors not only validate this phenomena, but also show that these links are critical in the network backbone structure. This is a paper that offers some deep insights and fundamentally advances our knowledge of how information flows in social networks.

Social Media Research Themes

A couple of weeks ago, over at LinkedIn Rob Van Alphen was looking for social media research/thesis topics and asked the community for possible suggestions. I decided to share my reply here and I hope that this would inspire other graduate students who are looking for possible thesis topics. Please feel free to add to the following list by posting your suggestions in the comments. Here is an excerpt from my reply:

There are many interesting areas of research in social media. Following are a few starting points you might wish to look at:

1. Opinion/Sentiment retrieval (Also look at TREC papers from last two blog tracks)
2. Blog feed distillation (Finding important/relevant blogs for a topic)
3. Community detection: Partitioning social networks and blog graphs into communities (tech, politics games etc)
4. Temporal data mining: Both for interesting event detection/buzz/trend analysis and evolutionary community detection/clustering.
5. Spam detection: Also look into adversarial challenges
6. Classification: There are many challenges in classifying blogs/social media content into different "topics" or "categories"
7. Feed indexing: how do you ensure the freshness of your index. The timeliness of the results etc matter a whole lot in social media.
8. NLP and entity detection from noisy unstructured text that is common in social media settings.
9. Microblogs and real time data from short updates like twitter and friendfeed.
10. Advertising possibilities: research on better advertising models for social media.
11. Better image search: combine tagging information with Image processing for improved image search.
12. Social recommendation systems like netflix,last.fm

There are a number of papers and conferences that you might wish to follow up on. Best place to start would be the ICWSM conference papers. There are also several interesting papers from social sciences and psychology perspectives as well (for example, perception of self vs. other's perception of your profile on facebook). This is an exciting field and you can do a lot of cool stuff. Please feel free to get in touch with me if you are a grad student and are starting work in this area. And if you are a UMBC student (grads/undergrads) interested in social media, the eBiquity research group is Hiring!

DERI/NUI boards.ie SIOC Data Competition

Following Announcement is Via Dr. John Breslin spotted on W3C's Semantic Web Mailing List:

The Digital Enterprise Research Institute (DERI) at NUI Galway is running a unique competition from 1st August to 30th September 2008 in conjunction with
boards.ie, Ireland’s largest discussion forum site. The competition is an open contest in which entrants can win over €4000 in Amazon.com vouchers by submitting an interesting creation based on an RDF data set of discussion posts from boards.ie over the past ten years:

* The first prize is an Amazon voucher for $4000 (~€2500)
* The second prize is a voucher for $2000 (~€1250)
* The third prize is a voucher for $1000 (~€625)

Read the rules and find out more information on the contest at:

http://data.sioc-project.org/

The data set (approximately 9 million documents) has been represented in the Semantically-Interlinked Online Communities (SIOC) RDF format developed by DERI, NUI Galway for expressing the information contained in social websites (forums, mailing lists, blogs, etc.). Entrants may create whatever they feel is interesting based on this data: it could be a novel web application that makes use of the data set, a report on analyses performed on the data, a tool that allows one to visualise or browse the semantic structure, or whatever else the imagination can come up with!

This event is duly noted in the Social Media Events Calendar.

Some things are just Semi-Social

Social Media is a lot about sharing. Prior to the growth of social software, it wasn't that people did not share stuff -- they just did it offline or via email. Now we share at a massive scale and a lot more easily. 

Some things we are willing to share "openly"

• Music playlists (Last.fm)
• Books we read (iread, shelfari)
• Calendars and Travel plans (google calendar)
• Status updates (via Twitter and Microblogging)
• Restaurant recommendations (yelp)
• Knowledge and expertise (via Wikipedia)

As we start to experiment with social software we realize that sharing is good and soon become open to sharing a lot more. There are some things though, that just seem semi-social. What I mean by Semi-Social is roughly "Thing I would not mind sharing with a small group of trusted friends and family members".

Until just a few years back there would have been a lot more people squirming if they were asked to share such 'sensitive data' with others. I see this perception slowly eroding away. There is a small, albeit enthusiastic bunch experimenting with new tools that fall into the category of Semi-Social. 

Some cases that I can think of are as follows:

• Investment portfolio: One example is Covestor. I have an account there but it is under pseudonym. I would not be that enthusiastic to reveal my pathetic attempt to bet on the stock market by watching (mostly tech) blogs. sigh!
• TV watching habits: I think Television as we know it today is completely broken. There is no social aspect to it whatsoever. At ICWSM, Noor Ali-Hassan presented a paper on "Social Media Scenarios for Television". What struck me about this talk was her statement that "Despite its social nature, there is a private aspect of TV that people want to preserve".
• Income and financial information: This is something we had least anticipated. How did we get to a point where I am actually not that scared while putting all my bank details and credit card information into a site like Mint? Mint is not a social site as such. But it reflects how we are now willing to part with some really sensitive data. In contrast, there are other examples of recruitment sites like SimplyHired where people reveal their salary information and can search for companies by salary. A more recent startup that is quite similar is Glassdoor.
• Location: Location can be an extremely sensitive piece of information. Fortunately, Yahoo's fireeagle provides access control for various applications and one can set the privilege that each app has to access location information (latlong, zip, state, country etc).

There will always be some who are at the extreme end of the spectrum and are quite comfortable with being completely (publicly) transparent about "sensitive data". However, most would still only dare to share some of this data with close friends and select people -- i.e. if there is enough value proposition in it for them. Some would be comfortable with aggregate analysis over the data as long as they are not personally identified or targeted in some way (advertising or otherwise).

Although it requires a great deal of courage (to work with privacy sensitive data), the opportunity to invent in the semi-social space may be quite a bit.

These Tweets are from Mars

I am really enjoying the tweets from @MarsPhoenix. Ofcourse this isn't the actual robot sending Twitter updates from millions of miles away, the researchers tweeting on it's behalf are definitely engaging in some interesting conversations. This is one fantastic example of how large organizations can engage in Social Media.

The thought that we are having a conversation with a tiny bot makes the whole experience rather exciting. It wouldn't have been half as much fun if it were for a human persona at the other end. This "bot persona" is more lovable, in part due to our collective imagination and desire of being able to have an intelligent conversation with machines -- our R2-D2s and WALL*Es.

This has been a fantastic experiment in social psychology as well as a superb publicity approach.  MarsPhoenix has about 20K followers  making it one of the most popular Twitter users. Accolades to JPL researcher Veronica McGregor, for this terrific idea and posting interesting updates.

I think that there is a lot more to this story. I imagine that soon we will have more devices that we can talk to directly on Twitter and IM. One idea I had recently was to rig up our lab's coffee machine, Mr. Capresso, with a temperature sensor so that he can automatically inform us when fresh coffee is brewed in the lab.

And at the cost of sounding much like Eliza, I think that for a limited domain, we might even have the capabilities to build Natural Language Generation tools that could automatically post Tweets. I am aware that there are many bots on Twitter. But the tools I would like to see are the ones that can do more than just post a message (like a new video on qik, etc) -- true interaction would come only from conversations. A really wacky (but simple) example would be a poetic bot (yep! people have researched on that too! ;-) )that would send intelligible rhymes in response to @ messages. Might be quite hilarious to follow it!!

Quantifying Social Capital

Since attending the talk by Dr. Tufekci on "The New Social Physics", I have been thinking about social capital and how we can quantify it.

Social Capital, is a term used to describe the intrinsic value of social networks. Robert Putnam attributes social capital to "civic engagement" and as an indicator of "communal health". Pierre Bourdieu describes how social capital explains how people find jobs through their social connections. Similarly, the strength of weak links, describes the importance of social relations in job searches.

In general social capital can be described in terms of bridging capital and bonding capital. Bridging capital is the notion that chance, long range social connections, that we build as part of our social interactions, can help us connect with heterogeneous groups. The idea of "bridges" in social relation is again similar to the notion of connectors in the book "Tipping Point" by Malcolm Gladwell. As Gladwell describes it 

"Connectors are people who link us to the world ... people with a special gift for bringing the world together"

So how can we quantify the connectors? According to the Wikipedia entry:

"There is no widely held consensus on how to measure social capital, which is one of its weaknesses."

One simple way to explain such relations is to use the analogy of bridges. These are individuals who link across the different departments in your office, they are the researchers who have worked with people from other fields and universities. We all know such people and run to them to find our link to the "other side of the planet". One measure that might be useful in quantifying bridging capital is "Edge betweenness". It is a measure that indicates the number of all pair shortest paths that flow through an edge.  In other words, if the edge is removed, many pairs of nodes need to follow a longer path to communicate with each other. Edge-betweenness is also used in some of the community detection techniques. By iteratively removing edges that are most in-between, we can identify the communities that exist in a social network.

Bridging capital is easier to conceptualize than bonding capital. Bonding capital is defined as

"the value assigned to social networks between homogeneous groups of people"

Another way of thinking about bonding capital is as follows: If you were in an urgent need for $500, which you promised to return the next day -- whom would you turn to? The person most likely to lend you the money is one with whom you share a strong bond. In my opinion, one simple way in which bonding capital can be quantified is by measuring the "strength of ties" or the number of common relations you share with another individual. If we think about business partners, it is quite likely that they share the same set of social relationships. Thus their bonding capital will be quite high. By identifying social relationships, which if removed would cause the least effect in the overall shortest path distance between other nodes, we can identify the edges that have a high bonding capital.

Here is a simple example, from the classic karate club dataset. In this graph there are 34 nodes that represent the members of a karate club. During this study the group split into two with half the members going to the founder of the club, node 34 and the rest to the instructor, node 1. Here we can find interesting examples of bridging and bonding capital. The edge between node 33 and node 34 reflect a high bonding capital.. both these nodes have several friends in common. On the other hand the link from 9 to 1 among others are examples of bridging capital.

I would also like to point out a very interesting piece of research by Dr. Tufekci on social relations in Facebook. According to her study, she found that women use Facebook as a means to establish bonding capital while men are trying to increase bridging capital. This is an excellent study on Facebook from a social science perspective and I would highly recommend reading it.

The Cost of Manual Annotation

For many machine learning tasks it can be quite difficult to get the "ground truth" data. In some cases the best way to verify the results is by a painful, laborious and mindnumbing task of labeling data manually. When Pranam and I were working on the Splog detection task, we spent a good deal of time painstakingly labeling independently if a blog from a random sample was legitimate or spam. The part that makes this task difficult is:

• Sometimes it is not clear when something is a blog is a splog
• You need to also look at the inlinks and outlinks
• Plagiarized content makes it harder to judge authenticity
• Sploggers are getting more sophisticated in the methods they are using

On an average we spent about 2-3 minutes per blog and in the end, were only able to hand label a small collection. In comparison to many other tasks this was still a relatively straightforward judgment. Consider the task of relevance ranking that NIST has to perform each year for the TREC tracks. Here the goal is for the annotators to figure out if a result is relevant for a query. The guidelines are strict and NIST has many professional annotators who are trained to perform these tasks. Even more complicated are some of the annotation that might be required in certain Natural Language Processing experiments. These can range anywhere from just verifying a parse tree or an output to actually constructing gold standards or hand crafted parse trees. Moreover, some NLP tools require tremendous amounts of linguistic resources -- be it tediously constructing an ontology, lexicon, gazetteer lists or identifying word senses. Many of these tasks require linguists or experts whose time might be quite valuable.

lets consider a simple case where the annotator was asked to label a URL with a tag. Lets also say that it takes roughly a minute to load the page, quickly glance over it, make a judgment and then type in the appropriate labels. I know from experience that this is not a minute but more like 1.5-2 minutes on an average (try it! it is a braindead boring task and if you are asked to do it continuously, you will slow down!). If say I can work 10 hours on this task without loss in quality of my annotations, it would only result in 600 URLs being tagged. UMBC pays lets say around $10/hour for on-campus jobs. That means we would spend about $100 just to label 600 URLs. Not so sure if that would be the best way I would like to spend a hundred bucks! Additionally, just one human annotator is never sufficient. You always need to answer questions like : "So, what was your inter-annotator agreement?". Well then you just blew another $200 or $300 on this task and still have just 600 URLs marked up. No wonder del.icio.us and Flickr are such amazing sources for free (yaay!), human assessed labels and annotations. It works out great if you can use these instead.

Mechanical Turk is an attempt by Amazon to make it easy for such tasks to be distributed to people who would perform them in return for small micropayments. However, it seems to me that the incentive for completing the task (or doing it well) is so minimal that there is very little enthusiasm around this product. I suspect, the only people completing these HITS are individuals in countries where the dollar still has some value. In fact, there seems to be something fishy about atleast a handful of HITS that are high paying. It looks like the system is totally getting gamed by spammers - look at this example requesting 20 backlinks to a site ($3) or creating bogus accounts ($7) and likes.

The most interesting tool for manual annotation that I have ever seen is the ESP game. It is an excellent entertaining and I must warn you totally addictive. The game works by showing you an image and asking you to label it. You are randomly paired with another player and both get a score if a word matches. This totally ingenious way of collecting annotations for images means that the annotations come absolutely free of cost!

To bring the cost of manual annotation to zero or close to it the best incentive is to provide some value to the annotator. Ofcourse some tasks are so specific or specialized that this might be truly difficult without actually paying someone to go through it. 

From a research perspective, when we build a classifier and use the UCI dataset we have a good "gold standard" and accessible body of literature that has studied the very same data. But as we are dealing with ever increasing size of datasets, access to ground truth or manually verified samples is becoming even more challenging. So is the significance of using it. What does it really mean to annotate less than 0.1% of the data (say you have a very large collection of blogs, images, graph -- whatever social media content you can imagine)?

[Image Courtesy http://www.socialfiction.org/]

The Trilogy of Social Networks Research in Four Parts

Following are some of the books that I highly recommend for anyone interested in the science behind Social Networks research. I like to call this set of books as the "A Trilogy of Social Network Research in Four Parts".

Linked Dr. Albert-László Barabási is a pioneer in social networks research. The concepts of preferential attachment and scale-free networks were first proposed by Dr. Barabási. This has led to our understanding of how human communication works, fault tolerance in real-world networks and discovery of several algorithms that describe the growth of networks, community formation. Linked is a story of a researchers quest for answers to complex phenomena from the spread of viruses to behavior of hubs. Both Linked and Sync are books that teach us how the simplest explanation is usually the best.

Six Degrees Dr. Duncan Watts (Ph.D. student of Dr. Strogatz) presents an excellent look into the recent discoveries in network theory. The book is a tribute to all the academic work that went behind the discovery of small world phenomena, scale free networks and the theory behind search in such complex networks. I particularly enjoyed the book because being in school and working towards a Ph.D., I can really relate to the author's narration of the trials, tribulations and all excitement (yes!) of grad school.

Sync written by Dr. Steven Strogatz, this book was rated as the best of 2003 by Discover magazine. This book talks about how synchrony emerges from a seemingly random and chaotic nature of universe and nature. Its a true science thriller that touches upon complex topics with ease and finesse. It is an inspiring book that truly reflects the passion of someone who is excited about his work, research. Dr. Strogatz has the ability to engage even someone who may have a very little understanding of the subject and describe complex theories in really simple terms.

Nexus This was an interesting read that complemented the Six Degrees and Sync quite nicely. Dr. Marc Buchanan talks about how networks that seem random are actually quite closely linked. The book is a journey from the early days of social networks research and Milgrams experiment of "six degrees of separation" to the most recent discoveries in Physics, Biology and Computer Science that deal with network theory.

Of these I am currently reading  Sync. I read both Linked and Six Degrees simultaneously and really enjoyed how the two books complemented each other and show how two scientists approach the same problem in very different, and equally exciting ways.

[Update] This post should have really been titled "A Researchers Guide to Social Networks: A trilogy in five parts" with the inclusion of "Tipping point". However, despite being a great book, I felt that Tipping point was not as scientifically in-depth and hence decided to leave it at "A trilogy in four parts". But feel free to include tipping point in this reading list since it is a book that highlights some important ideas and in many ways has made the subject appealing to a vast audience.

Oh BTW, Trilogy here was a reference to the three main underlying themes in these books: scale-free networks, small world phenomena and emergence/Synchronization in such systems.