Expansion and Search in Networks

Details Expansion and Search in Networks Expansion and Search in Networks

2010-09-22

arxiv.org/abs/1009.4383v2

CIKM 2010: 19th ACM International Conference on Information and Knowledge Management

Computer Science

Social and Information Networks

10 pages

Scientific paper

Borrowing from concepts in expander graphs, we study the expansion properties of real-world, complex networks (e.g. social networks, unstructured peer-to-peer or P2P networks) and the extent to which these properties can be exploited to understand and address the problem of decentralized search. We first produce samples that concisely capture the overall expansion properties of an entire network, which we collectively refer to as the expansion signature. Using these signatures, we find a correspondence between the magnitude of maximum expansion and the extent to which a network can be efficiently searched. We further find evidence that standard graph-theoretic measures, such as average path length, fail to fully explain the level of "searchability" or ease of information diffusion and dissemination in a network. Finally, we demonstrate that this high expansion can be leveraged to facilitate decentralized search in networks and show that an expansion-based search strategy outperforms typical search methods.

Affiliated with

Also associated with

No associations

Rating

Expansion and Search in 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 Expansion and Search in Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expansion and Search in Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-638070