Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Graphlet correlation distance to compare small graphs

Abstract : Graph models are standard tools for representing mutual relationships between sets of entities. In most scientific fields, graph have been used to study the organisation of large group of entities with a small number of connections (e.g. social media relationships, infectious disease spread). A few years ago, the Graphlet Correlation Distance (GCD) was proposed as a graph distance to assess similarity between graphs. This paper deals with two main gaps in the literature. First, we assess the performance of GCD using a numerical experimental design to extend its domain of applicability in the small graph domain characterised by small numbers of entities and high densities of connections. We study its discriminating power with respect to the density and order of the graphs, but also with respect to the differences in order and density between the compared graphs. Second, we develop a statistical test based on the GCD to compare empirical graphs to three possible null models (Erd ős-Rényi, Barbási-Albert scale free and k-regular) for both small and large-size graphs. Finally, we illustrate the relevance of this approach by using two fishing case studies to assess the independence of observed proximities between fishing vessels modeled by graphs. The statistical test does not rule out independent behavior within one of the two fleets studied.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03635934
Contributor : Jérôme ROUX Connect in order to contact the contributor
Submitted on : Friday, April 8, 2022 - 7:21:06 PM
Last modification on : Wednesday, May 18, 2022 - 10:45:05 AM

File

ARTICLE_SMALL_GRAPHS_COMPARISO...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03635934, version 1

Collections

Citation

Jérôme Roux, Nicolas Bez, Paul Rochet, Rocío Joo, Stéphanie Mahévas. Graphlet correlation distance to compare small graphs. 2022. ⟨hal-03635934⟩

Share

Metrics

Record views

28

Files downloads

18