Uncovering disassortativity in large scale-free networks

Onderzoeksoutput: Boek/rapportRapportAcademic

Uittreksel

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.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's11
StatusGepubliceerd - 2012

Publicatie series

NaamarXiv.org [physics.soc-ph]
Volume1204.0266

Vingerafdruk

Complex networks
Computer networks
World Wide Web
Internet
Experiments

Citeer dit

@book{e2579545e3f44cf08b859874b1723a0d,
title = "Uncovering disassortativity in large scale-free networks",
abstract = "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.",
author = "N. Litvak and {Hofstad, van der}, R.W.",
year = "2012",
language = "English",
series = "arXiv.org [physics.soc-ph]",
publisher = "s.n.",

}

Uncovering disassortativity in large scale-free networks. / Litvak, N.; Hofstad, van der, R.W.

s.n., 2012. 11 blz. (arXiv.org [physics.soc-ph]; Vol. 1204.0266).

Onderzoeksoutput: Boek/rapportRapportAcademic

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 -