Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks

Details Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks

2004-06-02

arxiv.org/abs/cond-mat/0406048v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

14 pages, 6 figures

Scientific paper

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 "uniform 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".

Affiliated with

Also associated with

No associations

Rating

Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-348494