Social Media Research Blog

Social Media Conferences and Workshops

ICWSM was a great hit! And now there are a growing number of conferences (WWW 08 social networks and Web 2.0)  and workshops (DEBSM) for social media research. This is fantastic for the community as a whole: as more people are excited about working in this area, we can bet there will be some significant advances in research and improve our understanding of online communities and social media content. What I particularly love is the fact that Social Media research is an exciting interplay of computer science, social science, psychology and other related fields.

I decided to maintain a list of upcoming conference deadlines and venues for social media research. With a little help from the community, I will try and keep this list up-to-date and accurate. Here is an initial list of upcoming venues for the next few months, while I gather and organize all the deadlines in Google Calendar or something.

• The First International Workshop on Data Semantics in Social Computing
  Systems (DiSCo `08) [http://www.deg.byu.edu/ding/workshop/disco08.html]
• International Workshop on Computational Social Networks (IWCSN 2008)
  http://www.softcomputing.net/~csn/
• The First Workshop on Information Retrieval for Advertising
  Collocated with SIGIR 2008
  http://research.microsoft.com/workshops/ira2008/
• AND08: Second Workshop on Analytics for Noisy
  Unstructured Text Data http://and2008workshop.googlepages.com/
• Workshop on Urban, Community, and Social Applications of Networked
  Sensing Systems http://sensorlab.cs.dartmouth.edu/urbansensing/
• Search in Social Media (SSM 2008)
  A workshop held in conjunction with CIKM 2008
  http://ir.mathcs.emory.edu/SSM2008/
• Wikis, Blogs, Bookmarking Tools - Mining the Web 2.0 (WBBTMine'08)
  http://www.kde.cs.uni-kassel.de/ws/wbbtmine2008/
• The 2nd International Workshop on Social Network Mining and Analysis (SNAKDD 2008)
   http://workshops.socialnetworkanalysis.info/SNAKDD2008/
• [Update] Special Session on Mining of Social Media @ SAMT 2008 http://samt2008.uni-koblenz.de/index.php?page=calls_papers

Please comment below or email me if you know of any other venues and I shall make sure to add them to this list. Hope to see you at the next conference/workshop!

Nonnegative Matrix Factorization

Sometimes you learn about a new mathematical technique that is so intriguing that it can be only described as "beautiful". Nonnegative matrix factorization is one such method that I did not know of until quite recently. The details of the method are available in the paper "Document Clustering Based On Non-negative Matrix Factorization" by Wei Xu, Xin Liu, Yihong Gong.   

The basic idea behind this method is that you want to factorize a matrix X into two smaller matrices U and V such that, both U and V are non negative. This is achieved by using minimizing the following optimization function

So if we have a matrix X that represents a Term*Document matrix: it can be factorized into the two matrices U and V such that U signifies the Term*ClusterAssociation and V transpose signifies the ClusterAssociation*Document matrix. Now since the two matrices U and V are non negative, meaning all the elements in them are >= 0, we can identify the cluster to which a document belongs by projecting the vector V onto the dimension with the highest value.

Singular Valued Decomposition(SVD), decomposes X into dense matrices that can contain negative elements and it is not always intuitive what the basis vectors really signify. However using NMF the clusters are readily and directly available from the factorization. In addition, the sparsity makes this technique quite appealing.

In the following example, I have clustered the CLASSIC3 dataset, which is a standard corpus frequently used for evaluating different clustering methods. Notice how the three datasets CISI, MEDLINE and CRANFIELD line up nicely along the three different axis.

I like this method for its simplicity and intuition and have been exploring its use in clustering blog/social data.

The Psychology of Social Networks (KQED Talk)

Just wanted to share a quick note to the KQED/NPR radio talk on "The Psychology of Social Networks" (via Meghavini Shah, Thanks for the pointer!) 

Radio host par excellence,  Michael Krasny talks to

• B.J. Fogg, director of the Persuasive Technology Laboratory at Stanford University and the author of an upcoming book on the psychology of Facebook

• Sam Gosling, assistant professor of psychology at the University of Texas at Austin

They cover a wide range of topics and discuss the how social networks are changing the way we interact with each other. It is a really good show and I would highly recommend listening to it if you can.

Over the past few weeks, I have learned of many interesting anecdotal evidences about our online and offline behaviors and how social networks have become such an important part of the equation. I thought I would share it in the context of this talk. Here are a few noteworthy examples:

• Teenagers in India are socially quite comfortable expressing their relationship status on Facebook/myspace/orkut -- but would not reveal this information to their parents or family.
• Social networks have provided a socially acceptable setting for "checking out" profiles. Arranged marriages in India are still fairly common and it is not unusual for people to check out the profile, scraps and testimony pages of prospective partners before actually meeting them in person. I guess the same is true for dating in general, people judge you by not just who you are and how you look but also who your friends are (and I guess even how they look) and what they have to say about you.
• Coaches usually "friend" athletes on Facebook so that they can keep tabs on any parties that students have been going to and to check if they have a "red cup" in their hand (indicating that they have been consuming alcohol). Cell phone cameras are the easiest way for such information to leak onto Facebook. So parties these days have a "NO CELL PHONE" policy.
• Dont assume that your school teachers or professors dont know what Facebook is! Students found cheating on exams have been completely baffled to see that their profs actually checked their FB profiles to know if the students are friends -- despite their claims of innocence and that they dont know each other.
• Finally, at SocialDevCamp one really cool trend was that people were exchanging their Twitter ids more frequently than business cards. I am still enjoying the conversations that this community of users is having on Twitter. What would have been a one-off meeting is not a sustained community thanks to the power of social networks.

Footnote: Please consider supporting KQED or your local public broadcasting station, who bring to you such excellent programming.

News feed vs. blog posts vs. email

What is the difference in size distribution of a news wire vs. a blog post vs. email message?

The below three images compare the size distribution of news wires (Reuters collection) , blog posts (from the ICWSM dataset) and email messages (Enron Corpus).  The charts show the histograms of the size of the documents in these collections:

The three distributions above (ignoring documents smaller than 2000 bytes) were fitted using the matlab scripts for powerlaw fits (Thanks to Aaron Cluaset). 

The linguistic properties of blogs email and news stories are quite different and this has already been highlighted in several research papers. While the three data sets are quite different in many ways, here I am analyzing just the size distributions. The  important point to note is 

• News wire stories are quite short
• Blogs and emails are much longer and have a heavy tail distribution
• Power law exponents for blog size distribution and email size distribution are quite similar (around 2.7)

So...what does this mean? It is fairly obvious that news wire stories are quite short due to the nature of reporting. Sometimes the initial news story is quickly reported by agencies like Reuters/AP. These are at times brief and to the point to allow readers to get a quick gist of its contents.

In contrast the size of blogs tend to be much larger than news wires. Citizen journalism is full of opinions thoughts and punditry thus bloating the post. This also goes back to my previous analysis of the blog homepage size vs. Web page size. Indeed the contribution of blogs has been reported to be 4-5 times that of edited text (like the news wires).

What I had not expected was the similarity in the slopes for email and blogs. One thing to note however is that here the emails are aggregated across a number of different users. This is an important distinction. While a single user may receive a few hundred emails, they potentially have access to millions of blogs. Recently, industry's top usability expert Jakob Nielsen concluded that readers skim through and read at most 20% of the words on a Webpage. While there are millions of blog posts every day... there is very little time to read them all in detail. The volume of email is limited by a person's social network but for blogs the act of prioritizing what to read is entirely left upon the user. This essentially necessitates the use of Memetrackers and explains the popularity of filtering tools like digg, techmeme etc. By summarizing popular blog posts and providing blurbs for these, such tools essentially act as a  "social news wire service for the blogosphere".

Distinguished Speaker: Jiawei Han on "Research Challenges in Data Mining"

It was an honor to have Dr. Jiawei Han on our campus today. He was hosted by the Information Systems (IS) department as part of the distinguished speaker series. Dr. Han is a pioneer in the field of data mining and has written a book that I had used for the Data Mining class I took with Dr. Kargupta.  In fact,  Dr. Han even obliged to autograph the copy for me :-D. (I know thats geeky but is'nt that cool?)

Here is a summary of his talk on "Research Challenges in Data Mining".

Dr. Han narrates and interesting episode where Dr. Jim Gray brought in a hard disk and asked his students to guess the capacity... this was perhaps just 10 years back and a 2G disk evoked a jaw dropping response from the audience. According to Dr. Jim Gray, "We are in the era of Data Science". Science used to be
experimental (observe the stars) then it moved to computational (run simulations) but now we are really moving towards  "Data Science" (Gigabytes, Terabytes and Petabytes of data all around us).

The main themes of the talk were:

1) Pattern Mining: Classification by finding frequent, discriminative patterns.

Dr. Han described an interesting experiment in which they analyzed the feature length vs information gain. What they found was that you get more information by combining features (2,3,4), while single features dont give you much information. On the other hand too long pattern, and it is not too informative either. This has an important implication, especially in text mining where using NGrams (bigrams and trigrams) has generally been found to be useful but if you use too long a pattern, it is not that helpful.

Another analysis presented was of information gain vs pattern freq: Frequent patterns have more information gain than less frequent ones. On the other hand extremely frequent patterns have little gain (for example stop words).

The implication of these results is in using SVMs and C4.5,  classification accuracy can be improved by using discriminative patters/feature selection.  Dr. Han suggests that "It is not the number of patterns its the quality of patterns. Its Not the more the better ......instead, the better the better." A few selected discriminative patterns are more useful than a lot of features in case of classification.

2) Streams Data Mining Classification for rare events.

When you have multiple streams of information and you can not store all the data, but need to remember some of the history, (in order to do classification of a new stream) it is helpful to use sampling techniques. Dr. Han discusses results from one of their recent papers on using biased sampling. The idea here is that you dont toss off positive data (all of it is stored since there are very few samples). Now, by selective sampling of negative data one can use equal amount of positive and negative data for training a classifier. In case of multiple streams, using an ensemble approach to classification is suggested.

3) Information network analysis. Distinguishing objects with identical names. (eg author names, song names)

Name disambiguation is a very difficult problem. For eg there are 14 Wei Wang on DBLP -- some with even same co-authors, same conferences, etc. in such cases, textual similarity can not be used, since they are all basically in the same field. Dr. Han discusses how using only information from DBLP, they make links powerful. The basic idea is to group references according to their similarity. By performing a random walks along different join paths, they can group the authors and determine the different name ambiguities in the graph. Often, in computer science and other fields, Collaboration behavior within the same community share some similarity and this can be helpful in disambiguation.

Another research paper that Dr. Han highlights is on "Truth discovery with multiple conflicting information providers on the web". The goal here is to algorithmically determine what piece on the Web is more trustworthy. The proposed approach is to model it as a tripartite graph of (website,facts,object).

Assumption is that there is just one true fact and that false 'facts' are introduced due to random factors (and not malicious intent). The domain was restricted to identifying the right book title, which is slightly easier than something like political opinions. The basic idea behind their approach is that a site is trustworthy if it provides many facts with high confidence and once again this can be modeled as a matrix computation problem of identifying trustworthiness.

Some of the other areas that were very briefly mentioned by Dr. Han were:

4) Mining moving objects - unrestricted, restricted (cars) scattered (Cell phone and rfid)
5) Spatio temporal multimedia clustering with obstacles
6) blog mining, etc.
7) data cubes.
8) Visual data mining
9) Biological data mining
10) DM for software engineering/bug mining

This was a great talk and very informative. I really liked how the Dr. Han gave the basic intuition behind their methods and yet managed to give a broad overview of some of the challenges in the field.

The Bane of Fame

I was working on this post and read a timely piece by Erik at Techcrunch on the level of noise and our inability to keep up with the conversations online. Further comments by Alexander as well.

Clay Shirky, in his book "Here Comes Everybody" mentions how fame can come at a cost. The example he presents is that of a blogger with 10,000 strong audience, is interacting with each of his readers for 1 min; it amounts to almost a full-time job ~ 40 Hours/Week. Here the interaction can mean that someone has just created a link and you go check it out; someone has written a blog post in response; posted a video/podcast; just commented on your blog, sent a tweet in response to yours, posted a photo from the conference you attended or plain old fashioned email/phone conversations.

I tried to extrapolate this and see how it would work in a typical scenario. Lets say you are an average blogger who spends 30 Mins /post/day  and your audience created 1000 items for you to responding to. Perhaps on an average you spend 5 Mins per response (this might include reading the comment, tweet, post, email; thinking time; writing time etc.) Then one would pretty much spend about ~25 Hours / Week for about 1000 responses/month.

This is the bane of fame! As you get famous, and receive more attention in your social network -- you cant respond to everyone. I can hardly figure out how Scoble can keep up his pace on his blog and Twitter! I think Tech bloggers are slightly better at managing how they use technology to their advantage and can keep up with a much larger audience than most people. Still, Shirky's book is a great place to understand how the attention economy is changing our social interactions.

That also makes me wonder if someone has seen any research on email/usenet usage patterns? Somehow that is one area that shares similarities and I am certain that usability experts would have done some such studies already. How do you think this would compare with Facebook and Social Media in general? There are people for whom Facebook is their default -- everything from email/IM to SN -- So it does not feel like they are trying to respond to requests from many different networks! I wonder what is the cost of context switching from one network to another and perhaps that is the reason why FriendFeed seems like a neat way to manage multiple information streams?

Clustering Tags and Links Simultaneously

I have a large collection of blogs that I would like to cluster. For the blogs in my collection, I have the following information:

• Text aggregated across all the posts
• A dump of the homepage of the blog
• Tags obtained from del.icio.us or "Feeds that matter"
• And finally how the blogs link to each other (aggregated across all the posts)

If we want to cluster the blogs, one can take the following approaches:

1. Cluster the blogs using only the text (Kmeans style)
2. Cluster the blogs using only the link information (By say performing NCut)
3. First cluster all the tags (so you would group "tech", "technology", "geek" etc) and then group the blogs that are categorized in each of these clusters.
4. Using a bipartite graph of the form <Blog,tag>. This is also known as co-clustering.

The problem with using the text alone is that the data can be huge (typically in Gigs) and it is almost essential to use some dimensionality reduction techniques like PCA etc. By performing NCut over the graph alone, you land up ignoring the text or the tag information that could be quite helpful. By clustering in only the tag space and then mapping the resulting clusters to the blog graph, we miss how the blogs might be interconnected. Finally, co-clustering technique too misses the fact that the blogs might link to each other and this information can be quite useful in grouping them together.

The question I was wondering about was how to cluster the blogs while using both the link and the tag information simultaneously. I think that the tags provide a reduce dimensional representation of the text. The tag space is of a much lower dimension than the complete text of the collection and it can be efficient to cluster the blogs using tags than the complete text.

Recently, I came across a very interesting piece of work that talked about "Classification Constrained Dimensionality Reduction". The idea here is that if we have a bunch of data points for which we know the true class information, we would like to classify the remaining points such that the available class information is utilized to guide the dimensionality reduction.

The above paper applied very well to our problem. One simple way to combine the two different information is to use the matrix W' shown here. C is a k*n matrix where n is the number of blogs and k is the number of tags. While W is the adjacency matrix of size n*n. I is an identity matrix of size k*k. Typically, we can get away by using only the top 200-500 most popular tags. Now, if we perform NCut using the matrix W' instead of using W alone, we can combine/fold-in the tag information with the link information. The parameter \beta controls how much importance we would like to give to the graph versus the tag information.

For example for a blog graph consisting of ~3000 blogs, I fetched the tags from del.icio.us and the link graph from the WWE/Buzzmetrics collection. Figure on the right shows 20 clusters if we use just the link information and perform NCut and the same graph using the simultaneous clustering method. Notice, how the 20 odd clusters seem nicely block diagonalized in comparison with the results using link information alone. It would be interesting to look at how these techniques compare with that using the entire text from all the blogs. I am working on this and the intuition is: we might be able to show that using just tag and link information, we can do as good (or better) than using the entire text. Afterall tags are nothing but a place holder for the "topic" of the blog.

An even more interesting extension would be to use the original paper that presented the constrained classification using dimensionality reduction and apply the same technique to our problem, such that we can perform clustering using just a small set of labeled blog and labels (matrix C).

Laplacian Eigenmaps

In the previous posts I talked about some of the papers I have read recently on spectral clustering and graph based methods. I wanted thought I would provide one more example that would try and explain the use of graph Laplacian. The basic idea is that the graph lies on a 'manifold' which, to completely simplify it, would mean that the graph lies in some multidimensional space.

For example, here is a random dataset that was generated using three Gaussian distributions. In order to obtain a graph from these points, an RBF kernel was used. The corresponding graph Laplacian is then computed from this kernel. When we project the data onto the vectors corresponding to the second and third smallest non-zero eigenvalues , we can see that the three Gaussian distributions are clearly distinguishable. This type of projection is known as Laplacian eigenmap. For more details please refer paper by Niyogi et al.

As  an example of how this applies to the community detection / Semi-Supervised graph learning problem, here is a graph of the political books dataset. The corresponding  projection is shown below. While most of the conservative and liberal books can be identified some neutral books are a bit ambiguous making them harder to classify correctly.Typically, in case of spectral clustering we would only need to consider the second smallest eigenvector of the graph laplacian. It is also known as the "Fiedler" Vector and is used in graph partitioning.

Please note that this series of blog post on spectral methods is my attempt to share my understanding of the papers I have read recently. I am happy to receive further references and clarifications of the points discussed here.

Labeling Blogs using Graph Regularization

Recently I learned about semi-supervised learning over graphs. Using a small number of labeled nodes, the task is to find the appropriate nodes that belong to the same class as the labeled, training data. This problem is typical in Web spam detection where some hosts are identified as spammers (possibly manually) and the goal is to automatically tag the rest of the hosts as either spammers/non-spammers.

A similar task can be formulated for learning the labels in blog graphs. For popular blogs, it is not hard to find good quality labels using either Bloglines or del.icio.us. Often these labels are most reliable for popular blogs that have been tagged by many readers. Now in order to find out the other blogs that share the same label, a method recently suggested is Graph Regularization. (And for an overview on label propagation methods here is a nice tutorial).

Graph regularization uses the spectral properties of the graph to find a function that satisfies the following two constraints:

• Smoothness Constraint
• Fitting Constraint

According to the smoothness constraint, nodes that are close to each other in the graph would have the same label. On the other hand the fitting constraint ensures that the final label assignments do not deviate too much from the training data. Thus imposing a penalty for misclassification of training examples. The two constraints can be formulated in terms of the graph Laplacian. For details refer Zhou et al.

As an example, for a small blog graph, I obtained the del.icio.us tags corresponding to each blog. Empirically, I find that del.icio.us tags provide very good description of the blog. Once the tags are obtained (I used the JSON API), I use just 10 blogs tagged as "sports" and use the above regularization method to find other blogs that might be similar. The final scores (see figure, right) after regularization correspond to the community structure (found using Ncut, left) as shown in the figure below.

Here is the list of some blogs that were categorized under the label "sports", starting with the training set of 10 blogs.

In my opinion, two things stand out... one the Ncut algorithm itself may be improved if it was to be using additional tag information. Secondly, label propagation for blogs is slightly more complicated than just the original binary classification (spam/not spam) problem. One could have a few hundreds different labels that might need to be propagated, moreover -- the labels themselves may be quite related ("tech","technology","Programming", etc). Adding the constraint that labels should be propagated, subject to some known distribution makes optimizing the above cost function slightly more complicated. Furthermore, a blog may be equally relevant to two very different labels -- "politics" and "sports".

Any thoughts? Other techniques that might be useful? Ideas on how inter-related, multiple labels, can be propagated over a graph?

Measuring Similarity in Social Media?

What is similarity? Does the richness of meta-data and the range of content in social media make it harder to define similarity in the context of Social Media? Jonathan's comments reminded me of a few thoughts I had recently on similarity in Social Media. And I think Jon raises a critical point which applies to this post as well. Like relevance, how we define similarity would really be dependent on the task.

Nevertheless, the traditional view of similarity measure is in terms of document similarity measured using cosine similarity. An extension is that rather than using content similarity, some researchers model topics using techniques like LDA, thus resulting in topic similarity. While, content/topic similarity is surely still used in blog analysis there are wider set of interesting features to build on.

Tag Similarity: Folksonomies for instance offer user-generated tags. This is a helpful feature to find out if two blogs are somehow related. The tags used by the author of the post is another feature. These may or may not correspond with the tags used by their readers (or on bookmarks in del.icio.us). I find it interesting that these two may often complement each other. Authors might tag their posts with specifics (like "Hilary clinton", "immigration" etc), while the reader can simply categorize the blog under a general tag "politics".

Community Structure: The graph itself has cues that offer hints about the similarity between two blogs. Community structure is definitely of importance and blogs that structurally belong to the same cluster are often related. The slight issue is that link semantics in the Blogosphere can be different from that of the Web.

Link Semantics: Traditional view of links is that of endorsement, but in the Blogosphere, sentiments may even play a big role. Related with link semantics is also the question of relation-type. Blogrolls and linkrolls are yet another way in which two blogs can be related. Adding a blog in my blogroll might not necessarily mean that its topically related -- it could just mean a sort of vague friendship / foaf:friend type of a relation.

Additionally, a significant percentage of links created on blogs point to main stream media. One can consider this as a bipartite graph  with blogs and MSM sites as the two node types. Clustering blogs that point to similar set of MSM sources can reveal additional similarity cues. This would be more particularly distinct in political domain.

While I approach this question from the viewpoint of blogs, social network and flickr communities have still further relation-types and features. In such systems comments, group memberships, affiliations etc. can be additional indicators for similarity measures.

I believe that it is still an open question how such varied features can be utilized to measure similarity in Social Media. I am sure that there are going to be a TON of interesting discussions on some of these issues at ICWSM, which I am eagerly looking forward to.