DEPARTMENT OF MATHEMATICS
       ALGEBRA AND COMBINATORICS SEMINAR

  12 noon THURSDAY 18 NOVEMBER 2004  in 67-641

       
Iterated 2-Cycle Contractions and Strong Connectivity
        in Random Directed Graphs

               David A. Pike
      Memorial University of Newfoundland


Abstract
 
The structure of the World Wide Web can be represented by
a very large directed graph $W$ in which each vertex 
corresponds to a distinct webpage and each arc corresponds 
to an actual hyperlink between two webpages.  
Given just this structural information about the WWW, 
the question arises:  can groups of related webpages
be identified?

Consider the hypothesis that two vertices, say  u  and  v, 
of  W, are related to each other if  W  contains arcs  
u --> v  and  v --> u
(i.e., W contains a directed 2-cycle u <---> v ).

This hypothesis can be further generalised.  Suppose that
u  and  v  have been deemed to be related.  If  W  contains arcs
u --> w  and  w --> v  for some vertex  w,
then we deem  w  to be related to  u  and  v, and vice-versa.

This generalisation lends itself to a simple algorithm for 
finding maximal sets of mutually related vertices in  W:
find a directed 2-cycle  u <---> v, contract this 
cycle so that  u  and  v  coalesce into a single new vertex, 
and then iterate this procedure until no directed 2-cycles remain.

We begin our investigation by studying the behaviour of this
iterated 2-cycle contraction procedure in random directed graphs.

This work is joint with Alasdair Graham.



All welcome.