TBTB Gabor Szabo

haveone yeah thanks uh well thanks everyone for for coming here for the talk my name is Gabor Sao I work at Twitter as a data scientist and I would like to talk a little bit about how we could detect uh possibly topics a bigger subjects in TW uh Twitter streams uh in twit in particular obviously so that's what the um this talk is going to be about we worked on this project with uh with my intern at that time with Dan Frank so uh so that's and then obviously with Engineers on productionizing uh the the the project so just as an outline very quickly in the beginning I would like to talk about Twitter in general like probably you know most um most things about about Twitter to be known but still I would like to just kind of like talk U just give a very short intro then then basically just talk about the problem what we are trying to solve here and then then the methods then the data that we use for this project for this uh uh for this uh event detection we will see some metrics about uh these events the subjects that we can mine from the twe streams and I'm going to show you a couple of plots about that and what are the characteristics of the users that contribute to these streams and how active they are so so we can also get a Gams of like depending on the size of the of the subject that we will see what are the types of people that are talking about that and then also at the end some some uh measurements about the temporal characteristics of these events before I conclude so uh just about Twitter as I promise very quickly uh obviously uh tweets are very short messages they can uh be of um at maximum length 140 characters this is because originally they were started as you know SMS messages and then SMS can only comprise 160 characters so we had Ator for the username as well in the beginning so that's why it's so short but this is also a good medium for for like very quick updates and then users usually follow other users uh based on their interests so um the way that we like to think about this social network is that this is an asymmetric follow Network where you don't necessarily have to reciprocate the links that people make to you but in fact you know if if you are um celebrity or an opinion leader or whatnot or just just like a normal person then then you your uh the followers can get updates from you but you don't necessar have to follow them back at this point we have more than like two 28 to 90 million users uh a month uh they're sending a lot of tweets a day so that's why I just put there the statistics like 500 million tweets because this is the amount of data that we have to kind of cope with at this point uh in the uh in the algorithm and um and so that's that's the challenge basically that you have to figure out what is five what some of these 500 million tweets talk about um in a day the majority of our users are on mobile using mobile phones and uh as I mentioned several times Twitter has this very timely nature where tweets are usually like there this fleeting messages people see something they talk about that or they hear something in the news or news about something then they tweet that so that's why it's also like interesting to find out automatically what kind of events are happening there and um uh so there are obviously the big events there that that happen that people talk about on Twitter but there are also smaller ones and then we would also um like to see whether we are able to capture also those smaller events and then uh um um because of this distribution between the large and small events you will be able to see that there's like this long behavior in the size of the events that's perhaps um kind of like a reflection of of how kind of of the importance of news that that actually happen in real life right so there are like very important news but only a few of them and there are like not very important pieces of information of which there is a lot all the time so uh we would like to see what people talk about publicly uh basically and that's that's what the service is for and then automatically uh find these events now when we talk about events right we haven't really finded what an event is up until this point because it's not very obvious what they should be but we have a feeling that that they should be about the same topic so uh textually they should use the same words the same key Expressions uh they should refer to the same uh same people same entities but uh um but obviously um for for for an algorithm that would be the most that that we can achieve that that we match match up text with each other in the tweets so they also pretty localized in time uh which is very important right so when an event event is happening there is a what component of the event like what happened and when it happened because that's that's what what the important thing is uh otherwise if it's spread out in time or when people say good morning to each other every single morning that's not very interesting that's also an event but but probably not of a very high interest to us uh another requirement that we wanted to see with this project is that we know that uh uh when there is an event happening then there are also like um subjects that relate to this to this main event but they are not but they also can have a life of their own so uh if there is like a say a big storm somewhere then there could be um there could be a news or pieces of news about this this big storm but there could be uh news about some floods in an area and then that should be more important to the people that live in that area so that this is what we mean by by the high structure of events that that it can evolve in time and that it can uh give rise to like new little sub events well I'm going to show you examples about like how we we approach this the the purpose of all this is obviously like we could uh show updates to our users about about the events so this is about news Discovery personalization if you are interested in something then we could show you events that are about the same subjects and then uh for targeting say If you think about um um um the the targeting vehicles that we use the promoted tweets then we could figure out what events people are interested in say this this conference then then we would know that who are the people who are interested in tax analytics because we know that this event is happening right now and then internally uh for us for my team we were more interested in the analytics part of the of the uh outcome of the results here so uh basically there is a lot of tweets as I as you could see uh coming in all the time like 500 million a day and so that's why we should uh choose models that are very minimal that are just just very fast to execute and uh and that's what I'm I'm uh going to show here uh in a second and uh because tets are very short very emotional most of the times and require very little for on part of the user to write they also they can have like um um the the the words that Express what the user is talking about is is they they they they don't always make sense so they are sometimes slang words they don't the sentences are not full and so on but there is usually because they can be only so short there is usually one or two keywords in there that that relate that reflect uh on the event and so that's that's a good thing that either the hashtags or some keywords there they they particular uh refer to that so that's the that's a good way to uh to to correlate these um to find the correlations between the Tweets in terms of text but uh of course um if you think about how we would normally find uh documents in a big document set that are related to each other that you would use like normal document processing techniques here it would be hard pressed to do this because this TW it's are so short so if you think about like using tfidf to to give weights to to terms that's going to be a bit hard because one document is so short here they are just like five words at most on sound so that's why we consider a document as a set of tweets so basically we're going to pull TW together and consider that as a kind of a smaller or bigger document that relates to that that event but obviously it's not going to be a document like a legal document that that you would normally see and then of course there's a lot of noise here so there's a lot of spam uh in the system there's a lot of uh kind of non-events that I just mentioned like people saying good mornings to each other so that's not very important and so that's why uh we prepared the data we we looked at the the tweets that are coming in try the the the clustering a few times and and basically um we've already done that we need to obviously uh do the proper stemming uh of the words uh in this case we use the snowball stemmer and then uh we have to remove the punctuation and the atmes and hashtags and that's when you are left with the keywords in the tweets so that's the the normal way to to prepar text and then um obviously there are different languages uh on Twitter but in this case uh the examples I'm going to show you just just relate to to English so that's only English language tweets and then so basically this uh this requirement of of having a very simple algorithm was uh um um kind kind of we we uh we chose to uh to implement it with a streaming streaming clustering algorithm uh in which case uh we only had to have a limit memory uh in terms of storing all the tweets because obvious you cannot store like like a billion tweets all the time and then and try to do some clustering on them so we had to have a streaming algorithm that only has a finite amount of memory assigned to it and then obviously the parallelism was a very important factor so that we can we can distribute the the workload and then of course we didn't want to have um very strong human Supervision in this so we didn't want to hand label the events that come out and uh of course speed is important and and um then we can also check um how topical the Clusters are that we are finding here and that that we can do with the with the hashtags so we we kind of kept back the hashtags to to be labels for the tweets to be labels for the events and then uh that that way you can find how pure the Clusters are for the for the events in terms of uh the hashtag usage the uh algorithm that is this clustering of the tweets again like imagine that that we have the streaming all the the streaming TW tweets and they go to like different worker machines in parallel so um in this case the the clustering Works in such a way that um again when when when when twiets are coming in uh you would like to see whether there is already something uh in my um um uh in um among my clusters that are already similar to these tweets if there is already a cluster that's kind of growing in in topics then I assign that tweet to that cluster so that's what I mean by this leader follower type of clustering which which is by the way it's um it's a usual way of of clustering um items in a streaming way so we start with a with a clean slate uh the new items are coming in if they are not similar to anything else yet based on our Co side distance then we just start new new clusters with them and then they be able to seed for the cluster but as more and more tweets are coming in they will assign to the closest cluster and if the closest cluster is even further than a than a specific distance based on this cosine distance then then we start a new cluster so as as I as I said in the beginning and so this is uh this is a way to basically pre-cluster these tweets uh in um in a way that that we will now that each each basically this worker machine will see just um say if you have 10 workers one tenth of the stream and then it will do this follower leader follower type of clustering where we would have at the end of this run or like continuous during this run kind of like clusters that are growing but they are similar to each other um textually right so so the the tweets are mapped to a bag of words um and basically we are just looking at the coign distances between the Clusters and their between the tweets and the cluster centroids and then so this gives you something but you can already see that by kind of randomly Distributing this workload among like the 10 worker machines we will have the same clusters like forming on all the on all the parallel distributed uh workers because uh if you just like randomly Shuffle around the tweets then the same topic may go to like different machines of course so this is not going to be good if you want to um so at this point you will have the the the same topics distributed across different machines that do not know about each other at all if we didn't do any kind of like like uh secondary stage of of clustering or uh processing so that's why uh what we did as a second stage so this is the first stage which is really fast so this this with this you can you can eliminate spam by by by various ways and then you can um you can cluster these tweets uh basically uh that to the smaller or or larger uh first level clusters they could have like between 100 200 tweets so um I will uh in the second in the next slide I will have the uh the the second stage of the algorithm that that's easier to to understand but the data that we used here basically uh as I said the English English language tweets from uh um um us users the users also had a high reputation score that we use kind of internally this is like how reliable that user is so if if there are good followers of the user then they also be good uh basically um uh they will have a high reputation if people with high reputation scores follow each other then again like there will be a um there will be a refor reinforcement between their reputation scores so this is this author Hub model that we kind of use inside uh for this examples uh I just took a sample it was like 5% and at the beginning of the this project this this is data from 2012 so about two years ago uh this is just for the analytics for that and the uh later on we worked on the implementation of this the the time STS are obviously important for the twi because that gives you the the time locality the temporal locality so you also when when you are creating these clusters um with in this parallel fashion at some point you also want to say that hey now I'm going to stop because this cluster hasn't seen any more addition in a little while right so when when when I'm growing these clusters and then I I'm I'm stopping it I think this this cluster is done this this document is done now about this subject and so that that's why it's important um in this case we have uh a samp of 100 million tweets here with tens of millions of authors at at at that time uh when this data was taken there were a couple of interesting events going on worldwide or at least in the US since this is us data there were the presidential elections happening at that time the unfortunate event of this Hurrican Sandy also hit at that time and then there was Halloween happening and for the further analysis we can also use the the P so just in terms of data we can use the users pass activities when I can show like how active users are so we also use that data just to be con complete so this is the second stage stage of the clustering that I was referring to so the the first stage with this leader follower type of clustering then we take care of like quickly just having a course view of the the events that happened there but now we have have to merge this information together so that we we know that when the workers are seeing this uh the same topics then basically they will be brought together in in into one uh here at this stage so this stage is different this stage is is just run on one one um uh kind of strong uh computer that has like um enough memory and processing power and then basically all these uh the Clusters together with the centroids they are pushed onto this this this uh um this this uh one one machine one server here that that will perform this this bottom sub bottom subclustering so you are you're probably familiar with this if we have items that now again represent documents based on the uh on the weighted uh weighted sum of the tweets Bas using the the bag of words for the tweets right so we are each each tweet is a vector of words then we are just summing up the the vectors and that those that's going to be the centroid of that of that little cluster there now we are we have these items that we want to Cluster further here in this agglomerative clustering so here the two two most similar clusters are first brought together into one and they will start forming one one new cluster then we we decrease by by this we decrease the total number of clust items by one right so it's n minus one and now we can do the same thing again we can check which two clusters are now more similar to each other and then we bring those also together so that gives you basically a this is the operational view of of this clustering and then uh that's why it's agglomerative because it's agglomerates clusters together but it also gives you a nice view of the hierarchy of the of the events that happen right because um here if you imagine that on the leaves on of this dendrogram so this dendrogram kind of symbolizes the these merges that I was just describing this agglomerations so on each level uh each like horizontal line is a uh is a distance at which two clusters were were joined together and then you can see somewhere here that for instance cluster like actual the bigger one here so they were joined at the distance of about I don't know 4.5 terms of like coine distance uh in the end and uh and that means that they are not that similar to each other so they were like pretty far from each other but they were still closer than say something on the left hand side of the of the dorram so this way you can see that um if you now now look at the leaves of this of this dendrogram these these will be events that that are are that that people talk about and then these this uh these merges the height of these merges will be how similar those those subtopics are to each other so that's the way that we are looking at basically subtopics and um and uh their their hierarchy because this way just from textual similarity you can see that how far is one event from from another and by the different colors I just colored like sub branches of this uh of this dendrogram I just made a cut at 0.7 distance and then anything below that uh uh sub Branch was was colored the same way so that you can see also visually what is the what is the the topic that was um uh formed by by the tweets within the sub Branch uh and then the way that I kind of refer to that we have to remove span um that that's an interesting trick that um if you if you basically look at the look at these clusters so we initially we don't look like try to remove spam spam in any way but if you look at clusters uh that form in in this first uh leader follower type of clustering then many times you will see that that they are all about they use the same words they they all kind of like want to sub uh take a survey so that you can get an iPhone right and they all use the same words there so the word entropy within this clusters will be very low they they because it's all the same words but if this is about a nice real event uh then and the word entropy will be pretty high because people always use like different words so that's the way of of basically like filtering out for us um the spammy tweets or sorry the spammy Clusters uh when it's all about the same thing then then it's not interesting and that's those are all to the left hand side of this process there's a lot of like this these clusters that that I'm not even showing here and those are the spammy ones and then so just to show you examples these were uh these were the events that happened at that time so um I just plotted the basically this word clouds for the sub branches so imagine that each sub Branch R to the yellow one here for instance on the right hand side this about something there are lots of tweets on the right hand side within the the first level clusters and then they all all have the this the stem the the stems of the words so you can see that if you do this that indeed you will discover that this uh this big yellow cluster is is uh is talking about the the elections at that time right so there are debates there uh Biden Romy Obama you can all all see the the the the the ECT words in there another interesting one for instance here this is the purple cluster again it's bar visible there but but it's there so so this way uh you can see people talking about the same thing this about all right so this is about like Halloween October November at that time and then then again you can see that without us doing like anything this comes out from from just automatically from this clustering uh maybe you know like less uh kind of popular topics or or subjects the uh this PSAT tests were administered at that time so the students were talking about that you can see some sentiment around that that I I'm I'm afraid of that or I I don't know what I'm going to do and things like that there is this Krick Lamar um this this singer uh artist that that release some album again you can see all that happened then and another use case for that is that you can also see like how people feel about that right so so the sentiment you can see that I like this I love this I I don't and so on and uh and then so just looking at one event there you can also see that how how it was perceived basically the uh yeah there is um another big event here Bo was can send and again you see that here probably this one next to the election shows a very strong kind of sub structure you can see that there like sub events here all refer to the then but but basically because uh it went on for a longer time that's why you can see that there were like several developments around that that you can capture with this clustering as well and then uh so this this was for for uh the the example for uh for the clustering for this uh uh hierarchical clustering and then now we can look at just in the next couple of slides about like some some statistics about these events like how big they are what kind of users contribute to the to this event so in terms of the sizes the first thing that you can obviously look at is like how big these these events are going to be so here uh I basically performed this clustering and then uh they looked at how how big these this clusters uh were uh once once I did that and then then obviously you can you can plot the distribution of the of the size of the Clusters and that's that's the exact same plot ex except that on the left hand side I there's this double logarithmic rescaling where you see that this is a very very straight line there so this means this is the same on the right hand side so this means that that basically if you take uh take the the size of the Clusters in other words kind of the size of the topics or maybe the interest in the top topics you can see that it shows like a very very kind of like regular this power low behavior that you see in a lot of other social media settings in terms of user activities everything and that means that basically there are um maybe this to see that clust that tws you have quite a few of them thise let's but as you go the cluster size you will have very fast drop off in terms of the number of clusters and that means that of the large clusters of the very important events there are only very few right uh that that that means that yeah the very popular events there are there are just just so many of those but this is again like like the same as as everything that you you see so the same for the you know word usage distribution the zip lows and and all that so they all show the same power low behavior and uh it could we could ask ourselves that why is it so why is it so that there is like like we show this this very uh strong regularity I mean I was very surprised uh when we saw this like very uh um straight power LW across many many decades there in terms of uh number of tweets and and how could we model it some could could be give a reasonable model of how topics are formed at least on Twitter and then maybe real times as like in real world as well and uh so for that we came up with with something and then this is more like kind of just um thought experiment but I wanted to share it with you because U maybe uh you are interested in like how we could uh look at uh um things like that analytically so uh imagine that that for instance I will come back to to why this analogy May hold but imagine that we have earns that uh that uh that can contain balls and we are going to drop balls in these ears but uh we don't have a fixed number of earns they they can be we can add add ears to to our to our system basically so in every time step or we we continuously introduce these new balls and we are going to drop them in ears but uh the the kind of uh the um the interesting part here is that uh we just with a given probility P here let's call it P we we also can create a new earn so when we have a new ball we can either drop it into one of the existing earns or we can create a new earn and drop the ball there right and um uh so with this probability we create a new earn but if this prob doesn't hold like in most of most of the cases with one minus P then we just drop it into the one of the existing earns but that we choose which one we choose which ear do we choose we will choose it with a uh probability proportional to the number of BS are already in the turn so basically if an earn already has a lot of balls in it then we are going to drop it we are going to drop the ball into that turn with a much higher probability but this is going to be uh proportional linear proportional to the number of BS so why is this reant I mean why why we did we do this detour uh so basically if you think about earns as topics and balls as tweets so a new piece of U contribution to that topic then uh if you were to run this model then you would get back the exact same kind of power low distribution as you saw in the in the previous slide here so the number of balls in the earns is going to follow something like this and the the slow so how how fast it decays that depends on on basically the the parameter P that that you choose for the uh for this uh introduction of new Earth so you could say that yeah I I mean we we could maybe give a very simplistic view of how people contribute and create new topics or new news and this is this way that uh basically there is like a infinite number of topics out there that people may contribute to May write about and then uh they they can choose to to contribute to one and then if they have seen that there is a very important topic out there very important subject or just by themselves they somehow there is this intrinsic importance of a topic they contribute to that then they you know in this picture they drop their ball into that into that topic into that ear uh however there could be like new topics coming up all the time so in this case they just tweet about something completely new and so this gives you this this Dynamic uh uh um creation and contribution which sort of may explain how people are talking about topics and um this also is similar to this um very kind of uh famous realization of Rich will get richer where where where where where the people that already have a lot of connections for instance in social networks or even like in in in in financial terms of course the the the people for instance with a lot of connections they get more connections because others already see that they have a lot that's why they're going to connect to them so it's it always works like that and uh but this uh this model perhaps is is closer to a a picture where where people choose topics that that they can write about so um the the other thing that we can uh basically look at is U is how users are different between these topics so um the uh we can also ask that yeah we have we have now say one one topic that people can talk about but what is what is the the profile of the users that are going to write about that topic and uh in this case what we did was basically we just took the we just took the topics and then we we characterized the topics with their size right so the size would the importance of that top to and that's on the uh on the horizontal axis and the the the the vertical axis for each size of the or for for each cluster we looked at the the previous number of tweets sent by the people that talked about that topic right so so this would mean that uh if uh that there's user say there's Joe who writes about something who who who tweets about something we know in which in which cluster in which topic they they wrote that tweet about and then we also know how many times they tweeted so if we average over the number of tweets uh that people previously sent for a given topic then that would give you kind of the overall activity of people that that contributed to that topic and uh so uh what you can observe here is that if we average over if you take like like uh Grand averages for for all the topics uh and then classify them by their sizes then you can see this kind of this this slight uh but but significant uh decrease especially here in the beginning of the of the uh of the plot where you can see that if he grow if he grow higher and higher with the number of Tweets in the topics then you will get less and less active people there contributing to that topic so the the question why we asked this was that is it possible for us to basically bring people back or or or kind of like uh motivate people to tweet about subjects uh that are more or less uh more or less popular overall in the general sense and it seems to be so that even without kind of any active uh intervention we can see that uh we can see the topics that are more popular overall so which are on towards the right hand side of the scale they will get less active people also talking about them and so this was kind of for us interesting because um or just in general it may be interesting because that it means that uh if if something gets really big if a topic gets like really popular widespread then maybe also the less active users in other words those users that usually just tweet less they will also talk about that so um in other words this could mean that if I want to create a service that lets people know about like upcoming events or something or like important things Beyond just personalization in terms of like like shared interest you could also try to see whether that whether that uh um event in terms of its volume hits the uh the threshold for that users kind of uh um own activity profile you can uh mean the very exact very same thing you can also see in the number of retweets the decline is probably well different scale so I'm not going to say that but there's also a a um um a decline in the number of retweets then we look at the retweets instead of theet so this is exactly the same exactly the same uh plot except for looking at retweets so less active people contribute to bigger topics now when we look at the kind of the network activity of the users in terms of how many follow uh links they created right we also see that now we can see kind of the opposite so as we go to like more important topics we will see that um the people contributing to a more U popular topic they will create more follows so that was counterintuitive to us first and that that's why I'm kind of showing this is that they are less active in terms of twet but they're creating more links so the way that they could kind of explain that to us is that these people are sort of the consumer type that they are there on Twitter because they want to read they want to read tweets they don't necessar want to kind like always uh write or like like tweet and that's why only when it's very popular then they with but they are also the ones that that like to follow a lot of people so they they like to like get get information rather than than than uh then produce information um in in the number of in terms of the the number of followers received we kind of saw a flat uh contribution plot uh again like huge noise so we don't have to like read a whole lot into that but it could also mean that people um they don't differ so much in in terms of like how important themselves are when they are contributing to P right so when I see how important themselves are I mean that a person that follows a lot of uh uh person that receives a lot of follows that you know that's a lot of follows received but it doesn't really matter if you receive a lot of follows or not you will like contribute to the same amount to uh to Cluster to topics uh just very quickly about the temporal characteristics of these events so when you look at the this uh the length of these events and then how many number of tweets events get n we we chose to plot it this way that here on the on the left hand side you can see that uh how many how many minutes it takes for the event to to come from uh from the beginning when we start seeing the first fits up until the end when it dies out now you can see that it's kind of like it's a it's an increasing curve on the right hand side you can see we we kind of rescale one of the axis the the y- axis that it's more or less kind of exponential a very slow exponential but it's exponential so it's like increasing but you also see the interesting thing I would like to point out two kind of the Peaks there at 1 hour and that's about two hours so uh this would mean to us that uh without really like looking into detail about this this events that this this kind of like pre-arranged events like say this conference right so you are sitting in one of the talks takes about an hour that's when people are talking about events or in a movie TV show whatnot why it lasts people are talking about that and uh there is this definite two PS at one and two hours so maybe relating to this uh um daily rhm and so basically this is a this was the um the topic that I wanted to talk about how to identify uh topics in a big uh large amounts of data in a streaming Manner and how we we created this this um hierarchical description of of the of the subjects and and the types of the people that that contribute to those and if you have any questions yeah please please ask me now or even after thank you very much for your attention