Today I read an interesting paper that used Twitter data. It's a paper by Aron Culotta on detecting influenza outbreaks.
http://arxiv.org/abs/1007.4748
Summary =======
This paper examines the correlation between flu-related tweets and the actual flu trends (reported by the US centers for disease control and prevention, CDC). The author borrows the methodology used in Google's Nature paper on flu tracking (Ginsberg et al. 2009) and uses the log-odds to measure the correlation between two variables: (a) the fraction of population that have flu over several weeks, reported by CDC, and (b) the fraction of tweets that contain flu related keywords.
Findings =======
(1) Similar to the Google's Nature paper, the accuracy in prediction is pretty high---around 95%. (Google paper, based on google search keywords, reported 97% accuracy.)
(2) What is new in this work is that it investigates the need to prune out spurious words like 'swine', 'h1n1', 'vaccine', and 'http'. Tweets containing spurious words likely contain information about the flu passing, but not flu symptoms. However, removing spurious words didn't always increase the accuracy in the prediction of flu trends.
(3) Hence, the author tried out further with two different supervised learning methods to see if spurious words could be removed in a smart way. The answer is partly yes, based on one of the classification methods used.
My thoughts =======
The paper made me think about what sorts of research we are pursuing on the field of data-driven social science. Application-driven research usually has a clear goal, but it always leaves me the feeling of wanting to know more about the data.
(1) Higher accuracy really needed? After reading the first part of the paper, I was less convinced why the author went after increasing the accuracy in prediction. 95% accuracy seems high enough to be used in a surveillance system.
(2) What's next? Maybe to look at social network topology or geography? The frequency of words is one interesting statistic someone can draw from data. But the data has so much more to tell. How are the users connected -- are users who talk about flu symptoms connected? Or are they located nearby in geography?
PS: I am limiting comments only to the members of this blog, as I started getting too many spams.
Apr 27, 2010
The fragility of interdependency
Today, at AALab, we had an interesting discussion about a Nature paper that was published this month: Catastrophic cascade of failures in interdependent networks by Sergey V. Buldyrev, Roni Parshani, Gerald Paul, H. Eugene Stanley & Shlomo Havlin
The paper is about surprising characteristics of a failure on two mutually dependent networks. While most existing studies on network robustness have focused on a single network, this doesn't mean that most real networks are independent of each other. Real networks are often mutually dependent, like the power network and the Internet described in the paper. A router cannot function if a nearby power station is out; a power station cannot function if it is disconnected (i.e., if Internet fails). Logical networks like those of financial and political networks are also mutually dependent. Some networks even share the same entities; we belong to multiple social networks like Facebook and Twitter. And when networks are mutually dependent, a single local failure could trigger a disruptive avalanche of cascading and escalating failures.
Here are three surprising results from the paper:
(Summarized well in Vespignani's article)
1. Networks exhibit a critical threshold value for the fraction of nodes that can be removed above which the network becomes totally fragmented (i.e., the size of the giant component becomes 0). Compared to a single independent network, mutually dependent networks have a much smaller threshold value. This means that mutually dependent networks could collapse at a smaller level of damage.
2. In independent networks, increasing random failures will gradually harm the integrity of the network. However, in mutually dependent networks, increasing random failures lead to abrupt collapse of the network as shown in the graph below. G means the fraction of nodes that belong to the giant connected component. Failures in mutually dependent networks cause a step-like first-order jump around q_c.
3. In independent networks, heavy-tailed degree distributions have been proven to add great robustness under random failures. Power-law graphs are known more robust to random failures than Erdos-Renyi random graphs. This, however, is also not true in mutually dependent networks. Power-law graphs are more fragile when they are mutually connected. The broader the degree distribution is, the more fragile the networks are.
The paper is about surprising characteristics of a failure on two mutually dependent networks. While most existing studies on network robustness have focused on a single network, this doesn't mean that most real networks are independent of each other. Real networks are often mutually dependent, like the power network and the Internet described in the paper. A router cannot function if a nearby power station is out; a power station cannot function if it is disconnected (i.e., if Internet fails). Logical networks like those of financial and political networks are also mutually dependent. Some networks even share the same entities; we belong to multiple social networks like Facebook and Twitter. And when networks are mutually dependent, a single local failure could trigger a disruptive avalanche of cascading and escalating failures.
Here are three surprising results from the paper:
(Summarized well in Vespignani's article)
1. Networks exhibit a critical threshold value for the fraction of nodes that can be removed above which the network becomes totally fragmented (i.e., the size of the giant component becomes 0). Compared to a single independent network, mutually dependent networks have a much smaller threshold value. This means that mutually dependent networks could collapse at a smaller level of damage.
2. In independent networks, increasing random failures will gradually harm the integrity of the network. However, in mutually dependent networks, increasing random failures lead to abrupt collapse of the network as shown in the graph below. G means the fraction of nodes that belong to the giant connected component. Failures in mutually dependent networks cause a step-like first-order jump around q_c.
3. In independent networks, heavy-tailed degree distributions have been proven to add great robustness under random failures. Power-law graphs are known more robust to random failures than Erdos-Renyi random graphs. This, however, is also not true in mutually dependent networks. Power-law graphs are more fragile when they are mutually connected. The broader the degree distribution is, the more fragile the networks are.
Jan 12, 2010
A Nature paper on human insurgency
Common ecology quantifies human insurgency
by Bohorquez, Gourley, Dixon, Spagat, and Johnson
(CEIBA complex systems research center in Columbia, etc)
The paper presents an empirical data analysis of 9 major insurgencies, consisting of 54,679 events worldwide. The paper centers around the theme of finding a common factor across different insurgent conflicts and proposes a model of conflict organization, which treats insurgent population as an ecology of dynamically evolving, decision-making groups. Although groups are heterogeneous in terms of their strategies, they tend to converge towards similar response when fed the same information.
Finding (a) Insurgent conflicts have different characteristics from the traditional wars: their scaling factor is around 2.5 and typically show a power-law trend (rejects log-normality), while traditional wars cannot reject log-normality and show a smaller scaling factor. The implication of this scaling factor (2.5) is at its robustness. (It's hard to fragment such insurgent group.)
Finding (b) Burstiness in terms of the number of events per day shows abundance of heavy and light days, or conversely, lack of 'medium' days. The implication of this burstiness is at maximizing the media attention. (Modern insurgent conflicts are not about killing others, but about media show. It's better to attack on a quiet day)
Model assumes two mechanisms: (a) on-going group dynamics within the insurgent population (coalescence and fragmentation of members to different groups over time) (b) group decision making about when to attack
Personal note: I read this paper twice. At first, the model seemed too simple and I wasn't really impressed by the work. Given the general theme of the paper, I expected there to be lots of sophisticated ideas and theories that people have looked at. The model in the paper, however, was extremely simple. After a second read, I starting seeing how a simple model could link together many different empirical patterns the paper showed (e.g., why insurgencies occur around a scaling factor of 2.5, why the distribution of Columbian and Afghanistan insurgencies have different tail shapes.)
Among the tricks I've learned from the paper, I liked the frequency distribution of real wars against random wars. 10,000 random wars were generated such that dates of the events were shuffled and the average frequency was taken across the samples. Authors then compare the frequency distribution of actual data with this randomly shuffled wars. I also liked the link between this work and the same patterns shown in financial data (how people herd around different stock items each day) -- it might really show a crucial link between violent and non-violent forms of human behavior.
Now moving forward, how could we utilize the result of this work to other social network data like Twitter? Insurgency, rallies, and demonstration -- all seem difficult in terms of parsing data. But if we can do anything, what would I want to look at? Adopting methodology is an obvious way, but could we do something cooler?
by Bohorquez, Gourley, Dixon, Spagat, and Johnson
(CEIBA complex systems research center in Columbia, etc)
The paper presents an empirical data analysis of 9 major insurgencies, consisting of 54,679 events worldwide. The paper centers around the theme of finding a common factor across different insurgent conflicts and proposes a model of conflict organization, which treats insurgent population as an ecology of dynamically evolving, decision-making groups. Although groups are heterogeneous in terms of their strategies, they tend to converge towards similar response when fed the same information.
Finding (a) Insurgent conflicts have different characteristics from the traditional wars: their scaling factor is around 2.5 and typically show a power-law trend (rejects log-normality), while traditional wars cannot reject log-normality and show a smaller scaling factor. The implication of this scaling factor (2.5) is at its robustness. (It's hard to fragment such insurgent group.)
Finding (b) Burstiness in terms of the number of events per day shows abundance of heavy and light days, or conversely, lack of 'medium' days. The implication of this burstiness is at maximizing the media attention. (Modern insurgent conflicts are not about killing others, but about media show. It's better to attack on a quiet day)
Model assumes two mechanisms: (a) on-going group dynamics within the insurgent population (coalescence and fragmentation of members to different groups over time) (b) group decision making about when to attack
Personal note: I read this paper twice. At first, the model seemed too simple and I wasn't really impressed by the work. Given the general theme of the paper, I expected there to be lots of sophisticated ideas and theories that people have looked at. The model in the paper, however, was extremely simple. After a second read, I starting seeing how a simple model could link together many different empirical patterns the paper showed (e.g., why insurgencies occur around a scaling factor of 2.5, why the distribution of Columbian and Afghanistan insurgencies have different tail shapes.)
Among the tricks I've learned from the paper, I liked the frequency distribution of real wars against random wars. 10,000 random wars were generated such that dates of the events were shuffled and the average frequency was taken across the samples. Authors then compare the frequency distribution of actual data with this randomly shuffled wars. I also liked the link between this work and the same patterns shown in financial data (how people herd around different stock items each day) -- it might really show a crucial link between violent and non-violent forms of human behavior.
Now moving forward, how could we utilize the result of this work to other social network data like Twitter? Insurgency, rallies, and demonstration -- all seem difficult in terms of parsing data. But if we can do anything, what would I want to look at? Adopting methodology is an obvious way, but could we do something cooler?
Jan 11, 2010
Decentralized Search Algorithms
Complex network research focuses on large-scale network structures such as social systems, cell biology, neurology, etc. The goal is to bserve real-world network properties and model the observed properties under random mechanisms.
Erdos-Renyi (1959) random graph G(n,p) connects two pairs of nodes with a probability p=c/n where c is a constant. It has two important properties: (a) when c is less than 1, composed of small components all of which have O(logn) (b) when c is greater than 1, a.a.s. (asymptotically almost surely), a unique giant component containing theta(n) nodes appears, which is called the phase transition.
Stanley Milgram's 6-degree separation states that not only there exist a short path in a society, it is possible for individuals to find such a path using only local information.
Small world networks by Watts and Strongatz uses grids (to guarantee clusters) and makes short cuts in the network uniformly random. This leads to preserving small-world properties (i.e., short distance and high clustering). The prevailing need for this model is that Erdos-Renyi random graph does not support the notion of clusters.
Extended model by Kleinberg is a variant of the small-world model. Rather than making shortcuts that are uniformly random, Kleinberg assumes shortcuts follow a particular distance distribution, rho(v,w)^-alpha, and showed that (a) alpha=2, decentralized algorithm exists that is of O(log^2 n). (b) Otherwise, there does not exist any poly-logarithmic decentralized algorithm.
Further readings:
1. J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
2. J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
Erdos-Renyi (1959) random graph G(n,p) connects two pairs of nodes with a probability p=c/n where c is a constant. It has two important properties: (a) when c is less than 1, composed of small components all of which have O(logn) (b) when c is greater than 1, a.a.s. (asymptotically almost surely), a unique giant component containing theta(n) nodes appears, which is called the phase transition.
Stanley Milgram's 6-degree separation states that not only there exist a short path in a society, it is possible for individuals to find such a path using only local information.
Small world networks by Watts and Strongatz uses grids (to guarantee clusters) and makes short cuts in the network uniformly random. This leads to preserving small-world properties (i.e., short distance and high clustering). The prevailing need for this model is that Erdos-Renyi random graph does not support the notion of clusters.
Extended model by Kleinberg is a variant of the small-world model. Rather than making shortcuts that are uniformly random, Kleinberg assumes shortcuts follow a particular distance distribution, rho(v,w)^-alpha, and showed that (a) alpha=2, decentralized algorithm exists that is of O(log^2 n). (b) Otherwise, there does not exist any poly-logarithmic decentralized algorithm.
Further readings:
1. J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
2. J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
Winter School on Algorithms and Combinatorics
Attending a very interesting winter school organized by KAIST professors. It's refreshing to brush up on theoretical concepts.
(1) Talk by Heekap Ahn (Postech) on Voronoi Diagram
Computational efficiency assumes that basic operations (+,-,*,assign,etc) take constant time O(1) and tries to count, given an input size n, how many basic operations is needed.
Convex hull is a set S of points in the plane that is the smallest convex set containing S: A naive algorithm will incur n^3 (n^2 to pick two points and see if it's at the edge) , but a smart algorithm will scan the network in clockwise direction (called the plane sweeping technique) and solve in nlogn (sort by x-axis) + 2n (clockwise step)
Line segment intersection has the worst case of n^2, but an output-sensitive algorithm (relative to the number of intersection) runs in (2n*2+2k)*logn = nlogn + klogn
(2) Talk by Kyomin Jung (KAIST) on NP-Completeness
Interesting observation about how our brains do arithmetics: We remember the addition of two numbers between 0-9, like a turing machine storing 10^2 combinations!, then extends this knowledge to do more complicated calculations. Turing machine is a device with a finite amount of read-only "hard" memory (states) and an unbounded amount of read/write tape-memory. 변하지 않는 부분의 메모리 (하드웨어) + 연습장 (소프트웨어)
Notes on P and NP: (a) P is the set of problems that can be solved in polynomial time, given an input size n (b) NP is the set of problems that can be *verified* in polynomial time, Given candidate solutions, one can verify whether a solution is right or wrong in P time (c) P is a subset of NP (d) The question of P=NP is related to the meaning of intelligence. (Let's say you've solved NP. If P=NP, then there might not be intelligence in the brain that solved it) (e) Cryptography relies on P!=NP. Public keys are given out, but the combinations to generate a public key is practically hard to get. (f) Unless we know P=NP, it is important to develop approximation algorithms!
If P (HP) reduces in polynomial time to Q (TSP), then P is no harder to solve than Q. (a) NP-hard: if all problems all R\in NP are reducible to P, then P is NP-hard; NP중에서 가장 어려운 것 (b) NP-complete: if P is NP-hard and P\in NP, P is NP-complete (NP중에서 가장 쉬울 수 있다) (c) Cook-Levin theorem: the first real case of NP-complete
Combinatorial optimization, max cut, underlying assumption is again P!=NP: (a) rho (ALGO, G) : given a graph G, how efficient is algorithm ALGO? (b) rho (ALGO) = min_G ( rho(ALGO, G) ): given any G instances, what is the best algorithm to solve a problem? (c) rho (maxcut) = max_algo ( rho(algo) ): how hard is the problem itself?
PTAS (polynomial time approximation scheme): 1+/-e of the optimal
FPTAS (fully PTAST)
(3) Talk by Jinwoo Shin (MIT) on Metropolis-Hastings Rule
Suppose we only know local information, how could you sample users uniformly random? This problem is to find random walk without bias. (a) Uniformly random property is p_ij = p_ji (b) Adding a self loop can fix this easily, but could be prone to even-odd number oscillations. (c) A seminar work: Metropolis-Hastings rule since 1950s
(4) Talk by Sang-il Oum (KAIST) on Parameterized Complexity
Concepts: (a) Vertex cover : a set of vertices meeting all edges (b) vertex cover problem (G, k): does G have a vertex cover of size <= k? (c) Minor of a graph: a graph that could be obtained by contracting nodes or deleting nodes or edges
FTP (fixed parameter tractable): a problem with a parametr k is FPT if it can be answered in time O(f(k) n^c) for a computable function f and a fixed c. that is exponential on a fixed parameter k, but not in the input size n. Rod Downey & Michael Fellows
Kernelization: A decidable problem is FTP if and only if it has a kernel
문제가 input 사이즈와 상관없이 사이즈 k에 대해 변형될 수있을때
Main definition: The crossing number, denoted by cr(G), of a graph G is the least possible number of pairs of crossing edges in a graph of G. (a) Finding the crossing number is NP-hard. (b) There exist efficient algorithms to find crossing number of smaller than k; that is the problem is fixed parameter tractable.
(6) Talk by Kyomin Jung on Randomized Algorithms
Define a turing machine that can through a binary random coin, called a probabilistic turing machine. (a) What is good about it? Smoothes the "worst case input distribution" into "randomness of algorithm." (b) Law of large number property means that independent random samplings lead to an average that is close to the expectation, e.g., Erdos-Renyi random graph G(n,p) (when does a giant component appears?), voting poll (how to find good sample for a poll?).
Chernoff Bound: (a) Suppose we have a coin with a probability of a head p, then the expected number of heads is 1*p + 0*(1-p) = p. (b) After flipping a coin m times, the error rate is <= exp ( - lamda^2*m
) where lambda is an error. (c) Las Vegas algorithm is a randomized algorithm that always gives correct answer. (d) Monte Carlo algorithm has deterministic running time, but its output could be correct with a certain probability.
BPP (bounded-error, probabilistic, polynomial time): the set of problems that have Monte Carolo algorithms. (a) Is BPP=P (deterministic language)? (b) Pseudo-random generator (PRG) picks a random number not purely random, but is very hard to determine its randomness in polynomial time.
Randomized min cut algorithm by David Karger: Repeat until |V|<=2, pick a random edge and contract the edge. The two remaining nodes represent the cut points.
(1) Talk by Heekap Ahn (Postech) on Voronoi Diagram
Computational efficiency assumes that basic operations (+,-,*,assign,etc) take constant time O(1) and tries to count, given an input size n, how many basic operations is needed.
Convex hull is a set S of points in the plane that is the smallest convex set containing S: A naive algorithm will incur n^3 (n^2 to pick two points and see if it's at the edge) , but a smart algorithm will scan the network in clockwise direction (called the plane sweeping technique) and solve in nlogn (sort by x-axis) + 2n (clockwise step)
Line segment intersection has the worst case of n^2, but an output-sensitive algorithm (relative to the number of intersection) runs in (2n*2+2k)*logn = nlogn + klogn
(2) Talk by Kyomin Jung (KAIST) on NP-Completeness
Interesting observation about how our brains do arithmetics: We remember the addition of two numbers between 0-9, like a turing machine storing 10^2 combinations!, then extends this knowledge to do more complicated calculations. Turing machine is a device with a finite amount of read-only "hard" memory (states) and an unbounded amount of read/write tape-memory. 변하지 않는 부분의 메모리 (하드웨어) + 연습장 (소프트웨어)
Notes on P and NP: (a) P is the set of problems that can be solved in polynomial time, given an input size n (b) NP is the set of problems that can be *verified* in polynomial time, Given candidate solutions, one can verify whether a solution is right or wrong in P time (c) P is a subset of NP (d) The question of P=NP is related to the meaning of intelligence. (Let's say you've solved NP. If P=NP, then there might not be intelligence in the brain that solved it) (e) Cryptography relies on P!=NP. Public keys are given out, but the combinations to generate a public key is practically hard to get. (f) Unless we know P=NP, it is important to develop approximation algorithms!
Hamiltonian Path Problem (HP) - visit each node exactly once
Traveling salesman problem (TSP) - find the shortest path that is HP
If P (HP) reduces in polynomial time to Q (TSP), then P is no harder to solve than Q. (a) NP-hard: if all problems all R\in NP are reducible to P, then P is NP-hard; NP중에서 가장 어려운 것 (b) NP-complete: if P is NP-hard and P\in NP, P is NP-complete (NP중에서 가장 쉬울 수 있다) (c) Cook-Levin theorem: the first real case of NP-complete
Combinatorial optimization, max cut, underlying assumption is again P!=NP: (a) rho (ALGO, G) : given a graph G, how efficient is algorithm ALGO? (b) rho (ALGO) = min_G ( rho(ALGO, G) ): given any G instances, what is the best algorithm to solve a problem? (c) rho (maxcut) = max_algo ( rho(algo) ): how hard is the problem itself?
PTAS (polynomial time approximation scheme): 1+/-e of the optimal
FPTAS (fully PTAST)
(3) Talk by Jinwoo Shin (MIT) on Metropolis-Hastings Rule
Suppose we only know local information, how could you sample users uniformly random? This problem is to find random walk without bias. (a) Uniformly random property is p_ij = p_ji (b) Adding a self loop can fix this easily, but could be prone to even-odd number oscillations. (c) A seminar work: Metropolis-Hastings rule since 1950s
(4) Talk by Sang-il Oum (KAIST) on Parameterized Complexity
Concepts: (a) Vertex cover : a set of vertices meeting all edges (b) vertex cover problem (G, k): does G have a vertex cover of size <= k? (c) Minor of a graph: a graph that could be obtained by contracting nodes or deleting nodes or edges
FTP (fixed parameter tractable): a problem with a parametr k is FPT if it can be answered in time O(f(k) n^c) for a computable function f and a fixed c. that is exponential on a fixed parameter k, but not in the input size n. Rod Downey & Michael Fellows
Kernelization: A decidable problem is FTP if and only if it has a kernel
문제가 input 사이즈와 상관없이 사이즈 k에 대해 변형될 수있을때
(5) Talk by Heekap Ahn (Postech) on Geometric Graphs
Notations: (a) A graph without cycle is a forest; a connected forest is a tree. (b) A separating set of G will make the graph disconnected. (c) k-connected, if separating set has cardinality of at least k. (d) A graph is planar if it can be drawn in the plane wihtout crossing edges. That is, a planer graph has a crossing number of zero. (e) Geometric graph is a subset of topological graph.
Main definition: The crossing number, denoted by cr(G), of a graph G is the least possible number of pairs of crossing edges in a graph of G. (a) Finding the crossing number is NP-hard. (b) There exist efficient algorithms to find crossing number of smaller than k; that is the problem is fixed parameter tractable.
(6) Talk by Kyomin Jung on Randomized Algorithms
Define a turing machine that can through a binary random coin, called a probabilistic turing machine. (a) What is good about it? Smoothes the "worst case input distribution" into "randomness of algorithm." (b) Law of large number property means that independent random samplings lead to an average that is close to the expectation, e.g., Erdos-Renyi random graph G(n,p) (when does a giant component appears?), voting poll (how to find good sample for a poll?).
Chernoff Bound: (a) Suppose we have a coin with a probability of a head p, then the expected number of heads is 1*p + 0*(1-p) = p. (b) After flipping a coin m times, the error rate is <= exp ( - lamda^2*m
) where lambda is an error. (c) Las Vegas algorithm is a randomized algorithm that always gives correct answer. (d) Monte Carlo algorithm has deterministic running time, but its output could be correct with a certain probability.
BPP (bounded-error, probabilistic, polynomial time): the set of problems that have Monte Carolo algorithms. (a) Is BPP=P (deterministic language)? (b) Pseudo-random generator (PRG) picks a random number not purely random, but is very hard to determine its randomness in polynomial time.
Randomized min cut algorithm by David Karger: Repeat until |V|<=2, pick a random edge and contract the edge. The two remaining nodes represent the cut points.
Aug 28, 2009
Iran election in Twitter
One of the most exciting events in social media would definitely be how the use of Twitter lead to some of the rallies and protests in Iran. Our team at MPI-SWS started looking at Twitter to study the patterns of information propagation. After numerous days of data collection and parsing, finally we are ready to investigate how tens of millions of users communicated with each other. Here's a sneak peek of our on-going research: (Disclaimer: this is definitely an exciting, yet preliminary result and could be changed later on.)
We've looked at whether users who posted tweet(s) on Iran election are connected in the social graph. Imagine the entire social graph of Twitter. Then mark all nodes (=users) who wrote at least one tweet about Iran election. Remove all other nodes in the social graph. Now focus on the remaining nodes in the network. What do they look like?
The plot above shows the size and the number of connected components, where each connected component represents a set of users who are connected by friendship. There were 200,000 users who talked about Iran election in our (sampled) dataset. Surprisingly, 85% of the users belonged to a single large component and 2% of the users to smaller tons. 15% of the users were singletons; they were not connected to any other users who talked about Iran election.
We initially expected to see a power-law distribution whose characteristic pattern is a straight line. This means that the number of connected component should have x^a relationship with the size of the connected component x. (a is called the power-law exponent). But we see two different exponents in the plot.
So why don't we see a straight line in the size distribution of connected components? I have several hypotheses for why we might see a multi-scaling trend, such as the language barrier and the effect of mass media.---I like these moments when I encounter unusual patterns. This is what makes research all the more challenging and fun.
Focusing on the largest connected component, users in this group do show a power-law distribution in their connectivity. Some users potentially influenced tweets of more than 1,000 others (meaning that these users had more than 1,000 fans who also wrote about Iran election); likewise, a user can be influenced by more than 1,000 others in one's subscription list. Both indegree and outdegree distributions follow a power-law trend; but interestingly these quantities turn out to be not related (correlation coefficient of 0.3066).
There are a lot that need to be done and I'm fascinated to investigate how social media like Twitter have changed the way we encounter new information and collaboratively propagate messages among users.
Aug 12, 2009
The 1st International Workshop on Mining Social Media
If you're working on social networks and data mining, here's a perfect workshop to consider at a wonderful south of Spain:
Mining Social Media (MSM'09)
Paper submission deadline: September 6th
Venue: November 9th, 2009 Seville, Spain
Mining Social Media (MSM'09)
Paper submission deadline: September 6th
Venue: November 9th, 2009 Seville, Spain
Jun 26, 2009
Timely research
I'm reading a nature paper that was published yesterday, Origins and evolutionary genomics of the 2009 swine-origin H1N1 influenza A epidemic.
This is a 4-page letter paper. According to the Nature authors' guide, this means the paper provides an outstanding finding whose importance means that it will be of interest to scientists in other fields. Regular articles in Nature is 5 page long and needs to make a substantial advance in understanding of an important problem.
As the title says, the paper is about the recent 2009 swine flu. I'm amazed that scientists put together good work in such a short period of time. Well, informally, I've heard of a couple of immediate rejections on the Swine flu to Nature. This says, there are *lots* of scientists who are quick and good.
What can social network researchers do with the abundance of data and the recent Iran election? This could turn into another great Nature letter paper in a few months.
Jun 17, 2009
Twitter FAQ
So it happened that I finally came across something to ReTweet about. My very first use of "RT". For those of you who are not familiar with Twitter codes, here is a brief and useful tutorial on Twitter FAQ.
RT means ReTweet or Repeat.
Copy the message you want your want to retweet and start with "RT @UserName"
OH means OverHeard
When you hear something funny or insightful with your ears (as opposed to reading it on Twitter) and you want to repeat it, prefix it with OH. Generally, this is used anonymously, not for quoting people.
HT means HeardThrough
This is similar to OH in that you use it to repeat things you heard with your ears. A difference is that you can quote the person's name.
Starting with @ sign means Reply
When you want to reply to someone, start your tweet with @UserName.
Hash Tags (#) help to designate topics that people might search for
When you head to conferences, look for hash tags.
#FollowFriday means recommended followers
This is like book recommendations from a friend. You can list your top followers in the form of @UserName after this tag.
May 20, 2009
ICWSM'09 note - day three
Leveraging Diversity
- Ideas embracing diversity in opinions getting popular: Sidelines, Google moderator
- Goal is to project an accurate proportion of users supporting different opinions. let users get an exposure to challenges or new ideas.
- Quick Q: do people really like diversity?
- Similar work on news media bias "NewsCube" (CHI'09). This work looks at content to aggregate similar news and project different themes news articles. Sidelines paper simply looks at voting counts.
- "Diversity in user activity and content quality in online communities" by Tad Hogg. How many activities does a user do per day?
- Users with very little online time or little activity harder to model (i.e., difficulty of modeling in a heavy-tail distribution).
- Visibility (or exposure) is the key mechanism by which information spreads? (whether exposed by friends or by serendipitous browsing). Visibility and interest are different. (look paper)
- Check out Lada Adamic's write-up on social networks at HP labs.
"Unlike viruses, which spread indiscriminately from host to host, pieces of information are propagated by people who find them interesting and who pass the information to others who they think may be interested. Since people are most similar to their immediate contacts, and this similarity decays as the distance in the social network between individuals increases, information becomes less relevant further away from the source and is unlikely to spread throughout the network. This holds true even in networks with power-law connectivity distributions where highly connected individuals, known as hubs, have the opportunity to potentially spread information to a large number of people. " (See paper)
- Spetrum: retrieving different points of view from the blogosphere.
- Meta search engine for blogs. Would be nice to see memes in the search results. Predicting bloggers' interests in realtime difficult.
- Blog directory (blog category, blogging fusion, yahoo! directory) - Do these sites really work? Blogs are ephemeral.
May 19, 2009
Duncan Watts keynote speech at ICWSM
(1) evolution of social network structure over time
- Work with Gueorgi Kossinets
- Social network changes over time. Averages about network structure (e.g., path length, clustering coefficient, node degree) stay rather steady over time, but individual quantities (e.g., rank) change rapidly.
- What does this mean in terms of social applications?
(2) macro-sociological experiment on social influence
- Music lab experiment -- very cute idea.
- People do get influenced by others. However, the top favorites in the social influence world also did well in the independent world. (Same trend for the bottom ones in the popularity distribution. Lots of noise in medium hot content)
(3) network survey on facebook
- Launched "Friend Sense" app on Facebook and asked political preferences of users and their friends.
(4) influence of financial rewards on performance
- Crowd sourcing site Amazon's Mechanical Turk (AMT) is a fantastic place to launch quick and inexpensive social science studies.
- Increased pay resulted in more work, but not increased accuracy in work. People always feel they are underpaid---the anchoring effect in psychology
(5) final remarks
- We moved from having too little data to having too much data.
- Facebook's 200+M users don't fit on a single memory for us to analyze!
- Having one more zero in your dataset (huge-data) doesn't mean that you're asking big questions. It's more important to ask important questions and set up experiment that can answer the question.
- Lada Adamic's recent work on diffusion of gesture on second life
- Duncan said, "You might ask why are we even asking this obvious question. After many years of being a sociologist, nothing is obvious!"
ICWSM'09 note - day two
Panel Discussion
- Cameron Marlow@Facebook: Look at data to do informed design
- Q: How do users find information on site? Are social links actively used? What about search?
- Slideshare A: We do see clicks from social networking sites, but most requests come from Google. So we put a lot of efforts and make sure our slides are easily searchable in Google. Front page is also important -- but that's more of a setting a tone about the site. (identity). We do lots of editorials in the front page.
- Facebook A: news feed is definitely the most important. This is a huge optimization problem. Facebook provides two feeds: live feed, highlights.
Modeling Social Dynamics
- Interesting paper "Stochastic models of user-contributory web sites" does modeling in social sites, similar to the famous Huberman et al. Science paper from 1998.
- One thought. Modeling is based on visible data. How would a model of user behavior change if we were to consider both visible and invisible activity? (e.g., browsing takes up most of our online time!)
- Prediction of content popularity based on early data possible--we've seen the same trend in YouTube. Is this a general trend in any massive content system?
- Flickr and YouTube are not about social relationship, but ultimately about information sharing. See evidence: paper "Personal Information Management vs. Resource Sharing"
- Social dimension (Shneiderman 2002): People search for other people's content on Flickr and YouTube. vs. People search for their own content on Delicious and Connotea. So is the purpose of tagging.
- Social computing & sustainability of sites: it's important to understand what, where, and why people share.
- Interesting paper by Nov et al.
- Motivation for sharing, two axes: self or others, intrinsic or extrinsic. All four combinations have positive loop to user behavior.
- This reminds me of comment from a director at Big Brothers. He said people post videos in YouTube, because they want to be the Steven Spielberg on the web.
May 18, 2009
ICWSM'09 note - day one
Some of the interesting comments and conversations I heard:
Keynote speech
- In opinion mining, simply using bag of words is not enough. Structure of the text is also important, e.g., look for "still" and "however".
- ? and ! are negative feedback cues
Community
- Over a billion dollars spent on influential viral marketing.- My social cascade work got some attention.
- People's exposure to feed is the most critical factor in social cascade. Number of friends didn't play any significant role (i.e., accidental influential users?).
- Search "Facebook data" in Facebook. Join the Page!
- In a system like Yahoo! Answers, people reward answerers the most on topics like Music, Computer, and Medicine. However, Science questions were rewarded low.
Psychology and Users
- Like Stanley Milgram's familiar strangers in the offline world, we can find familiar strangers in the online counterpart. One key insight to do this is that it will benefit a lot of people. (Social networks have power-law degree distribution, where many people have few contacts. Knowing familiar stranger for people in the tail.)
- Download geotag data at DBpedia
Ranking
- CourseRank program in Stanford by Georgia Koutrika, popularly used by students to rank courses and plan course scheduling.
- Some cute findings: (a) the larger the department size, the smaller individual contribution is. (b) students who got better grades gave higher ranking to the course.
- High median node degree in social networks can reflect spurious relationships? Search "top friends" application on Facebook.
- Similar to "Predicting Tie Strength With Social Media" from CHI2009, paper "Using Transactional Information to Predict Link Strength in Online Social Networks" looked at wall and photo posts to guess tie strength. They used Top Friends app results as the ground truth.
Some thoughts on tie strength and influential users
- After listening to some of the talks, I had the following thought. Network-activity based studies on user interaction mostly focus on visible interactions, e.g., wall posts and photo tagging. This might be a good predictor when we want to measure the strength of ties between individuals (or simply ask who are my best friends?). Then, what does a tie strength mean in terms of viral marketing? Are friends of stronger ties a good indicator of influential people?
- I get a feeling that this is not the case. Based on the Facebook paper "Gesundheit! Modeling Contagion Through Facebook News Feed", we also learned that adoption of information has to do with simple exposure (but not on how popular a friend is). Indeed, exposure is an important and dominant factor in social networks. My recent work using social network clickstream data showed that more than 80% of user activity had to do with "silent" browsing---which a crawl-based study cannot capture. Which friends are important then in viral marketing? Best friends or those whom I get exposed to?
- Obviously there will be lots of overlap between the two groups. But, my conclusion today is that influential users are the ones whom I "actively" get exposed to. This means friends whom I follow up on their updates by visiting their pages. Would accidental influentials would be those whom I got opportunistically exposed to (e.g., Facebook's news feed) and joined cascades?
Tutorial: Psychology of Social Media
This was a 2-hour long tutorial at ICWSM'09, delivered by Sam Gosling (UT Austin) and Kate Niederhoffer (Nielsen Online). It was refreshing to listen to people in different fields who look at the very same problems (audience span psychologists, sociologists, computer scientists, wall street analysts). Sharing my note below.
1. Social media (like Facebook, Twitter) is serving some psychological needs. What?
- Everybody spends their day by doing something. What do they do and what does that tell us about the person?
- Psychologist Maslow says everyone has his own "hierarchy of human needs". This means that we all have our own set of priority in the action set.
2. Fundamental social needs of people: People want to (1) get along and (2) get ahead.
- Get along meaning, socialize. Get ahead meaning, step up in the social hierarchy level. How could this be projected in social media?
- What do our friends tell us about us? In a lab test, people with low self-esteem wanted to hang out with those who gave negative feedback, against those who gave positive feedback. Homophily?
3. People want to be seen accurately, than being projected more positively than they actually are.
- Sam looked at webpages of people, contacted the webpage owners, interviewed them and asked what person they'd like to be, asked their friends what the person is like, and found the projection is rather accurate.
- Would this hold in Facebook too?
4. What are identity claims?
- This mean the things about you that is deliberately chosen for other people. Examples are t-shirts that you wear, bumper sticker, webpage, pictures you hang in your room, etc.
- Music is not an identity claim. It's a tone-setter. It is typically chosen to set our mood in a particular way. You listen to upbeat music when you head out for clubbing vs. when you are home, you may listen to a different music.
- Books are inadvertent identity claims. This is not so deliberate, but is a behavioral residue over a longer time period. Just by looking at the variety, topics, and organization of books at home, we can tell so much about the person. For example, does the person read a wide variety of books (openness), are the books actually read, are there notes, how are they ordered -- neatly or messy, are cheesy books hidden behind, etc.
5. Language is the backbone of our expression.
- There are a lot of approach to understand human behaviors based on their linguistic styles. The use of pronouns (which we think is garbage word) can already reveal sex and age of a person.
- 140 characters in Twitter can tell so much.
- Usage of word "I" : more common among females. more common among people with low social status. Usage of word "We": group action. but also reflects future trouble (meaning, followed by "but")
6. What do we need to know to know a person?
(a) big five traits (openness = creativity + interest + opinions, conscientiousness = daily life, extraversion = documenting life, agreeableness = polite topic covered, neuroticism = cathartic or auto-therapeutic purpose - standard way, look Goldberg 1992, Costa and McCrae 1992)
(b) personal concerns (visions and goals)
(c) identity (personal myth - very difficult to measure)
May 15, 2009
John Wilkes
John (who is my Facebook friend!) visited MPI-SWS and gave a talk about data center storage design. His theme was the design of "light out data center": can we design a data center that will continue to work when all the light goes out (without human intervention?) This means automated control.
He also shared one very interesting thought. SLAs are ad-hoc and random (e.g., service outage should be within three-nines, or 0.999 availability). Sometimes meeting this arbitrary number means investing arbitrary money and effort. So why not have flexible SLA and see what are the losses as we fail to meet the needs?---what a refreshing idea. John further said cost of not meeting the needs at Google may mean loosing customers. He said "users are one click away from leaving to other services" and the cause of leaving may depend on many axes including a particular shade of blue they use in the logo.
May 9, 2009
Chocolate pie chart
I have been quite busy with a paper deadline, advisory board visit, etc. While looking for a nice graphics tool to plot a pie chart, I came across this irresistible chart made of 70% milk + 20% dark + 10% milk chocolate. I'd love to make a program to generate this.
If tempted to put on your paper, consult Mary and Matt store
If tempted to put on your paper, consult Mary and Matt storeApr 18, 2009
Social Mobile Web 2009
I am looking forward to reviewing interesting papers for the Social Mobile Web 2009 workshop. We have very cool Program Committee members and I am happy to be part of the group. Mobile devices are everywhere and I would love to see innovations coming out in this area.
Call for Paper:
The mobile space is evolving at an astonishing rate. At present there are over 3.5 billion mobile subscribers worldwide and with continued advances in devices, services and billing models, the mobile web looks set to inspire a new age of anytime, anywhere information access. The inherent characteristics of mobile phones enable new types of interactions, e.g. mobile phones are personal to the individual, they are always on and always connected. And as such we are seeing a shift towards mobile devices for social mediated tasks. The world is also witnessing an explosion in social web services. Online social networking sites such as Facebook and MySpace continue to experience huge increases in usage, with more and more users seeking novel ways of interacting with their friends and family.Topics:
Novel social interactions on mobile devices.
Social mobile content sharing and distribution services.
Context aware mobile services - beyond location based services.
Social mobile search and social mobile browsing.
User evaluations of social mobile services.
Mobile user interfaces that incorporate social elements.
Mobility and social networks.
Models of mobile social behavior and mobile traces.
Urban gaming, mobile mixed reality, etc.
Innovative social mobile applications.
Deadline: May 11th 2009
Apr 9, 2009
Plotting Venn diagrams
I'm having fun with this marvelous program Twitter Venn: a program that takes in search keywords and plots a Venn diagram that represents the overlap in the use of keywords in Twitter messages. Making of this application appear in Jeff Clark's blog.
Twitter makes the search possible online (search.twitter.com), which allowed this to happen. Very nice. I want to make more sophisticated Venn diagram: similar to the Google's key word trend, I'd like to see how the relationship evolves. Or a given keyword, I'd like to see the hottest matching set of keywords.
BTW, what went happened with such small overlap in cat and sleep? Am I the only one with a cat that sleeps all day long?
Apr 7, 2009
Crawling YouTube
I started crawling YouTube site (again!) to get video comments. This time, I'm using Google Data API and properly approaching the site. The API makes the code very short and I like that it runs fast. Here is a sample code for getting comments.
comment_feed=yt_service.GetYouTubeVideoCommentFeed(video_id=video_id)
for comment_entry in comment_feed.entry:
print comment_entry.ToString()
for comment_entry in comment_feed.entry:
print comment_entry.ToString()
Strangely, the code gives me a subset of video comments (say 100), even when there are thousands of comments I can see in YouTube. I'll have to go through the documentation or switch back to wget and urlopen.
PS: Crawling YouTube is rather distracting. I ended up watching 20 cat videos and participated in viral spreading of those videos (i.e., sending spam video links to friends). My favorite of the day: cat massage.
Subscribe to:
Posts (Atom)