Growth of common friends in a preferential attachment model

Abstract

The number of common friends (or connections) in a graph is a commonly used measure of proximity between two nodes. Such measures are used in link prediction algorithms and recommendation systems in large online social networks. We obtain the rate of growth of the number of common friends in a linear preferential attachment model. We apply our result to develop an estimate for the number of common friends that can significantly reduce the cost of computing these measures. We also observe a phase transition in the limiting behavior of the number of common friends; depending on the range of the parameters of the model, the growth is either power-law, or, logarithmic, or static with the size of the graph.

Keywords:

• Heavy-tail
• limit theorem
• link prediction
• preferential attachment
• social network

AMS 2000 SUBJECT CLASSIFICATIONS:

• Primary 60F15
• 60G42
• Secondary 90B15
• 91D30

Acknowledgements

The authors would like to thank the editor and two anonymous referees for their helpful and insightful comments which helped in improving the paper.

Additional information

Funding

This work was supported by MOE Tier 2 grant MOE2017-T2-2-161.