Uncovering disassortativity in large scale-free networks

Nelly Litvak, Remco van der Hofstad

Research output: Contribution to journalArticleAcademicpeer-review

36 Citations (Scopus)
5 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number022801
Number of pages7
JournalPhysical review E: Statistical, nonlinear, and soft matter physics
Volume87
DOIs
Publication statusPublished - 2013

Fingerprint

Scale-free Networks
Spearman's coefficient
Spearman's rho
Graph in graph theory
Web Graph
World Wide Web
Biological Networks
Coefficient
Self-organizing
organizing
Social Networks
coefficients
Decrease
Alternatives
Vertex of a graph
Experiment

Keywords

  • EWI-23283
  • IR-86102
  • METIS-297617

Cite this

@article{55baaa2a77254186bf18696a47b42f65,
title = "Uncovering disassortativity in large scale-free networks",
abstract = "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.",
keywords = "EWI-23283, IR-86102, METIS-297617",
author = "Nelly Litvak and {van der Hofstad}, Remco",
note = "eemcs-eprint-23283",
year = "2013",
doi = "10.1103/PhysRevE.87.022801",
language = "English",
volume = "87",
journal = "Physical review E: covering statistical, nonlinear, biological, and soft matter physics",
issn = "2470-0045",
publisher = "American Physical Society",

}

Uncovering disassortativity in large scale-free networks. / Litvak, Nelly; van der Hofstad, Remco.

In: Physical review E: Statistical, nonlinear, and soft matter physics, Vol. 87, 022801, 2013.

Research output: Contribution to journalArticleAcademicpeer-review

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 -