· Modeling of Small World graph
A class of
small world graph:
WWW web graph
We can treet the whole WWW
internet as a directed graph, if we take a web page as a node, and a hyper-link
from one page to another as a directed arc from one node to another node. If we
consider the "Back" function in most browsers, we can take each
hyper-link as bidirectional. According a recent study of web graph, there are
about 800 million nodes in this graph, the diameter of web graph is only 19!
This means if you always know which link to click, you can get to whatever web
page on the whole internet in no more than 19 clicks!
Erdos' Collaboration Graph
http://www.acs.oakland.edu/~grossman/erdoshp.html
Telephone "call graph"
The nodes of this "call
graph" are telephone numbers, the edges are the calls made from one number
to another number in a given time period. This is studied by AT&T Shannon
Laboratories in Florham Park, New Jersey. A one-day call graph has 53,767,087
nodes and 170 million edges.[ref]
It is not connected but has 3.7 million separte components, most of them are
pairs of telephones that called only each other. Yet, it also has one giant
component, with 80% of the total nodes, and diameter as 20. This implies that
any telephone in the component can be linked to any other through a chain of no
more than 20 call.
Hollywood Collaboration Graph
http://www.cs.virginia.edu/oracle/
Nervous system of a certain worm
The name of the worm is Caenorhabditis
elegans.
Your own Accquaintance Graph
Modelling of
Small World graph
Because small graphs are too huge, up to now, we
can build mathmatical models that keep the same properties of a real Small
World graph. Then we can use the model to generate small samples of the graph
in order to further study its properties."The more basic goal is simply
finding computational techniques that will not choke on a graph with 10^8
nodes."[ref]
Measures and propertities of Small World graph
Modellings:
Rewiring of
Circle
Revision of
2-D Mesh
The fruit of
web graph reserach:
The Google
search engine.
Among the tons of pages the
search engin has found carrying the target key word, a link analysis is
done, concerning about those pages with the most in-comming links or out-going
links. By this apporach, the Google search engine is more likely to give the
most pertinent page than any other engines.
My work:
Study
propertites of WWW web graph
Web graph has
a few "building nodes". They are with very large in-degree. Just
because those nodes, the diameter of web graph is small.
The web graph
is growing. Study the patern of this growing.
Find
different modellings of WWW graph, based on the above propertites.
Mathematically
study these models.
In-degree distribution in random digraphs.([ps] ,[Presentation
slides(ps)] To appear in "32nd
Intl. Conference on Combinoritics, Graph Theory and Computing"
In this
paper, it is prooved that the in-degree distribution in a random di-graph is
Poisson when n->infinity and expected value of in-degree is finite.
Run Simulations
on small world graphs
Resources I
have found for this area:
Random Graph(&random
digraph):
After it is
introduced by Paul Eurdos in 1963 to prove a normal graph theory theorem, this
model has been extensively studied!
Here are
magazines that may have papers about this area:
Random
structures and algorithms
Random
graph people
Last Updated at 2/13/2001.
By Chao Gui