» Articles » PMID: 37669967

Metrics for Network Comparison Using Egonet Feature Distributions

Overview
Journal Sci Rep
Specialty Science
Date 2023 Sep 5
PMID 37669967
Authors
Affiliations
Soon will be listed here.
Abstract

Identifying networks with similar characteristics in a given ensemble, or detecting pattern discontinuities in a temporal sequence of networks, are two examples of tasks that require an effective metric capable of quantifying network (dis)similarity. Here we propose a method based on a global portrait of graph properties built by processing local nodes features. More precisely, a set of dissimilarity measures is defined by elaborating the distributions, over the network, of a few egonet features, namely the degree, the clustering coefficient, and the egonet persistence. The method, which does not require the alignment of the two networks being compared, exploits the statistics of the three features to define one- or multi-dimensional distribution functions, which are then compared to define a distance between the networks. The effectiveness of the method is evaluated using a standard classification test, i.e., recognizing the graphs originating from the same synthetic model. Overall, the proposed distances have performances comparable to the best state-of-the-art techniques (graphlet-based methods) with similar computational requirements. Given its simplicity and flexibility, the method is proposed as a viable approach for network comparison tasks.

References
1.
Faisal F, Newaz K, Chaney J, Li J, Emrich S, Clark P . GRAFENE: Graphlet-based alignment-free network approach integrates 3D structural and sequence (residue order) data to improve protein structural comparison. Sci Rep. 2017; 7(1):14890. PMC: 5668259. DOI: 10.1038/s41598-017-14411-y. View

2.
Piccardi C . Finding and testing network communities by lumped Markov chains. PLoS One. 2011; 6(11):e27028. PMC: 3207820. DOI: 10.1371/journal.pone.0027028. View

3.
Fagiolo G . Clustering in complex directed networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2007; 76(2 Pt 2):026107. DOI: 10.1103/PhysRevE.76.026107. View

4.
Gera R, Alonso L, Crawford B, House J, Mendez-Bermudez J, Knuth T . Identifying network structure similarity using spectral graph theory. Appl Netw Sci. 2019; 3(1):2. PMC: 6214265. DOI: 10.1007/s41109-017-0042-3. View

5.
Pierri F, Piccardi C, Ceri S . Topology comparison of Twitter diffusion networks effectively reveals misleading information. Sci Rep. 2020; 10(1):1372. PMC: 6987152. DOI: 10.1038/s41598-020-58166-5. View