TY - JOUR
T1 - Uncovering disassortativity in large scale-free networks
AU - Litvak, Nelly
AU - van der Hofstad, Remco
N1 - eemcs-eprint-23283
PY - 2013
Y1 - 2013
N2 - Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, and social and biological networks, are often characterized by degree-degree dependencies between neighboring nodes. In this paper, we propose a new way of measuring degree-degree dependencies. One of the problems with the commonly used assortativity coefficient is that in disassortative networks its magnitude decreases with the network size. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as Spearman’s $\rho$. Our experiments convincingly show that Spearman’s $\rho$ produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In particular, we discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. Rank correlations allow us to compare the assortativity of networks of different sizes, which is impossible with the assortativity coefficient due to its genuine dependence on the network size. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
AB - Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, and social and biological networks, are often characterized by degree-degree dependencies between neighboring nodes. In this paper, we propose a new way of measuring degree-degree dependencies. One of the problems with the commonly used assortativity coefficient is that in disassortative networks its magnitude decreases with the network size. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as Spearman’s $\rho$. Our experiments convincingly show that Spearman’s $\rho$ produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In particular, we discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. Rank correlations allow us to compare the assortativity of networks of different sizes, which is impossible with the assortativity coefficient due to its genuine dependence on the network size. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
KW - EWI-23283
KW - IR-86102
KW - METIS-297617
U2 - 10.1103/PhysRevE.87.022801
DO - 10.1103/PhysRevE.87.022801
M3 - Article
VL - 87
JO - Physical review E: covering statistical, nonlinear, biological, and soft matter physics
JF - Physical review E: covering statistical, nonlinear, biological, and soft matter physics
SN - 2470-0045
M1 - 022801
ER -