Abstract
We propose efficient algorithms for two key tasks in the analysis of large
nonuniform networks: uniform node sampling and cluster detection. Our sampling
technique is based on augmenting a simple, but slowly mixing uniform MCMC
sampler with a regular random walk in order to speed up its convergence;
however the combined MCMC chain is then only sampled when it is in its üniform
sampling" mode.Our clustering algorithm determines the relevant neighbourhood
of a given node u in the network by first estimating the Fiedler vector of a
Dirichlet matrix with u fixed at zero potential, and then finding the
neighbourhood of u that yields a minimal weighted Cheeger ratio, where the edge
weights are determined by differences in the estimated node potentials. Both of
our algorithms are based on local computations, i.e. operations on the full
adjacency matrix of the network are not used. The algorithms are evaluated
experimentally using three types of nonuniform networks:
Dorogovtsev-Goltsev-Mendes "pseudofractal graphs", scientific collaboration
networks, and randomised "caveman graphs".
Users
Please
log in to take part in the discussion (add own reviews or comments).