An egonet-based approach to effective weighted network comparison

Abstract

With the impressive growth of network models in practically every scientific and technological area, we are often faced with the need to compare graphs, i.e., to quantify their (dis)similarity using appropriate metrics. This is necessary, for example, to identify networks with comparable characteristics or to spot anomalous instants in a time sequence of graphs. While a large number of metrics are available for binary networks, the set of comparison methods capable of handling weighted graphs is much smaller. Yet, the strength of connections is often a key ingredient of the model, and ignoring this information could lead to misleading results. In this paper we introduce a family of dissimilarity measures to compare undirected weighted networks. They fall into the class of alignment-free metrics: as such, they do not require the correspondence of the nodes between the two graphs and can also compare networks of different sizes. In short, they are based on the distributions, on the graph, of a few egonet features which are easily defined and computed: the distance between two graphs is then the distance between the corresponding distributions. On a properly defined testbed with a pool of weighted network models with diversified characteristics, the proposed metrics are shown to achieve state-of-the-art performance in the model classification task. The effectiveness and applicability of the proposed metrics are then demonstrated on two examples. In the first, some "filtering" schemes -- designed to eliminate non-significant links while maintaining most of the total weight -- are evaluated in their ability to produce as output a graph faithful to the original, in terms of the local structure around nodes. In the second example, analyzing a timeline of stock market correlation graphs highlights anomalies associated with periods of financial instability.

References in corpus (25)

• The architecture of complex weighted networks
• Analysis of weighted networks
• Prediction and predictability of global epidemics: the role of the airline transportation network
• Intensity and coherence of motifs in weighted complex networks
• Extracting the multiscale backbone of complex weighted networks
• Biological network comparison using graphlet degree distribution
• Clustering in Complex Directed Networks
• Generalizations of the clustering coefficient to weighted complex networks
• Global organization of metabolic fluxes in the bacterium, Escherichia coli
• The backbone of the climate network
• Clustering and information in correlation based financial networks
• Dynamic asset trees and Black Monday
• On the Topological Properties of the World Trade Web: A Weighted Network Analysis
• Network structure of multivariate time series
• Patterns of dominant flows in the world trade web
• Correlations in weighted networks
• An information-theoretic, all-scales approach to comparing networks
• Topology comparison of Twitter diffusion networks effectively reveals misleading information
• Vulnerability of weighted networks
• Finding and testing network communities by lumped Markov chains
• A parametric approach to information filtering in complex networks: The Pólya filter
• Weight-driven growing networks
• Search in weighted complex networks
• An Evaluation Tool for Backbone Extraction Techniques in Weighted Complex Networks
• Metrics for network comparison using egonet feature distribution