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.

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!

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.

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.

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

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.

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.

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.