A Deductive-Formal Derivation for the Preferential Attachment Metric for Link Prediction

Abstract

We present an analytical derivation of the preferential attachment metric to predict social ties in complex networks. This metric was originally proposed by Newman in 2001 and by Barabasi et al. in 2002 and it was obtained by empirical means. We propose in this paper an analysis based on a deductive-formal reasoning, giving the metric a formal theoretical basis. In our analysis we use two random graph models for power-law graphs. We show that in these models, by using formal reasoning, we can derive the preferential attachment metric proposed by Newman and Barabasi et al.