Tuesday, May 16, 2006

Random Graphs and the Probabilistic Method...

In analysis of Random Graphs, we are especially interested in testing whether the observed graph has a given property. The technique known as the Probabilistic Method is often used in proofs of these properties. The basic idea is simple and elegant : To prove the existence of an object with certain properties, we demonstrate a sample space of objects in which the probability is positive that a randomly selected object has required properties.
For example, we can demonstrate a outline of simple proof of the following theorem :
Let K_n be a complete graph (having n vertices and (n \over 2) eges) and let K_k be a complete subgraph in K_n , with k vertices.
If (n \over 2)2^{-(k \over 2)+1) \lt 1 then it is possible to color the edges of K_n with two colors so that it has no monochromatic K_k subgraph
There are 2^(n \over 2) possible coloring of edges of K_n using two colors, so the probability of each coloring, choosed uniformly at random is 2^-(n \over 2). There are (n \over k) different k-vertex cliques of K_n. If we assume that A_i is the event that the clique i is monochromatic, then is we color the first edge in i, the remaining (k \over 2) edges must be of the same color. Therefore, the probability of this coloring is Pr(A_i) = 2^-(k \over 2)+1. We can use unior bound to determine that probability of all possible A_i events is less than (n \over k)2^-(k \over 2)+1 that is less than 1, meaning that the inverse probability (of picking the coloring without monochromatic k-vertex clique) is greater than 0, wich means that there exists a coloring with no monochromatic k-vertex clique.
So, we have proved that such graph exists, without explicitly constructing one, which is a reason that the probabilistic method proofs are known as a nonconstructive proofs.
todo : convert tex formulas into gifs...

Modelling the Web Graph.....

The structure of the Web is usually represented as a directed graph, also known as a Web Graph. The pages of the Web represent nodes, while the links between pages represent the edges of the graph. The structural properties of this graph can be used to derive information about various aspects of the Web. For example, algorithms such as PageRank and HITS use this graph model in order to estimate the relevance of a given Web page. In order to provide the proper theoretical framework for analysis of the behavior of algorithms on the Web Graph, we are interested in developing a theoretical model that describes the generative model of this graph.
The basic model is the model of Random Graph, derived by Paul Erdős and Alfréd Rényi in 1959.
The Random Graph G(n,p) represents the graph with n vertices with edges beetween every pair of vertices generated with probability p . We can easily generate such graph using Matlab. The picture represents the G(n,p) random graph with n = 40 and p=0.5 .

Of special interest is the analysis of the limiting behaviour of the random graphs.
The most noteable phenomenas are the existence of the phase transitions in evolution of the random graph.
By phase transitions we assume the events of apperiance of certain properties of the graph in the process of increasing the probabilities of edge generation. We can identify the exact transitional probabilities at which certain properties of the graph (such as connectivity) appear.

Monday, May 08, 2006

The learning theory on hold.....

The time went by and none of the planned posts on learning theory appeared....
I guess I will leave these on the side for now. But, for those interested, the upcoming COLT 2006 conference http://learningtheory.org/colt2006/ is a definite place to be. The Open Problems sessions are always a source of inspiration. You can get some of the Open Problem papers from previous conferences at http://learningtheory.org/
As far as I am concerned, I have finally succeded in setting up a broadband connection at home, so there should be some meaningfull posts in the following period. Hopefully, there should be some reviews of miscellanious research topics related to the area of Web Search Algorithms.
Definitelly, we should wait and see... :)