Graphlets reveal detailed structural patterns in complex networks
Graphlets as structural fingerprints of complex networks
Social and Information Networks
Summary
Comparing complex networks often relies on simple measures that capture broad properties. The authors introduce graphlets, small network patterns, as fingerprints to describe network structure from local up to medium scales. These graphlets distinguish synthetic networks with subtle differences better than traditional metrics. When applied to brain connectivity data, graphlets detected small changes well but did not outperform classical measures in distinguishing schizophrenia. This shows graphlets are a flexible tool for capturing network topology, with strengths in some areas and limitations in others.
What this means in practice
- •For network analysts: Use graphlet fingerprints to detect subtle structural differences in synthetic or real-world complex networks more precisely than standard metrics.
- •For neuroimaging data scientists: Improve sensitivity to localized connectivity changes in brain network analyses, such as in studies of neurological disorders like schizophrenia.
Authors
Anna Pidnebesna, David Hartman, Aneta Pokorna, Daniel Trlifaj, Jaroslav Hlinka
Abstract
Complex networks are often compared using selected graph-theoretical measures that capture a selected set of properties with effects ranging from local to global, such as degree, clustering or betweenness centrality. Here we introduce a structural fingerprinting framework based on graphlets: small rooted subgraphs whose distributions provide a systematic description of local-to-mesoscale topology. Across synthetic networks generated from several random graph models, graphlet fingerprints capture parameter-dependent structural differences, outperform standard graph-theoretical measures, and identify even subtle local patterns driving discrimination. We then apply the framework to empirical resting-state functional connectomes, documenting that while graphlets show superior sensitivity also to controlled topological perturbations of brain connectivity, specifically in schizophrenia-control classification they perform only comparably to classical graph-theoretical features. This is in line with the notion that schizophrenia-related alterations are dominated by spatially localized connectivity changes rather than general topological reorganization. Altogether, the generative modeling, targeted perturbations and real-world neuroimaging classification challenge position graphlets as flexible structural fingerprints of complex networks, while carefully outlining their strength and weaknesses compared to more classical graph theoretical features.