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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Assortativity Coefficient Calculation in Large-Scale Social Networks

  • Liru Cao,
  • Wangyang Liu,
  • Lican Zhang,
  • Wei Liao,
  • Yi Shen

摘要

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.