Social Media Research Blog

SocialDevCamp East: Local BarCamp Event in Baltimore

I am excited about the local BarCamp event organized by David Troy of Twittervision and Ann Bernard, Keith Casey from WhyGoSolo. It looks like a fun event and a great "UnConference" for local entrepreneurs, social media enthusiasts and researchers to get together and talk about the future, innovation of Social Media and the Web.

It promises to be an event that would

bring together forward thinkers – developers, social media gurus, bizdev types – to discuss and Chart the Next Course.

The Agenda and signup details are available on the PBWiki site. Some of the proposed session topics (From the Wiki):

• Mobile Application Development with iPhone & Android
• What are the implications of Geo-based web applications?
• How will Agile Development practices affect ideation and funding processes?
• Platforms Present & Future
• What will matter on the web a year or two from now?
• Where will information aggregation take us?
• Social Media is here to stay – so where will it go next?
• How will Google keep affecting development, the web and our lives?
• What are the next things web users will want from the web?
• What will be the impact of future generations to the current web we know today?
• Social Media in the workplace vs. in life
• How the Web is being broken apart into pieces - Justin Thorp

Fantastic! Cant wait to be there!

There are also some sponsorship opportunities (starting @ $250) available for this event. Also please note that there is no cost for participants (which is great for grad students like me!). :-D

For more details please contact Dave Troy or come and chat with us on Facebook.

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?

Notes from DEBSM Workshop: Inferring Privacy Information via Social Relations

Inferring Privacy Information via Social Relations
Wanhong Xu, Xi Zhou Lei Li (presenter)

The presentation started with a neat quote: "Your social activities tell who you are". Social Networking are part of everyday life and for many of us a primary way in which we keep in touch with friends and family. Privacy is a huge problem in such networks. Li provided some statistics from a recent survey of British social network users: about  62 percent are concerned about the security of their personal data. 31% of the users falsify information to protect identity. This is a huge figure and definitely shows the level of concern.

This paper was motivated with applications for social advertising (which is a 2.2B US market). One can target users based on location, age gender etc. and social advertising allows advertisers to choose their audience. The problem comes up where users do not wish to disclose too much of their information online. The proposed solution is to automatically infer such missing information.

The authors use an undisclosed dataset for this study. The assumption is users fake personal information but not their activities. It is well known in offline-social networks that gender preference exist in friendship. however in online social networks this is not true (Jure Leskovec, WWW,2008). The key question that authors of this paper ask is : "Users may fake their personal information...But what about social activities?"

The insight that this paper offers is that certain group membership gives hints of user gender information. Joining groups has a gender preference. So the way in which one can infer the gender is to use a bipartite graph of users->groups with missing gender information using relation between users and groups. One approach is to use the User*Group matrix and build a classifier. However, they found that Naive Bayes does not work very well. Many social groups in fact dont have any gender preference. This can really hurt the classifier accuracy. So one approach they propose is to choose the discriminating social groups. i.e. groups that dominated by males or females. One major disadvantage that this technique suffers from is that the membership for users that dont join any of these groups can not be predicted. Once you restrict to the set of discriminating groups, now Naive Bayes performs well.

For users that cant be predicted they propose the use of an iterative algorithm to combine discriminative social groups and results from Naive Bayes classifier. Testing is performed by removing or making some data missing and then predicting the missing gender information.

My concern here is that the authors might have been able to avoid this disadvantage if they had used SVD to map the Groups to a set of lower dimensions that way it would automatically "cluster" the groups based on whatever the discriminating factor is (in their case the gender information). Secondly, while the authors had access to "verifiable" ground truth data, in real world how do we know the influence of fake profiles on these discriminative groups?

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).

Notes from DEBSM Workshop: Monitoring the Evolution of Interest in Blogosphere

Monitoring the evolution of interests in the blogosphere
Iraklis Varlamis (Presenter), Vasilis Vassalos, Antonis Palaios

The authors present a simple (perhaps even obvious) hypothesis that "Interests of bloggers converge around real world events".

A prototype system was built to to analyze blogs and monitor the evolution of interests. Existing search engines monitor the term popularity of words in isolation and the related terms are not clustered in any way to identify the topics. A motivating example presented was around the football world cup season, where there might be terms like "football" "round" "final" "result" "world cup" and aggregated scores for topic would be helpful rather than having to find/view the histograms for each of these terms. Also one can not know all the terms for a given topic. In many cases, multilingual content and difference in vocabulary can further make it difficult to just monitor the term popularity. Other approaches require training a topic based on a given set of training/pre-annotated document pool. This is an expensive and a semi-supervised method can be strongly effected by the selection of the initial document pool.

The goal of their paper is to build an unsupervised approach to cluster the documents and identify the evolution of interest. However, the current algorithm presented is not incremental; but they claim some recent work on an incremental version. The current version of their algorithm uses the DBScan clustering technique. Term space is clustered at the post level and their evaluation is done using inter cluster, intra cluster similarity and the utility function. They have used the BuzzMetrics dataset, however they only focus on blogs that have a post everyday, which brings the dataset down to 2500 blogs. The posts are classified into topics and then the blogs are clustered. The categories are determined by using the Cyberfiber news groups to find the topics and training documents. This is an interesting dataset that I was not aware of.

Some questions that came up were the choice of using newswire documents to learn classifiers, and also the accuracy of the classifiers. While the original hypothesis seems obvious, it can be seen as a litmus test for the efficacy of the clustering algorithms. In particular the examples presented were using the "London Bombing" Event. Any clustering algorithm that groups the related terms must at the very least pass the litmus test to show that it works.

I think that in general there are perhaps two types of events, one concerning a very specific group of individuals  ("County elections", social events, conferences etc) where online communities emerge due to offline events. The other is around real word events like "London bombings" or "Hurricane Katrina": both of which are examples of events that cut across community boundaries and which invoke reaction from almost every part of the blogosphere and almost in unison. In such cases on might see that the original community affiliation of the bloggers dont matter and tech, politics, religion and every other community might be talking about the same issue.

Notes from DEBSM Workshop: Exploiting Social Relations for Query Expansion

Exploiting Social Relations for Query Expansionand Result Ranking
Matthias Bender, Tom Crecelius, Mouna Kacimi, Sebastian Michel, Thomas Neumann, Josiane Xavier Parreira, Ralf Schenkel, Gerhard Weikumza

This paper was presented by Mouna Kacimi.

This paper is about Query expansion in social networks and addresses the question of defining the valuable content to users in rich, online communities. Mouna suggests that one way to improve the search experience is by utilizing the social network information. The paper defines a social graph and provides scoring mechanism for finding and ranking relevant content for each node. In social networks, users can be both producers and consumers of information.Typically, the user has documents (photos, posts, etc) and tags. There are relations between nodes of the same type, for example

• friendship between nodes
• similarity between text
• similarity between tags
• linkage between the documents 

Further there can be relations between nodes of different types:

• Between tags and document
• users and tags -- how imp is this tag for a user;
• user can also have a relation with documents in terms of ratings

This paper presents a generic framework for ranking relevant information for a given user; by utilizing the various elements of the social information. The scoring model can be thought of as a means of querying what your friends think about the relevance of the given information. It combines the following pieces of information:

• what your friends think of this document
• how strong is your friendship with your friend
• user rank for the friend who described the document
• document rank of the document.

Note that the authors have considered an independence assumption in computing the scores. I am not certain if this is a good assumption, but it would be one simple way of combining the scores.

In order to do query expansion, i "ask" my friends about Paris, friend's documents about paris are retrieved and other similar tags are obtained. These are used to compute the query expansion. Friendship strength is computed using the "social distance" while the tag similarity is computed based on co-occurence of the tags.

I was surprised by their finding that social search works better in flickr but not very well in del.icio.us. I think that this is because the social networks of del.icio.us are very sparse. The meaning of friendship is also different here (aka friends and fans).

However, Mouna also pointed out that an improved version of their technique has been accepted at SIGIR 2008 and has a more detailed analysis. I look forward to checking out their extended paper. What I really liked about this paper was that it was a generic framework for combining social information (network, tags, documents, etc) and can be extended in ways that would be suitable for a particular type of network or task.

 

ICDE Workshop on Data Engineering for Blogs Social Media and Web 2.0

The Data Engineering for Blogs, Social Media and Web 2.0 workshop was held in conjunction with ICDE 2008. There were some really interesting papers and the invited talk was given by  Prof. Ravi Sandhu. I had the opportunity to present some of our work at this workshop. My talk was about "Communities in Social media" which was about some of our recent work on "Approximating the Community Structure of the Long Tail" (ICWSM) and an overview of our previous and recent research in this area.

As Matt noticed already, not all the authors have their papers online, yet. I am still trying to figure out what the IEEE conference policy is for uploading the PDFs of the papers on the workshop website. Perhaps, I shall try to request the authors to upload the copies and link to them from the workshop website. In the following series of posts, I will share some of my notes from the different talks.

And oh yesss! the fact that the conference was in Cancun was just great! :-D

Notes from Brad Fitzpatrick's Invited Talk at ICWSM

Brad Fitzpatrick was over at ICWSM and gave a keynote on "Decentralization and Social Graphs". Following are some notes from the talk. Please note these are from rush transcription during the talk and from my recollection of what was presented. Please feel free to comment if I have missed something or if you feel something is incorrect.

Brad talks about Social graph and highlights some of the problems with traditional forms of communication. Email for example, lacks sender authentication or verification which lead to spam. Phone traditionally did not have any sender authentication and later these services were bolted on to the original infrastructure. Instant Messenger services don't always offer interoperability. Brad says that the  future of IM is Jabber/XMPP, which offers a decentralized system protocol. Gtalk, Livejournal both use Jabber and this makes it easily interoperable. In general the his talk highlights the importance of decentralization. Other things that are decentralized are email, wikis, ethernet, bittorrent etc.

Blogs are pretty much decentralized and interoperate using ATOM/RSS, but the difficult thing is commenting. Social Network sites are still "walled gardens" and basically need to re-invent everything -- sign up process, profile etc.... just to be able to provide one "cool feature". So as of now many of them dont work with each other. This is bound to change.

Brad says that the "glimmers of hope" are the following:

• XMPP Gtalk uses XMPP and in fact I have played around with it a bit and it is really a simple and neat way to communicate with instant Messengers.

• RSS/ATOM Ofcourse blog readers have relied on RSS/ATOM. From David Sifry's talk I recollect that ATOM is the preferred form of syndication for Technorati, since it avoids having to crawl the entire HTML content to be sure that partially syndicated feeds are handled correctly.

• OpenID This eases signups/logins. Already many of the providers and sites have adopted the OpenID standard.

• OAuth This provides an easy way for authorization... Often we are faced with a situation where some new random site says "hey why dont you gimme your password?". However, can you trust it with your password? OAuth is an alternative way for one website to request action on another.

• XFN/Microformat/FOAF Machine Readable format of the social graph. While there is a good amount of FOAF data online, it is hardly enough to cover the entire social graph. Apparently XFN is more popular and is also used by Twitter.

• OpenSocial This is a standard way for containers (social network sites) to host social apps. Same app works on Orkut, Myspace, Hi5 and .... now also Yahoo. This is a big leap towards interoperability.

• XRDS (Yardis) provides a discovery mechanism on a URL... suppose a site needs to ask another "where is your OpenID server" ... "Where is your calendar" etc.

• Social Graph API This is Brad's very own pet project. It finds and parses XFN, FOAF, me links. Provides an API for the social graph. A nice way to find missing friends. This solves the problem of not knowing all the alternative userids for my friends.

So to summarize the talk : use OpenID to log in to the site..... Site reuses public profile..... it can ask for pvt stuff using OAuth..... container app uses OpenSocial and Social Graph finds friends. And we all live happily ever after in our nice little online worlds :-) and all sites talk to each other and we are all F.R.I.E.N.D.S! :-)

The talk also highlighted some missing pieces:

    - messaging URLs

    - URL - email interop

    - XMPP/JID binding

    - Reputation server

    - promoting or documenting.

Some startups that are currently using open protocols twitter, dopplr, plaxo, pownce.

Brad says that users expect things to interoperate ... and decentralized is more robust. Social networks are broken today but are getting better.

Overall, it was a very interesting talk but I felt that it was kind of short and it would have also been fun to see more details.

On Approximating the Community Structure of the Long Tail

Social Networks and Web graphs exhibit certain typical properties. The classic work by Barabási–Albert showed how nodes in such network link preferentially -- popular nodes often gain disproportionately larger share of the links. This is also known in other fields as the 80/20 rule or simply the "rich get richer phenomenon".  Another early work by Steve Borgatti studied social networks and found that they exhibit a core-periphery property. A small set of (popular) nodes form the core and the rest comprise of the peripheral nodes. To the best of my knowledge, community detection algorithms have often worked independent of the underlying network properties.

I have been exploring an idea that can utilize the core-periphery structure of social networks to approximately compute the communities in the graph. The intuition behind this method is really quite simple. The basic idea boils down to the following:

"The core of the social network typically defines the communities present in it. By looking at the link structure of the core and identifying how the rest of the network connects to the core we can efficiently compute communities in large graphs."

This idea can be easily explained by considering the following network of email communication (obtained from Dr. Mark Newman's site). The original adjacency matrix was permuted to order the nodes based on  their degree. Thus the core is represented by submatrix A which is quite dense. The submatrix B, here corresponds to how the rest of the network links to its core. The submatrix C is a very sparse matrix that consists of links between nodes in the long tail. From a mathematical point of view this is quite sparse and can be ignored, without much degradation of the clustering/community detection results. Thus it leads to saving a significant amount of computation and storage. By utilizing just the core of the social network (matrix A) and how other nodes link to the core (matrix B) we can approximate the overall community structure of the entire graph, much more efficiently.

The rest boils down the to the mathematical formulation of the above idea. You can read more about it in my poster paper that was recently accepted to ICWSM. (Available for download on 02/16/08)