Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles

This study is an overview of network topology metrics and a computational approach to analyzing graph topology via multiple-metric analysis on graph ensembles. The paper cautions against studying single metrics or combining disparate graph ensembles from different domains to extract global patterns....

Full description

Bibliographic Details
Main Authors: Bounova, Gergana, de Weck, Olivier L.
Other Authors: Massachusetts Institute of Technology. Engineering Systems Division
Format: Article
Language:en_US
Published: American Physical Society 2012
Online Access:http://hdl.handle.net/1721.1/71866
https://orcid.org/0000-0001-6677-383X
_version_ 1826200846846656512
author Bounova, Gergana
de Weck, Olivier L.
author2 Massachusetts Institute of Technology. Engineering Systems Division
author_facet Massachusetts Institute of Technology. Engineering Systems Division
Bounova, Gergana
de Weck, Olivier L.
author_sort Bounova, Gergana
collection MIT
description This study is an overview of network topology metrics and a computational approach to analyzing graph topology via multiple-metric analysis on graph ensembles. The paper cautions against studying single metrics or combining disparate graph ensembles from different domains to extract global patterns. This is because there often exists considerable diversity among graphs that share any given topology metric, patterns vary depending on the underlying graph construction model, and many real data sets are not actual statistical ensembles. As real data examples, we present five airline ensembles, comprising temporal snapshots of networks of similar topology. Wikipedia language networks are shown as an example of a nontemporal ensemble. General patterns in metric correlations, as well as exceptions, are discussed by representing the data sets via hierarchically clustered correlation heat maps. Most topology metrics are not independent and their correlation patterns vary across ensembles. In general, density-related metrics and graph distance-based metrics cluster and the two groups are orthogonal to each other. Metrics based on degree-degree correlations have the highest variance across ensembles and cluster the different data sets on par with principal component analysis. Namely, the degree correlation, the s metric, their elasticities, and the rich club moments appear to be most useful in distinguishing topologies.
first_indexed 2024-09-23T11:42:40Z
format Article
id mit-1721.1/71866
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T11:42:40Z
publishDate 2012
publisher American Physical Society
record_format dspace
spelling mit-1721.1/718662022-10-01T05:26:14Z Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles Bounova, Gergana de Weck, Olivier L. Massachusetts Institute of Technology. Engineering Systems Division de Weck, Olivier L. Bounova, Gergana de Weck, Olivier L. This study is an overview of network topology metrics and a computational approach to analyzing graph topology via multiple-metric analysis on graph ensembles. The paper cautions against studying single metrics or combining disparate graph ensembles from different domains to extract global patterns. This is because there often exists considerable diversity among graphs that share any given topology metric, patterns vary depending on the underlying graph construction model, and many real data sets are not actual statistical ensembles. As real data examples, we present five airline ensembles, comprising temporal snapshots of networks of similar topology. Wikipedia language networks are shown as an example of a nontemporal ensemble. General patterns in metric correlations, as well as exceptions, are discussed by representing the data sets via hierarchically clustered correlation heat maps. Most topology metrics are not independent and their correlation patterns vary across ensembles. In general, density-related metrics and graph distance-based metrics cluster and the two groups are orthogonal to each other. Metrics based on degree-degree correlations have the highest variance across ensembles and cluster the different data sets on par with principal component analysis. Namely, the degree correlation, the s metric, their elasticities, and the rich club moments appear to be most useful in distinguishing topologies. 2012-07-27T13:35:02Z 2012-07-27T13:35:02Z 2012-01 2011-10 Article http://purl.org/eprint/type/JournalArticle 1539-3755 http://hdl.handle.net/1721.1/71866 Bounova, Gergana, and Olivier L. de Weck. "Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles." Physical Review E 85 (2012): 016117-1-016117-11. http://link.aps.org/doi/10.1103/PhysRevE.85.016117 Copyright 2012 American Physical Society. https://orcid.org/0000-0001-6677-383X en_US http://dx.doi.org/10.1103/PhysRevE.85.016117 Physical Review E Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf American Physical Society APS
spellingShingle Bounova, Gergana
de Weck, Olivier L.
Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title_full Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title_fullStr Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title_full_unstemmed Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title_short Overview of metrics and their correlation patterns for multiple-metric topology analysis on heterogeneous graph ensembles
title_sort overview of metrics and their correlation patterns for multiple metric topology analysis on heterogeneous graph ensembles
url http://hdl.handle.net/1721.1/71866
https://orcid.org/0000-0001-6677-383X
work_keys_str_mv AT bounovagergana overviewofmetricsandtheircorrelationpatternsformultiplemetrictopologyanalysisonheterogeneousgraphensembles
AT deweckolivierl overviewofmetricsandtheircorrelationpatternsformultiplemetrictopologyanalysisonheterogeneousgraphensembles