Funnelling effect in networks

Abstract

Funnelling effect, in the context of searching on networks, precisely indicates that the search takes place through a few specific nodes. We define the funnelling capacity $f$ of a node as the fraction of successful dynamic paths through it with a fixed target. The distribution $D(f)$ of the fraction of nodes with funnelling capacity $f$ shows a power law behaviour in random networks (with power law or stretched exponential degree distribution) for a considerable range of values of the parameters defining the networks. Specifically we study in detail $D_1=D(f=1)$, which is the quantity signifying the presence of nodes through which all the dynamical paths pass through. In scale free networks with degree distribution $P(k)\propto k^{-\gamma }$, $D_1$ increases linearly with $\gamma$ initially and then attains a constant value. It shows a power law behaviour, $D_1\propto N^{-\rho }$, with the number of nodes $N$ where $\rho$ is weakly dependent on $\gamma$ for $\gamma >2.2$. The latter variation is also independent of the number of searches. On stretched exponential networks with $P(k)\propto \exp (-k^{\delta })$, $\rho$ is strongly dependent on $\delta$. The funnelling distribution for a model social network, where the question of funnelling is most relevant, is also investigated.

Talk given in Complex2009, Shanghai; some results reported earlier in arXiv:0801.0370

References in corpus (8)

• Self-similarity of complex networks and hidden metric spaces
• Search in weighted complex networks
• How Do Networks Become Navigable?
• Search in Complex Networks : a New Method of Naming
• Navigation in a small world with local information
• A novel approach to study realistic navigations on networks
• Realistic searches on stretched exponential networks
• Effect of a static phase transition on searching dynamics