Spectral density-based clustering algorithms for complex networks

Author(s)

Ramos, Taiane Coelho ; Mourao-Miranda, Janaina ; Fujita, Andre

• Document type: Journal article
• Source: FRONTIERS IN NEUROSCIENCE; v. 17, p. 14-pg., 2023-03-30.

Abstract

IntroductionClustering is usually the first exploratory analysis step in empirical data. When the data set comprises graphs, the most common approaches focus on clustering its vertices. In this work, we are interested in grouping networks with similar connectivity structures together instead of grouping vertices of the graph. We could apply this approach to functional brain networks (FBNs) for identifying subgroups of people presenting similar functional connectivity, such as studying a mental disorder. The main problem is that real-world networks present natural fluctuations, which we should consider. MethodsIn this context, spectral density is an exciting feature because graphs generated by different models present distinct spectral densities, thus presenting different connectivity structures. We introduce two clustering methods: k-means for graphs of the same size and gCEM, a model-based approach for graphs of different sizes. We evaluated their performance in toy models. Finally, we applied them to FBNs of monkeys under anesthesia and a dataset of chemical compounds. ResultsWe show that our methods work well in both toy models and real-world data. They present good results for clustering graphs presenting different connectivity structures even when they present the same number of edges, vertices, and degree of centrality. DiscussionWe recommend using k-means-based clustering for graphs when graphs present the same number of vertices and the gCEM method when graphs present a different number of vertices. (AU)

• FAPESP's process: 20/08343-8 - Graph/Hypergraph (spectral) analysis to compare metabolic networks of pathogenic Trypanosoma sp.
• Grantee: André Fujita
• Support Opportunities: Regular Research Grants
• FAPESP's process: 18/21934-5 - Network statistics: theory, methods, and applications
• Grantee: André Fujita
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 19/22845-9 - Computational approaches with the objective to explore intra and cross-species interactions and their role in all domains of life
• Grantee: André Fujita
• Support Opportunities: Regular Research Grants