Optimal network topologies for local search with congestion

Details Optimal network topologies for local search with congestion Optimal network topologies for local search with congestion

2002-06-21

arxiv.org/abs/cond-mat/0206410v2

Phys. Rev. Lett. 89, 248701 (2002)

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 pages. Final version accepted in PRL

Scientific paper

10.1103/PhysRevLett.89.248701

The problem of searchability in decentralized complex networks is of great importance in computer science, economy and sociology. We present a formalism that is able to cope simultaneously with the problem of search and the congestion effects that arise when parallel searches are performed, and obtain expressions for the average search cost--written in terms of the search algorithm and the topological properties of the network--both in presence and abscence of congestion. This formalism is used to obtain optimal network structures for a system using a local search algorithm. It is found that only two classes of networks can be optimal: star-like configurations, when the number of parallel searches is small, and homogeneous-isotropic configurations, when the number of parallel searches is large.

Affiliated with

Also associated with

No associations

Rating

Optimal network topologies for local search with congestion 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 Optimal network topologies for local search with congestion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal network topologies for local search with congestion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-255727