TY - BOOK
T1 - Uncovering disassortativity in large scale-free networks
AU - Litvak, N.
AU - Hofstad, van der, R.W.
PY - 2012
Y1 - 2012
N2 - Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social and biological networks are often characterized by degree-degree dependencies between neighbouring nodes. In this paper we propose a new way of measuring degree-degree dependencies. We show that the commonly used assortativity coefficient significantly underestimates the magnitude of dependencies, especially in large disassortative networks. 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 the well-known 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, using the Spearman's rho we show that preferential attachment model exhibits significant negative degree-degree dependencies. We also discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. 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, social and biological networks are often characterized by degree-degree dependencies between neighbouring nodes. In this paper we propose a new way of measuring degree-degree dependencies. We show that the commonly used assortativity coefficient significantly underestimates the magnitude of dependencies, especially in large disassortative networks. 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 the well-known 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, using the Spearman's rho we show that preferential attachment model exhibits significant negative degree-degree dependencies. We also discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
UR - http://arxiv.org/pdf/1204.0266v3.pdf
M3 - Report
T3 - arXiv.org [physics.soc-ph]
BT - Uncovering disassortativity in large scale-free networks
PB - s.n.
ER -