Today I read a paper titled “Navigation in non-uniform density social networks”
The abstract is:
Recent empirical investigations suggest a universal scaling law for the spatial structure of social networks.
It is found that the probability density distribution of an individual to have a friend at distance $d$ scales as $P(d)\propto d^{-1}$.
Since population density is non-uniform in real social networks, a scale invariant friendship network(SIFN) based on the above empirical law is introduced to capture this phenomenon.
We prove the time complexity of navigation in 2-dimensional SIFN is at most $O(\log^4 n)$.
In the real searching experiment, individuals often resort to extra information besides geography location.
Thus, real-world searching process may be seen as a projection of navigation in a $k$-dimensional SIFN($k>2$).
Therefore, we also discuss the relationship between high and low dimensional SIFN.
Particularly, we prove a 2-dimensional SIFN is the projection of a 3-dimensional SIFN.
As a matter of fact, this result can also be generated to any $k$-dimensional SIFN.