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.
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.
0 Comments:
Post a Comment
<< Home