  The problem of distributed maximal independent set (MIS) is investigated on
inhomogeneous random graphs with power-law weights by which the scale-free
networks can be produced. Such a particular problem has been solved on graphs
with $n$ vertices by state-of-the-art algorithms with the time complexity of
$O(\log{n})$. We prove that for a scale-free network with power-law exponent
$\beta > 3$, the induced subgraph is constructed by vertices with degrees
larger than $\log{n}\log^{*}{n}$ is a scale-free network with $\beta' = 2$,
almost surely (a.s.). Then, we propose a new algorithm that computes an MIS on
scale-free networks with the time complexity of
$O(\frac{\log{n}}{\log{\log{n}}})$ a.s., which is better than $O(\log{n})$.
Furthermore, we prove that on scale-free networks with $\beta \geq 3$, the
arboricity and degeneracy are less than $2^{log^{1/3}n}$ with high probability
(w.h.p.). Finally, we prove that the time complexity of finding an MIS on
scale-free networks with $\beta\geq 3$ is $O(log^{2/3}n)$ w.h.p.
