Fast Assortativity Coefficient Calculation in Large-Scale Social Networks
摘要
Assortativity coefficient, a metric utilized to quantify the tendency of nodes to connect with others sharing similar attributes, is important for analyzing social network structures, elucidating user behavioral preferences and predicting the evolution of networks. However, real-world social networks usually involve immense amounts of data and complex network structures, posing a challenge to rapidly and efficiently computing this coefficient within large-scale social networks. This paper proposes a Fast Assortativity Calculation (FAC) method tailored for large-scale social networks. FAC leverages a hybrid approach that combines breadth first search with random walks to achieve incomplete yet effective traversal of the graph structure, concurrently updating degree correlation coefficient during the traversal. Experimental results from four large-scale social network datasets, which contain millions of nodes and tens of millions of edges, demonstrate that FAC achieves a minimum improvement of 43.62% and a maximum of 66.91% in computational efficiency compared with the standard calculation modules provided by classical graph analysis tools. Notably, the absolute value of precision loss remains below 0.0068, maintaining an acceptable level of accuracy.