quinta-feira, 15 de março de 2012

PageRank: Standing on the shoulders of giants

This paper presents the PageRank algorithm from a historical perspective. PageRank is an algorithm for ranking web pages in terms of relevance based on the structure of the web graph. It was proposed by Sergey Brin and Larry Page in 1998 and has been applied by the Google search engine. This paper is authored by Massimo Fraceschet, from University of Udine, Italy, and was published by the Communications of the ACM magazine.

The HTML protocol, which is the basis for the Web as we know, was invented in 1989 by Berners-Lee while he was working at CERN. PageRank was one of the first efforts on the use of the web topology (that emerges from links between pages) to measure the importance of a page. The basic idea of PageRank is that a web page is important if it is pointed to by other important links. The formulation of the score is as follows:

PI = alpha.PI.S + (1-alpha).u

Where alpha is the damping factor, S is the adjacency matrix of the graph after dangling pages (i.e., without output links) have their output probabilities set as uniform, and u is a uniform probability vector.

The PageRank equation is known to have a unique solution. The existence of at least one solution comes from the fact that the transformed adjacency matrix is stochastic (i.e., all rows sum up to 1). Moreover, according to the Perron-Frobenius theorem,  the equation has a single solution.

Perron-Frobenius theorem: If A is irreducible (i.e., its associated directed graph is strongly connected) nonnegative square matrix, then there exists a unique vector x such that xA = rx, x > 0, and Sum_{i} x_i = 1, where r is the maximum eigenvalue of A in absolute value.

The solution to the PageRank equation can be obtained using the power method, which computes the eigenvector and eigenvalue of a matrix through an iterative process. An initial vector PI^{0} is set to u (uniform vector) and PI^{k+1} = PI^{k}. G, where G is the google matrix. The result converges after a limited number of iterations that depends on the damping factor alpha.

After presenting PageRank, the author discusses a list of very similar methods in Computer Science, Bibliometrics, Sociology and Economics. One of these methods is HITS (Hypertext Induced Topic Search), developed by Jon Kleinberg. HITS is based on the concept of authorities and hubs. Good authorities are pages that are pointed to by good hubs and good hubs are pages that point to good authorities. Given an adjacency matrix L, the authority (x) and hub (y) vectors are defined as follows:

x^k = L^T.y^{k-1}
y^k = L.x^k

These equations can be solved using the power method, like was discussed for PageRank.

I wont discuss the other methods in detail. The point is that ideas very close to PageRank and HITS were developed decades before in other areas.

Bibliometrics (1976): A journal is influential if it is cited by other influential journals.

Sociometry (1949): A person is prestigious if he is endorsed by prestigious people.

Econometrics (1941): Highly remunerated industries are those that receive substantial inputs from highly remunerated industries.

This is a great paper. It is funny how recurring ideas appear somehow independently in some different areas. In the case of PageRank and HITS, the research was developed almost in parallel. Something that I ask to myself sometimes is whether I should know Math a lot or just be able to model the a given problem and then search for the mathematical solution. I've heard somewhere that the second approach is better.

 Link: http://arxiv.org/abs/1002.2858

quarta-feira, 14 de março de 2012

Trust Transitivity in Social Networks

Here goes another paper written by Physicists. This paper studies trust in a social network where trust relationships are transitive. Understanding trust is a very relevant problem in society. In particular, several web applications, such as e-markets and P2P file systems, rely on trustful users in order to provide quality service. Trust transitive plays a special role in non-centralized scenarios, i.e. when there is not a central source of trust available.

Two trust metrics based on transitivity are proposed. The first one, called best trust, is defined as follows:

s_{u,v} = max{PROD_{e_i} c_{e_{i}}}, for all {e_i} in P{u=>v}

According to this metric, the trust of u towards v is the maximum trust product of the direct trusts over the path P{u=>v}is the set of all paths between u and v, {e_i} is the set of edges in a given path, and c_e is a value of direct trust associated to an edge. This metric can be computed using a shortest path algorithm, but the authors argue that it is biased towards high values of trust, so they propose another metric, called pervasive trust:

t_{u,v}=(Sum_w A_{w,v}.(s_{u,v}^{G\{v}})^2.c_{w,v})/(Sum_w A_{w,v}.s_{u,w}^{G\{v}})

Where A is the adjacency matrix, and s_{u,v}^{G\{v}} is the best trust from u to a neighbor of v (v is excluded). In this case, several paths are considered, instead of a single one. Moreover, this metric does not tend to 0 when N approaches to infinite.


The authors give a short discussion on the Eigentrust and the trustWebRank, which are other trust metrics in the literature. These metrics are based on the concept of feedback centrality and are calculated by solving some linear system. Eigentrust requires a stochastic matrix (i.e., the sum of the trust values of the out-edges of all vertices must sum to 1) and the inferred trust values are given by the steady state distribution of the corresponding Markov chain (i.e., the left eigenvector of the stochastic matrix must have an unity eigenvalue). Therefore, the trust values are not personalized and the absolute values of trust are lost. TrustWebRank is based on the PageRank algorithm and also requires a stochastic matrix but is personalized. It also depends on a damping factor that eliminates the contribution of longer paths.

Properties of the two trust metrics presented are studied theoretically. The authors consider a random direct network with arbitrary degree distribution and direct trust values between c and c+dc given by an arbitrary distribution. In this scenario <t> = <s><c> in the limit of large network size. The discussion seems to be heavily based on the paper "Random graphs with arbitrary degree distributions and their applications" that I've not read yet. Therefore, I will not cover the math here. Basically, the authors give a formulation for <s> and compute it through numerical simulations and an analytical solution. In- and out-degree distributions following a Poisson and a Zipf are studied. The authors found a first-order transition from vanishing to positive trust values that correspond to the formation of a giant component in the network when the degree distributions are Poisson. For a Zipf distribution, the transition is of second order and the average trust is smaller than for the Poisson distribution.

Trust transitivity is also studied using data from the PGP (Pretty Good Privacy) network, which is a mechanism for users to attach a signature to the public key of another user for cryptography purposes.  The largest connected component of this network has 40k vertices. It is shown that this network does not grow in a purely random fashion because the power-law distribution of the waiting time between new keys and signatures. Degree distributions seem to follow a power-law. Moreover, the in- and out-degree of  vertices are strongly correlated and the reciprocity is very high. The degree correlation is assortative for intermediary degree values and dissortative for very high and very low degrees. Two paradigms of trust organization are studied: Authority (trust relies on a few universally trusted vertices) vs. Community-based (densely connected components provide trust to each other). The authority-based trust is more efficient but also more prone to forgery. The community-based trust has opposite characteristics. These two mechanisms seem to work together in the PGP network. In order to identify the communities, the authors a modularity maximization algorithm is applied. Two types of communities were found: one that represents the vicinity of an authority vertex and another that represents a "real" community. As means to understand trust transitivity in the PGP network, the authors assign a direct trust c=1/2 to all edges except for a fraction gamma of edges to which c=1. Three scenarios are considered: 1) Edges are selected at random (Random); 2) Edges with the largest betweenness are selected (Authority-centered); and 3) Edges with largest edge clustering are chosen (Community-centered). The authority-centered trust leads to higher values of average trust (<s> and <t>). On the other hand, the community-centered trust leads to lower values of average trust.  Moreover, for random trust distributions, vertices with large degree achieve higher <s> but have uniformly distributed <t>, as desired. For authority-based trust, both small and large degree vertices achieve high trust values. For community-based trust, vertices with intermediary degree achieve higher trust than the small and large degree ones.

This paper is very interesting and relevant. It is similar to another Physics paper I've read some weeks ago. This pattern of studying complex features of simple models seem to be a standard for these kind of paper. In the case of this particular paper, a real dataset (the PGP network) is also analyzed. I found some minor typos that were probably corrected in the "official version" of the paper (this one is from ArXiv). I think that the formulation for <s> is not clear. I will read the paper "Random graphs with arbitrary degree distributions and their applications" in the near future in order to understand the formulation in detail.

Link: http://arxiv.org/abs/1012.1358

terça-feira, 6 de março de 2012

The Role of Social Networks in Information Diffusion

This paper was accepted in the next WWW conference, to take place in Lyon, France. Its authors are from Facebook and University of Michigan (Lada Adamic). The idea of the paper is covering a gap in the study of social influence and information propagation in social networks, which is the fact that most of the existing studies do not distinguish influence/propagation from other sources of correlation (e.g., homophily). Although this problem has been known for years, previous studies had no access to a large dataset that could enable this kind of analysis. Thanks to Facebook, these guys performed an experiment in order to quantify the effect of social relationships in the diffusion of information.

Given a pair of users (A,B) that are friends, the researchers considered two scenarios in which A posts a URL on Facebook: (1) the URL does not appear in B's news feed, and (2) the URL appears in B's news feed. For a large set of pairs subject-URL selected at time of display, the researchers were able to randomly select whom were going to be exposed to the URL and whom were not going not. The number of subjects, URLs and subject-URL pairs considered were 253M, 75M, and 1B, respectively. The collection period ranged from August 14th to October 4th.

Social exposure x diffusion: In order to account for the possible effect of bias towards frequent URLs or active users, the authors considered the bootstrap average by URL to compute the likelihood of sharing for the feed and no feed group. Bootstrapping is a statistical technique for assessing the variation in estimate based on sampling. They found that The likelihood of sharing is 0.191% for the feed and 0.025% for the no feed group. Individuals in the feed condition are 7.37 times more likely to share.

Temporal clustering: Subjects in the feed group share the information sooner than those from the no feed one. The median sharing latency is 6 hours for the feed and 20 hours for the no feed group.

Multiple sharing friends: One important aspect in the literature on social influence and information diffusion is the effect of the number of active/affected/sharing friends.  The authors found that sharing probability increases with the number of sharing friends in both the feed and no feed groups. However, the ratio between the shared probability  in the feed and no feed group decreases with the number of sharing friends.

Tie strength: The frequency of private communication, frequency of public online interaction, number of appearances of users in the same photo, and the number of times users comment on the same posts were considered as tie strength measures. Data from three month prior to the experiment was applied in this evaluation. The goal is to bring back the concepts of strong and weak ties, from a seminal work developed in 1973 called The Strength of Weak Ties, in which was found that weak ties play an important role in social networks. The results presented in this paper also showed that the strength of ties is positively correlated with the probability of sharing for the feed and no feed conditions, but this effect diminishes with tie strength.

Collective impact of ties: On the same topic of the previous section, here the authors compute the effect of exposure to information shared by friends with strength k, which is computed by the following equation:

ATET(k) = p(k,feed) - p(k,n feed)

Where p is the probability of sharing. This value is multiplied by f(k), which is the fraction of links displayed in all users' feeds posted by friends with tie strength k. Ties for which k = 0 were classified as weak and those with k > 0 were classified as strong. The results show that most of the diffusion occurs through weak ties.

This paper is not bad. Handling a dataset like the one used in this paper is an once in a lifetime opportunity for an ordinary researcher. I'm just a little bit disappointed because when I read the tittle and the list of authors, I pictured a better paper in my head. I was expecting a more rich statistical analysis, a bunch of cool visualizations, and also some kind of influence/propagation model based on the data. I did not buy the sections about tie strength, which were probably intended to be the high point of the paper.

Link: http://arxiv.org/abs/1201.4145

segunda-feira, 5 de março de 2012

How (not) to predict elections

This paper is a very simple, but still interesting paper, that brings skepticism on the current hype about making predictions, specially wrt elections, using social media data. I would say that it is somehow similar to the paper 'Predicting Consumer Behavior with Web Search', summarized here 2 months ago.  The authors are from Wellesley College (US) and Universidad de Oviedo (Spain), and I confess I have never heard about any of them.

Several recent papers have reported positive results of the use of social media in the real-time prediction of many outcomes. Similar results have also been reported w.r.t. the use of search engine data. This studies have promptly attracted the interest of the general public. In this paper, the authors revisit some of these studies and show that the results achieved are actually disappointing or misleading. The authors emphasize that fair baselines, such as the incumbency (re-election) rate are not considered and also that the proposed methods perform much worse than professional pollsters or even chance.

In the experimental section, two datasets from Twitter are applied, one related to the Senate elections in Massachusetts (about 234K tweets) and other from an uniform sample of tweets related to 6 races for the US Senate (about 13K tweets). Two published strategies for predicting election results are evaluated, one based on the number of mentions of the candidate and the other based on sentiment associated to terms contained in tweets.  Results show that the number of mentions predicted the victory of the wrong candidate in Massachusetts but sentiment analysis worked. In the other dataset, the number of mentions predicted 3 out of 6 results correctly, same performance achieved by the sentiment analysis. In a further analysis, the authors show that the automatic strategy for sentiment analysis applied achieves very low accuracy (37%). A champaign against a given candidate had most its tweets classified as positive or neutral towards her. Finally, the aggregate opinion of all tweets from users is weakly correlated with the average ADA (Americans for Democratic Action) score of the candidates they follow.

Based on these results, the authors propose set of guidelines for the study of techniques for election prediction: (1) Adjustments should be determined before hand (they always seem obvious afterwards), (2) Social media data should not be considered as from a natural phenomena, since it can be manipulated, (3) We need to understand why a given method works, (4) Proper baselines (e.g., incumbency) should be considered, and (5) Existing polling strategies, based on statistically significant samples, should be considered.

This kind of paper have an interesting contribution to any research area, specially when it comes to criticizing research lines that attract too much publicity without the proper scientific rigor. I would be really concerned if I was cited by one paper like this. Publishing misleading results on purpose is unethical. Although seeing a researcher on NYT or CNN is always inspiring, there is no space for flawed results in  serious research.

Link: http://bit.ly/qUHJyv

domingo, 4 de março de 2012

Education of a Model Student

This is another theoretical paper. Its authors are from Cornell University and include Jon Kleinberg and Steven Strogatz. The subject of the paper is the study of mathematical models for scheduling of educational material. Many asymptotic analysis of the relationship between learning rate and spacing constraints are given for different families of constraints and educational goals.

The authors consider a simplified educational model that is based on a set of educational units u_1, u_2, ... u_n which have spacing constraints defined by sequences {a_k} and {b_k}. A pair (a_i,b_i) tells us that the (i+1)-th ideal time to the student see a given unit is between a_k and b_k time steps after seeing it for the i-th time. In general, the spacing constraints are the same for all units and can be defined by functions. Moreover, the paper studies two educational goals: the infinite perfect learning and the finite sequence (cramming). Infinite perfect learning consists of never forgetting what have been learned so far. Cramming is a method of learning that has a specific temporal target (e.g., a test) and does not assure that the learned material will be remembered after this target.

From now, I will summarize some of the most important results presented in the paper. Proofs will be discussed without much detail.

The Recap Method: Based on the idea of infinite perfect learning and a quick learning rate (i.e., rate at which new content is introduced). The learning rate t_n (i.e., the time stamp when the content n is introduced) grows as theta(n log n) and a_k = 2^k and b_k=2^(k-1)(k+1). An algorithm for generating this schedule can be defined in terms of a depth-first post-order traversal of a binary tree. An example for 4 units is: u_1,u_2,u_1,u_2,u_3,u_4,u_3,u_4,u_1,u_2,u_3,u_4,...

The Superlinearity of the Introduction Time Function: For schedules that exhibit infinite perfect learning, the introduction time function t_n must be superlinear. This is my favorite result of the paper and it makes me think a lot about my own lousy educational strategy. They prove it by contradiction. A linear learning rate means that there is a c such that t_n <= c.n for all n. Let n_0 be an integer such that n_0 > Sum_{j=1}^k b_j. At least c.n_0 units has been introduced at n_0. Moreover, at least n_0  units will have occurred c+1 times by time step c.n_0+Sum_{j=1}^k b_j. So, c.n_0+Sum_{j=1}^k b_j >= (c_1).n_0 and Sum_{j=1}^k b_j >= n_0, which is a contradiction.

The Slow Flashcard Schedule: This schedule is based on a deck of flashcards, where the kth card corresponds to the unit u_k. A card is taken from the top and inserted into the k+1 position, where k is the number of times the card has already been taken. This generates a schedule such as: u_1,u_2,u_1,u_2,u_3,u_1,u_3,u_2,u_4,u_3... It is shown that this schedule exhibits infinite perfect learning with spacing constraints (a_k,b_k) = (k,k^2). Simulation results suggest that this schedule may even exhibit infinite perfect learning with spacing constraints (k,2k).

Flexible Students: For flexible students a_k = 1 for all k. In this scenario, the authors propose a sequencing for which b_1>=2 , b_k => inf and in which the constraints are met and new material is quickly introduced. The idea is increasing the level of the sequences as follows:

Level 1: u_1,u_2,u_1,u_2,...
Level 2: u_3,u_1,u_3,u_2,u_3...
Level 3: u_4,u_1,u_4,u_2,u_4,u_3...
...

This schedule exhibits infinite perfect learning and b_k can grow arbitrarily slowly, depending on the value of b_k.

The Finicky Slow Student: For this family of constraints, where a_k = b_k = k it is not possible to achieve infinite perfect learning. It is proved by contradiction by showing for two or more units, it is not possible to meet the constraints without conflicts. Unit u_1 will occur at times t_1,t_2, ... where t_i = Sum_{k=1}^i a_k. Lets state that u_2 starts at s_0 and also occurs at s_1,s_2, ... where s_i=s_0+Sum_{k=1}^i a_k. We know that s_i - t_i = s_0 and s_{i+1}-s_i = t_{i+1}-t_i=a_{i+1}. Choose k large enough so that t_{k+1}-t_k>s_0, then t_{k+1}>t_{k}+s_0=s_k and t_{k+1}>s_k. Let m be the smallest number such that t_m+1>s_m. The authors show that t_{m}=s_{m-1}.

Cramming: The authors show that for every positive integer n and every set of spacing constraints with b_k approaching to infinite, there exists a sequence that achieves bounded learning of order n. In other words, if you have a given content to study for a test, it is possible to organize a schedule for this test for any valid spacing constraints with enough time. They prove it by induction, using the idea of inserting a new unit into a sequence S_n. They also present limits on the amount of content that can be crammed in a limited amount of time. I confess that I did not understand this part very well, I believe an example would help.

This paper is very interesting. Based on a real complex problem, the authors propose a very simple model and apply asymptotic analysis to study it from several perspectives. During the reading, I discovered that asymptotic analysis was borrowed/stolen by computer scientists, having many (maybe more) applications outside it. I should study this subject more in the future, specially from a broader perspective (e.g., a book about asymptotic analysis in general).

Link: http://www.pnas.org/content/early/2012/01/13/1109863109.full.pdf+html

quinta-feira, 1 de março de 2012

The Power of Sampling in Knowledge Discovery

This is the first completely theoretical paper summarized here. And as completely theoretical I mean that it has no empirical result at all. It took me roughly a week to read this paper carefully, and I still do not think I  understood it fully. The idea is to keep trying papers like these and get used to more theoretical studies with time.

The title of the paper misled me. I was expecting a more general theory to explain why sampling is a good strategy in data mining. However, this paper proves that universal and existential sentences of tuple relational calculus can be verified approximately using a sample of a relation (table). Lower bounds on sample size based on the expected accuracy of this verification are the main contribution of this work. Sampling is expected to enable the analysis of large databases efficiently.

Tuple relational calculus is a query language for the definition of logical conditions and has its origins rooted with the relational model, defined by Edgard Codd in 1969. In this language, tuples are variables and conditions are defined as atoms. The result of a formula can the set of tuples that satisfy it or simply TRUE or FALSE. An example of a formula is:

for all t (R(t) => ((t[A] < t[B]) ^ (t[B] < t[C])))"

This paper focuses on two classes of formulas: universal, like the one above, and existential, which verifies the existence of a tuple with a given property. Moreover, they consider approximate verifications, which associate an error value to a formula. This error is close to 0 if the sentence almost holds  or to 1 if it does not hold. An error threshold epsilon is defined in order to verify sentences in this scenario. In case sampling is applied, a confidence parameter delta gives the probability of a sentence with error greater than epsilon in the relation to remain undetected in a sample. The first error expression is defined as follows:

g_1(sentence theta,relation M) = | {a_1...a_k} in M, such that theta does not hold in M | / |M|^k

This error measure gives the probability that theta does not hold for a random k-tuple. The second error expression is defined as:

g_3(sentence theta,relation M) = |M| - |max subset N of M for which theta holds| / |M| 

In other words, g_3 is the fraction of tuples from M that must be removed in order to make theta hold in the remaining of M.

Relation between g_1 and g_3(Prop. 3.1): For a sentence theta = for all t_1 ... for all t_k phi(t_1...t_k), consider g_3(theta,M)=epsilon, then

epsilon/|M|^(k-1) <= g_1(theta,M) <= 1 - (1-epsilon)^k = k.epsilon + O(epsilon^3)

If N is the maximal subset of M such that theta holds and L = M - N, then epsilon = |L| / |M| and g_3(theta,M) = epsilon. If V = {(a_1...a_k) in M^k such that theta does not hold}, then g_1(theta,M) = |V| / |M|^k. Because |V| >= |L|, g_1(theta,M) >= epsilon/|M|^(k-1). Moreover, |V| <= |M|^k - |N|^k = |M|^k(1-(1-epsilon)^k), therefore, g_1(theta,M) <= 1 - (1-epsilon)^k.

Upper bound on sample size, one sentence, g_1: Let theta = for all t_1 ... for all t_k phi(t_1...t_k), if g_1(theta,M) >= epsilon, then with probability at least 1-delta theta does not satisfies a sample S of M with size m >= k.ceil((1/epsilon).ln(1/delta)).

The sample of size m can be divided into l = ceil((1/epsilon).ln(1/delta)) k-tuples. The sentence theta holds for a k-tuple with probability 1-epsilon, and holds for all these k-tuples with probability (1-epsilon)^k <= e^(-l.epsilon) <= delta.

Upper bound on sample size, K sentences, g_1: For a set of K sentences, m >= k.ceil((1/epsilon).ln(K/delta)).

The probability that one of the K formula holds is delta/K.

Upper bound on sample size, one sentence, g_3: Let theta = for all t_1 ... for all t_k phi(t_1...t_k), k>= 2, there is a constant C_k such that if |M| >= C_k and g_3(theta,M) >= epsilon, then with probability at least 1-delta theta does not satisfies a sample S of M with size:


 m = max{(8/epsilon).ln(2/delta) , (2/epsilon).ceil(7.k^k.ln(2/delta)).ceil(|M|^(1-1/k))}.


 m = O((|M|^(1-1/k)/epsilon).log(1/delta)).

The proof for this theorem is not straightforward. It is based on the idea of a set P which is the maximal subset a set T composed of the tuples that does not satisfy theta such that the elements of P are pairwise disjoint. Given the union of the tuples in P (UP), we know that theta holds for N = M - (UP) and |UP| >= epsilon.|M|. For a sample of m elements from M, the expected number of elements from UP is at least m.epsilon and the probability of having at least m.epsilon/2 elements from UP is at most e^(-me/8) according to the Chernoff bound. Replacing one of the upper bounds on the value of the m in this expression gives that the probability of having at least m.epsilon/2 elements from UP is at most delta/2. Assuming that the sample has at least m.epsilon/2 elements from UP, we can extract from the sample h independent subsamples of size l, where h = ceil(7.k^k.ln(2/delta)) and l = ceil(|M|^(1-1/k)). The authors show that with this values of h and l, the probability of a subsample having all the elements of a set in P is at least 1/(7.k^k), this part was omitted. Therefore, the probability that all subsamples fail to contain all the elements from a set from P is at most (1-1/(7.k^k))^k <= delta/2. The value C_k comes from lower bounds on the size of samples in order to guarantee the given probability of a subsample having all the elements of a set in P is at least 1/(7.k^k). The formula theta holds in the sample in case it fails to contain at least m.epsilon/2 elements from UP or it does not contain all the elements from a set S in P. Therefore, theta does not hold with probability 1-(delta/2 + delta/2) = 1-delta.


Upper bound on sample size, K sentences, g_3: For a set of K sentences:



 m = max{(8/epsilon).ln(2K/delta) , (2/epsilon).ceil(7.k^k.ln(2K/delta)).ceil(|M|^(1-1/k))}.


 m = O((|M|^(1-1/k)/epsilon).log(K/delta)).

It is also shown that these upper bounds can not be improved because their are dependent on epsilon (g_1) and M (g_2). Moreover, the authors give examples of scenarios where each of the error measures provide better bounds and also propose a similar formulation for existential formulas.


I felt disappointed with myself many times while reading this paper. As a computer scientist I was supposed to understand, with a little effort, any paper on computer science. I should try to read papers with a more theoretical focus, like this one. On the other hand, this paper does not seem well-written to me. The authors give no intuition about how they defined some bounds. These intuitions are more important than just proving such bounds. I'm aware that research papers are not supposed to teach, but, at the same time, the worth of a paper is a function of the number of people who can actually read it.

Link: www.cs.helsinki.fi/u/jkivinen/publications/km-pskd-94.ps.gz

quinta-feira, 23 de fevereiro de 2012

The Pulse of News in Social Media: Forecasting Popularity

This is another paper on the series "Predicting popularity of Online Content", written by researchers from UCLA and HP Labs, including Bernardo Huberman. Different from a previous paper I've read, here the authors studied the problem of predicting popularity of news articles based on properties of the articles themselves and not on early popularity records. This problem is very relevant for journalists, content providers, advertisers, and news recommendation systems because of the convergence of news and social media in the dissemination of content on the Web.

The dataset used in this study come mainly from two sources. The first one is feedzilla, a news aggregator, and the second from Twitter. For a given news article from feedzilla, all Twitters that mentioned its respective URL were crawled. Properties of an article are: source, category, subjectivity, and named entities mentioned. For each of of these properties, the authors define a score called t-density. The score of a category is the number of tweets per article of the given category. Subjectivity is a binary attribute defined using a subjectivity classifier. This classifier was fed with tv and radio show transcripts as the subjective class, and articles from c-span (politics and history) and First Monday as the objective class. Named entities were identified using the Stanford-NER tool. For a given article, the score is the average score of the entities it mentions. Source score is based on the success of the given source in another sample of tweets (different from the main dataset). Scores were smoothed and normalized to reduce the effect of temporal variations.

Based on information from google news made available by KnewsKnife (news site rating), the paper investigates whether the top sources found using their score measure match the top sources on google news. The conclusion is that they do not match. Although the number of tweets and articles from a given source are somehow positively correlated with the google news rating, the proposed score is not correlated with the ratings. In fact, the top sources on google news are traditional media websites (e.g., WSJ, Reuters) while the top sources identified in the study are web marketing blogs (e.g., Mashable, Google Blog).

Two problems versions of the popularity prediction problem are considered in the paper: regression and classification. In the regression problem, the goal is to predict the exact number of tweets mentioning a given articles using the features just described. Three models (linear, KNN, and SVM) were applied and the linear model achieved the best results (R^2=0.34). The result is even better when only one category (technology) is considered (R^2=0.43). The authors argue that this is due to the overlap across categories on feedzilla. In general, the most important evidence is the source of the article. In the classification problem, three classes were defined (1-20, 20-100, and 100-2400 tweets). Four classification models were considered (SVM, Decision Tree, Bagging, and Naive Bayes). The bagging and the decision tree algorithm achieved the best result (84% accuracy). Again, the most important feature is the source.

I did not like this paper very much. I think it is due to a lack of theoretical background and the excess of ad-hoc decisions w.r.t. the datasets and the scoring schemes. The results show that the source determines the popularity of news articles what was somehow expected. Maybe, a more important question would be: What makes an article from a ordinary blog or news website to become popular? Or what makes an article from a famous blog or news website fail?

Link: http://arxiv.org/abs/1202.0332