Notes on My Research Topics

Flashmobs might be the future of the Social Web

the ideas in this post have formed in our discussions together with Maxim Grinev and Martin Hentschel

Look at Facebook social graph. Started originally as a tool to keep in touch with your friends, it has now become too general and unspecific. Many Facebook users have more than 200 friends, and among them are: their real friends, family relatives, people they have met at professional events, favorite news sites (as a way to subscribe to the daily news feed), news feeds from favorite brands.

And it is natural, because as soon as we discover another interesting source of information, we like to subscribe to keep up with it. But all those streams put together into a common timeline represent a huge, messy, hard to consume stream of information, which, in theory, should be relevant to you.

In the result, what we tend to do when we open up Facebook or Twitter, is reading some latest updates only. You usually do not read the stream far back because as you start reading the latest updates, you start communicating around them and stick at the top of the stream. Often this communication is in real time as people who post recent posts are still online.

I’ve noticed myself and heard recently from other people, that, surprisingly to themselves, they now open Facebook more often than Twitter. I think the reason is that Facebook is a mix of stream and real-time communication platform (you can see who is online and start chatting, play games, etc) while Twitter is a pure stream platform. Opening Facebook is like entering a room where continuous discussion is always going on and seeing who is there right now discussing what. The problem is that if the current discussion on your Facebook page is not interesting, you don’t have an instrumentation to “change the room” to go hang out with another group of people.

We need a service that would dynamically fetch small groups of people from your big general contact list, specific to your current context. So that you can communicate/interact within the group in real time and then move on. We called such a group a flashmob.

Such services start to appear, here are the examples.

• Turntable.fm - is the brightest example of this idea. I am a huge fan of Turntable.fm! People get together in virtual rooms to listen to music or play music for each other, communicate and interact synchronously. In Turtable.fm, your Facebook contact list serves as a serendipitous guide to choose the room: you can check out the rooms where one of your Facebook friends is currently hanging out.  Friends-based recommendation here serves only as a hint to start. Often you quickly find a cool room and it is not necessary that your friends are there. You choose a room that suits best your current situation, like “Coding Soundtrack” or “90s night”. Here is a great post by GigaOm about the idea and Turntable.fm: “Say hello to the alive web”.

• Shaker - a Facebook application recently launched at TechCrunch Disrupt that turns your Facebook page into a bar ;). From MG Siegler’s post: “Your Facebook profile becomes a walking avatar. Your pictures are placed on an actual (well, virtual) wall. You can choose what music is playing in the room for everyone to hear. And you interact with other Facebook users as avatars. You can even buy people drinks.”

• Google+ Hangouts - online video chat with some of your G+ friends. From another GigaOm’s post: “It isn’t a chat (in the traditional Internet sense) and it isn’t a conference call. Hangout with folks you want to connect, even for a few seconds, enjoy an immersive interaction and then move on.”

• Chill - turntable.fm for video. You enter a “lounge” where you can passively watch videos currently playing in that lounge, or choose a video to play, and wait for your turn.

• Foursquare - even old Foursquare partly supports this idea: when you check-in to a venue, Foursquare shows you who else is around, not necessary your Foursquare friend. Thus, organizing a flashmob of people who is at this venue right now.  

• GroupMe, Kik and many other group messengers for mobile phones. They are designed for synchronous communication within a group of your friends. My friends and I use Kik and it is very useful. In Kik, you create different groups out of your big flat contact list. You can communicate via short messages within those groups. Groups can be easily created for each new topic. Sometimes I participate two discussion threads in parallel on Kik, talking about different things in different groups - flashmobs.

• Chatroulette was an early example of this trend, although the world instead focused on the vileness of its content. Here is my favorite post about Chatroulette by Nick Bilton: "The Surreal World of Chatroulette".

My course at ETHZ: The Structure of Social and Information Networks

This Spring, I am giving lectures at ETH Zurich. Check out my course blog: "The Structure of Social and Information Network".

The course goes very close to the new book by Jon Kleinberg and David Easley: "Networks, Crowds and Markets" and also the book by Clay Shirky: "Cognitive Surplus" (whom I really admire).

 

 

 

Analytics for the Real-Time Web

The Web 2.0 era is characterized by large amounts of user-generated content. People started generating and sharing data on Web services like blogs, social networks, Wikipedia, photo sharing sites and other. 

Today, with the emergence mobile Internet access, the nature of user-generated content has changed. Now people contribute more often, with smaller posts and the life-span of these posts has become shorter. On Twitter people share short posts on what they are doing now or reading now, they discuss breaking news, share their current location on services like Foursquare or Facebook places.

MapReduce/Hadoop has become the state-of-the-art approach for analytical batch processing of user-generated data. But now, processing data in batches is becoming too slow for real-time sensitive data. Accumulated data can lose its importance in several hours or, even, minutes. Real-time Web brings new requirements for analytical systems: they must aggregate values in real-time, incrementally, as new data arrives. It follows that workloads are more database-intensive because aggregate values are not produced at once, as in batch processing, but stored in a database constantly being updated.

At Systems group @ ETH Zurich, we are working on Triggy - a system for real-time analytics. Our system is based on Cassandra, distributed key value store. You can find an overview of Cassandra's internals in my presentation embedded below and read about its data model here. We extend Cassandra with push-style procedures and with a serialized access to aggregate values. Push-style processing allows us to immediately propagate the data to the analytical computations. Serialization is used to arrange light-weight transactions for consistent updates of counters (aggregate values), as Cassandra initially does not provide any support for transactions.

In Triggy, we implemented programming model similar to MapReduce, but we modified it to support incremental processing. 

Here is my presentation about Triggy where I describe its internals and programming model; compare it to similar systems: Yahoo! S4 and Google Percolator; and discuss applications for Triggy. See presenter notes for slides to get more information.

Triggy will be demostrated at VLDB2011: Max Grinev, Maria Grineva, Martin Hentschel and Donald Kossmann: "Analytics for the Real-Time Web"

Analytics for the Real-Time Web

View more presentations from maria.grineva.

Poster for the demo.

Filtering Out Noise In Twitter Lists

Twitter has a very important yet still under-hyped feature: Twitter lists. Twitter list is a manually created set of users who have something in common. For example, one can create a Twitter lists of people who tweet on NoSQL topic (for example: http://twitter.com/al3xandru/nosql), then others can subscribe to this list to get news from NoSQL community. So, Twitter list is a united stream of tweets from all of its members.

For example, here is a list of people supposed to tweet often about NoSQL http://twitter.com/al3xandru/nosql. The list created by @al3xandru. It unites 74 Twitter users, and 22 users have subscribed to read it.

Lists seem to be a new perfect way of getting real-time news on any topic of your interest. Still, the problem is that lists contain too much noise. People included into a list tend to tweet about other topics too (not relevant to the list's topic): their other interests, as well as their personal things, jokes, pics, Foursquare check-ins, etc. Here are, for example, lists where I am included: http://twitter.com/mariagrineva/lists/memberships. I post tweets about: social media, information retrieval, Zurich, NLP, entrepreneurship, startups and other things. Some of them are relevant to one list and not relevant to another.

As a result, an average Twitter list produces stream of tweets most of which are relevant to the main list's topic, and there are still tweets on other topics too. Normally, relevant tweets dominate noise. But there are situations when lists reflect global Twitter trends like #worldcup or #ash for example. Then trending event can dominate main list topic.

In order to filter noise in Twitter list, one needs to identify list's main (niche) topic. The words representing the main topic change over time, new words can arrive. That is, once identified, list's topic should be maintained actual in near real-time. The other thing is that trending news can flood list and even crowd out main topic for some short period of time. To fix it, we should differ two kinds of noise: (1) off-topics – tweets on other topics, not relevant to the main list topic, and very diverse. (2) trendy off-topics – tweets about recent important global event not relevant to the main topic, but most of the list members post about it.

We (Baris Guc and me) developed a prototype of the system that filters out noise in Twitter lists. And here are the main ideas of our approach.

We consider list filtering task as a classification of new coming tweets as relevant or irrelevant.

Real-time identification of list's main topic. Our system monitors list's tweets and creates list's topic signature – a ranked set of words that represent the main topic of the list. Normally, relevant tweets dominate, and it's easy to create topic signature. But we also need to deal with trends. For this reason we consider twitter list in the context of the global twitter stream. That is, if everybody on the list if writing about #WorldCup, but it is also a popular topic in global stream, that means it's trendy off-topic and it should not affect list's topic signature.

Combining textual and social features. Filtering can be improved by using information from Twitter social graph. Members of twitter list organize a social subgraph. Looking at this subgraph one can see who is the center personality in list community and who is an outsider. Usually, members who are most followed by other members of the list subgraph (more central in the list), tend to post relevant tweets often. We have experimented with this idea and found out that combining textual (topic signature) with social features gives best classification accuracy.

User feedback. The system starts classification without any training. It fetches list's tweets back and identifies topic signature. But it can be improved by giving feedback: you can mark the erroneously filtered tweets and you can mark not filtered noise tweet. The system improves very quickly with the user feedback: on average, it needs around 5 labeled tweets to achieve best classification accuracy (86%-90%).

Read the full thesis on Filtering Twitter Lists.

SIGMOD 2010 talk on Sedna XML Database Management System

Sedna: native XML database management system (internals overview).

 

Sedna is a big old project of ISP RAS which we started in our group (MODIS) at 2003 with Max Grinev as a team leader. I've been working on it in 2003-2007, and this project is still going on now. Sedna has become quite a mature system and there is an active open source community formed around it. If you need more info, find it on Sedna's homepage.

Planning Marketing Campaign In A Social Network

Recently, Valdis Krebs posted this picture of a kite network in his blog asking a question: “Where would you plant your msg in this net? Why?”

span style="font-family: 'trebuchet ms', geneva; line-height:18px;">
In other words, if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?

When you start thinking about it, you understand that you need additional information about this network: how does the innovation diffuses in this network? And what are the thresholds of adoption of nodes?

Suppose, for example, that any node in this network when targeted, is able to spread a word only to it's immediate neighbours. Then targeting Diane and Ike is enough to cover the whole network.

But what if targeting a node is expensive (for example, targeting an individual means to grant her a sample of product)? Then targeting Diane is three times more effective than targeting Ike, as Diane would influence 6 people while Ike only 2. So, we can reason about the cost and effectiveness of targeting a set of nodes

If a targeted individual is able to spread a word on two steps, then Heather is the best choice, as she can reach everyone in the network in two steps.

Domingos and Richardson posed a fundamental algorithmic problem for such social network processes in this paper: "Mining the Network Value of Customers", 2001.

Conversational Advertising Platform

It's been long ago when first variants of this idea came to my mind. The idea is still very raw, but I think writing a post will advance it. This post is a draft of the conversational advertising platform and its features.

Today traditional Internet advertising is considered as kind of annoying toll. People became resistant to it. But if to forget about banners and sponsored links, and just think about advertisement' initial idea: to spread information about a new products – you feel that now, when Web provided us all with huge brand new conversational abilities, this thing can be done much more effective. It sometimes happens to everyone when you really want to advertise a good product that you use and like to your friends. And your friends sometimes ask you for a recommendation about a product. And we all do this often on Twitter and other social networks. People share information about products they like via conversations on social networks. As social networks become more advanced and ubiquitous, they're getting new tools to manage, filter and guide information streams; this trend is becoming more obvious.

This problem is partly addressed by the advent of collaborative filtering recommendations of the form “people who bought x also bought y” feature (Linden 2003). From “The Dynamics of Viral Marketing”: “These refinements help consumers discover new products and receive more accurate evaluations, but they cannot completely substitute personalized recommendations that one receives from a friend or relative.” A Lucid Marketing survey found that 68% of individuals consulted friends and relatives before purchasing home electronics, more than the half who used search engines to find product information.

Another example. I am really surprised with how our product TwitterTim.es is being spread all over Twitter. We paid nothing for the advertisement, and it’s a pleasure to observe how people from different parts of the world, of different professions, describe the idea of the product in their own words and suggest their friends to try it! And we also employed a couple of simple tricks: (1) including 'via @twttimes' in retweets from newspaper; (2) a big button “Tweet your newspaper” so that you can send the link to your newspaper on Twitter with the message “Check out my fresh twittertim.es newspaper”. It makes sense to press the button regularly because newspaper is becoming “fresh” every 2 hours.

The important thing is that new twittertim.es subscribers are not arriving evenly. Instead, it has always been like waves: when someone influential praises twittertim.es – we have new wave of subscribers. Harnessing, stimulating the right influential nodes in network can dramatically change the speed of propagation of knowledge in social network.

So, if sharing product recommendations via conversations is a natural people's activity, why not to build a conversational advertisement platform upon a social network?

Of course, this idea is going around in different forms currently. John Battelle and his company, Federated Media, is working on aggregating blogs into a conversational media platform where brands can advertise.    They are working on estimating people's “engagement”. From FM's white paper: “Engagement” is the term we use to describe all the various ways that consumers interact with your brand and your campaign assets. This includes traditional metrics such as page views, click-through-rates and time spent, but it also includes a new set of metrics unique to conversational media such as posts, trackbacks, votes, RSS subscriptions, comments and more”. See TechCrunch post about FM's 'Conversation as An Ad'-platform here.

Look at Federated Media's latest product: ToyotaConversations.  It is a channel that features what is being discussed about Toyota on Twitter, and negative stories are not filtered out. This channel is an attempt to participate in a conversation with consumers and to influence how the brand is viewed.

What does Conversational Advertisement Platform consist of:

Who can advertise: Identifying right influential personalities in a social network. This problem has got a lot of attention among data mining researchers. TunkRank metric was proposed by Daniel Tunkelang for computing global influenceability of a person on Twitter. TunkRank computes some global measure of influence. For any Twitter user it computes its absolute score based on number of followers, mentions, retweets.

Here is another research on calculating influence on Twitter (The Million Follower Fallacy: Audience Size Doesn't Prove Influence on Twitter).

I really think identifying some global influenceability is a wrong way. We need to identify topical communities, and find central, influential personalities in those communities. The paper “TwitterRank: Finding Topic-sensitive Influential Twitterers” - is an attempt to do that. From the paper: “For example, a handphone manufacturer can engage those twitterers influential in topics about IT gadgets to potentially influence more people”.

Whom to advertise: Identifying target audience for a ad. Analyzing of what people tweet can help understand what they need. It’s clearly that its best to receive a product recommendation from your friend – so, returning to the previous point – we can identify the right personality to advertise among person's friends first. Authors of “The Dynamics of Viral Marketing” automatically find network communities (using graph theoretic community finding algorithm) and observe that communities usually centered around a product group such as books, music, or DVDs, but almost all of them shared recommendations for all types of products.

Bidding auction model for social network advertising. Google AdWords is based on generalized second-price auction. This model can be adapted for a social network, substituting Web-page rank with Twitter user rank. Ad.ly already has something like that for Twitter. I'll write a separate post on that soon.

Brand monitoring in social networks. Understanding how information about a brand is spreading over the Twitter, what nodes influence on the brand image. Using sentiment analysis techniques. Identification of blog posts/news articles that influence people's opinions about a brand.

So, in general the platform would allow to find : who, whom and what to advertise.

The Twitter Times – a new paradigm for news consumption

Using Twitter to read news

More often people use Twitter for:  1) getting news, read something interesting 2) to communicate/chat 3) as an easy way to present her authority online. First usage is probably the most widespread.

In Twitter, you explicitly build your community of people who interests you. Naturally, news items, recent blog posts and jokes popular and actively discussed by your tweeps, are interesting for you. Community of your tweeps is the best filter for the massive volume of daily news.

But since you collect more than ~300 tweeps it starts to be difficult to follow them all. From Mashable's post: "Some of us are starting to deal with what we recently dubbed followholism. You’ve followed so many people, it’s hard to keep up..." Usually you just glance over the most recent pages of tweets and quickly try to determine what is going on today. There is a need for tool that would turn this huge stream of tweets from your friends into a static easy-to-glance-over representation - a newspaper!

We are working on The Twitter Times – a tool that builds a near real-time newspaper of what is new and actively discussed among your friends on Twitter. News are ranked according to some nice combination of recency + popularity among your friends and presented in form of newspaper. You can see who posted the news item and retweet it. It is principally different from news aggregators based on the global popularity such as Techmeme , Tweetmeme or Digg.

Thematic newspapers

In this post @maxgrinev covers the main aspects of The Twitter Times : 1) real-time, 2) personalized 3) media-rich.  I’d like to point out one more implicit feature: a brand new ability to construct thematic newspapers.

The beautiful Twitter feature is its openness – you can follow almost any Twitter user unless she protects her updates, which is quite rare. So, you can build thematic community – create separate account, discover and follow people from a single field:  venture capitalists, AI computer scientists, photographers, fashion addicts …

To discover new people to follow is easy: you can use Twitter directory WeFollow, or just google for something like "VCs to Follow on Twitter" , "Entrepreneurs to Follow on Twitter" ...

Once you collected followees –let us build newspaper for this account. Such newspaper appears to be thematic by definition. To demonstrate the idea I’ve build 100-VCs newspapers so you can see what is currently discussed among venture capitalists: www.twittertim.es/venturecaps

We will soon create an easier way to construct newspapers without the need to create new Twitter account.

We are extending deadlines for 'Web As A Stream' session at FQAS

This year, thanks to my friend Henning Christiansen I have a chance to organize a session at FQAS conference related to my own interests.

So we are organizing 'Web As A Stream' session, which concerns everything related to the new stream-like nature of the Web that is so much discussed today.

Speaking more formally, we invite contributions relating to the following topics:

 

 

•     real-time search
•     extending traditional Web search engines to capture stream data and their integration with specialized vertical search engines
•     archiving streams and exploring stream archives
•     stream personalization
•     stream analysis
•     stream filtering
•     spam identification in streams
•     identification of trends in streams
•     monitoring brand's reputation in streams
•     identification of influential members in network of streams (for example, in Twitter)
•     natural language processing and indexing techniques for microblogging streams
•     advertisement for streams
  

Paper submission deadline: July 12, 2009 !!!

------------------------------------------------------------------

In my opinion, the field of real-time Web streams have not gained popularity among academic researches yet. While it is so much discussed in the blogs. But I am pretty sure this topic will have its burst in academic conferences in 1/2 or a year.
Here are interesting posts about real-time Web:

•   Distribution … now , by John Borthwick
•   Jump Into The Stream, by Erick Schonfeld
•   Mining The Thought Stream, by Erick Schonfelds
•   Welcome to the Stream: The Next Phase of the Web by Nova Spivack

Poster "Analysis of Community Structure in Wikipedia" at WWW2009

-- guest post by Dmitry Lizorkin --

In the poster we presented at WWW2009 in addition to our research paper, we proposed an approach to automatically organize Wikipedia knowledge by locating the implicit groupings of related Wikipedia articles into communities.

In this blog post we describe our background ideas behind the poster, as well as our subsequent considerations we discussed during the poster session.

Our initiating goal for the poster was to provide people with better insight of the knowledge available in Wikipedia using machine aid. To address this goal, we decided to consider Wikipedia as a graph (formed by articles and links between them) and to study what structure this graph had. Namely, we supposed that the graph should contain communities - groups of densely interlinked Wikipedia articles. Our inclination was motivated by the following two reasons:

A. First, Wikipedia is becoming really big, so big that no person alone is now able to mentally grasp the complete knowledge contained in Wikipedia as a whole. Even for a person who is an expert in some field, her field of expertise generally fits into some tens/hundreds Wikipedia articles, and that's just a small bit of Wikipedia as a whole. When humans edit Wikipedia to hyperlink articles or to organize articles into categories, each human is actually working on a tiny bit of Wikipedia that she is able to mentally grasp. And due to collaborative nature of Wikipedia, the global effect of such individual edits is a new formation on its own that goes qualitatively beyond comprehension of each individual contributor.So, we decided to analyze this big storage of knowledge globally with automatic techniques to reveal more coarse-granular groups of information there that would make it easier for humans to comprehend.

 B. Second, when we studied communities within a graph formed by terms located in some text (for extracting key terms from text), we were intrigued to observe that these communities closely correspond to main topics considered in the text (recall our recent blog post). Encouraged by this observation, we felt eager to study the same approach in the global scope of Wikipedia as a whole.

With this motivation in mind, we chose the community detection algorithm by Girvan and Newman for achieving our task. The Girvan-Newman algorithm automatically detects the appropriate number of communities in a graph and analyses the global link structure in the graph to agglomerate densely linked groups of articles into communities. We applied the algorithm to the set of articles from the English Wikipedia and the subset of links that are used to convey stronger relationships between articles (in particular, links from Wikipedia "See also" sections). Even with the restricted set of links (made for computational reasons) the input graph was so large that it took the algorithm several days to complete the calculation. But the results we obtained were worth this computation effort.

And the first two notable results are:

1. Wikipedia turns out to have distinct division into communities.

That is, Wikipedia articles actually organize themselves into groups, such that articles within a single group are densely interlinked, and articles from different groups are linked more loosely.

2. Communities in Wikipedia turn out to contain more semantically similar Wikipedia articles.

That is, if you take a community and take a look at its member articles, you can observe that these articles are more similar to each other than if they were selected from Wikipedia merely at random.

Moreover, the smaller the community, the more similar member articles it contains. Even more, for a community that is relatively small (consisting of less than about 200 articles) one can usually notice that all articles in the community share a common topic (e.g., "ecology", "rail transport", "beer").

And that's not all:

When we initiate PageRank computation over such a community, the highest PageRank score typically gets assigned to the article that gives in its title the topic of the whole community.

For example, in the community that contains Wikipedia articles about tea, the highest PageRank is owned by the article entitled "Tea" (see the demo http://modis.ispras.ru/wikipedia/Tea.html)

If we stop for a bit and think of these findings, we realise that they are truly amazing ones:

In all the techniques we use above for analysis, we do not use any textual content from Wikipedia at all. What we are using is solely the link structure of Wikipedia (since both community detection and PageRank rely on link information only). And, having solely link information, we are able to (a) organize Wikipedia articles into communities with semantically similar articles, and (b) infer the title for each community, that gives the generalized topic for all the articles in the community.

This means that the link structure of Wikipedia is actually no less important in conveying global knowledge than the textual content of Wikipedia, - the fact that usually goes underestimated and even unnoticed.

The question that further arises is:

how can we now organize larger communities?

We noted above that for a larger community we usually cannot clearly observe that all its articles have a single close topic: either these are multiple topics or the topic is too broad.

However, we discovered that if we once again apply the Girvan-Newman algorithm to such a community on its own, it in turn exhibits distinct division into (sub)communities.

This means that the community (being the group of densely interlinked articles) desintegrates into distinct subgroups of articles that are interlinked even more densely.

That is, a larger community in fact exhibits a distinct nested division of its own!

By repeating this process while the community detection algorithm approves the good quality of division, we are able to automatically build a complete hierarchy.

The hierarchy we discovered provides the intuition on how knowledge in Wikipedia reveals to organize itself as the result of collaborative effort of Wikipedia contributors.

In particular, if we graphically depict each community with a circle, denote nested communities by nested circles and make circle sizes proportional to community sizes, then the hierarchy implied by Wikipedia looks schematically as follows:

The further natural question is:

Since Wikipedia provides its own mechanism for (manually) organizing articles into the categories, how do the located communities correlate with the Wikipedia category structure?

And our observation is:

In some cases, a community contains almost the same set of articles as some Wikipedia category does.

And in some cases, articles within a community are not associated into any common Wikipedia category.

But the second case does not actually mean that Wikipedia categories provide the "ground truth", while any other data organization is incorrect.

In fact, as we noted in the beginning of this post, a person combines Wikipedia articles into a category based on her local knowledge of the subject represented in these articles.

On the other hand, the ability of a machine to analyze the global link structure of Wikipedia reveals that the collaborative effort of individual human contributors sometimes reflects a different grouping, more appropriate according to the relations between articles expressed with links.

So with our findings we rather provide the insight on how knowledge in Wikipedia organises itself implicitly, and the hierarchy we constructed can be considered as an extension to the category structure existing in Wikipedia.

This poster is a joint work with our colleague Olena Medelyan from the University of Waikato.

Online demonstration of the constructed hierarchy is available at:

http://modis.ispras.ru/wikipedia/

We organized full-text search over the constructed hierarchy, by building full-text index over Wikipedia article titles and their abstracts (the piece of text in Wikipedia from the beginning of an article till its first section).

Thus indexed, search produces results for any search string that matches anything in a article title or abstract in Wikipedia.

Searching gives you the individual communities that match your search string and that are the leaves of the hierarchy, ranked by exactness of the match.

The demonstration allows you to find and navigate over the semantically similar Wikipedia articles on the subject of your interest.