Social Media Research Blog

Ph.D. Dissertation Defended!

Yep, its true! I just defended my Ph.D. dissertation yesterday! w00t! w00t! The defense presentation went quite well and I had all the paper work turned in today. A few minor updates to my document and I should be done. I was back in the lab today and attended the CSEE colloquium talks and then the Hi Tea. Doesn't feel like I am no longer a grad student. But it is time for me to move on.

I am real excited about my new position: I will be joining Microsoft Live Labs and moving to Seattle next month!! w00t! Live Labs is a wonderful place and I am absolutely thrilled at the opportunity to work with so many smart folks there. When I interviewed at Live Labs I just knew for sure that this is where I wanted to go. It is a fun place and a perfect match especially for the type of stuff I am passionate about.    

Everyone has been asking me about how I feel now that I am done? It hasn't sunk in yet, but all I can say is that I just feel glad to have finally completed my Ph.D.  I feel honored that I am Prof. Finin's protege. There is so much I have learned from my advisor and many qualities that I still aspire for. Prof. Joshi has been equally instrumental in guiding my research and ensuring my progress, for which I feel grateful. There are many colleagues at UMBC who have enriched my skills and I feel my school (and definitely the lab!) has been a second home. A special shout out to my good friend and academic sibling Pranam Dr. Kolari. Also, through various internships during my academic years, I have been fortunate to have collaborated with many brilliant researchers who have been inspirational to me.  I think I was also lucky to find myself doing research at just the right point of time in Web's history where things are changing so quickly and becoming richer and more social. This has been incredibly exciting for my research. Most of all I feel thankful to my parents, my family, friends and so many people who totally believed in me. Thank you all for always being there for me.

On Monday, I will be heading home to India for a few days to spend some time with my family. Blogging might be intermittent for a while. :-)

We the Numerati

A quick post: I am almost finished reading "the Numerati" by Stephen Baker. I must say that I had very high expectations from this book and it seems to have come slightly short of it. Dont get me wrong, it is certainly a good book but, it wasn't a very technical book. So many of the topics and ideas presented here might sound quite familiar to someone who is wading in data and algorithms every waking hour. What I really like about the author is the way he treads a fine line between dismissing some of the myths about data miners and highlighting some legitimate concerns in the field. It is a great compilation of interviews and summarizes a number of research topics. A few interesting points/quotes from the book: Be watchful of the fact that in some fields (like analyzing terrorist networks) where lives are at stake, we need to be very very careful. False positives doesnt necessarily mean that it is a non-event. On the other hand, innocent folks can find themselves on terrorist watch lists. Failure can cost lives. From David Sifry's interview in the book -- be cautious of "mistaking correlation for causation". Don't think of privacy filters as add-ons that we can worry about after coming up with the data mining techniques. In Jeff Jonas's words sometimes "repurposing" data can lead to unintended uses. Watch out! Stephen Baker touches upon many different applications and profiles a number of scientists, companies and startups that make up the Numerati. My favorite chapter ofcourse was the "Blogger" and "Terrorist" for its social media and social network related discussions (OK I admit there is a slight bias here :-). And Pranam too is eagerly looking forward to reading the pages that talk about splogs. (I am rather surprised that he wasn't interviewed for this!) Overall, its a good book that caters to a wide audience. But most importantly does a great job at demystifying the Numerati and showing a balanced, informed picture about what we do.

CFP: Workshop on Location and the Web (LocWeb 2009)

With the popularity of geolocation, mobile search, iphone/Andrioid apps, local advertising, location information is playing an important role in social media today. We have started sharing our location information on the web and via mobile devices through a number of services -- FireEagle, Brightkite, twitter, loopt, dopplr, Whrrl, geohash, citysense -- just to name a few. (phew!)

The "Second International Workshop on Location and the Web (LocWeb 2009)" to be held in conjunction with CHI 2009 (Boston, MA) looks like a very interesting venue to discuss ideas and research related to this topic.

From the CFP

Workshop Website: http://ifgi.uni-muenster.de/locweb2009/
Position Paper Submission Deadline: October 23, 2008

Overview

The goal of the Second International Workshop on Location and the Web
(LocWeb 2009) is to bring together researchers to discuss the ways in which
location as a first-class concept in Web services and Web applications will
transform the Web into a location-aware information system. We are
particularly interested in how location concepts can be shared across
applications to provide adequate support for an evolving ecosystem of
location-aware services and applications.

This event has been updated in the Social Media events calendar.

DAPD special issue on Data Management in Social Media

[Reposted from eBiquity Blog. Please contact me or Prof. Anupam Joshi for further details.]

We (Tim Finin, Anupam Joshi, and Akshay Java) are editing a special issue of Distributed and Parallel Databases on Data Management in Social Media. Manuscripts must be submitted by January 15, 2009 and should not exceed 25 pages in length. Authors will be notified by April 15 and camera ready copy will be due May 15. Submit papers online specifying article type S.I.: Data Management for the Social Web. For more information, see the call for papers (pdf) or contact Anupam Joshi at [email protected].

Social Media tools like blogs, wikis and social networking sites are providing new opportunities for us to connect and interact with each other. Many social theories that could once be researched only by conducting expensive surveys can now be studied and modeled due to the easy availability of large scale social annotations and explicit description of social relationships online. The rate at which blogs, videos, bookmarks and many other user generated content is growing presents several interesting research and data management questions. The opportunity to mine social media content for analyzing opinions, sentiments and trend identification has several applications in Web search, personalization, business intelligence and national security. This special issue of the International Journal of Distributed and Parallel Databases invites original research contributions on data management in social media. Topics include but are not restricted to the following.

• community detection and evolution in social media
• recommendation systems
• search in social media
• event detection, trend identification and tracking in social media
• influence, trust and reputation in social media
• opinion/sentiment analysis, polarity identification
• feed distillation and ranking blogs
• mining microblogging and real time data
• folksonomy, tag semantics, clustering and usage
• advertising models for the social web
• indexing social media content, index freshness
• visualizing social network data
• spam detection, social network spam and profile spam

Cfp - Upload a Document to Scribd

Crowdsourcing Academic Paper Reviews?

The book crowdsourcing has given me inspirations for a number of ideas. There are many examples in this book of how the crowds are collaborating, participating and sometimes even competing to make things better. The part that I find most exciting is to do with citizen science and citizen journalism.

• Take the patent review process for example. Peer-to-patent is a great example of how the crowds can work together with experts to speed up the broken patent system.
• The InnoCentive project that uses the diversity of knowledge from crowds to find solutions to tough research problems.
• How Talking points memo asked its readers to help parse through pages of documentation in the DoJ scandals.
• Assignmentzero and current TV are changing the way we think about reporting and journalism.

These examples make me wonder if we might be able to do the same thing with the academic review process. Academic reviews can be time consuming and lets just say --- "have their own problems". Academic research is built on the idea of sharing knowledge, tools and insights. To ensure their quality, results are scrutinized by a peer-review process. Ultimately, if approved, it leads to a publication. In theory, everything should work the way it is supposed to. 

Like any system there are some practical problems. Conferences can adopt a double blind or a single blind review process. In either case, reviewer incentive and motivations vary drastically -- some are motivated by a sense of giving back to the community, others are just helping organize an important event in their research field, some might just like to see their name on the conference PC list, some like the privilege of reading interesting papers first, others like the privilege of having a say in how the field progresses, some (grad students) are volunteered by their professors -- to list just a few.
Reviewers are never "paid" and often have to find time outside their normal work commitments to fulfill these responsibilities, which may not be easy at times. Well I could write a whole post on this topic alone but that is for some other time....

Following are few ways in which I think crowdsourcing can help reform this system:

• Completely public: One approach is to make the review process completely public. Identity of the authors and the reviewers would be public and this could cause HUGE problems and for practical reasons this might be impossible to implement.
• Revealed Reviews: Once the papers are accepted, only those papers that made it and the corresponding reviews for these papers can be made public --without revealing the identity of the reviewer directly. Readers can comment on the reviewers' review and rate them. They could even write a review themselves if they like.
• Crowdsourced Reviews: The problem with revealing the reviews is the same as that of making the identity of the reviewer public. Subtle points mentioned in the reviews can betray the anonymity of the reviewer. The alternative, which I think is most practical, would be to conceal the reviews but allow readers to rate the paper and write their own reviews. Other users can read the reviews and rate the reviews themselves. The crowd is usually good at reaching a consensus in such systems. This would mean that for all accepted papers we have a pretty accurate judgment of what the community as a whole thinks of the paper. Now the scores of the reviewers can be matched against these ratings.The neat thing about this model is that not just academics, but also folks from industry and other walks of life can read academic papers and write reviews about them. And as the book Crowdsourcing mentions "diversity often trumps ability". More people reading and scrutinizing academic work is good for progress of research.

A point to note here is that compensating a reviewer's time in terms of money is not going to work.I do not believe that money is the motivation for reviewers (the same reason why it did not work with Google Q&A). Free conference registrations in lue of their time would be one way to go. Most often though registrations are paid for by the company or the grant. Finally, some conferences have started inviting PC members for a special lunch. Ofcourse, there is no such thing as a free lunch! :-)

Ranking Nodes via Random Walks

A few days ago, we were discussing a research problem in the lab. It reminded me of two papers I had recently read. The problem that we were talking about involved a graph where we knew certain nodes of interest and wanted to identify and rank other nodes that might be relevant. This is a classic example of a situation where random walks can be quite effective. Following are brief summaries of two papers on this topic:

The first paper titled "Ranking on Data Manifolds" is by Dr. Dengyong Zhou. It is discusses a neat interpretation of a random walk. Following excerpt from the paper describes the basic intuition:

"We firstly define a weighted network on the data and assign an authoritative score to every query. The query points act as source nodes that continually pump their authoritative scores to the remaining points via the weighted network, and the remaining points further spread the authoritative score they received to their neighbors. This spreading process is repeated until convergence, and the points are ranked according to the amounts of authoritative score they received."

Manifold is defined by Wikipedia as:

an abstract mathematical space in which every point has a neighborhood which resembles Euclidean space, but in which the global structure may be more complicated.

(rdfs:seeAlso Wolfram page on manifold)

So basically, one can think of a graph or a social network as data that lies on a manifold. In order to learn and capture the structure of the manifold a the Laplacian Matrix is used to represent the original graph. The advantage here is that the Laplacian is capable of capturing the long range relations between the nodes and ensures overall smoothness when propagating the scores on the manifold.

As the scores are iteratively spread from the nodes of interest to the neighbors (via the graph laplacian), the algorithm converges and corresponds to the random walks in the graph. The final scores provide the overall ranking of the nodes, with respect to the initial nodes of interest. The applications of this method range from image processing to web search and recommendation.

I really like this paper for its simplicity and clarity in explaining the connection between random walks and node ranking.

The second paper I would like to mention here is "Fast Random Walks with Restart and its Applications" by Hanghang Tong et al. It is a really nice paper that talks about how random walks can be used to identify how close two nodes are in a graph. Moreover, the paper discusses some really neat mathematical tricks that can be applied for efficient, "on the fly" computation of the random walks in large graphs.  The basic intuition is to use the Sherman-Morisson Lemma to avoid directly computing the inverse of a large graph (which is prohibitive). This is actually a superb trick to use, especially when doing rank one updates. A number of applications are discussed in this paper, including image retrieval and neighborhood formation etc.

There is a more recent work by Alekh Agarwal and Soumen Chakrabarti on this topic, "Learning Random Walks to Rank Nodes in Graphs". There are many more papers and I have probably not read them all -- these are just a few of my favorites on this subject.

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach

Liveblogging from WebKDD 08

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach
Al M. Rashid, George Karypis, and John Riedl

[Update: This was the winner for the best paper award]

This paper is addresses the cold start problem in collaborative filtering, i.e. for new users since the system does not know of the user's preferences, the system cannot recommend items. This paper looks at a few different heuristics:

• Popularity of an item. The system picks most popular items and presents the new user with these. If the user rates these items, it constitutes the initial profile. The interesting point they note is that a good strategy is to pick popular items that have a varied rating distribution. The downside is unpopular items are harder to predict.
• Entropy: identify informative items. Downside is that entropy does not pick the right item when the ratings are few.
• Entropy0: treat missing ratings as separate rating items. However, this favors popular items more.
• HELF: combines entropy with popularity.
• ICGN: Information gain through clustered neighbors. Use ratings so far to determine what is informative next.

Evaluation was done on the MovieLens recommendation system.Overall ICGN and Entropy0 perform the best.

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems

Live blogging from WebKDD 08:

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems
Maryam Ramezani, J.J. Sandvig, Runa Bhaumik, Robin Burke, and Bamshad Mobasher

Explores how folksonomies can be used for social navigation and protect it from 'self-promotion tags'. in profile injection attacks, users create number of identities and add 'tag spam' for malicious intent. Spurl.net is an example of a social tagging system that was inundated with spam and had to shut down.With various entities (resource, tag and users) the profile injection attacks can effect each of the 'navigation contexts' like: related resources, co-occurring tags, recent items etc. The paper goes in depth into the various classes of such attacks. The paper uses del.icio.us crawls for this study that were split into three partitions: low freq, med freq, high freq.

Two main types of attacks discussed:

• attacks on popular tags
• Piggyback attack: force association of a particular resource with another resource to make it look similar.
• Overload attack: associate popular tags with a target URL.
• Focused overload attack: for a specific target users (say those, using the tag coffee) associate the target URL with those tagged as coffee

One interesting point is that piggyback attack is a problem mostly in the Low and medium freq partitions and just 3-5% of fake user profiles injected (using relatively few number of tags) can cause considerable problems in social tagging systems. The authors present various results based on number of tags, number of profiles etc.

I think as tagging systems become more main stream dealing with spam in such environments is quite important. 

Query-log mining for detecting polysemy and spam

Live blogging from WebKDD, 2008:

Query-log mining for detecting polysemy and spam
Carlos Castillo, Claudio Corsi, Debora Donato, Paolo Ferragina, and Aristides Gionis

The paper presents an approach to identify spam from both query logs and usage. The queries are a way to obtain the wisdom of the crowds. This information is used to  tackle spam detection and identify polysemy.

The sources of information used by the authors were:

• Query graphs: query to matched documents
• click graph: query to clicked documents
• view graph : The set of matches that were viewed
• anti-click graph (if the user skipped one of the previous documents from the top 3). This can be thought of as negative feedback.

Further feature extraction  & topics are identified from web directory. The intuition is

"documents that attract queries on many topics and queries have the potential of being spam."

Syntactic features used were: degree of node; the top query terms a document attracts.

Topics are propagated in the click graph using categories from dmoz to queries in the bipartite graph. Two approaches are used for the propagation: weighted avg and topic specific pagerank.The query logs were obtained from Yahoo! and labeled spam collection is WEBSPAM-UK2006 collection.

It was interesting that many polysemous queries were actually country names. For spam detection content + link + usage obtained the best results which was almost same as link+content. 

An Empirical Study of Dynamic Pari-mutuel Markets: Evidence from the Tech Buzz Game

Live Blogging from WebKDD 2008
An Empirical Study of Dynamic Pari-mutuel Markets: Evidence from the Tech Buzz Game
Yiling Chen, David Pennock, and Tejaswi Kasturi

Presented by Dr. Dave Pennock

Tech buzz game uses the wisdom of the crowds and people can 'bet' on events like: "Bird flu outbreak in UK in 2008" etc. An example of a prediction market that David talks about is InTrade and there are tons of other clones out there: Hollywood stock exchange etc. Pretty amazing some of the prediction accuracies that are shown in some of the examples.

Parimutuel markets: All the money goes into one pool and there is a (Zero sum) wagering game in play an winnings are shared equally. In dynamic parimutuel markets (DPM) the entry price changes as more people purchase the share (for either outcomes) in the pie. There is a cost function associated with each purchase price. C(q1,q) = sqrt(q1^2+q2^2). It has a nice property that the ratio of prices is same as ratio of shares.

This idea was used behind the Yahoo! Tech buzz game which was an amazingly cool site, if you remember. It still amazes me how much folks would do for fake money or points! Some research strategies presented for DPM as a prediction mechanism:

• Baseline: Implemented using robot traders buying and selling at random. Ofcourse the robot lost a lot of 'fake money'.
• Sophisticated vs. naive traders: myopic trading -- just decide based on immediate situation and not future.
• Crime pays: people open false accounts and move money from one account to another to add up the signup money.
• For 352 stocks prediction converges to the actual value/outcome closer to the cash out event.
• Markets were pretty accurate in determining the actual buzz (as measured using query logs)

Very cool! Watchout for a new prediction game called Yoopick, a sports prediction game! Here you can predict not just the outcome but the actual score ranges.