The effect of bridges between clusters

[Subbarao Kambhampati <SUBBARAO.KAMBHAMPATI@asu.edu>]

We know that if there are disjoint clusters, the majority cluster will 
get all the authority and the minority one gets zero. One question is
what happens if there are a small number of "bridge" notes that
connect both clusters. [[after all, there may be hub pages that link
to both pro-choice and pro-life pages]].

I did a bit of experimentation with n-m-k clusters--where there are
two clusters of sizes n and m respectively. The n-node cluster has n-1 
hub nodes pointing to the nth node. Same with m-node cluster. There
are k bridge nodes, which are hub nodes that connect to the nth node
of n-cluster and mth-node of the m-cluster. 

I played with n=50, m=49 and k varied over 0 (no bridges), 1 (one
bridge node), 10 (10 bridge nodes) and 100 (100 bridge nodes). In each 
case we run 200 iterations of the authority computation. 

Here are the results for the authorities of the 50th node of the
50-cluster and 49th-node of the 49-cluster (which are the cluster
centers of the two clusters)


                    50-cluster center              49-cluster center

k= 0		    1				   2.61e-4

k= 1		    .85				   .525

k=10                .724			   .689

k=100		    .7088			   .7053



Notice the abrupt jump at k=1. That is, the moment there is a single
bridge node between clusters, the authority of the 49-cluster center
jumpts from 0 to .525!

You will be asked to get a closed form solution for this case in the
next homework.


Rao
[Feb 27, 2001]