DRaWS: A dual random-walk based sampling method to efficiently estimate distributions of degree and clique size over social networks

Highlights：

• This paper proposes propose a dual random-walk based sampling process DRaWS, the first of its kind, with high accuracy and low cost to estimate the degree and clique structures simultaneously.

• The sampling method proposed in this paper drastically reduces its sampling costs while significantly reducing sampling errors.

• The paper proposes different re-weighted estimators by theoretical analysis on the dual random-walk based process to accurately estimate the degree and clique structures in large graphs with samples obtained by DRaWS.

• Extensive experiments are carried out to present the accuracy and efficiency of the newly proposed method.