Overview of metrics and their correlation patterns for multiple- metric topology analysis on heterogeneous graph ensembles
Overview of metrics and their correlation patterns for multiple- metric topology analysis on heterogeneous graph ensembles
复制标题
DOI：
10.1103/physreve.85.016117
复制
发表时间：
2012-01-30
影响因子：
2.4
通讯作者：
de Weck, Olivier
中科院分区：
文献类型：
--
作者：
Bounova, Gergana;de Weck, Olivier
本研究是一个网络拓扑度量的概述和计算方法来分析图的拓扑结构，通过多度量分析图集成。本文警告不要研究单一指标或将来自不同领域的不同图形集合组合起来以提取全局模式。这是因为共享任何给定拓扑度量的图之间通常存在相当大的多样性，模式根据底层图构造模型而变化，并且许多真实的数据集不是实际的统计集合。作为真实的数据的例子，我们提出了五个航空公司合奏，包括类似拓扑结构的网络的时间快照。维基百科语言网络被示为非时态集合的一个例子。度量相关性的一般模式，以及例外情况，讨论通过分层聚类相关热图表示的数据集。大多数拓扑度量不是独立的，它们的相关模式在集合中各不相同。通常，密度相关度量和基于图距离的度量聚类，并且这两个组彼此正交。基于度-度相关性的聚类分析在总体上具有最高的方差，并将不同的数据集与主成分分析进行聚类。也就是说，度相关性，S度量，它们的弹性，和丰富的俱乐部时刻似乎是最有用的区分拓扑结构。
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.