I already have a network which is like random complex network. Is there any way I can delete some of nodes and reduce the network into a scale-free network?

I notice there are some methods that can sample a scale-free subnet from a scale-free network. But I have not found anyone sampled a scale-free subnet from a random network.

  • $\begingroup$ I'm not sure what you are aiming at. What is a "scale-free network" for you? $\endgroup$ – Yuval Filmus Mar 17 '17 at 10:56
  • $\begingroup$ I am trying to sample a subnet whose degree distribution follows a power law. People call that network scale-free network. $\endgroup$ – James Mar 17 '17 at 14:14

In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.

Now, assume your initial random network indeed has high degree nodes. Since it is random, choosing random links in it will often lead to high-degree extremities. Indeed, the probability to pick a degree $k$ extremity when you choose a link at random is proportional to $k$.

This property underlies the works conducted to estimate bias in internet measurements. Several works show that power-law networks may indeed be obtained from initially random networks, for instance by taking a BFS tree.

See e.g. On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs for a formal analysis published in STOC and Journal of the ACM, as well as Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results for an experimental work published in INFOCOM and Journal of Computer Networks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.